2.2 试做一个计算器
向不了解yacc/lex的人介绍其功能的话，与其一上来就举“用yacc/lex制作编程语言”的例子，不如先从一些简单的例子讲起比较好。所以我们以一个简单的“计算器”为例做介绍。
将计算器作为yacc/lex的示例实在有些老套，但是又很实用。Windows都会预装一个带有图形界面的计算器软件，仔细想来，PC上明明有好用的键盘，却还要用鼠标去一个一个点计算器上的按钮未免有些傻
。正因为Windows的计算器不好用，所以有很多人会选择使用普通的计算器。可明明眼前就摆着高性能的电脑，偏要用买来的计算器，同样也显得很奇怪，更不要说还有“附带计算器功能的鼠标垫”这种创意产品，就更加本末倒置了。无论是Windows自带的计算器，还是从日杂店买来的计算器，都从上面看不到运算符号的优先顺序，也无法直接计算带括号的式子（因为看不到前一个输入的值）。几十个数值求和时，你会不会担心万一中间输错了该怎么办？我经常会。
而我们要制作的计算器，会通过命令行方式启动，可以通过键盘输入整个算式，然后直接显示计算结果。因此可以直观地看到运算的优先顺序，比如输入
1 + 2 ＊ 3
会得到结果7而不是9。因为能看到整个算式，所以还可以很容易地检查有没有输错。
计算器的指令名为mycalc。一个实际运行的例子是这样的（%是命令提示符）：
虽然只用了整数，却输出“3.000000”这样的结果，这是因为mycalc在内部完全使用double进行运算。
2.2.1 lex
lex是自动生成词法分析器的工具，通过输入扩展名为．l的文件，输出词法分析器的C语言代码。而flex则是增强版的lex，而且是免费的。
词法分析器是将输入的字符串分割为记号的程序，因此必须首先定义mycalc所用到的记号。
mycalc所用到的记号包括下列项目：
● 运算符。在mycalc中可以使用四则运算，即 +、 -、 ＊、 /。
● 整数。如123等。
● 实数。如123.456等。
● 换行符。一个算式输入后，接着输入换行符就会执行计算，因此这里的换行符也应当设置为记号。
在lex中，使用正则表达式定义记号。
为mycalc所编写的输入文件mycalc.l如代码清单2-1所示。
代码清单2-1 mycalc.l
1: %{
2: #include <stdio.h＞
3: #include "y.tab.h"
4：
5: int
6: yywrap（void）
7: {
8: return 1;
9: }
10: %}
11: %%
12: "+" return ADD;
13: "-" return SUB;
14: "＊" return MUL;
15: "/" return DIV;
16: "\n" return CR;
17:（[1-9][0-9]＊）|0|（[0-9]+\.[0-9]+）{
18: double temp;
19: sscanf（yytext, "%lf", &temp）;
20: yylval.double_value = temp;
21: return DOUBLE_LITERAL;
22: }
23: [ \t] ;
24: . {
25: fprintf（stderr, "lexical error.\n"）;
26: exit（1）;
27: }
28: %%
代码第11行为 %%，此行之前的部分叫作定义区块。在定义区块内，可以定义初始状态或者为正则表达式命名（即使不知道正则表达式的具体内容也可以命名）等。在本例中放置了一些C代码。
第2行至第9行，使用 %{和 %}包裹的部分，是想让生成的词法分析器将这部分代码原样输出。后续程序所需的头文件 #include等都包含在这里，比如第三行用 #include包含进来的y.tab.h头文件，就是之后yacc自动生成的头文件。下面的ADD、 SUB、 MUL、 DIV、 CR、 DOUBLE_LITERAL等都是在y.tab.h中用 #define定义的宏，其原始出处则定义于mycalc.y文件中（详见2.2.3节）。这些宏将记号的种类区分开来。顺便附上表2-1说明记号的具体含义。
表2-1 记号及其含义
第5行到第9行定义了一个名为yywrap（）的函数。如果没有这个函数的话，就必须手动链接lex的库文件，在不同环境下编译时比较麻烦，因此最好写上。本书不会再对这个函数做深入说明，简单知道其作用，直接使用就可以了。
第12行到27行是规则区块。读了代码就能明白，这一部分是使用正则表达式去描述记号。
在规则区块中遵循这样的书写方式：一个正则表达式的后面紧跟若干个空格，后接C代码。如果输入的字符串匹配正则表达式，则执行后面的C代码。这里的C代码部分称为动作（action）。
在第12～16行中，会找到四则运算符以及换行符，然后通过return返回其特征符。所谓特征符，就是上文所述在y.tab.h中用 #define定义、用来区别记号种类的代号。
之前提到了这么多次“记号”，其实我们所说的记号是一个总称，包含三部分含义，分别是：
1．记号的种类
比如说计算器中的123.456这个记号，这个记号的种类是一个实数（DOUBLE_LITERAL）。
2．记号的原始字符
一个记号会包含输入的原始字符，比如123.456这个记号的原始字符就是123.456。
3．记号的值
123.456这个记号代表的是实数123.456的值的意思。
对于 +或 -这样的记号来说，只需要关注其记号种类就可以了，而如果是DOUBLE_LITERAL记号，记号的种类与记号的值都必须传递给解析器。
第17行的正则表达式，是一个匹配“数值”用的正则表达式。表达式匹配成功的结果，即上面列举的记号三要素中，“记号的原始字符”会在相应动作中被名为yytext的全局变量（这算是lex的一个丑的设计）引用，并进一步使用第19行的sscanf（）进行解析。
动作解析出的值会存放在名为yylval的全局变量中（又丑一次）。这个全局变量yylval本质上是一个联合体（union），可以存放各种类型记号的值（在这个计算器程序中只有double类型）。联合体的定义部分写在yacc的定义文件mycalc.y中。
到第28行，又出现了一次 %%。这表示规则区块的结束，这之后的代码则被称为用户代码区块。在用户代码区块中可以编写任意的C代码（例子中没有写）。与定义区块不同，用户代码区块无需使用 %{ %}包裹。
2.2.2 简单正则表达式讲座
lex通过正则表达式定义记号。正则表达式在Perl、Ruby语言中广泛使用，而UNIX用户也经常会在编辑器或grep命令中接触到。本书的读者可能未必都有这样的技术背景，所以我们在本书涉及的范围内，对正则表达式做一些简单的说明。
在代码清单2-1的第17行中有这样一个正则表达式（初看可能稍微有点复杂）：
（[1-9][0-9]＊）|0|（[0-9]+\.[0-9]+）
首先，[与 ]表示匹配此范围内的任意字符。而 [ ]还支持使用连接符的缩写方式。比如写1-9与写123456789是完全一样的。
最初圆括号中的 [1-9]代表匹配1～9中任意一个数字。其后的 [0-9]代表匹配0～9的任意一个数字。
在此之后的 ＊，代表匹配前面的字符0次或多次。
因此，[1-9][0-9]＊这个正则表达式，整体代表以1～9开头（只有1位），后接0个以上的0～9的字符。而这正是我们在mycalc中对整数所做的定义。
在表2-2中列举了若干字符串，并展示其是否匹配我们所制定的整数规则。
表2-2 字符串的匹配
如上表所示，mycalc不会将012这样的输入作为数值接收，这完全符合我们的预期。
但是将0也排除的话还是有问题的，程序必须能接受所有的实数。因此在正则表达式中又使用了 |。|代表“或”的意思。
第17行的正则表达式就被修正为：
（[1-9][0-9]＊）|0|（[0-9]+\.[0-9]+）
现在应该可以明白前半段正则表达式的整体意思了，即将整数（0以外）的正则表达式与0通过 |分成两部分然后并列（加上圆括号（）是将这部分作为一个集合才能通过 |与0并列）。
后半部分的 [0-9]+\.[0-9]+中用到了 +。＊是代表“匹配前面的字符0次或多次”，而 +则是“匹配前面的字符1次或多次”，因此这部分整体代表“0～9的数字至少出现一次，后接小数点．后又接至少一位0～9数字”。这些与前面整合起来，共同构成了mycalc对于实数的定义。
小数点的书写不是只写一个 ．而是写成了 \.，因为 ．在正则表达式中有特殊的含义（后文即将介绍），所以需要使用 \转义。[ ]、 ＊ 、 +、 ．等这些在正则表达式中有特殊含义的字符称为元字符，元字符可以像上文那样用 \或双引号进行转义。代码的第12～14行，就是使用双引号转义的方法对乘法和加法的运算符进行了定义。
第23行的正则表达式 [ \t]是对空格以及制表符进行匹配，对应动作为空，因此可以忽略每一行的空白字符。
第24行的．会匹配任意一个字符。这里用于检测是否输入了程序不允许的字符。
首先，lex将输入的字符串分割到若干个记号中时，会尽可能选择较长的匹配。比如C语言中同时有 +运算符和 ++运算符，那么当输入 ++时，lex不会匹配为两个 +运算符，而是返回一个 ++（如果不按这个逻辑，程序很难正常工作）。如果两个规则出现同样长度的匹配时，会优先匹配前一个规则。也就是说，如果输入字符直到最后一条规则（匹配任意字符）才匹配成功的话，说明这个字符不符合前面所有的规则，是错误的输入。
在表2-3中列举了一些常用的元字符。元字符以外的字符直接书写就可以了。
表2-3 lex中正则表达式的元字符
2.2.3 yacc
yacc是自动生成语法分析器的工具，输入扩展名为．y的文件，就会输出语法分析器的C语言代码。bison则是GNU项目所发布的yacc的功能扩充版。
mycalc中yacc的输入文件mycalc.y如代码清单2-2所示。
代码清单2-2 mycalc.y
1: %{
2: #include <stdio.h＞
3: #include <stdlib.h＞
4: #define YYDEBUG 1
5: %}
6: %union {
7: int int_value;
8: double double_value;
9: }
10: %token <double_value＞ DOUBLE_LITERAL
11: %token ADD SUB MUL DIV CR
12: %type <double_value＞ expression term primary_expression
13: %%
14: line_list
15: : line
16: | line_list line
17: ;
18: line
19: : expression CR
20: {
21: printf（"＞＞%lf\n", $1）;
22: }
23: expression
24: : term
25: | expression ADD term
26: {
27: $$ = $1 + $3;
28: }
29: | expression SUB term
30: {
31: $$ = $1- $3;
32: }
33: ;
34: term
35: : primary_expression
36: | term MUL primary_expression
37: {
38: $$ = $1 ＊ $3;
39: }
40: | term DIV primary_expression
41: {
42: $$ = $1 / $3;
43: }
44: ;
45: primary_expression
46: : DOUBLE_LITERAL
47: ;
48: %%
49: int
50: yyerror（char const ＊str）
51: {
52: extern char ＊yytext;
53: fprintf（stderr, "parser error near %s\n", yytext）;
54: return 0;
55: }
56：
57: int main（void）
58: {
59: extern int yyparse（void）;
60: extern FILE ＊yyin;
61：
62: yyin = stdin;
63: if（yyparse（））{
64: fprintf（stderr, "Error ! Error ! Error ! \n"）;
65: exit（1）;
66: }
67: }
第1～5行与lex相同，使用 %{%}包裹了一些C代码。
第4行有一句 #define YYDEBUG 1，这样将全局变量yydebug设置为一个非零值后会开启Debug模式，可以看到程序运行中语法分析的状态。我们现在还不必关心这个。
第6～9行声明了记号以及非终结符的类型。正如前文所写，记号不仅需要包含类型，还需要包含值。记号可能会有很多类型，这些类型都声明在集合中。本例中为了方便说明，定义了一个int类型的int_value和double类型的double_value，不过目前还没有用到int_value。
非终结符是由多个记号共同构成的，即代码中的line_list、 line、expression、 term这些部分。为了分割非终结符，非终结符最后都会以一个特殊记号结尾。这种记号称作终结符。
第10～11行是记号的声明。mycalc所用到的记号类型都在这里定义。ADD、 SUB、 MUL、 DIV、 CR等记号只需要包含记号的类型就可以了，而值为DOUBLE_LITERAL的记号，其类型被指定为 <double_value＞。这里的double_value是来自上面代码中 %union集合的一个成员名。
第12行声明了非终结符的类型。
与lex一样，13行的 %%为分界，之后是规则区块。yacc的规则区块，由语法规则以及C语言编写的相应动作两部分构成。
在yacc中，会使用类似BNF（巴科斯范式，Backus Normal Form）的规范来编写语法规则。
计算器程序因为规则部分中混杂了动作，阅读起来有点难度，所以在代码清单2-3中，仅仅将规则部分抽出，并加入了注释。
代码清单2-3 计算器的语法规则
1: line_list /＊ 多行的规则 ＊/
2: : line /＊ 单行 ＊/
3: | line_list line /＊ 或者是一个多行后接单行 ＊/
4: ;
5: line /＊ 单行的规则 ＊/
6: : expression CR /＊ 一个表达式后接换行符 ＊/
7: ;
8: expression /＊ 表达式的规则 ＊/
9: : term /＊ 和项 ＊/
10: | expression ADD term /＊ 或 表达式 + 和项 ＊/
11: | expression SUB term /＊ 或 表达式 - 和项 ＊/
12: ;
13: term /＊ 和项的规则 ＊/
14: : primary_expression /＊ 一元表达式 ＊/
15: | term MUL primary_expression /＊ 或 和项 ＊ 一元表达式 ＊/
16: | term DIV primary_expression /＊ 或 和项 / 一元表达式 ＊/
17: ;
18: primary_expression /＊ 一元表达式的规则 ＊/
19: : DOUBLE_LITERAL /＊ 实数的字面常量 ＊/
20: ;
为了看得更清楚，可以将语法规则简化为下面的格式：
A
： B C
| D
;
即A的定义是B与C的组合，或者为D。
第1～4行的书写方式，是为了表示该语法规则在程序中可能会出现一次以上。在mycalc中，输入一行语句然后敲回车键后就会执行运算，之后还可以继续输入语句，所以需要设计成支持出现一次以上的模式。
另外，请注意在上面的计算器的语法规则中，语法规则本身就包含了运算符的优先顺序以及结合规律。如果不考虑运算符的优先顺序（乘法应该比加法优先执行），上文的语法规则应该写成这样。
expression /＊ 表达式的规则 ＊/
：primary_expression /＊ 一元表达式 ＊/
| expression ADD expression /＊ 或 表达式 + 表达式 ＊/
| expression SUB expression /＊ 或 表达式 - 表达式 ＊/
| expression MUL expression /＊ 或 表达式 ＊ 表达式 ＊/
| expression DIV expression /＊ 或 表达式 / 表达式 ＊/
;
primary_expression /＊ 一元表达式的规则 ＊/
：DOUBLE_LITERAL /＊ 实数的字面常量 ＊/
;
那么在这样的语法规则下，yacc是如何运作的呢？我们以代码清单2-3为例一起来看看吧。
大体上可以这样说，yacc所做的工作，可以想象成一个类似“俄罗斯方块”的过程。
首先，yacc生成的解析器会保存在程序内部的栈，在这个栈中，记号就会像俄罗斯方块中的方块一样，一个个堆积起来。
比如输入1 + 2 ＊ 3，词法分析器分割出来的记号（最初是1）会由右边进入栈并堆积到左边。
像这样一个记号进入并堆积的过程，叫作移进（shift）。
mycalc所有的计算都是采用double类型，所以记号1即是DOUBLE_LITERAL。当记号进入的同时，会触发我们定义的规则：
primary_expression
： DOUBLE_LITERAL
然后记号会被换成primary_expression。
类似这样触发某个规则并进行置换的过程，叫作归约（reduce）。
primary_expression将进一步触发规则：
term
： primary_expression
然后归约为term。
再进一步根据规则：
expression
： term
最终被归约为一个expression。
接下来，记号 +进入。在进入过程中，由于没有匹配到任何一个规则，所以只好老老实实地进行移进而不做任何归约。
接下来是记号2进入。
经过上述同样的规则，记号2（DOUBLE_LITERAL）会经过primary_expression被归约为term。
这里记号2本应该匹配到如下的规则：
expression
| expression ADD term
yacc和俄罗斯方块一样，可以预先读取下一个要进入的记号，这里我们就可以知道下一个进入的会是 ＊，因此应当考虑到记号2会匹配到term规则的可能性。
term
| term MUL primary_expression
归约完毕后再一次移进。
接下来记号3进入，
被归约为primary_expression后，
term、 ＊、 primary_expression这一部分将匹配规则：
term
| term MUL primary_expression
被归约为term。
之后，expression、 +、 term又会匹配规则
expression
| expression ADD term
最终被归约为expression。
每次触发归约时，yacc都会运行该规则的相应动作。比如乘法对应执行的规则如下文所示。
34: term
36: | term MUL primary_expression
37: {
38: $$ = $1 ＊ $3;
39: }
动作是使用C语言书写的，但与普通的C语言又略有不同，掺杂了一些 $$、 $1、 $3之类的表达式。
这些表达式中，$1、 $3的意思是分别保存了term与primary_expression的值。即yacc输出解析器的代码时，栈中相应位置的元素将会转换为一个能表述元素特征的数组引用。由于这里的 $2是乘法运算符（＊），并不存在记号值，因此这里引用 $2的话就会报错。
$1与 $3进行乘法运算，然后将其结果赋给 $$，这个结果值将保留在栈中。在这个例子中，执行的计算为2 ＊ 3，所以其结果值6会保留在栈中（如图2-3）。
图2-3 归约发生时栈的动作
咦，$1与 $3对应的应该是term和primary_expression，而不是2与3这样的DOUBLE_LITERAL数值才对呀，为什么会作为2 * 3来计算呢？
可能会有人提出上面的疑问吧。这是因为如果没有书写动作，yacc会自动补全一个 { $$ = $1 }的动作。当DOUBLE_LITERAL被归约为primary_expression、 primary_expression被归约为term的时候，DOUBLE_LITERAL包含的数值也会被继承。
34: term
35: : primary_expression
{
$$ = $1; /＊ 自动补全的动作 ＊/
}
…
45: primary_expression
46: : DOUBLE_LITERAL
{
$$ = $1; /＊ 自动补全的动作 ＊/
}
$$与 $1的数据类型，分别与其对应的记号或者非终结符的类型一致。比如，DOUBLE_LITERAL对应的记号被定义为：
9: %token <double_value＞ DOUBLE_LITERAL
expression、 term、 primary_expression的类型则为：
11: %type <double_value＞ expression term primary_expression
这里的类型被指定为 <double_value＞，其实是使用了在 %union部分声明的联合体中的double_value成员。
由于我们以计算器为例，计算器的动作会继续计算得出的值，但仅靠这些还不足以制作编程语言。因为编程语言中都会包含简单的循环，而语法分析只会运行一次，所以动作还要支持循环处理同一处代码才行。
因此在实际的编程语言中，会从动作中构建分析树。这部分处理的方法会在后面的章节中介绍。
2.2.4 生成执行文件
接下来，让我们实际编译并链接计算器的源代码，生成执行文件吧。
在标准的UNIX中，按顺序执行下面的指令（%是命令行提示符），就会输出名为mycalc的执行文件。
如果在Windows的环境下，参考1.6.1节中的说明，需要安装gcc、bison、flex，然后运行下面的指令（C:\Test＞ 是命令行提示符）。
这个过程中会生成若干文件。其流程以图片表示的话，如图2-4所示。
图2-4 yacc/lex的编译
y.tab.c中包含yacc生成的语法分析器的代码，lex.yy.c是词法分析器的代码。为了将mycalc.y中定义的记号及联合体传递给lex.yy.c, yacc会生成y.tab.h这个头文件。
此外，作为C语言程序当然要有main（）函数，在mycalc中main（）位于mycalc.y的用户代码区块（第49行以后），最终编译器会负责合并代码，所以这里的main（）与其他．c文件分离也不要紧。在main（）函数中的全局变量yyin可以设定输入文件，调用yyparse（）函数。
由于我们使用bison替代了yacc，默认生成的文件就不是y.tab.c和y.tab.h，而是mycalc.tab.c和mycalc.tab.h。所以在上例中添加了--yacc参数，可以让bison生成与yacc同名的文件。本书为了统一，bison会始终带上 --yacc参数。
2.2.5 理解冲突所代表的含义
实际用yacc试做一下解析器，可能会被冲突（conflict）问题困扰。所谓冲突，就是遇到语法中模糊不清的地方时，yacc报出的错误。
比如C语言的if语句，就很明显有语法模糊问题。
if（a == 0）
if（b == 0）
printf（在这里a与b都为0\n）;
else
printf（这里是a非0？错！\n）;
上面的代码中，我们不清楚最后的else对应的究竟是哪一个if，这就是冲突。
yacc运行时，遇到下面任意一种情况都会发生冲突。
●同时可以进行多个归约。
●满足移进的规则，同时又满足归约的规则。
前者称为归约/归约（reduce/reduce）冲突，后者称为移进/归约（shift/reduce）冲突。
即便发生冲突，yacc仍然会生成解析器。如果存在归约/归约冲突，则优先匹配前面的语法规则，移进/归约冲突会优先匹配移进规则。很多书会写归约/归约冲突是致命错误，而移进/归约冲突则允许，这两者的确是存在严重程度的差别，但是在我来看，无论发生哪一种冲突都是难以容忍的，我恨不得消灭代码中所有的冲突问题。
yacc运行时可以附带 -v参数，标准yacc会生成y.output文件（bison则会将输入文件名中的扩展名．y替换为．output并生成）。
这个y.output文件会包含所有的语法规则、解析器、所有可能的分支状态以及编译器启动信息。
那么我们实际做出一个冲突，然后观察一下y.output文件吧。
将代码清单2-2中的语法规则
更改为下文所示：
变更后会产生3个移进/归约冲突。
% yacc -dv mycalc.y
conflicts: 3 shift/reduce
然后再看y.output文件。
根据yacc或bison的版本与语言设置，y.output的输出会有微妙的区别。这里以bison2.3英文模式为例（为了节约纸张将空行都去掉了）。日语环境下，“Grammar”会变成“文法”等，错误信息也都会显示为日语。
总体来说，y.output文件的前半部分看起来基本都会是下面这个样子（代码清单2-4）。
代码清单2-4 y.output（前半部分）
首先将ADD改为MUL后，开头会出现“ADD没有被使用”的警告。下面会有3行冲突信息，此处后文会细说。再后面的“Grammar”跟着的是mycalc.y中定义的语法规则。
mycalc.y中可以使用 |（竖线，表示或）书写下面这样的语法规则：
line_list : line
| line_list line
实际上与下面这种写法的语法规则是完全一样的。
line_list : line
line_list : line_list line
y.output文件中，会给每一行规则附上编号。
上面的规则0，是yacc自动附加的规则，$accept代表输入的内容，$end代表输入结束，目前还不需要特别在意这个问题。
y.output文件的后半部分会将解析器可能遇到的所有“状态”全部列举出来（代码清单2-5）。
代码清单2-5 y.output（后半部分）
state 0
0 $accept: . line_list $end
DOUBLE_LITERAL shift, and go to state 1
line_list go to state 2
line go to state 3
expression go to state 4
term go to state 5
primary_expression go to state 6
state 1
10 primary_expression: DOUBLE_LITERAL .
$default reduce using rule 10（primary_expression）
state 2
0 $accept: line_list . $end
2 line_list: line_list . line
$end shift, and go to state 7
DOUBLE_LITERAL shift, and go to state 1
line go to state 8
expression go to state 4
term go to state 5
primary_expression go to state 6
state 3
1 line_list: line .
$default reduce using rule 1（line_list）
state 4
3 line: expression . CR
5 expression: expression . MUL term
6 | expression . SUB term
SUB shift, and go to state 9
MUL shift, and go to state 10
CR shift, and go to state 11
下略
前文中有一个俄罗斯方块的比喻，读者通过那个比喻可能会这样理解：解析器在一个记号进入栈后，从栈的开头一个字符一个字符扫描，如果发现这个记号满足已有的某个规则，就去匹配该规则。但其实这样做会让编译器变得很慢。
现实中，yacc在生成解析器的阶段，就已经将解析器所能遇到的所有状态都列举出来，并做成了一个解析对照表（Parse Table），表中记录了“状态A下某种记号进入后会转换到状态B”这样的映射关系，y.output的后半部分就罗列了所有可能的映射关系。听说这有点像麻将中的听牌，不过因为我不玩麻将，所以也不是很清楚。
有了这些列举出的状态，当记号进入后，就可以很容易找到在何种状态下移进，或者根据何种规则归约。那么对于之前我们故意做出的冲突，在我的环境下，y.output开头会输出如下信息：
State 5 conflicts: 1 shift/reduce
State 14 conflicts: 1 shift/reduce
State 15 conflicts: 1 shift/reduce
可以看到state 5引起了冲突，我们来看一下：
state 5
4 expression: term .
8 term: term . MUL primary_expression
9 | term . DIV primary_expression
MUL shift, and go to state 12
DIV shift, and go to state 13
MUL [reduce using rule 4（expression）]
$default reduce using rule 4（expression）
上例中，第一行的state 5即为状态的编号，1个空行后接下来的3行是y.output前半部分中输出的语法规则（语法规则还附加了编号）。语法规则中间有．，代表记号在当前规则下能被转换到哪个程度。比如state 5这个状态下，记号最多被转换为term，然后需要等待下一个记号进行归约。
再空一行，接下来记录的是当前状态下，下一个记号进入时将如何变化。具体来讲，这里当MUL（＊）记号进入后会进行移进并转换为state 12。如果进入的是DIV（/），则同样进行移进并转移到state 13。
再经过1个空行后下一行是：
MUL [reduce using rule 4（expression）]
意思是当MUL进入后，可以按照规则4进行归约。这也就是移进/归约冲突。
yacc默认移进优先，所以MUL进入后会转移到状态12。在y.output中state 12是这样的：
state 12
8 term: term MUL . primary_expression
DOUBLE_LITERAL shift, and go to state 1
primary_expression go to state 16
而如果是归约的情况，所要参照的规则4是这样的：
4 expression: term
也就是说，当记号被转换为term后，下一个记号 ＊进入以后，yacc会报告有冲突发生，冲突的原因是当前term既可以继续进行移进，也可以归约为expression并结束。而这正是由于我们将ADD修改为MUL后，＊的运算优先级被降低而引发的混乱。
对y.output阅读方法的说明就此告一段落，其实在实践中想要探明冲突原因并解决冲突，是比较有难度的。
因此即便表面上看起来都一样的编程语法，根据语法规则的书写方式不同，yacc可能报冲突也可能不报冲突（可以参考后文讲到的LALR（1）语法规定）。比如本节开头所说的C语言中if else语法模糊的问题，在Java中就从语法规则入手回避了这个冲突。而类似这样的小问题以及相应的解决“窍门”，在自制编程语言中数不胜数，所以从现实出发，模仿已有的编程语言时，最好也要多多参考其语法规则。
2.2.6 错误处理
前面的小节中介绍了如何应对语法规则中的冲突问题，即编译器制作阶段的错误处理。而在自制编程语言时，还要考虑到使用这门语言编程的人如果犯了错误该怎么办。
在稍微旧一点的编译器书籍中，常常能读到下面这样的文字。
让用户自己不断的编译，既浪费CPU资源也浪费时间，因此编译器最好只经过一次编译就能看到大部分错误信息。
但是程序中的一个错误，其原因可能是由于其他错误引起的（可能会引起错误信息的雪崩现象）。一边不希望无用的错误信息出现，一边又想尽可能多地显示错误的原因，这其中的平衡点是很难掌握的。
然而时至今日，CPU已经谈不上什么“浪费资源”了，因为在多数情况下，编译过程往往一瞬间就能结束。那么即便一次编译显示出很多错误信息，用户一般也只会看第一条（我就是这样），这样的话，“编译器最好只经过一次编译就能看到大部分错误信息”也就没什么意义了。
所以最省事的解决方法之一就是，一旦出错，立即使用exit（）退出。之后章节中的crowbar和Diksam都是这样处理的。
但是对于计算器来说，是需要与用户互动，如果输错了一点程序就强制退出的话，对用户也太不友好了。
因此我们可以利用yacc的功能实现一个简单的错误恢复机制。
首先在mycalc.y的非终结符line的语法规则中，追加下面的部分。
line
： expression CR
{
printf（"＞＞%lf\n", $1）;
}
| error CR
{
yyclearin;
yyerrok;
}
;
这里新出现的是error记号。error记号是匹配错误的特殊记号。error可以后接CR（换行符），这样书写可以匹配包含了错误的所有记号以及行尾。
动作中的yyclearin会丢弃预读的记号，而yyerrok则会通知yacc程序已经从错误状态恢复了。
既然是有交互的工具，一般都会使用换行来分割每次的会话，每一个错误信息后加上换行符应该会显得更美观吧。