yacc原理
Stephen C. Johnson
Bell Laboratories
Murray Hill, New Jersey 07974
翻译：寒蝉退士
译者声明：
译者对译文不做任何担保，译者对译文不拥有任何权利并且不负担任何责任和义务。
原文：https://www.wendangku.net/doc/1c6771198.html,/7thEdMan/vol2/yacc.bun
摘要
计算机程序的输入通常有某种结构；实际上，可以认为每个需要输入的计算机程序都定义了一门它所接受的“输入语言”。输入语言可以像编程语言那么复杂，或者像一序列的数那么简单。不幸的是，通常的输入设施是有限的、难于使用的，并经常疏于检查它们的输入的有效性。
Yacc 提供了一个通用工具来描述计算机程序的输入。Yacc 用户规定它的输入的结构，连同在识别每个这种结构的时候调用的代码。Yacc 把这样的规定转换成操作输入处理的一个子例程；用这个子例程处理用户应用中的多数控制流经常是方便和适当的。
Yacc 生成的输入子例程调用用户提供的一个例程来返回下一个基本输入项目(item)。所以，用户可以以单个的输入字符的方式，或以更高层构造如名字和数的方式来规定它的输入。通过用户提供的例程还可以处理惯用的特征如注释和(行)接续约定，这些东西典型的违反容易的文法规定。
Yacc 是用可移植的C 语言写成的。接受的规定类别是非常一般性的: 带有去歧义规则的LALR(1) 文法。
除了用于C、APL、Pascal、RATFOR 等编译器之外，Yacc 还用于非常规语言，包括一个照相排版机语言、一些桌面计算器语言、一个文档检索系统、和一个Fortran 调试系统。
July 31,1978
目录
?0: 介绍
?1: 基本规定
?2: 动作
?3: 词法分析
?4: 解析器如何工作
?5: 歧义和冲突
?6: 优先级
?7: 错误处理
?8: Yacc 环境
?9: 对准备规定的提示
o输入样式
o左递归
o词法搭配
o保留字
?10: 高级主题
o在动作中模拟错误和接受
o访问外围规则中的值
o支持任意的值类型
?11: 致谢
?引用
?附录A: 简单的例子
?附录B: Yacc 输入语法
?附录C: 高级的例子
?附录D: 支持但不鼓励的旧特征
date : month_name day ',' year ;
这里的date、month_name、day、和year 表示在输入处理中它感兴趣的那些结构；month_name、day 和year 大概是在其他地方定义的。逗号“,”包围在单引号之中；这暗示了逗号在输入中是作为文字(literal)出现的。冒号和分号只是充当规则中的标点符号，而对控制输入没有意义。所以，有着正确定义的输入
July 4, 1776
可以匹配上述规则。
输入处理的一个重要部分是完成词法分析器。这个用户例程读取输入流，识别低层结构，并把这些记号传达到解析器。出于历史原因，词法分析器识别的结构叫做终结符(terminal sym bol)，而解析器识别的结构叫做非终结符(nonterminal sym bol)。为了避免混淆，终结符通常会称呼为记号。
在使用词法分析器还是使用文法解析器之间有相当可观的回旋余地。例如，规则
month_name : 'J' 'a' 'n' ;
month_name : 'F' 'e' 'b' ;
. . .
month_name : 'D' 'e' 'c' ;
可以用于上述例子。这个文法解析器只需要识别单个字母，而month_name 将是一个非终结符。这种低层规则趋向于浪费时间和空间，并可能使规则复杂得超越了Yacc 的处理能力。通常的，词法分析器将识别月份名字，并返回见到了m onth_nam e 的一个指示；在这种情况下，month_name 将是一个记号。
文字字符比如“,”也必须通过词法分析器来传递，所以也被当作记号。
规定文件是非常灵活的。向上述例子增加规则是相对容易的
date : month '/' day '/' year ;
允许
7 / 4 / 1776
作为
July 4, 1776
的同义字。在多数情况下，这个新规则可以“滑入”到工作系统中，并带有最小的努力，和混乱现存输入的很小的危险性。
读取中的输入可能无法满足这个规定。检测到这些错误可以同从左至右扫描理论上能做到的一样早；所以，不只是充分的减少了读取并计算不良数据的可能性，而且通常可以快速的发现不良数据。作为输入规定的一部分提供的错误处理，允许不良数据的再入，或在跳过不良数据之后继续做输入处理。
在一些情况下，Yacc 在给出某一组规定的时候无法生成解析器。例如，规定可能自相矛盾，或者它们要求比Yacc 提供的更强力的识别机制。前者情况表示设计错误；后者情况经常可以通过使词法分析器更强力，或重写某些文法规则来修正。尽管Yacc 不能处理所有可能的规定，它的能力可以顺利的同类似系统相比较；此外，Yacc 难于处理的构造经常也是难于人类处理的。一些用户报告对他们的输入明确表述有效的Yacc 规定，暴露了程序开发中早期的概念或设计错误。
Yacc 底层的理论已经在其他地方[2, 3, 4]描述了。Yacc 已经在大量的实际应用中广泛的使用了，包括lint[5]、可移植 C 编译器[6]、和一个排版数学的系统[7]。
下面的章节描述准备Yacc 规定的基本过程；第 1 节描述准备文法规则，第 2 节描述准备与这些规则相关联的用户提供的动作，而第 3 节准备词法分析器。第 4 节描述解析器的操作。第 5 节讨论Yacc 有可能无法从规定生成解析器的各种原因和对此要做些什么。第 6 节描述处理在算术表达式中操作符(operator)优先级(precedence)的简单机制。第7 节讨论错误检测和修复。第8 节讨论Yacc 生成的解析器的操作环境和特殊特征。第9 节给出增进规定的样式和效率的一些建议。第10 节讨论一些高级主题，而第11 节给出致谢。附录 A 有一个简单的例子，而附录 B 给出Yacc 输入语法的总结。附录 C 给出使用Yacc 的某些高级特征的一个例子，最后，附录 D 描述出于同Yacc 老版本的历史延续性而提供的不再活跃支持的机制和语法。
1: 基本规定
名字称谓的是记号或非终结符二者之一。Yacc 同样的要求声明记号名字。此外，出于在第 3 节中讨论的原因，经常需要把词法分析器包括为规定文件的一部分；同样也可以包括其他有用的程序。所以，每个规定文件都由三段组成: 声明、(文法)规则和程序。使用双重百分号“%%” 来分隔各段。(百分号“%”在Yacc 规定中一般用做转义(escape)字符。)
换句话说，完整的规定文件看起来如下
声明
%%
规则
%%
程序
声明段可以为空。此外，如果省略了程序段，第二个%% 号也可以省略；
所以，最小的合法Yacc 规定是
%%
规则
除了不能出现在名字或多字符保留符号中之外，空白、tab 和换行被忽略。注释可以出现在名字是合法的任何地方；它们被包围在/* . . . */ 中，同 C 和PL/I 语言一样。
规则段由一个或多个文法规则构成。文法规则有如下格式:
A : BODY ;
A 表示一个非终结符名字，而BODY 代表一序列的零个或更多的名字和文字。冒号和分号是Yacc 标点符号。
名字可以有任意长度，并由字母、点“.”、下划线“_”和不开头的数字组成。区分大写和小写字母。在文法规则主体中使用的名字可以代表记号或非终结符。
文字由包围在单引号“'”中的字符组成。同 C 语言一样，反斜杠“\”在文字中是转义字符，并识别所有 C 转义。所以
'\n' 换行
'\r' 回车
'\'' 单引号 ``'''
'\\' 反斜杠 ``\''
'\t' tab
'\b' backspace
'\f' form feed
'\xxx' ``xxx'' 八进制数
出于一些技术原因，NUL 字符('\0' 或0)在文法规则中不应该使用。
如果有一些文法规则有相同的左手端，可以使用竖杠“|”来避免重写左手端。此外，在规则末端的分号如果在竖杠之前则可以去掉。所以给Yacc 的文法规则
A :
B
C
D ;
A : E F ;
A : G ;
可以写为
A :
B
C D
| E F
| G
;
在文法规则段中有相同左手端的所有文法规则出现在一起不是必须的，但是这使输入更加可读并易于改变。
如果一个非终结符匹配空字符串，则可以用明显的方式来指示:
empty : ;
代表记号的名字必须被声明；最简单的就是在声明段中写
%token name1 name2 . . .
。(更多的讨论参见章节3、5 和6)。假定没有在声明段中定义的每个名字都是非终结符。每个非终结符都必须至少在一个规则的左手端出现。
在所有非终结符中，有一个叫做开始符号的特别重要。解析器就是设计用来识别这个开始符号；所以这个符号代表文法规则描述的最大的最一般的结构。缺省的，在规则段中使用这个开始符号作为第一个文法规则。在声明段中使用%start 关键字显式的声明这个开始字符是可能的，并在实际上是需要的:
%start symbol
通过叫做结束标记(endmarker)的特殊记号向解析器通知输入结束。如果直到但不包括这个结束标记的记号形成了同开始符号相匹配的一个结构，则解析器函数在见到结束标记之后返回到它的调用者。如果在任何其他上下文中见到这个结束标记，都是一个错误。
在适当的时候返回结束标记是用户提供的词法分析器的工作；参见下面的第 3 节。通常结束标记代表某种相当明显的I/O 状态，比如“文件结束”或“记录结束”。
2: 动作
对于每个文法规则，用户都可以关联上在输入处理中每次识别了这个规则的时候进行的动作。这些动作可以返回值，并可以获得从前面动作返回的值。此外，词法分析器可以返回记号的值，如果需要的话。
动作是任意的 C 语句，同样可以做输入输出，调用子程序，和更改外部向量和变量。动作被指定为包围在花括号“{”和“}”中的一个或多个语句。例如，
A : '('
B ')'
{ hello( 1, "abc" ); }
和
XXX : YYY ZZZ
{ printf("a message\n");
flag = 25; }
是带有动作的文法规则。
为了便利在动作和解析器之间的通信，对动作语句要做稍微的改动。在这个上下文中使用美元符号“$”作为给Yacc 的一个信号。
要返回值，动作通常把伪变量(pseudo-variable)“$$”设置为某个值。例如，不做任何事但返回值 1 的动作是
{ $$ = 1; }
要获得前面动作和词法分析器的返回值，动作必须使用伪变量$1、$2、. . .，它们提及的是规则右手端的部件(component)的返回值，它们是从左至右读取的。所以，如果规则是
A :
B
C
D ;
例如，这里的$2 拥有 C 返回的值，而$3 是 D 返回的值。
作为一个更具体的例子，考虑规则
expr : '(' expr ')' ;
这个规则返回的值通常是圆括号中的expr 的值。这可以指示为
expr : '(' expr ')' { $$ = $2 ; }
缺省的，规则的值是其中第一个元素($1)的值。所以，如下形式的文法规则
A :
B ;
经常不需要显式的动作。
在上述例子中，所有动作都在规则的末端。有时，需要在一个规则被完全解析之前获得控制权。Yacc 允许在规则中间同末端一样写动作。假定这个动作(原文误作规则)返回一个值，它右面的动作可以通过平常的机制访问它。依次的，它可以访问它左面动作的返回值。所以，规则
A : B
{ $$ = 1; }
C
{ x = $2; y = $3; }
;
在效果上是设置x 为1，设置y 为 C 返回的值。
Yacc 通过制造一个新的非终结符名字，和把这个名字匹配到空字符串的一个新规则，来处理不终结一个规则的动作。内部动作是通过识别这个增加的规则而触发的动作。Yacc 实际上对待上述例子如同它被写为:
$ACT : /* empty */
{ $$ = 1; }
;
A :
B $ACT C
{ x = $2; y = $3; }
;
在很多应用中，动作不做直接的输出；转而在内存中构造一个一个数据结构，比如解析树，并在生成输出之前向它应用变换。给出建造并维护想要的树结构的例程，分析树就特别易于构造。例如，假定写了一个 C 函数node，调用
node( L, n1, n2 )
建立带有标签L 和后代节点的n1 和n2 的一个节点，并返回这个新建节点的索引。在规定中可以通过提供如下动作来构造析树:
expr : expr '+' expr
{ $$ = node( '+', $1, $3 ); }
用户可以定义动作使用的其他变量。这种声明和定义可以出现在声明段中，包围在标号“%{”和“%}”之间。这些声明和定义有全局作用域，所以它们可以被动作语句和词法分析器所知晓。例如，
%{ int variable = 0; %}
可以放置到声明段中，使variable 对于所有动作都是可以访问的。Yacc 解析器只使用以“yy”开始的名字；用户应当避免使用这种名字。
在这些例子中，所有变量都是整数: 对其他类型的值的讨论可以在章节10 中找到。
3: 词法分析
用户必须提供一个词法分析器来读取输入流并把记号(带有值，如果需要的话)传达到解析器。词法分析器使叫做yylex 的整数值的函数。这个函数返回一个整数的记号编号，它表示读取的记号的种类。如果这个记号关联着一个值，应当把它赋予外部变量yylval。
为使通信得以发生，解析器和词法分析器必须在记号编号上达成一致。编号可以由Yacc 或用户来选择。在这两种情况下，使用 C 语言的“# define”机制允许词法分析器使用符号来返回这
些编号。例如，假定在Yacc 规定文件的声明段中已经定义记号名字DIGIT。词法分析器的相关部分可能看起来如下:
yylex(){
extern int yylval;
int c;
. . .
c = getchar();
. . .
switch( c ) {
. . .
case '0':
case '1':
. . .
case '9':
yylval = c-'0';
return( DIGIT );
. . .
}
. . .
它的意图是返回一个DIGIT 记号编号，和等于这个数字的数值的一个值。倘若词法分析器代码位于规定文件的程序段，标识符DIGIT 将被定义为与记号DIGIT 关联的记号编号。
这种机制导致清晰的、易于修改的词法分析器；唯一的缺点是在文法中需要避免使用任何在 C 语言或解析器中保留的或有意义的记号名字；例如，使用记号名字if 或while 就一定会导致编译词法分析器时出现严峻的困难。记号名字error 保留给错误处理，不应该随便使用(参见章节7)。
同上所述，记号编号可以由Yacc 或用户来选择。在缺省的条件下，编号由Yacc 选择。文字字符的缺省记号编号是它在本地字符集中的字符数值。其他名字赋予从257 开始的记号编号。要把一个记号编号赋予一个记号(包括文字)，可以在声明段中记号或文字的第一次出现时直接跟随着一个非负整数。这个整数被接受为这个名字或文字的记号编号。不通过这种机制定义的名字和文字保持它们的缺省定义。所有记号编号都是不同的是很重要的。
出于历史原因，结束标记必须有记号编号0 或负数。这个记号编号不能由用户重定义；所以，所有词法分析器在到达它们的输入结束处的时候应当准备返回0 或负数作为记号编号。
构造词法分析器的一个有用的工具是Mike Lesk[8]开发的Lex 程序。这些词法分析器设计用来与Yacc 解析器紧密协调工作。这些词法分析器的规定使用正则表达式而不是文法规则。可以轻易的用Lex 生成非常复杂的词法分析器，但是仍有一些语言(比如FORTRAN)不适应任何理论框架，它的词法分析器必须手工制作。
4: 解析器如何工作
Yacc 把规定文件转换成C 程序，它依据给出的规定解析输入。做从规定到解析器转换的算法是复杂的，就不在这里讨论了(更多信息参见引用)。但是，解析器自身就相对简单了，理解它是如何工作的，尽管不是严格必须的，但会使错误修复和歧义处置更加易于理解。
Yacc 提供的解析器是由带有一个栈的有穷状态自动机组成。解析器自身还有能力读取和记住(叫做超前(lookahead)记号)下一个输入记号。当前状态总是在栈顶。有穷状态自动机的状态是一个给定的小整数标签(label)；最初时，机器是在状态0 下，栈只包含状态0，没有读取超前记号。
机器对它只能获得四个动作，叫做移进(shift)、归约(reduce)、接受和错误。解析器的移动按如下规则进行:
1. 基于它的当前状态，解析器决定是否需要一个超前记号来决定应当做什么动作；如果需要并且没有读取，则调用yylex 来获得下一个记号。
2. 使用当前状态，和超前记号(如果需要的话)，解析器决定它的下一个状态，并完成它。这可能导致状态压入栈中，或从栈中弹出来，和导致超前记号被处理或保留。
移进动作是解析器做的最常见的动作。在做移进动作的时候，这里总是有一个超前记号。例如，在状态56 下有这么一个动作:
IF shift 34
这是说，在状态56 下，如果超前字符是IF，则当前状态(56)在栈中被压下去，而状态34 成为当前状态(在栈顶)。超前字符被清除。
归约动作防止栈无限制的增长。在解析器已经见到一个文法的右手端的时候做归约动作是适当的，它准备好宣布它已经见到这个规则的一个实例(instance)，用这个规则的左手端替换它的右手端。有可能需要参考超前记号来决定是否归约，但是通常不需要；实际上，缺省动作(表示为“.”)经常是一个归约动作。
归约动作与单独的文法规则相关联。文法规则也以小整数给出，这导致了一些混淆。动作
. reduce 18
提及的是文法规则18，而动作
IF shift 34
提及的是状态34。
假定要归约的规则是
A : x y z ;
归约动作依赖于左手端符号(symbol)(这里是A)，和右手端符号的数目(这里是3)。要归约，首先从栈顶中弹出三个状态(一般的，弹出的状态数目等于规则右手端符号的数目)。在效果上，这些状态识在识别x、y 和z 的时候压入栈中的，并不再有任何用处。在弹出这些状态之后，开始处理这个规则之前，分析器处在暴露(uncovered)状态下。使用这个暴露状态，和在规则左手端的符号，进行实效上的移进A。获得一个新状态，压入栈中，并继续分析。在处理左手端符号和记号的普通移进之间有一个重要的区别，所以这个动作叫做跳转(goto)动作。特别是，移进清除超前记号，而跳转不影响它。在任何情况下，暴露状态都包含一个条目比如:
A goto 20
导致状态20 被压入栈中，并成为当前状态。
在效果上，归约动作在解析器中“把钟拨回”，从栈中弹出状态，以此回到首次见到这个规则的右手端的那个状态。解析器接着运转，如同它已经在此时见到了左手端那样。如果这个规则的右手端为空，则不从栈中弹出状态: 暴露状态实际上就是当前状态。
归约动作在用户提供的动作和值的处置中也是很重要的。在一个规则被归约的时候，在调整栈之前执行这个规则提供的代码。除了持有状态栈之外，还有另一个栈与它并行运行，它持有从词法分析器和这些动作返回的值。在发生移进的时候，把外部变量yylval 复制到值栈顶上。在从用户代码返回之后，完成归约。在做跳转动作的时候，把外部变量yyval 复制到到值栈顶上。伪变量$1、$2 等提及的就是这个值栈。
其他两个解析器动作在概念上非常简单。接受动作指示整个输入已经查看完了并且它与规定相匹配。这个动作只在超前记号是结束标记的时候出现，并指示出解析器已经成功的完成了它的工作。在另一方面，错误动作表示解析器不能再继续依据规定做解析的状况。已经见到的输入记号，与超前记号一起，不能遵循导致合法输入的任何东西。解析器报告一个错误，并尝试恢复状态并重新开始解析: 错误修复(相对于错误检测)将在第7 节中叙述。
是给出例子的时候了! 考虑下列规定
%token DING DONG DELL
%%
rhyme : sound place
;
sound : DING DONG
;
place : DELL
;
在使用-v 选项调用Yacc 的时候，生成一个叫做y.output 的文件，它包含对解析器的人类可读的描述。对应于上述文法的y.output 文件(去除了结尾处的一些统计)是:
state 0
$accept : _rhyme $end
DING shift 3
. error
rhyme goto 1
sound goto 2
state 1
$accept : rhyme_$end
$end accept
. error
state 2
rhyme : sound_place
DELL shift 5
. error
place goto 4
state 3
sound : DING_DONG
DONG shift 6
. error
state 4
rhyme : sound place_ (1)
. reduce 1
state 5
place : DELL_ (3)
. reduce 3
state 6
sound : DING DONG_ (2)
. reduce 2
注意，除了在每个状态的给出动作之外，在每个状态中还有对正在处理中的解析规则的描述。使用_ 字符指示在每个规则中见到了什么，和什么仍未出现。假定输入是
DING DONG DELL
跟踪解析器在处理这个输入期间的步骤是有教益的。
最初，当前状态是0。解析器需要参照输入来在状态0 下能获得的动作中做出抉择，所以读入了第一个记号DING，它成为超前记号。在状态0 下对记号DING 的动作是“shift 3”，所以状态 3 被压入栈中，超前记号被清除。状态 3 成为当前状态。读入下一个记号DONG，它成为超前记号。在状态 3 下对记号DONG 的动作是“shift 6”所以状态 6 被压入栈中，超前记号被清除。栈现在包含0、3 和6。在状态 6 下，不用参考超前记号，解析器按规则 2 归约。
sound : DING DONG
这个规则在右手端有两个符号。所以从栈中弹出两个状态 6 和3，暴露了状态0。参照状态0 的描述，查找对sound 的跳转，获得了
sound goto 2
；所以状态 2 压入中，成为当前状态。
在状态 2 下，必须读取下一个记号DELL。动作是“shift 5”，所以状态 5 被压入栈中，栈中现在有0、2 和5，超前记号被清除。在状态 5 下，唯一的动作是按规则 3 归约。它在右手
端有一个符号，所以从栈中弹出一个状态5，暴露了状态2。在状态 2 下对规则 3 的左手端place 做跳转到状态4。现在栈包含0、2 和4。在状态4 下，唯一的动作是按规则1 归约。规则 1 右手端有两个符号，所以从栈中弹出两个状态，再次暴露了状态0。在状态0 下，对rhyme 有一个跳转导致分析器进入状态1。在状态1 下，读取输入，获得了结束标记，它在y.output 中用“$end”来指示。在状态1 下在见到结束标记时的动作是接受，成功的结束了解析。
读者可能急切的想知道在面对不正确的字符串比如DING DONG DONG、DING DONG、DING DONG DELL DELL 等的时候解析器如何工作。在这个和其他简单例子中多花点时间，在更复杂的上下文中出现问题的时候解决起来就快速了。
5: 歧义和冲突
如果某些输入字符串可以按两种或更多方式来构造，则这组文法是有歧义的。例如，文法规则
expr : expr '-' expr
是表达算术表达式的一种自然的方式，把两个其他表达式放在一起并在中间的放一个减号就形成了算术表达式。不幸的是，这个文法规则没有完全的规定构造所有复杂输入的方式。例如，如果输入是
expr - expr - expr
规则允许这个输入被构造为
( expr - expr ) - expr
或者是
expr - ( expr - expr )
(第一个叫左结合(association)，第二个叫右结合)。
Yacc 尝试建造解析器的时候检测这种歧义。考虑在给出如下输入的时候解析器所面对的问题是有教益的
expr - expr - expr
当解析器读到第二个expr 的时候，它已经见到的输入是:
expr - expr
匹配上述文法规则的右手端。解析器可以通过应用这个规则来归约输入；在应用了这个规则之后，输入被归约成expr(规则的左手端)。解析器可以接着读取输入的最后部分:
- expr
并再次归约。这种效果是采用了左结合解释。
可供选择的，在解析器见到
expr - expr
它可以延迟应用规则，并继续读取输入直到它见到
expr - expr - expr
它可以接着向最右的三个符号应用规则，把它们归约成expr 并留下
expr - expr
现在这个规则可以再次归约；这种效果是采用了右结合解释。所以，读取了
expr - expr
分析器可以做两种合法的事情，一次移进或一次归约，在它们之间无法抉择，这叫做移进/归约冲突。也可能发生解析器选择两个合法归约动作的事情；这叫做归约/归约冲突。注意永远不会有什么“移进/移进”冲突。
在有移进/归约或归约/归约冲突的时候，Yacc 仍然生成解析器。它是通过在需要选择地方选择有效步骤之一而完成的。描述在一个给定状况下做如何抉择的规则叫做去歧义规则。
Yacc 缺省的调用两个去歧义规则:
1. 在移进/归约冲突中，缺省是做移进。
2. 在归约/归约冲突中，缺省是归约(按输入顺序)更早先的文法规则。
规则 1 暗示了只要有选择就推迟归约、以利于移进。规则 2 给予用户对解析器在这种情况下的行为的非常粗糙的控制，但是归约/归约冲突应当尽可能的避免。
引发冲突的原因可能是输入或逻辑中的错误，也可能因为尽管文法规则是一致的、但要求比Yacc 能构造的更加复杂的解析器。使用在规则内的动作也可能导致冲突，如果必须在解析器可以确定识别了哪个规则之前做这个动作的话。在这些情况下，去歧义规则的应用是不适当的，并导致不正确的解析器。为此，Yacc 总是报告规则 1 和规则 2 解决的移进/归约和归约/归约冲突的数目。
一般的说，只要有可能应用去歧义规则生成正确的解析器，就有可能重写文法规则，使对同样的输入没有冲突。为此，多数以前的解析器生成器认为冲突是致命错误。我们的经验是这种重写是有些不自然的，并生成更慢的解析器；所以Yacc 即使在有冲突存在情况下还是生成解析器。去歧义规则的一个例子是，考虑涉及“if-then-else”构造的编程语言的一个片段:
stat : IF '(' cond ')' stat
| IF '(' cond ')' stat ELSE stat
;
在这些规则中，IF 和ELSE 是记号，cond 是描述条件(逻辑)表达式的非终结符号，而stat 是描述语句的非终结符号。第一个规则叫做简单-if 规则，第二个叫做if-else 规则。
这两个规则形成一个歧义构造，因为如下形式的输入
IF ( C1 ) IF ( C2 ) S1 ELSE S2
可以依据两种方式构造:
IF ( C1 ) {
IF ( C2 ) S1
}
ELSE S2
或
IF ( C1 ) {
IF ( C2 ) S1
ELSE S2
}
第二个解释是多数编程语言对这个构造的解释。每个ELSE 都与最近的前面的“没有ELSE 的” IF 相结合。在这个例子中，考虑解析器见到
IF ( C1 ) IF ( C2 ) S1
并正在查看ELSE 的状况。它可以立即按简单-if 规则归约得到
IF ( C1 ) stat
并接着读取余下的输入，
ELSE S2
并按if-else 规则规约
IF ( C1 ) stat ELSE S2
。这导致输入的上述组合的第一种情况。
在另一方面，ELSE 可以被移进，读取S2，并接着把
IF ( C1 ) IF ( C2 ) S1 ELSE S2
的右面部分按if-else 规则规约得到
IF ( C1 ) stat
它可以按简单-if 规则规约。这导致输入的上述组合的第二种情况，这是通常想要的。
一旦解析器可以做两种有效的事情- 就有移进/规约冲突。应用去歧义规则 1 告诉解析器在这种情况下做移进，这导致想要的组合。
这种移进/归约冲突只发生在特定的当前输入符号ELSE，和特定的已经见到的输入的时候，比如
IF ( C1 ) IF ( C2 ) S1
的情况下。一般的说，有很多种冲突，每个都是同一个输入符号和一组以前读入的输入相关联。使用解析器的状态来表现这些以前读入的输入。
通过检查冗余(-v)选项输出文件Yacc 的冲突消息是最好理解的。例如，对应于上述冲突的输出可能是:
23: shift/reduce conflict (shift 45, reduce 18) on ELSE
state 23
stat : IF ( cond ) stat_ (18)
stat : IF ( cond ) stat_ELSE stat
ELSE shift 45
. reduce 18
第一行描述这个冲突，给出状态和输入符号。随后是普通的状态描述，给出在这个状态中活跃的文法规则和解析器动作。回想下划线标记出了文法规则中已经见到的部分。所以在这个例子中，在状态23 中解析器已经见到的输入对应于
IF ( cond ) stat
并且展示了在此时活跃的两个文法规则。解析器可以做两种可能的事情。如果输入符号是ELSE，可能移进到状态45。状态45 在它的描述中有下面这一行
stat : IF ( cond ) stat ELSE_stat
因为在这个状态下ELSE 已经被移进。回到状态23 中，“.”描述了一个可供选择的动作，如果输入符号在上述动作中没有明确的提及到则做这个动作；所以，在这种情况下，如果输入符号不是ELSE，则解析器将按文法规则18 归约:
stat : IF '(' cond ')' stat
再次注意紧随“shift”命令之后的数提及的是其他状态，而紧随“归约”命令的数提及的是文法规则编号。在y.output 文件中，规则编号在可以被归约的这些规则之后打印。在多数状态中，最有可能存在归约动作的是缺省命令。遇到未期望的移进/归约冲突的用户可以查看冗余输出来决定缺省动作是否合适。在真正的艰苦条件下，用户可能需要知道比这里覆盖的更多的解析器的行为和构造。在这种情况下，可以参考理论文献[2, 3, 4]；咨询本地技术领袖也是合适的。
6: 优先级
在一种常见的情况下，上述解决冲突的规则是不充分的；这发生在分析算术表达式中。算术表达式中多数经常使用的构造可以用操作符优先级概念(notion)、连同左或右结合性(associativity)的信息来自然的描述。使用带有适当的去歧义规则的歧义文法建造的解析器，比使用无歧义文法构造出的解析器更快速和容易写。基本概念是对想要的所有二元或一元操作符写如下形式的文法规则
expr : expr OP expr
和
expr : UNARY expr
。这建立了一个非常有歧义的文法，带有很多解析冲突。作为去歧义规则，用户指定所有操作符的优先级或粘连强度，和二元操作符的结合性。这种信息足够Yacc 依据这些规则解决解析冲突，并构造实现了想要的优先级和结合性的解析器。
在声明段中把优先级和结合性附加到记号上。在开始于Yacc 关键字: %left、%right
或%nonassoc，并跟随着记号列表的记号定义行中完成这项工作。所有在同一行的记号都被假定有相同的优先级级别和结合性；这些行按递增的优先级或粘连强度次序列出。所以
%left '+' '-'
%left '*' '/'
描述了四个算术操作符(算符)的优先级和结合性。加法和减法是左结合的，并有比星号和斜杠更低的优先级，它们都是左结合的。使用关键字%right 描述右结合操作符，使用关键
字%nonassoc 描述不能与自身结合的操作符，如Fortran 的 .LT.；所以，
A .LT.
B .LT. C
在Fortran 中是非法的，这种操作符在Yacc 中用关键字%nonassoc 描述。作为这些声明的行为的例子，描述
%right '='
%left '+' '-'
%left '*' '/'
%%
expr : expr '=' expr
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| NAME
;
可以用来构造输入
a =
b = c*d - e - f*g
为如下:
a = (
b = ( ((c*d)-e) - (f*g) ) )
在使用这个机制的时候，一元操作符一般必须给出一个优先级。有时一元操作符和二元操作符有相同的符号名字表示，但是有不同的优先级。一个例子是一元和二元…-?；一元减法可以给予同乘法相同的结合强度，甚至更高，而二元减法有比乘法更低的结合强度。关键字%prec 改变与特定文法规则关联的优先级级别。%prec 直接出现在文法规则主体之后，在动作或结束的分号之前，并跟从一个记号名字或文字。它导致文法规则的优先级变成随后的记号名字或文字的优先级。例如，要使一元减法与乘法有相同的优先级，则规则类似于:
%left '+' '-'
%left '*' '/'
%%
expr : expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '-' expr %prec '*'
| NAME
;
用%left、%right 和%nonassoc 声明的记号不需要但可以用%token 做同样的声明。Yacc 使用优先级和结合性来解决解析冲突；它们引起去歧异规则。形式上，规则工作如下:
1. 为有这种声明的这些记号纪录优先级和结合性。
2. 优先级和结合性与每个文法规则相关联；它是这个规则主体的最后的记号或文字的优先级和结合性。如果使用了%prec 构造，它替代这种缺省。一些文法规则可以没有与之关联的优先级和结合性。
3. 在有归约/归约冲突时候，或者有移进/归约冲突并且输入符号或者文法规则之一没有优先级和结合性的时候，则使用在章节开始处给出的两个去歧义规则，并报告冲突。
4. 如果有移进/归约冲突，并且文法规则和输入符号有与之关联的优先级和结合性，则以有利于关联着更高优先级的动作(移进或归约)的方式解决冲突。如果优先级相同，则使用结合性；左结合暗示归约，右结合暗示移进，而无结合暗示错误。
用优先级解决的冲突不计数到Yacc 报告的移进/规约冲突中。这意味着在优先级规定中的错误可以掩饰在输入文法中的错误；对优先级最好持保守的态度，并以本质上的“烹调书”方式使用它们，直到获得了某些经验。在判定解析器实际上是否在做打算让它做的事情时y.output 文件是非常有用的。
7: 错误处理
错误处理是一个非常困难的领域，很多问题是语义问题。例如，当找到一个错误的时候，可能必须收回解析树存储，删除或更改符号表条目，和典型的设置开关来避免生成进一步的输出。
在找到一个错误的时候就停止所有处理是很少能被接受；继续扫描输入来找到进一步的语法错误是更加有用的。这导致在一个错误之后使解析器“重新启动”的问题。做这件事的常规的算法涉及到从输入字符串中丢弃一些记号，和尝试调整解析器让输入可以继续。
为了允许用户在这个过程中做某些控制，Yacc 提供了一个简单但相当一般性的特征。记号名字“error”保留给了错误处理。这个名字可以用在文法规则中；在效果上，它提出了预期的错误和修复发生的位置。解析器弹出它的栈直到进入记号“error”合法的一个状态。它接着表现得如同记号“error”是当前超前记号一样，并进行遇到的动作。超前记号接着重置为导致这个错误的记号。如果没有指定特殊的错误规则，在检测到错误的时候处理停止。
为了防止连锁(cascade)的错误消息，解析器在检测到一个错误之后，保持在错误状态下直到成功的读取并移进了三个记号。如果在解析器已经在错误状态下的时候检测到一个错误，则不给出消息，并且安静的删除输入记号。
作为一个例子，如下形式的规则
stat : error
在效果上，意味着在语法错误的时候，解析器将尝试跳过在其中见到错误的语句。更确切的，解析器将向前扫描，查找可能合法的遵从一个语句的三个记号，并在其中第一个上开始处理；如果不能充分的辨别出语句的开始，它可能在一个语句的中作出失败的开始，并结束于报告第二个错误，而这里实际上没有错误。
对这些特殊的错误规则可以使用动作。这些动作可以尝试重新初始化表格，收回符号表空间等。