Yacc practice

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

1
2
%%
S: '(' S ')'|;

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" // from YACC , USE -d option
#include <stdlib.h>
extern int yylval;
%}
%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
[a-z] { yylval = yytext[0]; return NAME; }
[ \t\n] /* ignore whitespace */
. 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; /* value of evaluated expression */
int lvalue; /* index into symtbl for variable name */
}

%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; /* value of evaluated expression */
int lvalue; /* index into symtbl for variable name */
}

%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; } /* convert NUMBER token value to integer */
[ \t\n] ; /* ignore whitespace */
[a-z] { yylval.lvalue = yytext[0] - 'a'; return NAME; } /* convert NAME token into index */
. 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; /* value of evaluated expression */
int lvalue; /* index into symtbl for variable name */
}

%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 等函数。

1
2
a = 2.0
b = exp(a)

实现思路很简单,添加 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; /* int value of evaluated expression */
double dbl_rvalue; /* value of type double for evaluated expression */
int lvalue; /* index into symtbl for variable name */
}

%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; } /* convert token value to double */
[0-9]+ { yylval.rvalue = atoi(yytext); return T_NUMBER; } /* convert token value to integer */
[ \t] ; /* ignore whitespace */
[a-z] { yylval.lvalue = yytext[0] - 'a'; return T_NAME; } /* convert token into index */
\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


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!