小白说编译原理-3-yacc基本用法前提说明yacc规则计算器解释巧妙的地方更新版本支持浮点数修改的地方

165 阅读 0 评论 109 点赞

我是靠谱客的博主真实荷花，这篇文章主要介绍小白说编译原理-3-yacc基本用法前提说明yacc规则计算器解释巧妙的地方更新版本支持浮点数修改的地方，现在分享给大家，希望可以做个参考。

前言

这个编译原理是一个系列，系列地址为： https://blog.csdn.net/lpstudy/article/category/937055
考虑到很多小伙伴咨询代码的问题，现把链接发出来：https://github.com/lpstudy/compile
这个链接里面具有这个系列所有的VS工程和代码，工程是按照系列中的一个教程环境配置6来配置的，不过lib我好像没有上传到github。
如果大家发现任何问题，可以在github或者csdn，我有空的时候完善一下，争取做到下载github工程即可跑。

前提说明

前面lex的例子说明了可以通过定义正规式的方式，实现一个词法分析器。它主要是通过lex编译器将用户定义的正规式以及相应的action编译成对应的c++代码，交给c++编译器生成可执行程序exe。
同样的，应该可以定义语法规则，并由语法编译器将语法规则以及action编译成相应的c++代码，并执行。
这就是我们这节要说明的yacc。

yacc规则

声明部分
C++头文件，函数声明
文法记号的声明(类似于lex中词法token的声明)，例如%token DIGIT
%%
翻译规则
%%
翻译规则主要文法产生式和对应的动作组成。
例如 expr : expr ‘+’ term {$$ = $1 + $2}
其他c++语言的代码

#yacc示例，简单计算器
%{

复制代码

%}
%name yacc
// class definition
{
// place any extra class members here
virtual int yygettoken();
}
// constructor
{
// place any extra initialisation code here
}
// destructor
{
// place any extra cleanup code here
}
// place any declarations here
%include {
#ifndef YYSTYPE
#define YYSTYPE double
#endif
}
%%
lines : lines expr 'n' {printf("%fn", $2);}
| lines 'n'
|//empty line
;
expr : expr '+' term {$$ = $1 + $3;}
| expr '-' term {$$ = $1 - $3;}
| term
;
term : term '*' factor {$$ = $1 * $3;}
| term '/' factor {$$ = $1 / $3;}
| factor {$$=$1;}
;
factor : '(' expr ')'
{$$=$2;}
| DIGIT
;
DIGIT	:	'0'
{ $$ = 0.0; }
|	'1'
{ $$ = 1.0; }
|	'2'
{ $$ = 2.0; }
|	'3'
{ $$ = 3.0; }
|	'4'
{ $$ = 4.0; }
|	'5'
{ $$ = 5.0; }
|	'6'
{ $$ = 6.0; }
|	'7'
{ $$ = 7.0; }
|	'8'
{ $$ = 8.0; }
|	'9'
{ $$ = 9.0; }
;
%%
int YYPARSERNAME::yygettoken()
{
return getchar();
}
int main()
{
//create a lexer, and call the lex function.
//it will read from stdin and parser the tokens.
int n = 1;
YYPARSERNAME parser;
if (parser.yycreate())
{
n = parser.yyparse();
}
return n;
}

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
66
67
68
69
70
71
72
73
74
75
76
77
%}
%name yacc
// class definition
{
// place any extra class members here
virtual int yygettoken();
}
// constructor
{
// place any extra initialisation code here
}
// destructor
{
// place any extra cleanup code here
}
// place any declarations here
%include {
#ifndef YYSTYPE
#define YYSTYPE double
#endif
}
%%
lines : lines expr 'n' {printf("%fn", $2);}
| lines 'n'
|//empty line
;
expr : expr '+' term {$$ = $1 + $3;}
| expr '-' term {$$ = $1 - $3;}
| term
;
term : term '*' factor {$$ = $1 * $3;}
| term '/' factor {$$ = $1 / $3;}
| factor {$$=$1;}
;
factor : '(' expr ')'
{$$=$2;}
| DIGIT
;
DIGIT	:	'0'
{ $$ = 0.0; }
|	'1'
{ $$ = 1.0; }
|	'2'
{ $$ = 2.0; }
|	'3'
{ $$ = 3.0; }
|	'4'
{ $$ = 4.0; }
|	'5'
{ $$ = 5.0; }
|	'6'
{ $$ = 6.0; }
|	'7'
{ $$ = 7.0; }
|	'8'
{ $$ = 8.0; }
|	'9'
{ $$ = 9.0; }
;
%%
int YYPARSERNAME::yygettoken()
{
return getchar();
}
int main()
{
//create a lexer, and call the lex function.
//it will read from stdin and parser the tokens.
int n = 1;
YYPARSERNAME parser;
if (parser.yycreate())
{
n = parser.yyparse();
}
return n;
}

计算器解释

添加gettoken函数
virtual int yygettoken();
expr : expr ‘+’ term {$$ = $1 + $3;}
计算加法，$$表示当返回值，$1表示第一个参数，$3表示第三个参数
main
创建parser语法分析器，调用gettoken分析，即可。

巧妙的地方

1，支持多行
多行的关键在于lines的表示，lines既可以表示为空，又可以表示为lines expr ‘n’
2，支持算符优先级
term和factor的使用，先使用term，再使用factor
3，支持括号
最终的factor因子的表示，既可以表示单个数字，还可以表示(expr)。
3，只支持单个数字的加减乘除
这是由于对于DIGIT的解释只支持单个数字

更新版本支持浮点数

复制代码

%{
#include <stdio.h>
%}
%name yacc
// class definition
{
// place any extra class members here
virtual int yygettoken();
double yyvalue;
}
// constructor
{
// place any extra initialisation code here
}
// destructor
{
// place any extra cleanup code here
}
// place any declarations here
%include {
#ifndef YYSTYPE
#define YYSTYPE double
#endif
}
%token NUMBER
%%
lines : lines expr 'n' {printf("%fn", $2);}
| lines 'n'
|//empty line
;
expr : expr '+' term {$$ = $1 + $3;}
| expr '-' term {$$ = $1 - $3;}
| term
;
term : term '*' factor {$$ = $1 * $3;}
| term '/' factor {$$ = $1 / $3;}
| factor {$$=$1;}
;
factor : '(' expr ')'
{$$=$2;}
| NUMBER {$$=yyvalue;}
;
%%
int YYPARSERNAME::yygettoken()
{
int c;
double value;
while((c = getchar())
== ' ');//jump the empty
//here not the blank
if(isdigit(c) || c == '.'){
ungetc(c, stdin);
cin>>value;
yyvalue = value;
return NUMBER;
}
return c;
}
int main()
{
//create a lexer, and call the lex function.
//it will read from stdin and parser the tokens.
int n = 1;
YYPARSERNAME parser;
if (parser.yycreate())
{
n = parser.yyparse();
}
return n;
}

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
66
67
68
69
70
71
%{
#include <stdio.h>
%}
%name yacc
// class definition
{
// place any extra class members here
virtual int yygettoken();
double yyvalue;
}
// constructor
{
// place any extra initialisation code here
}
// destructor
{
// place any extra cleanup code here
}
// place any declarations here
%include {
#ifndef YYSTYPE
#define YYSTYPE double
#endif
}
%token NUMBER
%%
lines : lines expr 'n' {printf("%fn", $2);}
| lines 'n'
|//empty line
;
expr : expr '+' term {$$ = $1 + $3;}
| expr '-' term {$$ = $1 - $3;}
| term
;
term : term '*' factor {$$ = $1 * $3;}
| term '/' factor {$$ = $1 / $3;}
| factor {$$=$1;}
;
factor : '(' expr ')'
{$$=$2;}
| NUMBER {$$=yyvalue;}
;
%%
int YYPARSERNAME::yygettoken()
{
int c;
double value;
while((c = getchar())
== ' ');//jump the empty
//here not the blank
if(isdigit(c) || c == '.'){
ungetc(c, stdin);
cin>>value;
yyvalue = value;
return NUMBER;
}
return c;
}
int main()
{
//create a lexer, and call the lex function.
//it will read from stdin and parser the tokens.
int n = 1;
YYPARSERNAME parser;
if (parser.yycreate())
{
n = parser.yyparse();
}
return n;
}

修改的地方

删除了DIGIT采用语法分析器进行的表达，过去gettoken直接返回char型字符，由DIGIT或者+，-等进行语法翻译。现在使用一个token标记NUMBER，它代表一个数字。这个NUMBER标记是由对应的词法分析gettoken进行返回的。
gettoken中，如果遇到数字，则使用cin方式读取double型变量，保存到变量yylvalue中，这样当语法分析的过程中，遇到number，将yylvalue赋值给当前返回即可，即可以读取到浮点值。
为了更好的适应性，词法分析中还进行了跳过空格的操作，对于非数字不进行解析，直接返回。

本人lpstudy，转载请注明出处： http://blog.csdn.net/lpstudy/article/details/51225953