LinuxSir.cn,穿越时空的Linuxsir!

 找回密码
 注册
搜索
热搜: shell linux mysql
查看: 13100|回复: 12

Lex与Yacc学习实例——nepc小型计算器

[复制链接]
发表于 2005-3-30 14:56:38 | 显示全部楼层 |阅读模式
[前言]
  这两天进行编译原理实践,重点学习lex和yacc两个软件在词法、语法、语法制导的定义及翻译方案等方面的设计和应用。论坛上几乎没有这方面的资料,估计研究的人也不是很多。我特地把学习过程的一些心得体会写下来,既供初学者借鉴,也防止自己遗忘。
  因为lex和yacc文件的书写对格式要求比较严谨,所以推荐在某些带有辅助编辑功能的编写环境下进行编码工作。我用的是kdevelop,对lex和yacc语法均有高亮显示功能,挺不错。

[成果]
  主要的成果是我花了一个晚上加一个上午设计和编码,一个中午调试最后实现的一个小型文本计算器。我们知道GNU/linux已经提供了一个任意精度的calc文本计算器,其功能非常强大。我的nepc (neplusultra calculator )仅仅实现了calc的一小部分功能,但对于日常使用已经足够了。nepc完全由lex和yacc生成。
  已实现功能罗列如下:
  1、支持运算符:加减乘除、%(模运算)、逻辑运算(||、&&、!)、位运算(<<、>>、|、&、^(位异或)、~(取反))、大于小于运算、小括号()。各种运算符优先级遵从C语言标准。
  2、支持数制:八进制、十进制、十六进制。相应通过oct、dec、hex三个命令可以指定终端显示的数制类型。同时支持三种数制的输入:八进制数以0开头且至少两位;十六进制以0x或0X开头;十进制按日常书写规则书写。八进制和十六进制仅对整数类型有效。
  3、提供26个寄存器用以存储变量,从a到z,大小写忽略。用list命令可以查看所有寄存器变量;用erase命令可以清空全部寄存器变量。
  4、算术表达式可以任意长度。
  5、帮助:help命令
  待实现功能如下:
  1、历史记录功能。
  2、八进制及十六进制的小数表示形式。
  3、加入二进制数制支持。

[源码]
  我就不一一描述了,关键是给出一个样本,尤其是lex和yacc是怎样协调工作的。
对于比较重要的说明,一律以红色字体标示。


lex源码部分:nepc.l

  1. %{
  2. #define YYSTYPE  double  //[color=red]很多参考资料都没有正确解释重定义YYSTYPE的正确方法,我这样定义是安全的。[/color]
  3. #define  BIGINT long long
  4. #include <ctype.h>
  5. #include "y.tab.h"  [color=red]//这是yacc生成的文件,必须包含![/color]

  6. %}
  7.                        
  8. digit                [0-9]
  9. xdigit                [0-9a-fA-F]
  10. odigit                [0-7]

  11. decnum        (0(\.{digit}+)?)|([1-9]{digit}*(\.{digit}+)?)
  12. octnum        0{odigit}+
  13. hexnum        0(x|X){xdigit}+

  14. reg                [a-zA-Z]
  15. opt1                "+"|"-"|"*"|"/"|"&"|"|"|"%"|"^"|"~"|"!"|"<"|">"
  16. opt2                (&&)|(\|\|)|(\<\<)|(\>\>)

  17. exit                ((E|e)(X|x)(I|i)(T|t))|((Q|q)(U|u)(I|i)(T|t))
  18. clear                (C|c)(L|l)(E|e)(A|a)(R|r)
  19. list                (L|l)(I|i)(S|s)(T|t)
  20. erase        (E|e)(R|r)(A|a)(S|s)(E|e)
  21. hex                (H|h)(E|e)(X|x)
  22. oct                (O|o)(C|c)(T|t)
  23. dec                (D|d)(E|e)(C|c)
  24. help                (H|h)(E|e)(L|l)(P|p)

  25. %%
  26. [color=red]  // 此处可以定义局部变量。注意,该定义绝对不能从第一列开始!
  27.          //   而词法符号必须从第一列开始。
  28. [/color]
  29.                 int i ;
  30.                 BIGINT val;
  31.                
  32. [" "; \t]        {}
  33. {decnum}        {sscanf(yytext,"%lf",&yylval);return(NUM); }
  34. {octnum}        {
  35.                         i=1;val=0;
  36.                         while(i<yyleng)
  37.                         {
  38.                                 val=(val<<3)+yytext[i]-'0';
  39.                                 i++;
  40.                         }
  41.                         yylval=val;
  42.                         return(NUM);
  43.                 }

  44. {hexnum}        {
  45.                         i=2;val=0;
  46.                         while(i<yyleng)
  47.                         {
  48.                                 if(islower(yytext[i])) val=(val<<4)+yytext[i]-'a'+10;
  49.                                 else if(isupper(yytext[i])) val=(val<<4)+yytext[i]-'A'+10;
  50.                                 else val=(val<<4)+yytext[i]-'0';
  51.                                 i++;
  52.                         }
  53.                         yylval=val;
  54.                         return(NUM);
  55.                 }

  56. {reg}                {
  57.                         if(islower(yytext[0]))yylval=yytext[0]-'a';
  58.                         else yylval=yytext[0]-'A';
  59.                         return(REG);
  60.                 }
  61.                
  62. {opt1}        {
  63.                         switch(yytext[0])
  64.                         {
  65.                                 case '+':
  66.                                         return ADD;
  67.                                         break;
  68.                                 case '-':
  69.                                         return SUB;
  70.                                         break;
  71.                                 case '*':
  72.                                         return MUL;
  73.                                         break;
  74.                                 case '/':
  75.                                         return DIV;
  76.                                         break;
  77.                                 case '%':       
  78.                                         return MOD;
  79.                                         break;
  80.                                 case '^':
  81.                                         return BITXOR;
  82.                                         break;
  83.                                 case '&':
  84.                                         return BITAND;
  85.                                         break;
  86.                                 case '|':
  87.                                         return BITOR;
  88.                                         break;
  89.                                 case '<':
  90.                                         return LESS;
  91.                                         break;
  92.                                 case '>':
  93.                                         return MORE;
  94.                                         break;
  95.                                 case '!':
  96.                                         return NOT;
  97.                                         break;
  98.                                 case '~':
  99.                                         return BITREV;
  100.                                         break;
  101.                         }
  102.                 }

  103. {opt2}        {
  104.                         switch(yytext[0])
  105.                         {
  106.                                 case '&':
  107.                                         return AND;
  108.                                         break;
  109.                                 case '|':
  110.                                         return OR;
  111.                                         break;
  112.                                 case '<':
  113.                                         return LSHIFT;
  114.                                         break;
  115.                                 case '>':
  116.                                         return RSHIFT;
  117.                                         break;
  118.                         }               
  119.                                        
  120.                 }               
  121. {clear}        {return(CLEAR);}       
  122. {exit}        {return(EXIT);}
  123. {list}                {return(LIST);}
  124. {erase}        {return(ERASE);}
  125. {hex}        {return(HEX);}
  126. {oct}                {return(OCT);}
  127. {dec}        {return(DEC);}
  128. {help}        {return(HELP);}

  129. .|\n                {return(yytext[0]);}
  130. [color=red]%%辅助部分在与yacc协同工作时可以省略[/color]
复制代码

yacc源码部分:nepc.y

  1. %{
  2. #include <ctype.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include "lex.yy.c"  [color=red]//这是词法分析器生成的文件,必须包含![/color]

  6. YYSTYPE reg[26]={0};
  7. BIGINT ival;

  8. enum Display{DEC_ON, HEX_ON, OCT_ON};
  9. enum Display dflag=DEC_ON;
  10. int i;

  11. %}

  12. %token                CLEAR EXIT LIST ERASE DEC HEX OCT HELP
  13. %token                NUM        REG
  14. %token                ADD SUB MUL DIV MOD LSHIFT RSHIFT
  15. %token                AND OR  NOT LESS MORE
  16. %token                BITAND BITOR BITXOR BITREV

  17. %left                OR
  18. %left                AND
  19. %left                BITOR
  20. %left                BITXOR
  21. %left                BITAND
  22. %left                LESS MORE
  23. %left                LSHIFT RSHIFT
  24. %left                ADD        SUB
  25. %left                MUL        DIV MOD
  26. %right                RMINUS BITREV NOT

  27. %%
  28.        
  29. lines                : lines statement '\n'               
  30.                 | lines '\n'                                {printf("--> ");}
  31.                 | lines error '\n'                        {yyerrok;printf("\n--> ");}
  32.                 | lines cmdline        '\n'               
  33.                 |
  34.                 ;
  35.                
  36. statement        : expr                                {
  37.                                                                 if(dflag==DEC_ON)printf( "\t=%g\n--> " , $1 );
  38.                                                                 else if(dflag==HEX_ON)printf( "\t=0x%08X\n--> " , (BIGINT)$1 );
  39.                                                                 else printf( "\t=0%o\n--> " , (BIGINT)$1 );
  40.                                                         }
  41.                 | REG '=' expr                        {
  42.                                                                 i=(int)$1; reg[i] = $3 ;
  43.                                                                 if(dflag==DEC_ON) printf( "\t%c=%g\n--> " , 'a'+i,reg[i] );
  44.                                                                 else if(dflag==HEX_ON) printf( "\t%c=0x%08X\n--> " , 'a'+i,(BIGINT)reg[i] );
  45.                                                                 else  printf( "\t%c=0%o\n--> " , 'a'+i,(BIGINT)reg[i] );
  46.                                                         }
  47.                 ;
  48.                
  49. expr                : expr ADD expr                        { $$ = $1 + $3 ; }
  50.                 | expr SUB expr                        { $$ = $1 - $3 ; }
  51.                 | expr MUL expr                        { $$ = $1 * $3 ; }
  52.                 | expr DIV expr                        { $$ = $1 / $3 ; }
  53.                 | expr MOD expr                        { $$ = (BIGINT)$1 % (BIGINT)$3 ; }
  54.                 | expr BITAND expr                { $$ = (BIGINT)$1 & (BIGINT)$3 ; }
  55.                 | expr BITOR expr                { $$ = (BIGINT)$1 | (BIGINT)$3 ; }
  56.                 | expr BITXOR expr                { $$ = (BIGINT)$1 ^ (BIGINT)$3 ; }
  57.                 | expr LSHIFT expr                { $$ = (BIGINT)$1 << (BIGINT)$3 ; }
  58.                 | expr RSHIFT expr                { $$ = (BIGINT)$1 >> (BIGINT)$3 ; }
  59.                 | expr AND expr                        { $$ = (BIGINT)$1 && (BIGINT)$3 ; }
  60.                 | expr OR expr                        { $$ = (BIGINT)$1 || (BIGINT)$3 ; }
  61.                 | expr LESS expr                { $$ = $1<$3?1:0; }
  62.                 | expr MORE expr                { $$ = $1>$3?1:0; }
  63.                 | '(' expr ')'                        { $$ = $2 ; }
  64.                 | SUB expr %prec RMINUS        { $$ = -$2 ; }
  65.                 | BITREV expr                        { $$ = ~((BIGINT)$2); }
  66.                 | NOT expr                         { $$ = !( (BIGINT)$2 ) ; }
  67.                 | NUM                                { $$ = $1 ; }
  68.                 | REG                                { ival=(int)$1;$$ = reg[ival] ; }
  69.                 ;

  70. cmdline        : EXIT                                 { exit(0); }
  71.                 | CLEAR                                { printf("\033[2J\033[1;1H\n--> "); }
  72.                 | HEX                                { dflag=HEX_ON; printf(">> Hex display mod on!\n--> "); }
  73.                 | DEC                                { dflag=DEC_ON; printf(">> Dec display mod on!\n--> "); }
  74.                 | OCT                                 { dflag=OCT_ON; printf(">> Oct display mod on!\n--> "); }
  75.                 | LIST                                 {
  76.                                                                 for(i=0;i<26;i++)
  77.                                                                 {
  78.                                                                         if(dflag==DEC_ON)printf("\t%c=%g\n",'a'+i,reg[i]);
  79.                                                                         else if(dflag==HEX_ON)printf("\t%c=0x%08X\n",'a'+i,(BIGINT)reg[i]);
  80.                                                                         else printf("\t%c=0%o\n",'a'+i,(BIGINT)reg[i]);
  81.                                                                 }
  82.                                                                 printf("--> ");
  83.                                                         }
  84.                 | ERASE                                 { for(i=0;i<26;i++)reg[i]=0; printf(">>All registers erased!\n--> ");}
  85.                 | HELP                                {
  86.                                                                 printf(">> COMMANDS:\n");
  87.                                                                 printf("> help: Display this help section.\n");
  88.                                                                 printf("> clear: Clear the screen.\n");
  89.                                                                 printf("> dec: Decimal mode to display  numbers or registers.\n");
  90.                                                                 printf("> hex: Hexadecimal mode to display numbers or registers.\n");
  91.                                                                 printf("> oct: Octal mode to display numbers or registers.\n");
  92.                                                                 printf("> list: List the values in the 26 registers which are ranged from 'a'/'A' to 'z'/'Z'.\n");
  93.                                                                 printf("> erase: Reset all registers to 0.\n");
  94.                                                                 printf("> exit: Quit this program.\n");
  95.                                                                 printf("--> ");
  96.                                                         }
  97.                 ;               

  98. %%

  99. int yyerror(char *str)
  100. {
  101.         fprintf(stderr,"Error: %s\n",str);
  102.         return 1;      
  103. }

  104. int yywrap()
  105. {[color=red]
  106.         // 这个函数是做什么的?
  107.         // 简单的说,yywrap()在当前输入的符号流(token 流)结束时(比如碰到了EOF)被调用。
  108.         // 所以,如果当存在若干个token流需要被解析(包括词法、语法解析)时,可以在此处对yyin这个
  109.         // 内置的文件指针进行重新指派(比如yyin=fopen("xxx","r")或者rewind(yyin)啦)。
  110.         // 当yyin重新被指派后,为了开始新的解析,本函数必须return 0。
  111.         // 当没有新的输入流需要解析时,本函数须 return一非零值,以结束解析。[/color]
  112.          
  113.       return 1;
  114. }
  115. int main()
  116. {
  117.         printf("--------------------------------------------------------------\n");
  118.         printf(">> nepc - A mini limited precision caculator.\n");
  119.         printf(">> Copyright (C) 2005 neplusultra@linuxsir.cn\n");
  120.         printf(">> nepc is open software; you can redistribute it and/or modify\n\
  121.    it under the terms of the version 2.1 of the GNU Lesser \n\
  122.    General Public License as published by the Free Software\n\
  123.    Foundation.\n");
  124.         printf("--------------------------------------------------------------\n");
  125.         printf("--> ");
  126. [color=red]
  127.         // 此处开始对内建文件指针yyin指向的流(默认是stdin)进行词法和语法解析。
  128.         // yyin可以根据需要来指派,比如指向一个文件。
  129. [/color]
  130.         yyparse();
  131. }

复制代码


[编译]

按如下步骤可生成最终的可执行文件nepc :

  1. $ lex nepc.l
  2. $ yacc -d nepc.y
  3. $ gcc -o nepc y.tab.c
复制代码


[下载]

所有源码均在附件。
把扩展名.txt去除后即原始文件。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
 楼主| 发表于 2005-3-30 15:10:39 | 显示全部楼层
可执行文件:
nepc
下载后去除扩展名.txt
再chmod u+x nepc就可以执行了。
回复 支持 反对

使用道具 举报

发表于 2005-3-30 15:38:59 | 显示全部楼层
不错,做一个计算器是非常合适的作业。
鼓励一下,加精了!
回复 支持 反对

使用道具 举报

 楼主| 发表于 2005-3-30 15:50:40 | 显示全部楼层

更简单的例子:算术表达式后缀式的写法

把四则运算式(包括括号)转化为后缀式(逆波兰式)的一个简单例子。
采用的是算符优先文法,变分析边执行语义动作。供大家参考:

nbl.l

  1. %{
  2. #include "y.tab.h"
  3. %}

  4. digit                        [0-9]
  5. decnum                  (0(\.{digit}+)?)|([1-9]{digit}*(\.{digit}+)?)
  6. opt                    "+"|"-"|"*"|"/"

  7. %%

  8. [" " \t]               {}
  9. {decnum}                {sscanf(yytext,"%d",&yylval);return(NUM); }
  10. {opt}                  {
  11.                                 switch(yytext[0])
  12.                                 {
  13.                                         case '+':
  14.                                                 return ADD;
  15.                                                 break;
  16.                                         case '-':
  17.                                                 return SUB;
  18.                                                 break;
  19.                                         case '*':
  20.                                                 return MUL;
  21.                                                 break;
  22.                                         case '/':
  23.                                                 return DIV;
  24.                                                 break;
  25.                                 }
  26.                         }
  27. .|\n                            { return(yytext[0]); }
复制代码


nbl.y

  1. %{
  2. #include "lex.yy.c"
  3. %}

  4. %token                  NUM ADD SUB MUL DIV MOD
  5. %left                   ADD     SUB
  6. %left                  MUL     DIV

  7. %%
  8. lines                        : lines E '\n'
  9.                         | lines '\n'
  10.                         |
  11.                         ;

  12. E                        :  E ADD T { printf("+"); }
  13.                         |  E SUB T { printf("-"); }
  14.                         | T
  15.                         ;
  16. T                        : T MUL F { printf("*"); }
  17.                         | T DIV F { printf("/"); }
  18.                         | F
  19.                         ;
  20. F                        : NUM {printf("%d",yylval);}
  21.                         | '(' E ')'
  22.                         ;

  23. %%
  24. int yyerror(char *str)
  25. {
  26.         fprintf(stderr,"Error: %s\n",str);
  27.         return 1;
  28. }

  29. int yywrap()
  30. {
  31.          return 0;
  32. }
  33. int main()
  34. {
  35.           yyparse();
  36. }

复制代码
回复 支持 反对

使用道具 举报

发表于 2005-4-5 08:46:01 | 显示全部楼层
这是一个独立的程序哦,怎么用lex/yacc做一个程序中的一个子模块,在主程序中怎么调用呢
回复 支持 反对

使用道具 举报

 楼主| 发表于 2005-4-5 10:03:28 | 显示全部楼层
你可以单独写一个lex/yacc文件,并可能要写好自己的yywrap、yyerror甚至main等函数。
以lex模块为例,比如写好的lex文件名为lexmod.l,接下来:
lex lexmod.l

生成lex.yy.c这个文件。

然后只要在需要该模块的文件中#include “lex.yy.c",并调用yylex()函数即可。
回复 支持 反对

使用道具 举报

发表于 2005-4-6 08:57:25 | 显示全部楼层
关于输入的信息就写在yywrap中是吧,main不用写了吧
回复 支持 反对

使用道具 举报

 楼主| 发表于 2005-4-6 10:12:50 | 显示全部楼层
对,在yywrap()可以指定新的yyin,比如打开一个文件继续parse,此时要return 0。
若当前输入已经完毕且无其他输入,return 1即可。
回复 支持 反对

使用道具 举报

发表于 2005-5-5 21:28:19 | 显示全部楼层
哪有yacc下载呀???
回复 支持 反对

使用道具 举报

发表于 2005-5-6 08:42:51 | 显示全部楼层
Post by hivon
哪有yacc下载呀???

一般系统上都有安装。如果没有,估计安装的是bison。它和yacc也是可以兼容的。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回顶部 返回列表