Lex与Yacc学习实例(二) —— 解释器的编制

neplusultra · 发表于 2005-5-27 00:28:38

2005-5-29-21:00更新：基本把bug去除，加入若干重要数学函数支持；参考help命令
2005-5-28-12:40更新：重构文件组织，lex和yacc模块从main模块独立；去除一些bug(变量未定义时出现段错误)，增补自增(++) ,自减(--)运算
2005-5-27-20:19更新：去除一些bug，增补模运算、逻辑与、逻辑或运算

本来计划用yacc辅助做一个C语言子集编译器的，无奈往往有心无力没时间。 :beat
后来随便做个小解释器玩玩，算是对lex及yacc学习的一个了结。 :cool:

［简介］
　　nepc-0.2是上一个版本的进化：
1、加入了print、if语句、 if-else和 while语句的支持。从而你可以用nepc进行简单编程，比如输出非波纳妾数列啊、求质数数列啊等等(附件截图)。
2、数据类型增加为整数、浮点数、字符串。并提供类型转换。
3、变量可以自由定义了，而且必须先定义再使用。
　　nepc相当于一个最mini的解释器。（什么是解释器？ :ask 早期的gw-basic或者小霸王上的fbasic知道吗？）。解释器和编译器还是有差的，前者效率往往较低。
　　nepc-0.2采用yacc建立语法树，然后按深度优先遍历之，边访问边解释代码；当然，遍历时可以生成中间代码。
　　nepc-0.2仍旧只能算作教学程序。

［文法］

program:
parsed EXIT
;
parsed:
parsed stmt
| parsed error separator
|
;
stmt:
separator
| expr separator
| PRINT expr separator
| VARIABLE '=' expr separator
| WHILE '(' expr ')' stmt
| IF '(' expr ')' stmt %prec IFX
| IF '(' expr ')' stmt ELSE stmt
| '{' stmt_list '}'
| CMD
;
CMD:
ERASE
| HELP
| LIST
| CLEAR
| HEX
| DEC
| OCT
;
stmt_list:
stmt
| stmt_list stmt
;
separator: ';'
;
expr:
INTEGER
| FLOAT
| STRING
| VARIABLE
| '-' expr %prec UMINUS
| expr PP
| expr SS
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| expr '<' expr
| expr '>' expr
| expr '%' expr
| expr AND expr
| expr OR expr
| expr GE expr
| expr LE expr
| expr NE expr
| expr EQ expr
| '(' expr ')'
| functions // 一些数学函数，此处省略。详见附件源码
;

复制代码

代码量1000多行，只贴出lex和yacc文件内容，其他所有文件都放在附件压缩包里头供下载。另外一个很有用的是how to use lex&yacc .pdf ，也放在附件。
>>nepc.l<<

%{
#include "y.tab.h"
#include "nepc.h"
%}
digit [0-9]
xdigit [0-9a-fA-F]
odigit [0-7]
dec_int 0|[1-9]{digit}*
dec_flt (0\.{digit}*)|([1-9]{digit}*\.{digit}*)
oct_int 0{odigit}+
hex_int 0(x|X){xdigit}+
letter [a-zA-Z]
variable {letter}({letter}|{digit})*
%x ASTRING
%%
char *s, *v;
char tmpstr[MAX_STRLEN];
" { BEGIN ASTRING; s = tmpstr; }
<ASTRING>\\n { *s++ = '\n'; /* CARE BUFFER OVERFLOW HERE!!! */ }
<ASTRING>\\t { *s++ = '\t'; /* CARE BUFFER OVERFLOW HERE!!! */ }
<ASTRING>\\" { *s++ = '"'; /* CARE BUFFER OVERFLOW HERE!!! */ }
<ASTRING>" {
*s = '\0';
BEGIN 0;
yylval.pStr = tmpstr;
return STRING;
}
<ASTRING>\n { printf("invalid string"); exit(1); }
<ASTRING>. { *s++ = *yytext; }
"while" return WHILE;
"if" return IF;
"else" return ELSE;
"print" return PRINT;
"exit" return EXIT;
"quit" return EXIT;
"erase" return ERASE;
"clear" return CLEAR;
"cls" return CLEAR;
"ls" return LIST;
"list" return LIST;
"help" return HELP;
"dec" return DEC;
"hex" return HEX;
"oct" return OCT;
"acos" return ACOS;
"asin" return ASIN;
"atan" return ATAN;
"ceil" return CEIL;
"cos" return COS;
"cosh" return COSH;
"exp" return EXP;
"fabs" return FABS;
"floor" return FLOOR;
"log" return LOG;
"log10" return LOG10;
"sin" return SIN;
"sinh" return SINH;
"sqrt" return SQRT;
"tan" return TAN;
"tanh" return TANH;
{variable} {
v=malloc(yyleng+1);
strncpy(v, yytext, yyleng);
v[yyleng]='\0';
yylval.pStr = v;
return VARIABLE;
}
{dec_int} {
yylval.iValue = STR_TO_INT(yytext);
return INTEGER;
}
{dec_flt} {
yylval.fValue = STR_TO_FLT(yytext);
return FLOAT;
}
{oct_int} {
int i=1;
INT val=0;
while(i<yyleng)
{
val=(val<<3)+yytext[i]-'0';
i++;
}
yylval.iValue=val;
return INTEGER;
}
{hex_int} {
int i=2;
INT 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.iValue=val;
return INTEGER;
}
[-()<>=+*/{}.;%] {
return *yytext;
}
">=" return GE;
"<=" return LE;
"==" return EQ;
"!=" return NE;
"&&" return AND;
"||" return OR;
"++" return PP;
"--" return SS;
[ \t\n]+ ; /* ignore whitespace */
. yyerror("Unknown character");
%%
int yywrap(void)
{
return 1;
}

复制代码

>>nepc.y<<

%{
#include "nepc.h"
#include "nepc.c" /* routines for parse */
#include "lex.yy.c"
%}
%union{
INT iValue;
FLT fValue;
char * pStr;
nodeType *nPtr;
};
%token <iValue> INTEGER
%token <fValue> FLOAT
%token <pStr> VARIABLE
%token <pStr> STRING
%token <iValue> ACOS ASIN ATAN CEIL COS COSH EXP FABS FLOOR
%token <iValue> LOG LOG10 POW10 SIN SINH SQRT TAN TANH
%type <nPtr> stmt expr stmt_list function
%token EXIT ERASE CLEAR LIST HELP DEC HEX OCT
%token WHILE IF PRINT
%nonassoc IFX
%nonassoc ELSE
%left OR
%left AND
%left GE LE EQ NE '>' '<'
%left '+' '-'
%left '*' '/' '%'
%left PP SS
%nonassoc UMINUS
%%
program:
init parsed EXIT { freeSymTable(); exit(0); }
;
init: /* NULL*/ { initSymTable(); WAITINPUT;}
;
parsed:
parsed stmt { free(interpret($2)); freeNode($2); WAITINPUT; }
| parsed error separator { yyerrok; WAITINPUT;}
| /* NULL */
;
stmt:
separator { $$ = opr(';', 2, NULL, NULL); }
| expr separator { $$ = opr(PRINT, 1, $1); }
| PRINT expr separator { $$ = opr(PRINT, 1, $2); }
| VARIABLE '=' expr separator { $$ = (($3 == NULL)?NULL:(symname_install($1),opr('=', 2, var($1), $3)));}
| WHILE '(' expr ')' stmt { $$ = opr(WHILE, 2, $3, $5); }
| IF '(' expr ')' stmt %prec IFX { $$ = opr(IF, 2, $3, $5); }
| IF '(' expr ')' stmt ELSE stmt { $$ = opr(IF, 3, $3, $5, $7); }
| '{' stmt_list '}' { $$ = $2; }
| CMD { $$ = NULL; }
;
CMD:
ERASE { freeSymTable(); printf(">> All variables erased!\n"); }
| HELP {
printf(">> COMMANDS:\n");
printf("> help: Display this help section.\n");
printf("> clear/cls: Clear the screen.\n");
printf("> dec: Decimal mode to display numbers or variables.\n");
printf("> hex: Hexadecimal mode to display numbers or variables.\n");
printf("> oct: Octal mode to display numbers or variables.\n");
printf("> list/ls: List the values of variables.\n");
printf("> erase: Reset all variables to 0.\n");
printf("> exit/quit: Quit this program.\n");
printf("> functions supported: acos,asin,atan,ceil,cos,cosh,exp,\n");
printf("> fabs,floor,log,log10,sin,sinh,sqrt,tan,tanh.\n");
}
| LIST {
int i;
symType * p;
for(i=0;i<symtop;i++)
{
p=&symtab[i];
if(symtab[i].type==typeInt)
{
printf("\tINT %s = ", p->name);
PRINTINT(p);
}
else if(symtab[i].type==typeFlt)
{
printf("\tFLT %s = ", p->name);
PRINTFLT(p);
}
else if(symtab[i].type==typeStr)
{
printf("\tSTR %s = ", p->name);
PRINTSTR(p);
}
printf("\n");
}
}
| CLEAR { printf("\033[2J\033[1;1H\n"); }
| HEX { dflag=HEX_ON; printf(">> HEX display mode on!\n"); }
| DEC { dflag=DEC_ON; printf(">> DEC display mode on!\n"); }
| OCT { dflag=OCT_ON; printf(">> OCT display mode on!\n"); }
;
stmt_list:
stmt { $$ = $1; }
| stmt_list stmt { $$ = opr(';', 2, $1, $2); }
;
separator:
';'
;
expr:
INTEGER { $$ = con_int($1); }
| FLOAT { $$ = con_flt($1); }
| STRING { $$ = con_str($1); }
| VARIABLE { $$ = var($1); }
| '-' expr %prec UMINUS { $$ = opr(UMINUS, 1, $2); }
| VARIABLE PP { $$ = ((var($1)==NULL) ? NULL: opr(PP, 1, var($1))); }
| VARIABLE SS { $$ = ((var($1)==NULL) ? NULL: opr(SS, 1, var($1))); }
| expr '+' expr { $$ = opr('+', 2, $1, $3); }
| expr '-' expr { $$ = opr('-', 2, $1, $3); }
| expr '*' expr { $$ = opr('*', 2, $1, $3); }
| expr '/' expr { $$ = opr('/', 2, $1, $3); }
| expr '<' expr { $$ = opr('<', 2, $1, $3); }
| expr '>' expr { $$ = opr('>', 2, $1, $3); }
| expr '%' expr { $$ = opr('%', 2, $1, $3); }
| expr AND expr { $$ = opr(AND, 2, $1, $3); }
| expr OR expr { $$ = opr(OR, 2, $1, $3); }
| expr GE expr { $$ = opr(GE, 2, $1, $3); }
| expr LE expr { $$ = opr(LE, 2, $1, $3); }
| expr NE expr { $$ = opr(NE, 2, $1, $3); }
| expr EQ expr { $$ = opr(EQ, 2, $1, $3); }
| '(' expr ')' { $$ = $2; }
| function { $$ = $1; }
;
function:
ACOS '(' expr ')' { $$ = opr(ACOS,1,$3); }
| ASIN '(' expr ')' { $$ = opr(ASIN,1,$3); }
| ATAN '(' expr ')' { $$ = opr(ATAN,1,$3);; }
| CEIL '(' expr ')' { $$ = opr(CEIL,1,$3); }
| COS '(' expr ')' { $$ = opr(COS,1,$3); }
| COSH '(' expr ')' { $$ = opr(COSH,1,$3); }
| EXP '(' expr ')' { $$ = opr(EXP,1,$3); }
| FABS '(' expr ')' { $$ = opr(FABS,1,$3); }
| FLOOR '(' expr ')' { $$ = opr(FLOOR,1,$3); }
| LOG '(' expr ')' { $$ = opr(LOG,1,$3); }
| LOG10 '(' expr ')' { $$ = opr(LOG10,1,$3); }
| SIN '(' expr ')' { $$ = opr(SIN,1,$3); }
| SINH '(' expr ')' { $$ = opr(SINH,1,$3); }
| SQRT '(' expr ')' { $$ = opr(SQRT,1,$3); }
| TAN '(' expr ')' { $$ = opr(TAN,1,$3); }
| TANH '(' expr ')' { $$ = opr(TANH,1,$3); }
;
%%
void yyerror(char *s)
{
fprintf(stdout, "%s\n", s);
}

复制代码

>>nepcmain.c<<

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <math.h>
#include "y.tab.c"
extern int yyparse();
extern FILE * yyin;
void motd()
{
printf("--------------------------------------------------------------\n");
printf(">> nepc-0.2 - A mini limited precision interpreting calculator.\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>> Type 'exit' to quit, type 'help' to get help.\n");
printf("--------------------------------------------------------------\n");
}
int main(void)
{
motd();
yyin=stdin; /* set parse stream to standard input */
yyparse(); /* begin parse */
fclose(yyin);
return 0;
}

复制代码

［编译］

$ tar jxvf nepc-0.2-r1.tar.bz2
$ lex nepc.l
$ yacc -d nepc.y
$ gcc -o your-bin-name nepcmain.c -lm

复制代码

soloforce · 发表于 2005-5-27 08:12:02

微软的qbasic也是经典的解释器

herberteuler · 发表于 2005-5-27 10:29:29

Excelent work

But why not a makefile?

neplusultra · 发表于 2005-5-27 20:33:57

3x

不会弄makefile，也暂时没空去学了；
如何编译在文末有提到，很简单。

感兴趣的可以下载最新的版本玩玩

有朋友问到使用问题，其实看看文法就知道了；提示以下几点：
1、记得语句后面要用一个";"结尾，几个命令字可以不要，这是文法设计的原因。
2、print 目前仅跟一个打印对象，它可以用()括起来，也可以不用；如果是字符串，支持转义字符'\t' '\n' '\“‘。
3、字符串也可以相加；对于不支持的运算操作，会返回0值；

kj501 · 发表于 2005-5-28 10:45:21

ok,非常不错！

nait · 发表于 2005-5-28 16:00:56

强人，值的学习

千年沉冰 · 发表于 2005-6-16 02:14:23

为什么我完全按照楼主的做法去做，却出现以下结果呢：
＄gcc -o myyacc nepcmain.c -lm
In file include from nepc.y:3
from nepcmain.c:3:
nepc.c:In function 'var':
nepc.c:107:parse error before '*'
nepc.c:110:'nodeSize' undeclared (first used in this function)
nepc.c:...................
nepc.c:...................

明明已经定义了，为什么还说我没有定义呢
急！！期待热情高手帮忙！！

taurusivy · 发表于 2006-3-17 21:56:14

Post by 千年沉冰
为什么我完全按照楼主的做法去做，却出现以下结果呢：
＄gcc -o myyacc nepcmain.c -lm
In file include from nepc.y:3
from nepcmain.c:3:
nepc.c:In function 'var':
nepc.c:107:parse error before '*'
nepc.c:110:'nodeSize' undeclared (first used in this function)
nepc.c:...................
nepc.c:...................

明明已经定义了，为什么还说我没有定义呢
急！！期待热情高手帮忙！！

我也一样。。打印如下：
[root@YanXT:nepc-0.2](0)# lex nepc.l
[root@YanXT:nepc-0.2](0)# yacc -d nepc.y
[root@YanXT:nepc-0.2](0)# gcc -o nepc nepcmain.c
In file included from nepc.y:3,
from nepcmain.c:3:
nepc.c: In function `interpret':
nepc.c:222: `WHILE' undeclared (first use in this function)
nepc.c:222: (Each undeclared identifier is reported only once
nepc.c:222: for each function it appears in.)
nepc.c:238: `IF' undeclared (first use in this function)
nepc.c:257: `PRINT' undeclared (first use in this function)
nepc.c:288: `UMINUS' undeclared (first use in this function)
nepc.c:295: `PP' undeclared (first use in this function)
nepc.c:310: `SS' undeclared (first use in this function)
nepc.c:614: `AND' undeclared (first use in this function)
nepc.c:647: `OR' undeclared (first use in this function)
nepc.c:680: `GE' undeclared (first use in this function)
nepc.c:717: `LE' undeclared (first use in this function)
nepc.c:754: `NE' undeclared (first use in this function)
nepc.c:791: `EQ' undeclared (first use in this function)
nepc.c:828: `ACOS' undeclared (first use in this function)
nepc.c:837: `ASIN' undeclared (first use in this function)
nepc.c:845: `ATAN' undeclared (first use in this function)
nepc.c:853: `CEIL' undeclared (first use in this function)
nepc.c:861: `COS' undeclared (first use in this function)
nepc.c:876: `COSH' undeclared (first use in this function)
nepc.c:891: `EXP' undeclared (first use in this function)
nepc.c:906: `FABS' undeclared (first use in this function)
nepc.c:921: `FLOOR' undeclared (first use in this function)
nepc.c:936: `LOG' undeclared (first use in this function)
nepc.c:951: `LOG10' undeclared (first use in this function)
nepc.c:966: `SIN' undeclared (first use in this function)
nepc.c:981: `SINH' undeclared (first use in this function)
nepc.c:996: `SQRT' undeclared (first use in this function)
nepc.c:1011: `TAN' undeclared (first use in this function)
nepc.c:1026: `TANH' undeclared (first use in this function)
In file included from nepcmain.c:3:
nepc.y: At top level:
nepc.y:12: conflicting types for `YYSTYPE'
y.tab.h:53: previous declaration of `YYSTYPE'
y.tab.c:470: conflicting types for `yylval'
y.tab.h:54: previous declaration of `yylval'

taurusivy · 发表于 2006-3-17 21:56:17

Post by 千年沉冰
为什么我完全按照楼主的做法去做，却出现以下结果呢：
＄gcc -o myyacc nepcmain.c -lm
In file include from nepc.y:3
from nepcmain.c:3:
nepc.c:In function 'var':
nepc.c:107:parse error before '*'
nepc.c:110:'nodeSize' undeclared (first used in this function)
nepc.c:...................
nepc.c:...................

明明已经定义了，为什么还说我没有定义呢
急！！期待热情高手帮忙！！

我也一样。。打印如下：

[root@YanXT:nepc-0.2](0)# lex nepc.l
[root@YanXT:nepc-0.2](0)# yacc -d nepc.y
[root@YanXT:nepc-0.2](0)# gcc -o nepc nepcmain.c
In file included from nepc.y:3,
from nepcmain.c:3:
nepc.c: In function `interpret':
nepc.c:222: `WHILE' undeclared (first use in this function)
nepc.c:222: (Each undeclared identifier is reported only once
nepc.c:222: for each function it appears in.)
nepc.c:238: `IF' undeclared (first use in this function)
nepc.c:257: `PRINT' undeclared (first use in this function)
nepc.c:288: `UMINUS' undeclared (first use in this function)
nepc.c:295: `PP' undeclared (first use in this function)
nepc.c:310: `SS' undeclared (first use in this function)
nepc.c:614: `AND' undeclared (first use in this function)
nepc.c:647: `OR' undeclared (first use in this function)
nepc.c:680: `GE' undeclared (first use in this function)
nepc.c:717: `LE' undeclared (first use in this function)
nepc.c:754: `NE' undeclared (first use in this function)
nepc.c:791: `EQ' undeclared (first use in this function)
nepc.c:828: `ACOS' undeclared (first use in this function)
nepc.c:837: `ASIN' undeclared (first use in this function)
nepc.c:845: `ATAN' undeclared (first use in this function)
nepc.c:853: `CEIL' undeclared (first use in this function)
nepc.c:861: `COS' undeclared (first use in this function)
nepc.c:876: `COSH' undeclared (first use in this function)
nepc.c:891: `EXP' undeclared (first use in this function)
nepc.c:906: `FABS' undeclared (first use in this function)
nepc.c:921: `FLOOR' undeclared (first use in this function)
nepc.c:936: `LOG' undeclared (first use in this function)
nepc.c:951: `LOG10' undeclared (first use in this function)
nepc.c:966: `SIN' undeclared (first use in this function)
nepc.c:981: `SINH' undeclared (first use in this function)
nepc.c:996: `SQRT' undeclared (first use in this function)
nepc.c:1011: `TAN' undeclared (first use in this function)
nepc.c:1026: `TANH' undeclared (first use in this function)
In file included from nepcmain.c:3:
nepc.y: At top level:
nepc.y:12: conflicting types for `YYSTYPE'
y.tab.h:53: previous declaration of `YYSTYPE'
y.tab.c:470: conflicting types for `yylval'
y.tab.h:54: previous declaration of `yylval'

复制代码

bookstack · 发表于 2006-3-17 22:19:49

看来大家对lex, yacc颇有兴趣啊。
推荐一个http://cs.gmu.edu/~white/CS540/
——这个老师教compiler大概有8,9年的历史了。

大家可以看看slides， assigment，example.

对optimization有兴趣的朋友可以看看：
http://cs.gmu.edu/~white/CS640/

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

Lex与Yacc学习实例(二) —— 解释器的编制

本帖子中包含更多资源

浏览过的版块