Flex & Bison 实战：一个简单计算器

概述

本文以一个计算器的实现为例介绍 Flex & Bison 的使用。

词法分析

Flex 可帮助我们生成词法分析器。

代码：

calc.l

 1%%
 2"+"         { printf("PLUS\n"); }
 3"-"         { printf("MINUS\n"); }
 4"*"         { printf("TIMES\n"); }
 5"/"         { printf("DIVIDE\n"); }
 6"|"         { printf("ABS\n"); }
 7[0-9]+      { printf("NUMBER %s\n", yytext); }
 8\n          { printf("NEWLINE\n"); }
 9[ \t]       {}
10.           { printf("Mystery character %s\n", yytext); }
11%%

说明：

yytext：指向本次匹配的输入串

l 文件的结构是这样的：

声明部分
%%
翻译规则
%%
辅助性C语言例程

生成词法分析器：

flex calc.l

编译：

cc lex.yy.c -lfl

运行：

./a.out

效果：

image-20220404113139987

最简单的语法分析

上面生成的 Token 都是直接输出到控制台。为了与语法分析器交互，需要换一种方式。

calc.l 19:

 1%{
 2    #include<stdlib.h>
 3    void yyerror(char*);
 4    #include "calc.tab.h"  
 5%}
 6
 7%%
 8[0-9]+      {yylval=atoi(yytext); return NUMBER;}
 9[-+*/\n]   {return *yytext;}
10[ \t]       ;
11
12.    	    yyerror("Error");
13
14%%
15int yywrap(void)
16{
17  return 1;
18}

calc.y 31:

 1%token NUMBER
 2%left '+' '-' '*' '/'
 3
 4%{
 5    #include <stdio.h>
 6    #include <math.h>
 7    void yyerror(char *s);
 8    int yylex();    
 9%}
10
11%%
12    
13    prog: 
14        | prog expr '\n' { printf("= %d\n", $2); };
15    expr:
16        NUMBER {{ printf("read number %d\n", $$); }};
17        | expr '+' expr {{ $$ = $1 + $3; }}
18        | expr '-' expr {{ $$ = $1 - $3; }}
19        | expr '*' expr {{ $$ = $1 * $3; }}
20        | expr '/' expr {{ $$ = $1 / $3; }}
21        ;
22%%
23
24void yyerror(char *s) {
25    fprintf(stderr, "%s\n", s);
26}
27
28int main() {
29    yyparse();
30    return 0;
31}

可以看到，我们用 %token 可以声明词符。然后在 lex 文件中使用 #include "calc.tab.h" 可以引入这些声明。

编译：

Makefile 8:

1clean:
2	rm -f *.o *.out
3	rm *.tab.c *.tab.h *.yy.c *.yy.h
4
5calc: calc.l calc.y
6	bison -d calc.y
7	flex calc.l
8	cc -o $@ calc.tab.c lex.yy.c -lfl

make calc

运行：

./calc                                                root@hw-ecs-hk
1*2+3*4
read number 1
read number 2
read number 3
read number 4
= 20

我们发现算符是无结合顺序的。下面增加优先级

实现加减乘除的优先级

第一种方法最简单，使用 %left 指令：

1%left '+' '-'
2%left '*' '/'

image-20220404212628074

第二种方法，可以在修改规则实现优先级。

calc.y 33:

%token NUMBER
%left '+' '-' '*' '/'

%{
    #include <stdio.h>
    #include <math.h>
    void yyerror(char *s);
    int yylex();    
%}

%%
    
    prog: 
        | prog expr '\n' { printf("= %d\n", $2); };
    expr:
        expr '+' term { $$ = $1 + $3; }
        | expr '-' term { $$ = $1 - $3; }
        | term
    term:
        NUMBER {{ printf("read number %d\n", $$); }};
        | term '*' term { $$ = $1 * $3; }
        | term '/' term { $$ = $1 / $3; }        
        ;
%%

void yyerror(char *s) {
    fprintf(stderr, "%s\n", s);
}

int main() {
    yyparse();
    return 0;
}

实现括号指定运算顺序

下面实现计算 (1+2)*3 这样带括号的表达式：

calc.l 19:

 1%{
 2    #include<stdlib.h>
 3    void yyerror(char*);
 4    #include "calc.tab.h"  
 5%}
 6
 7%%
 8[0-9]+      {yylval=atoi(yytext); return NUMBER;}
 9[-+*/()\n]   {return *yytext;}
10[ \t]       ;
11
12.    	    yyerror("Error");
13
14%%
15int yywrap(void)
16{
17  return 1;
18}

calc.y 37:

 1%token NUMBER
 2%left '+' '-' '*' '/'
 3
 4%{
 5    #include <stdio.h>
 6    #include <math.h>
 7    void yyerror(char *s);
 8    int yylex();    
 9%}
10
11%%
12    
13    prog: 
14        | prog expr '\n' { printf("= %d\n", $2); };
15    expr:
16        expr '+' term { $$ = $1 + $3; }
17        | expr '-' term { $$ = $1 - $3; }
18        | term
19    term:
20        | term '*' factor { $$ = $1 * $3; }
21        | term '/' factor { $$ = $1 / $3; }        
22        | factor
23        ;
24    factor:
25        NUMBER {{ printf("read number %d\n", $$); }};
26        | '(' expr ')' { $$ = $2; }
27        ;
28%%
29
30void yyerror(char *s) {
31    fprintf(stderr, "%s\n", s);
32}
33
34int main() {
35    yyparse();
36    return 0;
37}

效果：

image-20220404213809951

实现绝对值和负数

将 | 添加到 token 富豪中。

calc.y 39:

 1%token NUMBER
 2%left '+' '-' '*' '/'
 3
 4%{
 5    #include <stdio.h>
 6    #include <math.h>
 7    void yyerror(char *s);
 8    int yylex();    
 9%}
10
11%%
12    
13    prog: 
14        | prog expr '\n' { printf("= %d\n", $2); };
15    expr:
16        expr '+' term { $$ = $1 + $3; }
17        | expr '-' term { $$ = $1 - $3; }
18        | term
19    term:
20        term '*' factor { $$ = $1 * $3; }
21        | term '/' factor { $$ = $1 / $3; }        
22        | factor
23        ;
24    factor:
25        NUMBER {{ printf("read number %d\n", $$); }};
26        | '-' factor { $$ = -$2; }        
27        | '(' expr ')' { $$ = $2; }
28        | '|' expr '|' { $$ = $2>0?$2:-$2; }
29        ;
30%%
31
32void yyerror(char *s) {
33    fprintf(stderr, "%s\n", s);
34}
35
36int main() {
37    yyparse();
38    return 0;
39}

实现乘方

需要引入 math 库，因此：

Makefile 5:

1
2calc: calc.l calc.y
3	bison -d calc.y
4	flex calc.l
5	cc -o $@ calc.tab.c lex.yy.c -lfl -lm
6
7clean:
8	-rm -f *.o *.out
9	-rm *.tab.c *.tab.h *.yy.c *.yy.h

calc.y 40:

 1%token NUMBER
 2%left '+' '-' '*' '/'
 3
 4%{
 5    #include <stdio.h>
 6    #include <math.h>
 7    void yyerror(char *s);
 8    int yylex();    
 9%}
10
11%%
12    
13    prog: 
14        | prog expr '\n' { printf("= %d\n", $2); };
15    expr:
16        expr '+' term { $$ = $1 + $3; }
17        | expr '-' term { $$ = $1 - $3; }
18        | term
19    term:
20        | term '*' '*' factor { $$ = pow($1, $4); }
21        | term '*' factor { $$ = $1 * $3; }
22        | term '/' factor { $$ = $1 / $3; }        
23        | factor
24        ;
25    factor:
26        NUMBER {{ printf("read number %d\n", $$); }};
27        | '-' factor { $$ = -$2; }        
28        | '(' expr ')' { $$ = $2; }
29        | '|' expr '|' { $$ = $2>0?$2:-$2; }
30        ;
31%%
32
33void yyerror(char *s) {
34    fprintf(stderr, "%s\n", s);
35}
36
37int main() {
38    yyparse();
39    return 0;
40}

效果：

image-20220404215856400

支持小数

这里需要注意的是，Flex 的规则表达式和常用的 Perl 格式不一样。参阅 Flex Regular Expressions (aau.dk)

calc.l 22:

 1%{
 2    #define YYSTYPE double
 3
 4    #include<stdlib.h>
 5    void yyerror(char*);
 6    #include "calc.tab.h"
 7
 8%}
 9
10%%
11-?([0-9]+|[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?)        {yylval = atof(yytext); return NUMBER;}
12[-+*/()|\n]   {return *yytext;}
13[ \t]       ;
14
15.    	    yyerror("Error");
16
17%%
18int yywrap(void)
19{
20  return 1;
21}

正则表达式太长了怎么办？可以用别名：

calc.l 24:

 1%{
 2    #define YYSTYPE double
 3
 4    #include<stdlib.h>
 5    void yyerror(char*);
 6    #include "calc.tab.h"
 7
 8%}
 9
10number        -?([0-9]+|[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?)
11
12%%
13{number}      {yylval = atof(yytext); return NUMBER;}
14[-+*/()\|\n]  {return *yytext;}
15[ \t]       ;
16
17.    	    yyerror("Error");
18
19%%
20int yywrap(void)
21{
22  return 1;
23}

calc.y 41:

 1%token NUMBER
 2%left '+' '-' '*' '/'
 3
 4%{
 5    #define YYSTYPE double
 6    #include <stdio.h>
 7    #include <math.h>
 8    void yyerror(char *s);
 9    int yylex();    
10%}
11
12%%
13    
14    prog: 
15        | prog expr '\n' { printf("= %lf\n", $2); };
16    expr:
17        expr '+' term { $$ = $1 + $3; }
18        | expr '-' term { $$ = $1 - $3; }
19        | term
20    term:
21        term '*' '*' factor { $$ = pow($1, $4); }
22        | term '*' factor { $$ = $1 * $3; }
23        | term '/' factor { $$ = $1 / $3; }        
24        | factor
25        ;
26    factor:
27        NUMBER {{ printf("read number %lf\n", $$); }};
28        | '-' factor { $$ = -$2; }        
29        | '(' expr ')' { $$ = $2; }
30        | '|' expr '|' { $$ = $2>0?$2:-$2; }
31        ;
32%%
33
34void yyerror(char *s) {
35    fprintf(stderr, "%s\n", s);
36}
37
38int main() {
39    yyparse();
40    return 0;
41}

Makefile 10:

1
2calc: calc.l calc.y
3	bison -d calc.y -v
4	flex calc.l
5	cc -o calc.out calc.tab.c lex.yy.c -lfl -lm
6
7clean:
8	-rm -f *.o *.out*
9	-rm *.tab.c *.tab.h *.yy.c *.yy.h

效果

image-20220404224949402

测试

测试发现，上面的代码有问题。-1-1 报错。解决方法：修改 number 的 token 定义：

calc.l 10:

1number        ([0-9]+|[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?)

至此，一个简单的计算器完成了。

你可以在这里找到源码。

最近发布

要查看全部文章，请点击右上角“归档”

随机文章