Yacc practice Yacc (Yet Another Compiler Compiler) 是一个用于生成语法分析器C代码的程序,一般配合 lex 使用。
bison 是 GNU 版本的 yacc 实现。
识别嵌套括号 lex 代码: parens.lex
1 2 3 4 [ \t]+ { } . return yytext[0 ];
yacc 代码: parens.y
Backus-Naur notation
1 S -> "(" S ")" | <epsilon >
表示空字符。
编译方法
1 2 3 bison -oparens.tab.c -d parens.y flex -oparens.lex.c parens.lex gcc -w -o ./parens parens.tab.c parens.lex.c -ly -ll
Yacc actions Yacc 和 Lex 一样,Lex 可以为每一个 regexp 指定 action, yacc 亦可为每一个规则指定 action
1 2 3 4 %% S: '(' S ')' { $ $ = $ 2 +1 ; printf("%d\n" , $ $ ); } | { $ $ = 0 ; } ;
$$
为左侧 Token 创建的值,用来传递给 parse tree$1
右侧第一个 Token 对应的值$2
右侧第二个 Token 对应的值, 上面代码中Token S 在 parse tree 中对应的值$3
右侧第三个 Token 对应的值
上面的程序输入 ((())) 输出如下
1 2 3 4 5 ➜ yacc-practice git:(master) ✗ ./parens ((())) 1 2 3
Simple Expression Interpreter 简单的表达式求值例子,只有加减赋值,实现解析 a=1+2+3 。
yacc 使用 %token 关键字定义 Token 常量,yacc 生成 Token 对应的头文件,lex 可引用 yacc 生成的头文件实现共同分析。
lex 通过 yylval 变量给 yacc 传递必要的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 %{ #include <stdio.h> extern int yylex (void ) ;extern int yyerror (char *) ; %} %token NAME NUMBER %% statement: NAME '=' expression { printf ("%c = %d\n" , $1 , $3 ); } | expression { printf ("%d\n" , $1 ); } ; expression: expression '+' NUMBER { $$ = $1 + $3 ; } | expression '-' NUMBER { $$ = $1 - $3 ; } | NUMBER { $$ = $1 ; } ; %%
lex 文件
1 2 3 4 5 6 7 8 9 10 11 %{#include "simple-expr.tab.h" #include <stdlib.h> extern int yylval; %} %% [0 -9 ]+ { yylval = atoi(yytext); return NUMBER; } [a-z] { yylval = yytext[0 ]; return NAME; } [ \t\n] . return yytext[0 ]; %%
编译(bison 是 GNU 版本的 YACC 实现,flex 是 GNU 版本的 lex 实现)
1 2 3 4 5 bison -osimple-expr .tab.c -d simple-expr .y flex -osimple-expr .lex.c simple-expr .lex cc -o ./simple-expr simple-expr .tab.c simple-expr .lex.c -ly -lfl echo "a=2+3+5" | ./simple-expr
bison -d 参数指定要输出 simple-expr.tab.h 文件,这个文件包含了必要的定义,可以给 lex 使用,比如 token 的定义。
simple-varexpr 上一个例子只求值没有赋值,这个例子是给变量赋值。
yacc 中数据类型的定义方法如下:
%union 可以改变 yylval 的数据类型。 yylval 默认类型是 int。用 %union 可以将不同类型聚合在一起。
%type 可以为非终结符的附加数据定义数据类型,只能是 %union 中定义的数据类型。
例如 yacc 中 %union 和 %type 定义如下
1 2 3 4 5 6 7 8 %union { int rvalue; int lvalue; } %token <rvalue> NUMBER %token <lvalue> NAME %type <rvalue> expression
非终结符 NUMBER 的类型为 rvalue
非终结符 NAME 的类型为 lvalue
非终结符 expression 的类型为 rvalue
lex 中对 NUMBER 和 NAME 解析赋值方法:yylval.rvalue, yylval.lvalue
varexpr 完整 yacc 代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 %{#include <stdio.h> #include <stdbool.h> int symtbl[26 ];bool issym[26 ];int yylex(void );int yyerror(char *); %} %union { int rvalue; int lvalue; } %token <rvalue> NUMBER %token <lvalue> NAME %type <rvalue> expression %%statement : NAME '=' expression { symtbl[$1 ] = $3 ; issym[$1 ] = true ; } | expression { printf("%d\n", $1 ); } ; expression: expression '+' NUMBER { $$ = $1 + $3 ; } | expression '-' NUMBER { $$ = $1 - $3 ; } | NUMBER { $$ = $1 ; } ;%%
symtbl 用于保存对应符号的值,issym 用于记录对应符号是否定义。
lex 代码如下
1 2 3 4 5 6 7 8 9 10 11 %{#include "simple-varexpr.tab.h" #include <math.h> %} %% [0 -9 ]+ { yylval.rvalue = atoi(yytext); return NUMBER; } [ \t\n] ; [a-z] { yylval.lvalue = yytext[0 ] - 'a' ; return NAME; } . return yytext[0 ]; %%
非终结符 NUMBER 的类型是 rvalue,使用 yylval.rvalue 对解析树赋值。
非终结符 NAME 的类型是 lvalue, 使用 yylval.lvalue 对解析树赋值。
进一步实现 varexpr 上面的代码只实现了单行对变量赋值,如何进一步实现多行赋值?如何实现变量引用?实现下面这种输入的解析。
1 echo "a=10\nb=a+10" | ./simple-varexpr
实现思路 多行 添加一条递归规则:
statementList: statement|statementList statement;
也可以这样写:
1 2 3 statement_list : statement '\n' statement_list | ;
符号计算 添加一条 realNum 规则用来处理值与 NAME,如果是 NAME 则判断是否已经定义。hhh 处理方法可能有点沙雕。
1 2 3 4 5 6 7 8 realNum: NUMBER { $$ = $1 ; } | NAME { if (!issym[$1 ]){ printf ("Undefined symbol:%c \n" , 'a' + $1 ); }else { $$ = symtbl[$1 ]; } }
完整的 yacc 代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 %{#include <stdio.h> #include <stdbool.h> int symtbl[26 ];bool issym[26 ];int yylex (void ) ;int yyerror (char *) ; %} %union { int rvalue; int lvalue; } %token <rvalue> NUMBER %token <lvalue> NAME %type <rvalue> expression %type <rvalue> realNum %% statementList: statement|statementList statement; statement: NAME '=' expression { symtbl[$1 ] = $3 ; issym[$1 ] = true ; printf ("%c = %d\n" , $1 + 'a' , $3 ); } | expression { printf ("%d\n" , $1 ); } ; expression: expression '+' realNum { $$ = $1 + $3 ;} | expression '-' realNum { $$ = $1 - $3 ; } | realNum ; realNum: NUMBER { $$ = $1 ; } | NAME { if (!issym[$1 ]){ printf ("Undefined symbol:%c \n" , 'a' + $1 ); }else { $$ = symtbl[$1 ]; } } %%
Adding Functions to your Expression Interpreter 实现 exp, sqrt, log 等函数。
实现思路很简单,添加 exp, sqrt, log 对应的 token, 语法分析阶段添加对应的规则。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 %{#include "exprdefs.h" #include <cstdlib> #include <cstdio> #include <cmath> int yylex (void ) ;int yyerror (char *) ; using namespace std ; double symtbl[26 ]; bool issym[26 ]; %} %union { int rvalue; double dbl_rvalue; int lvalue; } %token <dbl_rvalue> T_DOUBLE %token <rvalue> T_NUMBER %token <lvalue> T_NAME %token T_EXP T_SQRT T_LOG %type <dbl_rvalue> expression %% statement_list : statement '\n' statement_list | ; statement: T_NAME '=' expression { symtbl[$1 ] = $3 ; issym[$1 ] = true ; } | expression { printf ("%lf\n" , $1 ); } ; expression: expression '+' T_NUMBER { $$ = $1 + $3 ; } | expression '-' T_NUMBER { $$ = $1 - $3 ; } | expression '+' T_DOUBLE { $$ = $1 + $3 ; } | expression '-' T_DOUBLE { $$ = $1 - $3 ; } | expression '+' T_NAME { if (issym[$3 ]) { $$ = $1 + symtbl[$3 ]; } else { fprintf (stderr , "Error: variable %c not previously defined\n" , $3 +'a' ); exit (1 ); } } | expression '-' T_NAME { if (issym[$3 ]) { $$ = $1 - symtbl[$3 ]; } else { fprintf (stderr , "Error: variable %c not previously defined\n" , $3 +'a' ); exit (1 ); } } | T_NUMBER { $$ = $1 ; } | T_DOUBLE { $$ = $1 ; } | T_NAME { if (issym[$1 ]) { $$ = symtbl[$1 ]; } else { fprintf (stderr , "Error: variable %c not previously defined\n" , $1 +'a' ); exit (1 ); } } | T_EXP '(' expression ')' { $$ = exp ($3 ); } | T_SQRT '(' expression ')' { $$ = sqrt ($3 ); } | T_LOG '(' expression ')' { $$ = log ($3 ); } ; %%
lex 代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 %{#include "exprdefs.h" #include "expr-interpreter.tab.h" #include <cmath> #include <cstdlib> using namespace std ; extern double symtbl[26 ]; %} %%exp { return T_EXP; }sqrt { return T_SQRT; }log { return T_LOG; } [0 -9 ]*\.[0 -9 ]+ { yylval.dbl_rvalue = atof(yytext); return T_DOUBLE; } [0 -9 ]+ { yylval.rvalue = atoi(yytext); return T_NUMBER; } [ \t] ; [a-z] { yylval.lvalue = yytext[0 ] - 'a' ; return T_NAME; } \n | . return yytext[0 ]; %%
实现优先级和结合性 参考文章:https://www.epaperpress.com/lexandyacc/pry2.html
添加运算符 * /
yacc 使用 %left (%right 右结合) 指定运算符优先级
1 2 3 4 %left '+' '-' %left '*' '/' %left UMINUS
改写规则如下
1 2 3 4 5 6 7 8 expression:realNum | expression '+' expression { $$ = $1 + $3 ; } | expression '-' expression { $$ = $1 - $3 ; } | expression '*' expression { $$ = $1 * $3 ; } | expression '/' expression { $$ = $1 / $3 ; } | '-' expression %prec UMINUS { $$ = -$2 ; } | '(' expression ')' { $$ = $2 ; } ;
注意一元运算符比较特殊
1 2 3 %left UMINUS .....'-' expression %prec UMINUS { $$ = -$2; }
参考资料 http://anoopsarkar.github.io/compilers-class/yacc-practice.html
https://www.jianshu.com/p/1fe5a61fd9dc
https://stackoverflow.com/questions/1853204/yylval-and-union
https://www.epaperpress.com/lexandyacc/calc2.html