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

neplusultra · 发表于 2005-3-30 14:56:38

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

［成果］
　　主要的成果是我花了一个晚上加一个上午设计和编码，一个中午调试最后实现的一个小型文本计算器。我们知道GNU/linux已经提供了一个任意精度的calc文本计算器，其功能非常强大。我的nepc （neplusultra calculator

）仅仅实现了calc的一小部分功能，但对于日常使用已经足够了。nepc完全由lex和yacc生成。
　　已实现功能罗列如下：
　　１、支持运算符：加减乘除、%(模运算)、逻辑运算（||、&&、!）、位运算（<<、>>、|、&、^(位异或)、~(取反)）、大于小于运算、小括号()。各种运算符优先级遵从Ｃ语言标准。
　　２、支持数制：八进制、十进制、十六进制。相应通过oct、dec、hex三个命令可以指定终端显示的数制类型。同时支持三种数制的输入：八进制数以0开头且至少两位；十六进制以0x或0X开头；十进制按日常书写规则书写。八进制和十六进制仅对整数类型有效。
　　３、提供２６个寄存器用以存储变量，从a到z，大小写忽略。用list命令可以查看所有寄存器变量；用erase命令可以清空全部寄存器变量。
　　４、算术表达式可以任意长度。
　　５、帮助：help命令

　　待实现功能如下：
　　１、历史记录功能。
　　２、八进制及十六进制的小数表示形式。
　　３、加入二进制数制支持。

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

lex源码部分：nepc.l

%{
#define YYSTYPE double　　//[color=red]很多参考资料都没有正确解释重定义YYSTYPE的正确方法，我这样定义是安全的。[/color]
#define BIGINT long long
#include <ctype.h>
#include "y.tab.h"　　[color=red]//这是yacc生成的文件，必须包含！[/color]
%}
digit [0-9]
xdigit [0-9a-fA-F]
odigit [0-7]
decnum (0(\.{digit}+)?)|([1-9]{digit}*(\.{digit}+)?)
octnum 0{odigit}+
hexnum 0(x|X){xdigit}+
reg [a-zA-Z]
opt1 "+"|"-"|"*"|"/"|"&"|"|"|"%"|"^"|"~"|"!"|"<"|">"
opt2 (&&)|(\|\|)|(\<\<)|(\>\>)
exit ((E|e)(X|x)(I|i)(T|t))|((Q|q)(U|u)(I|i)(T|t))
clear (C|c)(L|l)(E|e)(A|a)(R|r)
list (L|l)(I|i)(S|s)(T|t)
erase (E|e)(R|r)(A|a)(S|s)(E|e)
hex (H|h)(E|e)(X|x)
oct (O|o)(C|c)(T|t)
dec (D|d)(E|e)(C|c)
help (H|h)(E|e)(L|l)(P|p)
%%
[color=red] //　此处可以定义局部变量。注意，该定义绝对不能从第一列开始！
　　　　　 // 而词法符号必须从第一列开始。
[/color]
int i ;
BIGINT val;
[" "; \t] {}
{decnum} {sscanf(yytext,"%lf",&yylval);return(NUM); }
{octnum} {
i=1;val=0;
while(i<yyleng)
{
val=(val<<3)+yytext[i]-'0';
i++;
}
yylval=val;
return(NUM);
}
{hexnum} {
i=2;val=0;
while(i<yyleng)
{
if(islower(yytext[i])) val=(val<<4)+yytext[i]-'a'+10;
else if(isupper(yytext[i])) val=(val<<4)+yytext[i]-'A'+10;
else val=(val<<4)+yytext[i]-'0';
i++;
}
yylval=val;
return(NUM);
}
{reg} {
if(islower(yytext[0]))yylval=yytext[0]-'a';
else yylval=yytext[0]-'A';
return(REG);
}
{opt1} {
switch(yytext[0])
{
case '+':
return ADD;
break;
case '-':
return SUB;
break;
case '*':
return MUL;
break;
case '/':
return DIV;
break;
case '%':
return MOD;
break;
case '^':
return BITXOR;
break;
case '&':
return BITAND;
break;
case '|':
return BITOR;
break;
case '<':
return LESS;
break;
case '>':
return MORE;
break;
case '!':
return NOT;
break;
case '~':
return BITREV;
break;
}
}
{opt2} {
switch(yytext[0])
{
case '&':
return AND;
break;
case '|':
return OR;
break;
case '<':
return LSHIFT;
break;
case '>':
return RSHIFT;
break;
}
}
{clear} {return(CLEAR);}
{exit} {return(EXIT);}
{list} {return(LIST);}
{erase} {return(ERASE);}
{hex} {return(HEX);}
{oct} {return(OCT);}
{dec} {return(DEC);}
{help} {return(HELP);}
.|\n {return(yytext[0]);}
[color=red]%%辅助部分在与yacc协同工作时可以省略[/color]

复制代码

yacc源码部分：nepc.y

%{
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include "lex.yy.c" [color=red]//这是词法分析器生成的文件，必须包含！[/color]
YYSTYPE reg[26]={0};
BIGINT ival;
enum Display{DEC_ON, HEX_ON, OCT_ON};
enum Display dflag=DEC_ON;
int i;
%}
%token CLEAR EXIT LIST ERASE DEC HEX OCT HELP
%token NUM REG
%token ADD SUB MUL DIV MOD LSHIFT RSHIFT
%token AND OR NOT LESS MORE
%token BITAND BITOR BITXOR BITREV
%left OR
%left AND
%left BITOR
%left BITXOR
%left BITAND
%left LESS MORE
%left LSHIFT RSHIFT
%left ADD SUB
%left MUL DIV MOD
%right RMINUS BITREV NOT
%%
lines : lines statement '\n'
| lines '\n' {printf("--> ");}
| lines error '\n' {yyerrok;printf("\n--> ");}
| lines cmdline '\n'
|
;
statement : expr {
if(dflag==DEC_ON)printf( "\t=%g\n--> " , $1 );
else if(dflag==HEX_ON)printf( "\t=0x%08X\n--> " , (BIGINT)$1 );
else printf( "\t=0%o\n--> " , (BIGINT)$1 );
}
| REG '=' expr {
i=(int)$1; reg[i] = $3 ;
if(dflag==DEC_ON) printf( "\t%c=%g\n--> " , 'a'+i,reg[i] );
else if(dflag==HEX_ON) printf( "\t%c=0x%08X\n--> " , 'a'+i,(BIGINT)reg[i] );
else printf( "\t%c=0%o\n--> " , 'a'+i,(BIGINT)reg[i] );
}
;
expr : expr ADD expr { $$ = $1 + $3 ; }
| expr SUB expr { $$ = $1 - $3 ; }
| expr MUL expr { $$ = $1 * $3 ; }
| expr DIV expr { $$ = $1 / $3 ; }
| expr MOD expr { $$ = (BIGINT)$1 % (BIGINT)$3 ; }
| expr BITAND expr { $$ = (BIGINT)$1 & (BIGINT)$3 ; }
| expr BITOR expr { $$ = (BIGINT)$1 | (BIGINT)$3 ; }
| expr BITXOR expr { $$ = (BIGINT)$1 ^ (BIGINT)$3 ; }
| expr LSHIFT expr { $$ = (BIGINT)$1 << (BIGINT)$3 ; }
| expr RSHIFT expr { $$ = (BIGINT)$1 >> (BIGINT)$3 ; }
| expr AND expr { $$ = (BIGINT)$1 && (BIGINT)$3 ; }
| expr OR expr { $$ = (BIGINT)$1 || (BIGINT)$3 ; }
| expr LESS expr { $$ = $1<$3?1:0; }
| expr MORE expr { $$ = $1>$3?1:0; }
| '(' expr ')' { $$ = $2 ; }
| SUB expr %prec RMINUS { $$ = -$2 ; }
| BITREV expr { $$ = ~((BIGINT)$2); }
| NOT expr { $$ = !( (BIGINT)$2 ) ; }
| NUM { $$ = $1 ; }
| REG { ival=(int)$1;$$ = reg[ival] ; }
;
cmdline : EXIT { exit(0); }
| CLEAR { printf("\033[2J\033[1;1H\n--> "); }
| HEX { dflag=HEX_ON; printf(">> Hex display mod on!\n--> "); }
| DEC { dflag=DEC_ON; printf(">> Dec display mod on!\n--> "); }
| OCT { dflag=OCT_ON; printf(">> Oct display mod on!\n--> "); }
| LIST {
for(i=0;i<26;i++)
{
if(dflag==DEC_ON)printf("\t%c=%g\n",'a'+i,reg[i]);
else if(dflag==HEX_ON)printf("\t%c=0x%08X\n",'a'+i,(BIGINT)reg[i]);
else printf("\t%c=0%o\n",'a'+i,(BIGINT)reg[i]);
}
printf("--> ");
}
| ERASE { for(i=0;i<26;i++)reg[i]=0; printf(">>All registers erased!\n--> ");}
| HELP {
printf(">> COMMANDS:\n");
printf("> help: Display this help section.\n");
printf("> clear: Clear the screen.\n");
printf("> dec: Decimal mode to display numbers or registers.\n");
printf("> hex: Hexadecimal mode to display numbers or registers.\n");
printf("> oct: Octal mode to display numbers or registers.\n");
printf("> list: List the values in the 26 registers which are ranged from 'a'/'A' to 'z'/'Z'.\n");
printf("> erase: Reset all registers to 0.\n");
printf("> exit: Quit this program.\n");
printf("--> ");
}
;
%%
int yyerror(char *str)
{
fprintf(stderr,"Error: %s\n",str);
return 1;
}
int yywrap()
{[color=red]
// 这个函数是做什么的？
// 简单的说，yywrap()在当前输入的符号流（token 流）结束时（比如碰到了EOF）被调用。
// 所以,如果当存在若干个token流需要被解析（包括词法、语法解析）时，可以在此处对yyin这个
// 内置的文件指针进行重新指派（比如yyin=fopen("xxx","r")或者rewind(yyin)啦）。
// 当yyin重新被指派后，为了开始新的解析，本函数必须return 0。
// 当没有新的输入流需要解析时，本函数须 return一非零值，以结束解析。[/color]
return 1;
}
int main()
{
printf("--------------------------------------------------------------\n");
printf(">> nepc - A mini limited precision caculator.\n");
printf(">> Copyright (C) 2005 neplusultra@linuxsir.cn\n");
printf(">> nepc is open software; you can redistribute it and/or modify\n\
it under the terms of the version 2.1 of the GNU Lesser \n\
General Public License as published by the Free Software\n\
Foundation.\n");
printf("--------------------------------------------------------------\n");
printf("--> ");
[color=red]
// 此处开始对内建文件指针yyin指向的流（默认是stdin）进行词法和语法解析。
// yyin可以根据需要来指派，比如指向一个文件。
[/color]
yyparse();
}

复制代码

［编译］
按如下步骤可生成最终的可执行文件nepc　：

$ lex nepc.l
$ yacc -d nepc.y
$ gcc -o nepc y.tab.c

复制代码

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

neplusultra · 发表于 2005-3-30 15:10:39

可执行文件：
nepc
下载后去除扩展名.txt
再chmod u+x nepc就可以执行了。

kj501 · 发表于 2005-3-30 15:38:59

不错，做一个计算器是非常合适的作业。
鼓励一下，加精了！

neplusultra · 发表于 2005-3-30 15:50:40

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

nbl.l

%{
#include "y.tab.h"
%}
digit [0-9]
decnum (0(\.{digit}+)?)|([1-9]{digit}*(\.{digit}+)?)
opt "+"|"-"|"*"|"/"
%%
[" " \t] {}
{decnum} {sscanf(yytext,"%d",&yylval);return(NUM); }
{opt} {
switch(yytext[0])
{
case '+':
return ADD;
break;
case '-':
return SUB;
break;
case '*':
return MUL;
break;
case '/':
return DIV;
break;
}
}
.|\n { return(yytext[0]); }

复制代码

nbl.y

%{
#include "lex.yy.c"
%}
%token NUM ADD SUB MUL DIV MOD
%left ADD SUB
%left MUL DIV
%%
lines : lines E '\n'
| lines '\n'
|
;
E : E ADD T { printf("+"); }
| E SUB T { printf("-"); }
| T
;
T : T MUL F { printf("*"); }
| T DIV F { printf("/"); }
| F
;
F : NUM {printf("%d",yylval);}
| '(' E ')'
;
%%
int yyerror(char *str)
{
fprintf(stderr,"Error: %s\n",str);
return 1;
}
int yywrap()
{
return 0;
}
int main()
{
yyparse();
}

复制代码

luddy2 · 发表于 2005-4-5 08:46:01

这是一个独立的程序哦，怎么用lex/yacc做一个程序中的一个子模块，在主程序中怎么调用呢

neplusultra · 发表于 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()函数即可。

luddy2 · 发表于 2005-4-6 08:57:25

关于输入的信息就写在yywrap中是吧，main不用写了吧

neplusultra · 发表于 2005-4-6 10:12:50

对，在yywrap()可以指定新的yyin，比如打开一个文件继续parse，此时要return 0。
若当前输入已经完毕且无其他输入，return 1即可。

hivon · 发表于 2005-5-5 21:28:19

哪有yacc下载呀？？？

kj501 · 发表于 2005-5-6 08:42:51

Post by hivon
哪有yacc下载呀？？？

一般系统上都有安装。如果没有，估计安装的是bison。它和yacc也是可以兼容的。

		自动登录	找回密码
密码			注册

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

本帖子中包含更多资源

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