Bison采用LALR(1)文法：
参考：https://blog.csdn.net/sirouni2003/article/details/400672
在Bison中,终结符也被称为符号类型(token type).
符号类型也可以由类似C语言标识符来表示.
根据惯例,这些标识符因改用大写子母表示以区分它和非终结符. 例如,INTEGER,INDENTIFIER,IF或者RETURN.
一个表示某语言的特定关键字的终结符应该由紧随该关键字之后的它的大写表示来命名. 终结符error保留用作错误恢复之用.
语义值
包括了记号的所有剩余信息.例如整数的数值,标识符的名称. (一个如’,'的记号只是一个标点,并不需要语义值.)
例如,一个分类为INTEGER的记号包含语义值4. 另一个也被分类为INTEGER的记号的语义值却是3989.
当一个语法规则表明INTEGER是允许的,任意的这些记号都是可接受的,因为它们都是INTEGER.
当一个分析器接受了记号,它会跟踪这个记号的语义值.
被存储在全局变量yylval中
为了更加实用,一个程序不仅仅要分析输入而且必须做的更多. 它应该可以在输入的基础上产生一些输出. 在Bison语法中,一个语法规则可以有一个包括多个C语句的动作(action). 分析器每次识别一个规则的匹配,相应的动作就会被执行. 获取这方面的更多信息,参阅 动作-Actions.
LALR(1)
在一些文法中,Bison标准的LALR(1)分析算法, 不能针对给定的输入应用一个确定的语法规则.
这就是说,Bison可能不能决定(在当前输入的基础上)应该使用两个可能的归约中的那一个,
或者不能决定到底应该应用一个归约还是先读取一些输入稍后再进行归约.
以上两种冲突分别被称为归约/归约(reduce/reduce)冲突(参阅归约/归约-Reduce/Reduce一章)和
**移进/归约(shift/reduce)冲突(参阅移进/归约-Shift/Reduce一章).
GLR:
有些时候, 为了使用一个很难被修改成LALR(1)文法的文法做为Bison的输入,
Bison需要使用通用的分析算法. 如果你在你的文件中加入了这样的声明%glr-parser(参阅语法大纲-Grammar Outline一章),
Bison会产通用的LR(GLR)分析器. 这些分析器(例如,在应用了先前所述的声明之后)
在处理那些不包含未解决的冲突的文法时, 采用与LALR(1)分析器一样的处理方式.
但是当面临未解决的移进/归约冲突和归约/归约冲突的时候, GLR分析器权宜地同时处理这两个可能,
即有效地克隆分析器自己以便于追踪这这两种可能性. 每一个克隆出来的分析器还可以再次被克隆,
这就保证在任意给定的时间,可以处理任意个可能的分析. 分析器逐步地进行分析,即所有的分析器它们进入到下一个输入之前,
都会消耗(归约)给定的输入符号. 每一个被克隆的分析器最终只有两个可能的归宿: 或者这个分析器因进入了一个分析错误而最终被销毁,
会这它和其它的分析器合并,因为它们把输入归约到了一个相同的符号集.
在有多个分析器并存的时刻,Bison只记录它们的语义动作而不是执行它们.
当一个分析器消失的时候,相应的语义动作记录也消失并且永远不会被执行.
当一个规约使得两个分析器等价而合并的时候, Bison会记录下它们两个的语义动作集.
每当最后两个分析器合并成为一个单独的分析器的时候, Bison执行所有未完成的动作.
这些动作既可能依靠语法规则的优先级被执行也可能均被Bison执行.
在执行完动作之后,Bison调用指定的用户定义求值函数来产生一个独立的合并值.
当使用平常的LALR(1)文法的时候,Bison会报告一个归约/归约冲突.
在冲突的时候,分析器在会众多选择中选取一个-随意地选择那个先声明的. 所以下面的正确输入不能被识别.
1
2type t = (a) .. b;
在Bison输入文件中, 加入这两个声明(在第一个`%%'之前)分析器可以将分析器编成一个GLR分析器, 并且Bison不会报告一个归约/归约冲突.
1
2
3%glr-parser %expect-rr 1
并不需要对语法本身进行修改. 分析器现通过上面的限制语法后,可以认识所有有效的声明. 用户实际上并不能查觉分析器的拆分.
这就是我们使用GLR而几乎没有坏处的例子. 即使像这样简单的例子,至少两个潜在的问题值得我们注意.
第一,我们总应该分析Bison的冲突报告来确定GLR拆分总发生在我们想要的时候.
一个GLR分析器的拆分会不经意地产生比LALR分析器在冲突中静态的错误选择 更加不明显的问题.
第二,要仔细考虑与词法分析器的互动(参阅语义记号-Sematic Tokens一章).
由于在拆分期间的分析器消耗记号时并不产生任何动作, 词法分析器并不能通过分析动作获得信息.
一些与词法分析器的互动在使用GLR来消除从词法分析器到语法分析器的复杂读时可以忽略. 你必须监察其余情况下时的正确性.
当GLR处理两条线都可以成功解释的路线时，要做的处理可能就不一样了。
位置-Locations
许多应用程序,如解释器和编译器,需要产生一些有用信息或者出错的信息.
为了达到这个目的,我们必须追踪每个语法结构的原文位置(textual location)或位置(location). Bison提供了追踪这些位置的机制.
每一个记号有一个语义值.类似地,每个记号也有一个位置, 对于所有记号和组来说,它们的位置的类型是相同的.
此外,输出的分析器也带有默认的存储位置的数据结构 (获取更多信息,参阅位置-Locations一章).
像语义值一样,位置可以在动作中使用特定的一套结构来访问. 在上面个的例子中,这个组的的位置是@$,而子表达式的位置是@1和@3.
当一个规则被匹配,一个默认的动作用于计算左侧的语义值(参阅动作-Actions一章). 类似地,另外一个默认的动作用于计算位置.
然而,这个默认动作对于对于大多数情况已经足够永, 即经常没有必要为每个规则描述@$应该是如何形成的.
当为一个给定的组建立一个新的位置的时候, 输出的分析器的默认行为是取第一个符号的开头和最后一个符号的末尾.
Bison的输出:分析器文件
当你运行Bison的时候,你需要给Bison一个语法文件做为其输入.
Bison的输出是一个分析这个语法文件描述的语言的C源代码文件.
这个文件叫做Bison分析器(Bison parse).
我们要记住Bison工具和Bison分析器是两个明显不同的程序:
Bison工具是一个以Bison分析器为输出的程序. 这个Bison分析器应是你程序的一部分.
Bison分析器的工作是依照语法规则组合记号–例如,
将标识符和操作符构建成表达式. 在组合的过程中它还要执行相应的语法规定的动作.
记号是来源于称为词法分析器(lexical analyzer)的程序.
你必须以某种形式提供词法分析器(如用C编写).
Bison分析器每当需要一个新的记号的时候就会调用词法分析器.
Bison分析器并不之道记号"中"有什么东西(即使它们的语义值可能反映这个).
典型的词法分析器靠分析字符来产生记号,但是Bison并不依靠这个.
获取更多细节,参阅 词法分析函数yylex-The Lexical Analyzer Function yylex.
Bison分析器文件是定义了名为yyparse并且实现了那个语法的函数的C代码.
这个函数并不能成为一个完成的C程序:你必须提供额外的一些函数.
- 其中之一是词法分析器.
- 另外的一个是一个分析器报告错误时调用的错误报告函数.
-
另外,一个完整的C程序必须以名为main的函数开头; 你必须提供这个函数.并且安排它调用yyparse.
否则分析器永远都不会运行. 参阅 分析器C语言接口-Parser C-Language Interface.
除了你编写的动作中的记号类型名称和符号以外 ,所有Bison分析器文件自己定义的符号都以yy'或者YY’开头.
这些符号包括了接口函数例如词法分析函数yylex,错误报告函数yyerror 和分析器函数yyparse.
这些符号也包括了许多内部目的的标识符. 所以你要在Bison语法文件中避免使用除了本手册定义的以外的以yy'或者YY’开头的C标识符.
在一些情况下,Bison分析器文件包含系统头文件. 在这中情况下,你的代码注意被这些文件保留的标识符. 在意些非GNU系统,<alloca.h>,<stddef.h>以及<stdlib.h> 被包含在内用于声明内存分配器及相关类型. 如果你定义YYDEBUG为非零值,其它的系统头文件也可能被包括进内. (参阅跟踪你的分析器-Tracing Your Parser一章)
使用Bison的流程-Stages in Using Bison
实际使用Bison设计语言的流程,从语法描述到编写一个编译器或者解释器,有5个步骤:
-
以Bison可识别的格式正式地描述语法.(参阅Bison语法文件一章) 对每一个语法规则,描述当这个规则被识别时相应的执行动作. 动作由C语句序列描述.
-
编写一个词法分析器处理输入并将记号传递给语法分析器. 词法分析器既可是手工编写的C代码(参阅词法分析函数yylex一章), 也可以由lex产生,但是lex的使用并未在这个手册中讨论.
-
编写一个调用Bison产生的分析器的控制函数.
-
编写错误报告函数.
-
将这些源代码转换成可执行程序,你需要按以下步骤进行.
复制代码1
2
3
4* 按语法运行Bison产生分析器. * 同其它源代码一样编译Bison输出的代码. * 链接目标文件以产生最终的产品.
Bison语法文件的整体布局
Bison工具的输入文件是以个Bison语法文件(Bison grammar file). 通常的Bison语法文件格式如下:
1
2
3
4
5
6
7
8
9
10
11
12%{ Prologue %} Bison declarations %% Grammar rules %% Epilogue `%%',`%{' 和`%}'是Bison在每个Bison语法文件中用于分隔部分的标点符号.
prologue可用来定义在动作中使用类型和变量.
你可以使用预处理器命令在那里来定义宏, 或者使用#include包含干这些事情的头文件.
你需要声在那里与许多要在语法规则的动总中使用的全局标识符一起
声明词法分析器yylex和错误打印程序yyerror.
Bison declarations声明了终结符和非终结符以及操作符的优先级和各种符号语义值的各种类型.
Grammar rules定义了如何从每一个非终结符的部分构建其整体的语法规则.
Epilogue可以包括任何你想使用的代码. 在Prologue中声明的函数经常定义在这里.
在简单的程序里,剩余的所有程序可以放在这里.
demo1 简单double计算器
代码：
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
78
79
80
81
82
83
84
85
86
87
88
89/* Reverse polish notation calculator. */ /* 逆波兰记号计算器 */ %{ #define YYSTYPE double #include <math.h> #include <ctype.h> #include <stdio.h> int yylex (void); void yyerror (char const *); %} %token NUM %% /* Grammar rules and actions follow. */ input: /* empty */ | input line ; line: 'n' | exp 'n' { printf ("t%.10gn", $1); } ; exp: NUM { $$ = $1; } | exp exp '+' { $$ = $1 + $2; } | exp exp '-' { $$ = $1 - $2; } | exp exp '*' { $$ = $1 * $2; } | exp exp '/' { $$ = $1 / $2; } /* Exponentiation */ | exp exp '^' { $$ = pow ($1, $2); } /* Unary minus */ | exp 'n' { $$ = -$1; } ; %% /* The lexical analyzer returns a double floating point number on the stack and the token NUM, or the numeric code of the character read if not a number. It skips all blanks and tabs, and returns 0 for end-of-input. */ /* 词法分析起在栈上返回一个双精度浮点数(注:指yylval)并且返回记号NUM, 或者返回不是数字的字符的数字码.它跳过所有的空白和制表符, 并且返回0作为输入的结束. */ int yylex (void) { int c; /* Skip white space. */ /* 处理空白. */ while ((c = getchar ()) == ' ' || c == 't') ; /* Process numbers. */ /* 处理数字 */ if (c == '.' || isdigit (c)) { ungetc (c, stdin); scanf ("%lf", &yylval); return NUM; } /* Return end-of-input. */ /* 返回输入结束 */ if (c == EOF) return 0; /* Return a single char. */ /* 返回一个单一字符 */ return c; } int main (void) { return yyparse (); } /* Called by yyparse on error. */ void yyerror (char const *s) { fprintf (stderr, "%sn", s); }
执行：
bison recalc.y
gcc rpcalc.tab.c -lm
1
2
3
4
5
6
7
8
9
10
11
12
13
14$ rpcalc 4 9 + 13 3 7 + 3 4 5 *+- -13 3 7 + 3 4 5 * + - n 注意负号操作符, `n' 13 5 6 / 4 n + -3.166666667 3 4 ^ 幂运算 81 ^D 文件结束标识符
demo2
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
78
79
80/* Infix notation calculator. */ /* 中缀符号计算器 */ %{ #define YYSTYPE double #include <math.h> #include <stdio.h> int yylex (void); void yyerror (char const *); %} /* Bison declarations. */ %token NUM %left '-' '+' %left '*' '/' %left NEG /* negation--unary minus */ /* 负号 */ %right '^' /* exponentiation */ /* 幂运算 */ %% /* The grammar follows. */ /* 下面是语法 */ input: /* empty */ | input line ; line: 'n' | exp 'n' { printf ("t%.10gn", $1); } ; exp: NUM { $$ = $1; } | exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | exp '*' exp { $$ = $1 * $3; } | exp '/' exp { $$ = $1 / $3; } | '-' exp %prec NEG { $$ = -$2; } | exp '^' exp { $$ = pow ($1, $3); } | '(' exp ')' { $$ = $2; } ; %% int yylex (void) { int c; /* Skip white space. */ /* 处理空白. */ while ((c = getchar ()) == ' ' || c == 't') ; /* Process numbers. */ /* 处理数字 */ if (c == '.' || isdigit (c)) { ungetc (c, stdin); scanf ("%lf", &yylval); return NUM; } /* Return end-of-input. */ /* 返回输入结束 */ if (c == EOF) return 0; /* Return a single char. */ /* 返回一个单一字符 */ return c; } int main (void) { return yyparse (); } /* Called by yyparse on error. */ void yyerror (char const *s) { fprintf (stderr, "%sn", s); }
执行：
bison calc.y
gcc calc.tab.c -lm
1
2
3
4
5
6
7
8$ calc 4 + 4.5 - (34/(8*3+-3)) 6.880952381 -56 + 2 -54 3 ^ 2 9
重点注意：
这段代码展示了两个重要的新特征.
在第二部分中(Bison declarations), %left声明了记号类型并且指明它们是左结合操作符.
%left和%right(右结合)的声明代替了%token.
%token是用来声明没有结合性的记号类型的. (这些记号(注:是指'+'',‘-’‘,'*'',’/‘’,`‘NEG’') 是原本并不用声明的单字符记号.我们声明它们的目的是指出它们的结合性.)
操作符优先级是由声明所在行的顺序决定的, 行号越大的操作符(在一页或者屏幕底端)具有越高的优先级. 因此,幂运算具有最高优先级,负号(NEG)其次, 接这是*'和/'等等. 参阅 操作符优先级-Operator Precedence.
另外一个重要的特征是在语法部分的负号操作符中使用了%prec. 语法中的%prec只是简单的告诉Bison规则`| ‘-’ exp’与NEG有相同的优先级–在前述的优先级规则中. 参阅 依赖上下文的优先级-Context-Dependent Precedence.
这个是要重点注意的，因为%prec是单独给某条规则进行赋值的！而不是仅仅用普通的依赖声明的符号优先级来执行
简单的错误恢复
修改为：
1
2
3
4
5line: '/n' | exp '/n' { printf ("/t%.10g/n", $1); } | error '/n' { yyerrok; } ;
这个添加的规则允许在语法错误发生的时候有简单的错误恢复动作. 如果一个读入一个无法求值的表达式, 这个错误会被识别成line的第三个规则并且分析会继续执行. (yyerror函数仍会被调用来打印它的信息).
执行这个动作的语句yyerrok是一个被Bison自动定义的宏. 它的含义是错误恢复已经完成(参阅错误恢复-Error Recovery一章).
我们应当注意到yyerror和yyerrok的区别, 它们的印刷都没有错误.
这种形式的错误恢复用于处理语法错误. 还有很多其它形式的错误;
例如,除数为0,这会产生一个通常致命的异常信号(an exception signal).
一个真正的计算器必须处理这种信号并且使用longjmp返回到main并且继续分析输入行;
它(注:真正的计算器)也可以丢弃剩余的输入行. 我们并不深入地讨论这个问题, 因为这与Bison程序无关.
demo3 带有位置追踪的计算器
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112/* Location tracking calculator. */ /* 位置追踪计算器 */ %{ #define YYSTYPE int #include <math.h> #include <stdio.h> int yylex (void); void yyerror (char const *); %} /* Bison declarations. */ /* Bison 声明 */ %token NUM %left '-' '+' %left '*' '/' %left NEG %right '^' %% /* The grammar follows. */ /* 下面是语法 */ input : /* empty */ | input line ; line : 'n' | exp 'n' { printf ("%dn", $1); } ; exp : NUM { $$ = $1; } | exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | exp '*' exp { $$ = $1 * $3; } | exp '/' exp { if ($3) $$ = $1 / $3; else { $$ = 1; fprintf (stderr, "%d.%d-%d.%d: division by zero", @3.first_line, @3.first_column, @3.last_line, @3.last_column); } } | '-' exp %prec NEG { $$ = -$2; } | exp '^' exp { $$ = pow ($1, $3); } | '(' exp ')' { $$ = $2; } ; %% /* 这里词法分析要记录位置信息！*/ int yylex (void) { int c; /* Skip white space. */ /* 跳过空白 */ while ((c = getchar ()) == ' ' || c == 't') ++yylloc.last_column; /* Step. */ yylloc.first_line = yylloc.last_line; yylloc.first_column = yylloc.last_column; /* Process numbers. */ /* 处理数字 */ if (isdigit (c)) { yylval = c - '0'; ++yylloc.last_column; while (isdigit (c = getchar ())) { ++yylloc.last_column; yylval = yylval * 10 + c - '0'; } ungetc (c, stdin); return NUM; } /* Return end-of-input. */ /* 返回输入结束 */ if (c == EOF) return 0; /* Return a single char, and update location. */ /* 返回一个单字符,并且更新位置 */ if (c == 'n') { ++yylloc.last_line; yylloc.last_column = 0; } else ++yylloc.last_column; return c; } int main (void) { yylloc.first_line = yylloc.last_line = 1; yylloc.first_column = yylloc.last_column = 0; return yyparse (); } /* Called by yyparse on error. */ void yyerror (char const *s) { fprintf (stderr, "%sn", s); }
重点：
- 这里值得注意的是添加了位置信息，使用的是Bison默认提供的yylloc。
- 该信息是由词法分析记录的
demo 4 多功能计算器
calc.h
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/* Function type. */ /* 函数类型 */ typedef double (*func_t) (double); /* Data type for links in the chain of symbols. */ /* 链表节点的数据类型 */ struct symrec { char *name; /* name of symbol */ /* 符号的名称 */ int type; /* type of symbol: either VAR or FNCT */ /* 符号的类型: VAR 或 FNCT */ union { double var; /* value of a VAR */ /* VAR 的值 */ func_t fnctptr; /* value of a FNCT */ /* FNCT 的值 */ } value; struct symrec *next; /* link field */ /* 指针域 */ }; typedef struct symrec symrec; /* The symbol table: a chain of `struct symrec'. */ /* 符号表: `struct symrec'的链表 */ extern symrec *sym_table; symrec *putsym (char const *, int); symrec *getsym (char const *); symrec * putsym (char const *sym_name, int sym_type) { symrec *ptr; ptr = (symrec *) malloc (sizeof (symrec)); ptr->name = (char *) malloc (strlen (sym_name) + 1); strcpy (ptr->name,sym_name); ptr->type = sym_type; ptr->value.var = 0; /* Set value to 0 even if fctn. */ /* 置0即是fctn */ ptr->next = (struct symrec *)sym_table; sym_table = ptr; return ptr; } symrec * getsym (char const *sym_name) { symrec *ptr; for (ptr = sym_table; ptr != (symrec *) 0; ptr = (symrec *)ptr->next) if (strcmp (ptr->name,sym_name) == 0) return ptr; return 0; }
mfcalc.y
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173%{ #include <math.h> /* For math functions, cos(), sin(), etc. */ /* 为了使用数学函数, cos(), sin(), 等等 */ #include <stdio.h> #include "calc.h" /* Contains definition of `symrec'. */ /* 包含了 `symrec'的定义 */ int yylex (void); void yyerror (char const *); %} /*%union声明了所有可能类型清单; 这是用来取代YYSTYPE的. 现在允许的类型是双精度(为了exp和NUM)和指向符号表目录项的指针. */ %union { double val; /* For returning numbers. */ /* 返回的数值 */ symrec *tptr; /* For returning symbol-table pointers. */ /* 返回的符号表指针 */ } %token <val> NUM /* Simple double precision number. */ /* 简单的双精度数值 */ %token <tptr> VAR FNCT /* Variable and Function. */ /* 变量和函数 */ %type <val> exp %right '=' %left '-' '+' %left '*' '/' %left NEG /* negation--unary minus */ /* 负号 */ %right '^' /* exponentiation */ /* 幂 */ %% /* The grammar follows. */ input: /* empty */ | input line ; line: 'n' | exp 'n' { printf ("t%.10gn", $1); } | error 'n' { yyerrok; } ; exp: NUM { $$ = $1; } | VAR { $$ = $1->value.var; } | VAR '=' exp { $$ = $3; $1->value.var = $3; } | FNCT '(' exp ')' { $$ = (*($1->value.fnctptr))($3); } | exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | exp '*' exp { $$ = $1 * $3; } | exp '/' exp { $$ = $1 / $3; } | '-' exp %prec NEG { $$ = -$2; } | exp '^' exp { $$ = pow ($1, $3); } | '(' exp ')' { $$ = $2; } ; /* End of grammar. */ %% #include <ctype.h> int yylex (void) { int c; /* Ignore white space, get first nonwhite character. */ /* 忽略空白,获取第一个非空白的字符 */ while ((c = getchar ()) == ' ' || c == 't'); if (c == EOF) return 0; /* Char starts a number => parse the number. */ /* 以数字开头 => 分析数字 */ if (c == '.' || isdigit (c)) { ungetc (c, stdin); scanf ("%lf", &yylval.val); return NUM; } /* Char starts an identifier => read the name. */ /* 以标识符开头 => 读取名称 */ if (isalpha (c)) { symrec *s; static char *symbuf = 0; static int length = 0; int i; /* Initially make the buffer long enough for a 40-character symbol name. */ /* 在开始的时候使缓冲区足够容纳40字符长的符号名称*/ if (length == 0) length = 40, symbuf = (char *)malloc (length + 1); i = 0; do { /* If buffer is full, make it bigger. */ /* 如果缓冲区已满,使它大一点 */ if (i == length) { length *= 2; symbuf = (char *) realloc (symbuf, length + 1); } /* Add this character to the buffer. */ /* 将这个字符加入缓冲区 */ symbuf[i++] = c; /* Get another character. */ /* 获取另外一个字符 */ c = getchar (); } while (isalnum (c)); ungetc (c, stdin); symbuf[i] = ''; s = getsym (symbuf); if (s == 0) s = putsym (symbuf, VAR); yylval.tptr = s; return s->type; } /* Any other character is a token by itself. */ /* 其余的字符是自己为记号的字符 */ return c; } /* Called by yyparse on error. */ /* 出错时被yyparse调用 */ void yyerror (char const *s) { printf ("%sn", s); } struct init { char const *fname; double (*fnct) (double); }; struct init const arith_fncts[] = { "sin", sin, "cos", cos, "atan", atan, "ln", log, "exp", exp, "sqrt", sqrt, 0, 0 }; /* The symbol table: a chain of `struct symrec'. */ /* 符号表: `struct symrec'链表 */ symrec *sym_table; /* Put arithmetic functions in table. */ /* 将数学函数放入符号表(注:保留字的实现方式) */ void init_table (void) { int i; symrec *ptr; for (i = 0; arith_fncts[i].fname != 0; i++) { ptr = putsym (arith_fncts[i].fname, FNCT); ptr->value.fnctptr = arith_fncts[i].fnct; } } int main (void) { init_table (); return yyparse (); }
执行:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15$ mfcalc pi = 3.141592653589 3.1415926536 sin(pi) 0.0000000000 alpha = beta1 = 2.3 2.3000000000 alpha 2.3000000000 ln(alpha) 0.8329091229 exp(ln(beta1)) 2.3000000000
重点：
- 语义值开始有不同的类型
- 由于语义值值现在可以有多种类型, 对每一个使用语义值的语法符号关联一个语义值类型是很必要的. 这些符号是NUM,VAR,FNCT,和exp. 它们的在声明的时候已经指明了语义值类型(在中括号之间).
- %union声明了所有可能类型清单; 这是用来取代YYSTYPE的.
- %type用来声明非终结符,就像%token用来声明符号类型(注:终结符)的一样. 我们之前并没有%type是因为非终结符经常在定义它们的规则中隐含地声明. 但是exp必须被明确地声明以便我们使用它的语义值类型.
- 提供了符号表的基础使用流程。
- 关注yylex是如何反馈符号，以及是如何设置语义值的
优化：
未定义的变量报错:
由于简单使用任何字符串都会自动创建一个VAR类型的变量，依据现在的逻辑添加思路：
- 添加一个属性isinit，然后在VAR ‘=’ exp 的语义动作中添加一isinit = true,然后在使用的时候进行判断。
步骤：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21.h添加一个属性： struct symrec { char *name; /* name of symbol */ /* 符号的名称 */ int type; /* type of symbol: either VAR or FNCT */ /* 符号的类型: VAR 或 FNCT */ char isinit; /* 判断是否赋初值，没有就是非法变量 */ union { double var; /* value of a VAR */ /* VAR 的值 */ func_t fnctptr; /* value of a FNCT */ /* FNCT 的值 */ } value; struct symrec *next; /* link field */ /* 指针域 */ }; .y添加逻辑： exp: NUM { $$ = $1; } | VAR { if($1->isinit == 0) {printf ("%s is not init !n", $1->name); YYERROR;} else $$ = $1->value.var; } | VAR '=' exp { $$ = $3; $1->value.var = $3; $1->isinit = 1; }
其他的方案目前还想不到。但是这个方案感觉是改动最小的。
注意这里使用了:
YYERROR的宏，可以在语义工作的文档中查看。
最后
以上就是孤独柠檬最近收集整理的关于bison进行语法分析学习记录Bison采用LALR(1)文法：使用Bison的流程-Stages in Using BisonBison语法文件的整体布局demo1 简单double计算器demo2demo3 带有位置追踪的计算器demo 4 多功能计算器的全部内容，更多相关bison进行语法分析学习记录Bison采用LALR(1)文法：使用Bison的流程-Stages内容请搜索靠谱客的其他文章。
发表评论 取消回复