原文链接：yacc

术语

简介

计算机程序输入通常有一些结构，实际上，每一次电脑程序输入可以被认为是定义了一种“输入语言”来接收。一门输入语言可能像一门变成语言那么复杂，也可能像数字序列那么简单。不幸的是，常见输入设施是受限制的，难以使用的，并且经常检查输入的校验是不严格的。

Yacc提供了一种用来描述计算机程序输入的通用工具。yacc的使用者指定了需要的输入结构，跟被调用的代码一起，作为每个这样接收的结构。yacc把这样一种说明转化为子程序来处理输入过程；经常地，通过这样的子程序可以很方便很合适地用来处理用户应用的大多数流控制场景。

yacc生产的输入子程序可以称为一种用户提供的程序来返回下一个基本输入项。因此，用户可以指定他的输入按照个人输入字符，或者按照更高级别的结构比如说名称或者数字。这个用户提供的程序也可以处理惯用的特性，比如说评论和延续惯例，用来对抗简单的文法规范。

yacc是使用portableC编写的。规范类接收一个非常通用的：LALR(1)语法，使用消除规则。

除了C,APL,Pascal,RATFOR等编译器。yacc也已经被使用在量级更小、更不常见的语言，包括照相机语言，多桌面计算器语言，文档检索系统，公式编辑器调试系统。

0：介绍

yacc为利用计算机程序输入的结构提供了一个通用的工具。yacc使用者准备了一种输入处理的规范，包括描述输入结构的规则，这些规则被识别调用的代码，一个低级别程序来执行基本的输入。yacc接着会生成一个函数来控制输入过程。这个函数，被称为一个解析器，调用用户提供的低级别的输入程序（词法分析器）从输入流挑选出基本项（被称为tokens）。这些tokens根据输入结构规则来组成，称为语法规则；当其中一个规则被识别，然后用户代码提供了这种规则，会执行相应的动作；这些动作拥有返回结果和使用其他动作的值的能力。

yacc由编写的方言的C语言编写，动作和输出的子程序也都是用C语言。此外，yacc的很多语法约定也跟随了C语言。

输入规范的主体是一个语法规则集。每一条规则描述了一个可允许的结构并赋予它一个名字。比如说，一个语法规则可能是如下：

date
:
month_name
day
','
year
;

在这里，date，month_name，day，year代表了输入处理关心的结构；可以推测出，month_name，day，year被定义在else的地方。符号","被单引号修饰，这意味着这个符号会在输入中的字面上出现。冒号和分号仅仅是作为规则中的标点符号，并没有意义来控制输入。因此，合理的定义，像这种输入

July
4, 1776

会跟上述规则比较匹配。

输入处理的一个重要部分由词法分析器来实现。这个用户程序读取输入流，识别低级别结构体，把这些tokens传递给解析器。由于历史原因，一个能被词法分析器识别的结构体称之为终端符号，同时被解析器parser识别的结构体被称为非终止符号。为了避免歧义，终端符号通常作为tokens被引用。

选择词法分析器还是语法规则来识别结构体，其差别是值得被考虑的。比如说，这些规则：

month_name
:
'J' 'a' 'n'
;
month_name
:
'F' 'e' 'b'
;
. . .
month_name
:
'D' 'e' 'c'
;

可以被使用在上面的例子中。词法分析器只会识别单独的字母，并且month_name将会是一个非终止符号。这种低级别的规则会导致浪费时间和空间，也会使得规范复杂化，导致超出yacc的处理能力。通常，词法分析器会识别月份名字，然后返回一个指示表名month_name被看见；在这种情况下，month_name将是一个token。

Literal characters（原义字符）比如说","必须也被传递到词法分析器中，也会被考虑成tokens

规范文件是非常灵活的。它非常可靠简单地添加上面的例子，这样的规则：

date
:
month '/' day '/' year
;

允许7 / 4 / 1776作为下面July 4, 1776的同义词

在大多数情况下，这个新规则可以被使用最小的代价”运送“到工作系统，并且对于破坏已有的输入的危险性是最小的。

读输入可能不符合规范。这些输入错误采用从左到右扫描的方法，理论上可以尽可能早地被检测到；因此，不只是减少了错误的读和计算的输入数据的几率，而且错误数据通常可以被很快地发现。错误处理，作为被提供的输入规范的一部分，允许错误数据的重新进入，或者跳过错误数据之后继续进行输入处理。

在一些情况下，当制定了一系列规范后，yacc无法生成一个解析器。比如说，规范可能自我矛盾，或者他们需要一个更强力的识别机制来保证yacc可用。前者代表涉及错误；后者经常可以修正通过制定更强大的词法分析器，或者通过重写语法规则。因为yacc无法处理所有可能的规范，它的功能相比起来更倾向于在相似的系统中发挥；而且，这些结构对于yacc来说很难处理，对人类来说处理起来也很难。有些用户已经提出，为他们的输入制定有效的yacc规范的原则，揭示了程序发展的早期的概念或设计错误。

1：基本规范

命名适用于tokens和非终止符号。yacc要求命名被声明成这样。另外，基于第三章讨论的原因，通常包含词法分析器作为规范文件的一部分是可取的；并且包含其他程序可能也是有用的。因此，每个规范文件由三个部分组成：声明，语法规则，和程序。这些部分被用两个百分号"%%"分隔开来标记。（百分号”%“通常被用在yacc规范里面作为一种逃逸字符）

也就是说，一个完整的规范文件长这样

declarations
%%
rules
%%
programs

声明（declarations）部分可能是空的。此外，如果程序（programs）部分被省略了，第二个%%可能也被省略掉；

因此，最小的合法yacc规范是

%%
rules

空白页，退格和新行会被忽略掉，除非这些不会出现在命名或者多字符保留符号里面。注释可能出现在任何命名合法的地方；C语言和PL/I语言中，它们会被/* ... */包裹。

规则rules部分由一个或多个语法规则。一个语法规则有这样的格式：

A : BODY;

A代表一个非终止符的命名，BODY代表零值或者其他命名和字面量的顺序。冒号和分号是yacc的标点符号。

命名可能是任意长度的，并且由字母组成，点号"."，下划线"_"，还有非初始化数字。大写小写字母是独特的。一个语法规则体可能代表tokens或者非终止符号。

一个字面量包含一个被单引号" ' "。就像C语言，反斜杠""在字面量里面是一个逃逸字符，并且所有的C语言逃逸符号是公认的。因此

'n'
newline
'r'
return
'''
single quote ``'''
'\'
backslash ``''
't'
tab
'b'
backspace
'f'
form feed
'xxx'
``xxx'' in octal

因为很多技术原因，NUL字符（''或者0）在语法规则中从不应该被使用。

如果在左手边有很多个相同的语法规则，竖线"|"可以被用来避免重复写左手边。此外，一个规则的尾部的分号可以在一个竖线前被丢弃。因此语法规则

A
:
B
C
D
;
A
:
E
F
;
A
:
G
;

可以给yacc提供成这样

A
:
B
C
D
|
E
F
|

没必要所有的左侧相同的语法规则一起出现在语法规则部分，尽管这样可以让输入变得更可读，并且修改更简单。

如果一个非终止符号匹配到空的字符串string，这种可以被表达成明显的方式：

empty :
;

命名代表了tokens必须被声明；这可以在声明（declarations）部分被书写得最简单。（看第三、五、六章）

%token
name1
name2 . . .

每一个在声明（declarations）部分未被定义到的命名name会被假定为一个非终止符号。每一个非终止符号必须出现在至少一个规则的左侧。

对所有的非终端符号来说，第一个被称为起始符号，有特别的重要性。解析器parser被设计来识别开始符号；因此，这个符号代表了被语法规则描述的最长，最通用的结构。默认来说，起始符号是在rules规则模块的第一个语法规则的左侧。在声明（declarations）模块明确声明起始符号很可能，事实上也可取，使用%start 关键词：

%start
symbol

parser解析器的输入结束事件由一个特殊的token来通知，称为结束标记。如果这些tokens符号指向（但是不包含）结束标记，形成一个结构来匹配开始符号，解析器parser函数在看到结束标记后返回它的调用者caller；它接收输入。如果结束标记出现在任何其他上下文中，这是一个错误error。

用户提供的词法分析器的工作职责是在合适的时候返回结束标记；看下面的第三章。通常结束标记代表一些合理的明显的I/O状态，例如说"end-of-file"或者"end-of-record"

2: Actions动作

对于每一条语法规则，在每一次输入流识别到一条规则的时候，用户可能会关联上一些动作行为被执行。而且，预期词法分析器会返回tokens的值

一个行为是C语言的一个专用描述，像这种可以做输入和输出的，并且修改外部向量和变量的，叫子程序。一个行为动作被一个或多个声明指定，被花括号包围。例如：

A
:
'('
B
')'
{
hello( 1, "abc" );
}
XXX
:
YYY
ZZZ
{
printf("a messagen");
flag = 25;
}

上述这两种就是包含动作的语法规则。

为了帮助actions和解析器parser的容易交流，动作action声明被轻微修改了。美元符号"$"被用来作为一个yacc上下文的信号。

action动作很常见地给一些值设置伪变量"$$"来返回一个值，action动作可能使用伪变量$1和$2，...，指的是被一个规则rule右侧的部分返回的值，变量是从左到右读取的。因此，如果规则是下面这样

A
:
B
C
D
;

比如说，$2具有的值是由C返回的，那么$3是由D返回的。

就像一个更具体的例子，考虑一个规则：

expr
:
'('
expr
')'
;

这条规则返回的值通常是expr在圆括号中返回的值。这可以被标记为：

expr
:
'('
expr
')'
{
$$ = $2 ;
}

默认来说，一个规则的值是它第一个元素的值($1)。因此，下面语法规则的形式经常不需要有一个明确的动作。

在上面的例子中，所有的actions动作出现在rules规则末尾。有时候，在一个规则被完全解析之前获得控制是可取的。yacc允许一个动作被写在一个规则的中间或者结尾处。这个规则被假定为返回一个值，通过通常的机制，通过它右侧的动作actions可以访问这个值。反过来，它可能通过符号来访问值返回给左侧的值。因此，在这个规则：

A
:
B
{
$$ = 1;
}
C
{
x = $2;
y = $3;
}
;

影响是设置x为1，设置y为C返回的值。

不终止一个rule规则的actions动作实际上是由yacc处理的，通过产生一个新的非终止符号名称name，然后一个新规则rule匹配上这个名称name为空字符串。这个内部动作是通过识别这个的额外的规则来激发的。yacc实际上把上面这个例子当成它已经被写成这样了：

$ACT
:
/* empty */
{
$$ = 1;
}
;
A
:
B
$ACT
C
{
x = $2;
y = $3;
}
;

在很多应用中，输出并没有被动作actions直接做完；rather（准确地说），一个数据结构，例如一个解析树，是在内存中被构造出来的，在输出结果被生成之前对其应用转换。解析树是极其容易构造的，给予程序来构建和维护预期的树结构。例如，假设有一个C函数节点，

node( L, n1, n2 )

被写来让调用创建一个带有L标签的节点，还有n1和n2后代子节点，然后返回最新创建的节点的索引。然后解析树可以通过提供动作actions被建出来，比如说在规范中：

expr
:
expr
'+'
expr
{
$$ = node( '+', $1, $3 );
}

用户可以定义其他通过动作actions使用变量。声明和定义可以出现在声明部分，包裹在%{和%}中间。这些声明和定义有全局的范围，所以它们被熟知在动作声明和词法分析器。例如：

%{
int variable = 0;
%}

这个可以被放在声明部分，让所有的动作都可以访问到变量。yacc解析器只使用命名names以"yy"开头；用户应该避免这些命名。

在这些例子中，所有的值都是integer：其他类型的值的讨论会被放在第十章

3：Lexical Analysis词法分析

用户/使用者必须提供一个词法分析器来读取输入流并且传递tokens（如果期望，可以带上values）

给解析器。词法分析器是一个叫做yylex的整数类型值的函数。函数返回一个整数型，token号，代表读取到的token类别。如果有一个值value关联到那个token，它应该被分配给外部变量yylval。

解析器和语法分析器必须约定这些token号按顺序排列，因为它们之间发生交流。号码可能被yacc选中，或者被使用者选中。无论哪种情况，C语言的"#define"机制被用来允许词法分析器象征性地返回这些号码。比如说，假设一个命名为 DIGIT的token已经被定义在yacc规范文件中的声明部分。词法分析器的相关部分可能长这样：

yylex(){
extern int yylval;
int c;
. . .
c = getchar();
. . .
switch( c ) {
. . .
case '0':
case '1':
. . .
case '9':
yylval = c-'0';
return( DIGIT );
. . .
}
. . .

目的是返回一个DIGIT的token号码，并且一个跟digit数值型的值相等的值。提供词法分析器代码被放置在规范文件的程序章节中，标识符DIGIT将会被定义成token号码，关联上token DIGIT。

这种机制可以生成清晰，更容易修改的词法分析器；唯一的缺陷是需要避免使用任何的C语言或者parser解析器语法中的保留的和有意义的token命名；比如说，当词法分析器被编译的时候，if 或者while符号的命名的使用将会几乎确定导致严重的困难。token命名error被保留来错误捕获，不应该被天真地使用（看第七章）。

就像上面提高的，token号码可能被yacc或者使用者选中。在默认的场景下，号码是被yacc选中的。字面量字符的默认token号在本地字符集中 是数字值类型的字符。其他命名被指定的token numbers从257开始。

因为一些历史原因，结束标记必须有token number 0或者负数。这种token number不能被使用者重新定义；因此，所有词法分析器必须准备好返回0或者负数作为一个token number，当到达他们输入的结尾。

一个非常有用的构造词法分析器的工具是由Mike Lesk开发的Lex 程序。这些词法分析器被设计来跟yacc解析器一起密切工作的。为这些词法分析器的更规范使用了常规的表达式而不是语法规则。Lex可以被简单使用，来生成很复杂的词法分析器，但存在一些语言（例如FORTRAN）不适用任何理论框架，它们的词法分析器必须被手工制作。

4：Parser如何工作？

yacc把规范文件变成一个C程序，根据规范提供的输入来解析。转换规范到parser解析器的算法是复杂的，在这里不会被讨论（可以看引用的更多信息）。然而，parser本身相对简单，明白它怎么工作的，不是非常严格的必要，不过也要对待错误恢复和使歧义的地方更加可理解。

yacc生产的parser解析器包含使用一个栈的有限的状态机。解析器parser也读取和脊柱下一次输入的token（叫做先行token）。当前的状态总是在栈顶的那个元素。有限状态机的状态是小integer标签；初始化时，机器是在状态0，栈只包含一个状态0，没有先行token被读取到。

机器只有四个动作可用，叫做shift（移位），reduce（减少），accept（接受），还有error（出错）。解析器的动作按这几步完成：

1. 根据当前状态，解析器parser决定它是否需要一个先行（lookahead）token来决定什么动作应该被完成；如果它需要1，但是没有1，它调用yylex来获取下一个token。

2. 使用当前状态，如果需要先行token，解析器依赖它的下一个动作，然后执行官。这样的结果是状态被推到栈上，或者出栈，然后先行token被执行或者不管。

shift（移位）操作是解析器最常见的操作。任何时候只要有shift操作，总是有一个先行token。例如，在状态56可能有一个操作：

IF
shift
34

这是在说，在状态56，如果先行token是IF，当前状态56被推到栈底，然后状态34成为当前状态（在栈顶）。最后先行token被清除。

reduce（减少）操作可以防止栈无限制地增长。减少操作是恰当的，当解析器已经看到右手边的语法规则，然后准备好了去宣布它已经看到了规则的一个实例，把右手边用左手边来替代。查阅先行token来决定是否减少可能是必要的，但是通常它没有；实际上，默认操作（由"."代表）经常是一个reduce操作。

reduce动作跟独特的语法规则有关。语法规则也是被赋予了小整形数字，导致了一些困惑。这个动作关联了语法规则18，

.
reduce 18

同时这个动作操作关联了状态34

IF
shift 34

假设被reduce的规则是A: x y z ;

reduce操作依赖左手边的标识（在这里是A），还有右手边的标识的数量（这里是3）。

为了reduce，首先从栈中出栈栈顶的三个状态（通常，状态数量出栈跟规则右侧的的标识数量一致）事实上，这些状态是识别到x，y，z的时候入栈的那些，并且不再提供任何有用的用途。这些状态出栈后，有一个状态没有被覆盖，是在解析器未开始进入处理规则之前的状态。使用这个未覆盖的状态，规则左侧的标识，执行A的移位操作的影响。一个新的状态被获得了，被推入栈，然后继续解析。处理左手边的标识和一个token的一个普通移位之间是有重大区别的，无论如何，这个操作被称作是一个goto操作。未覆盖的状态包含一个入口，例如：

A
goto 20

导致状态20被推入栈，然后成为当前的状态。

实际上，reduce操作在解析中"时钟回拨"，把状态出栈，回到规则的右手边被第一次解析器看到的状态。解析器然后表现得就像它当时已经看过左侧的样子。如果规则的右手边是空的，没有状态被出栈，为被覆盖的状态实际上是当前状态。

reduce操作在用户提供的动作和值的处理上也很重要。当一个规则被reduce处理，在栈被调整前，提供给规则的代码会被执行。除了栈持有状态，另一个并行运行的栈，持有了来自词法分析器和操作动作返回的值。从用户代码返回后，reduce操作被执行了。当goto操作被执行完，外部变量yyval被复制进value值栈。伪变量$1,$2等等，指向了值栈。

另外两个解析器操作动作在概念上更简单。接受动作表明整个输入已经被看见并且它匹配了规范。这个动作只出现在当先行token是结束标识符的时候，并且表明解析器已经成功地完成它的工作。报错动作，从另一方面来说，代表解析器无法再继续根据规范解析的一个地方。输入token它已经看到，连同先行token一起，无法被任何结果是正确的合法输入来跟踪了。解析器报告一个错误，试图去恢复这种情况并重新开始解析：错误恢复（与错误探测相反）会在第七章讲到

是时候来一个例子了！考虑这个规范

%token
DING
DONG
DELL
%%
rhyme
:
sound
place
;
sound
:
DING
DONG
;
place
:
DELL
;

当yacc被调用到-v的选项，一个被称为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

跟着这些解析器处理输入的步骤是有益的。

首先，当前状态是state 0。解析器需要涉及到输入，为了决定动作actions在状态 0之间可用，所以第一个token，DING，读取了，成为先行token。DING在状态0的动作是"shift 3"，所以状态3被推进栈顶，然后先行token被清除。状态3变成当前的状态。下一个token，DONG，读取了，成为先行token。token DONG上的状态3的动作是"shift 6"，所以状态6入栈，然后先行token被清除。现在栈中包含状态0，3，6。在状态6，甚至没有考虑先行，解析器由规则2来reduce。

sound
:
DING
DONG

这条规则在右手边有两个标识，所以两个状态6和3被出栈，没覆盖状态0。考虑到状态0的描述，在sound上寻找到一个goto，因此状态2入栈，成为当前状态。

sound
goto
2

在状态2，下一个token是DELL，必须被读取到。这个动作是shift 5，所以状态5被推入栈，目前栈中有0，2，5，然后先行token被清除。在状态5，唯一的动作是由规则3执行reduce。这条规则有一个标识在右手边，所以状态5出栈，状态2没有被覆盖到。place上的状态2的goto，规则3的左侧，是状态4。现在栈包含了0，2，4.在状态4，唯一的动作是被规则1执行reduce。规则1右侧有两个标识，所以栈顶两个状态出栈，再次没覆盖到状态0。在状态0，有一个goto在rhyme，导致解析器进入状态1。在状态1，输入被读取；结束标记被获取，这是由y.output文件中的"$end"符号表明的。当结束标记被看到接收到的时候，状态1的动作是成功地结束了解析。

读者被敦促来思考一下当面临这种不正确字符串，像"DING DONG DONG,DING DONG,DING DONG DELL DELL等"时，解析器会怎样工作？当问题出现在更多复杂上下文时，花几分钟的时候思考和其他简单例子可能会得到回报。

5：（Ambiguity and Conflicts）不明确和冲突

如果有一些输入的字符串可以被构造成两种或者更多种不同的方式，这套语法规则就是模棱两可的。例如，这个语法规则：

expr
:
expr
'-'
expr

这是一种很自然的方式来表达一种事实：组成算数表达式就是让另外两个表达式通过减法符号结合到一起。不幸的是，这种语法规则不能完全指定所有复杂的应该被构造的输入方式。例如说，如果输入是

expr
-
expr
-
expr

规则允许输入可以被构造成以下两种：

(
expr
-
expr
)
-
expr
expr
-
(
expr
-
expr
)

前者称为左连接，后者称为右连接。

当yacc试图构建解析器时，会探测这种不确定性。当yacc接收到这种输入时，考虑解析器所面临的问题是有益的。

expr
-
expr
-
expr

当解析器已经读取到第二个expr时，它已经看到的输入是下面这个，匹配到上述语法规则的右侧。

expr
-
expr

解析器可以通过应用这个规则来reduce输入；应用完这个规则后；输入被reduce到expr(规则的左侧)。然后解析器会读取到输入中的最后部分：然后再次reduce。

-
expr

这个影响是采用左连接解释。

或者，当解析器已经看见expr  -  expr时，它可以推迟规则的立刻应用，然后继续读取输入直到它看见：

expr
-
expr
-
expr

它可以然后应用规则到最右侧的三个标识，reduce它们到expr，然后剩下

expr
-
expr

现在规则可以被再次reduce；影响是采用右连接解释。因此，已经读到

expr
-
expr

时，解析器可以做两件合法的事情，一个shift操作或者是一个reduce操作，并且没有方法来决定它们。这就叫做shift/reduce冲突。当解析器有两个合法的reduce的选择时，冲突也可能会发生；这种叫做reduce/reduce冲突。注意，永远不可能有任何的"shift/shift"冲突。

当有shift/reduce或者reduce/reduce冲突时，yacc仍然会产生解析器parser。它通过在可以选择的地方选择其中一个有效的步骤来实现这一点。给定一个场景，一个规则描述出采用哪个选择。叫做消除二义性规则。

yacc默认上会调用两个消除二义性的规则：

规则1. 在一个shift/reduce冲突时，默认选择shift。

规则2. 在一个reduce/reduce冲突时，默认reduce更早的语法规则（按照输入顺序）

规则1意味着任何时候有选择，reduce操作会被推迟，有利于shift操作。

规则2在这种场景下，给使用者相当粗糙的解析器的行为的控制，但是reduce/reduce冲突任何时候应该尽可能避免。

冲突可能出现在错误的输入或者逻辑，或者因为语法规则虽然一致，但需要一个比yacc可以构造的更复杂的解析器。在规则内动作的使用也可能会导致冲突，如果这个动作必须在解析器可以确定哪个规则被识别之前完成。在这些案例中，消除二义性规则的应用就不适用了，导致就这样一个不正确的解析器。由于这个原因，yacc总是报告出被规则1和规则2解决的shift/reduce和reduce/reduce冲突的数量。

通常，任何时候都可能应用消除二义性规则来生成一个正确的解析器，也可能重写语法规则以致于同样的输入能被读取但是没有冲突。因为这个原因，大多数前置解析器生成器已经把冲突考虑成事故错误了。我们的经验建议，这种重写多少有些不自然，并且生成更慢的解析器；因此，yacc甚至会在冲突存在的情况下生成解析器。

作为一个消除二义性规则的强大的例子，考虑一个来自变成语言的片段，涉及到一个"if-then-else"结构：

stat
:
IF
'('
cond
')'
stat
|
IF
'('
cond
')'
stat
ELSE
stat
;

在这些规则里面，IF和ELSE是token，cond是一个描述条件（逻辑）表达式的非终止符号，然后state是一个描述状态的非终止符号。第一个规则将会被称为simple-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。它可以立马由simple-if规则的reduce操作来得到：

IF
(
C1
)
stat

然后读取剩下的输入：

ELSE
S2

然后由if-else规则执行reduce操作。

IF
(
C1
)
stat
ELSE
S2

这样会导致上述两种输入分组方式中的第一种。

另一方面，ELSE可能被shift，S2被读取，然后右手边的部分可以被if-else规则reduce后，最后可以被simple-if规则再次reduce。

IF
(
C1
)
IF
(
C2
)
S1
ELSE
S2
右侧被if-else规则reduce后：
IF
(
C1
)
stat

这种会导致上述两种输入分组方式的第二种，也是通常个被预期的结果。

解析器再一次可以坐两种合法的事情-有shift/reduce冲突。在这种情况下，消除二义性规则1的应用告诉解析器执行shift操作，会导致按预期来分组。

这种shift/reduce冲突值出现在当存在一个特别的当前输入标识ELSE时，特殊的输入已经被看见，比如说：

IF
(
C1
)
IF
(
C2
)
S1

通常，可能存在很多冲突，然后每一个都会跟一个输入标识和一套前置读取输入关联。前置读取输入是以解析器的状态为特点的。

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，很可能shift到状态45。状态45将会拥有这一行：作为它描述的一部分，从ELSE被shift进这个状态后。

stat
:
IF
(
cond
)
stat
ELSE_stat

回到状态23，可选的动作，被描述成"."，如果输入标识没有在上述动作中被明确提及，它将会被执行；因此，在这种情况下，如果 输入标识不是ELSE，解析器会被语法规则18执行reduce。

stat
:
IF
'('
cond
')'
stat

再次注意，"shift"指令后面的数字指的是其他状态，同时，"reduce"指令后面的数字指的是语法规则数字。在y.output文件中，规则数字在这些规则可以被reduce后被打印出来。在大多数的一种状态中，状态中的reduce动作的可能性是最大的，这会是默认的指令。使用者遭遇到非期望的shift/reduce冲突时将可能想去看冗长的输出，来决定默认的动作是否恰当。在非常困难的情况下，使用者需要知道更多关于解析器的行为和结构的信息，这里不提供这些信息。在这种情况，理论引用[2,3,4]的其中一个可以查阅；本地guru服务可能也是合适的。

6：Precedence（优先级）

有一个普遍的场景，上面给出的用来解决冲突的规则是不够充分的；就是在解析算术表达式的时候。大多数算术表达式常用的构造可以自然地被操作者的优先级的概念描述出来，包括左结合或者右结合的信息。结果是模棱两可的语法加上恰当的消除二义性规则可以被用来创建比通过非歧义的语法更快更简单的解析器。基本概念是把所有的二元和一元运算符预期的语法规则写成这种格式：

expr
:
expr
OP
expr
and
expr
:
UNARY
expr

这里创建了一个非常歧义的语法，还有很多解析冲突。至于非歧义的规则，用户对所有的运算符指定优先级，或者绑定强度，还有二运运算符的结合。这种允许yacc按照这些规则来解决解析冲突的信息是充分的，并且构造了一个实现了预期的优先级和结合性的解析器。

优先级和结合性是附属在声明（declarations）部分的tokens上的。这是由一系列以yacc关键字:%left,%right,或者%nonassoc等开头的行完成的，接着是tokens列表。同一行的所有tokens被认定为具有相同的优先级水平和结合性；这些行被按照递增的优先级或者绑定强度的顺序来排列。因此，

%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立刻出现在语法规则的body之后，在动作或者结束的分号之前，接着是一个token名称或者字面量。它导致了这条语法规则的优先级成为接下来的token名称或者字面量的优先级。比如说，让一元减法具有跟乘法相同的优先级，规则可能类似：

%left
'+'
'-'
%left
'*'
'/'
%%
expr
:
expr
'+'
expr
|
expr
'-'
expr
|
expr
'*'
expr
|
expr
'/'
expr
|
'-'
expr
%prec
'*'
|
NAME
;

一个被%left，%right, 和 %nonassoc声明的token不需要，但可能也被%token声明。

优先级和结合性被yacc使用来解决解析冲突；它们使得消除二义性规则发生。形式上，规则按照下面这些来工作：

1. 为那些具有它们的tokens和字面量记录优先级和结合性。

2. 一个优先级和结合性跟每个语法规则相关联；就是一条规则中的上一个token或者字面量的优先级和结合性。如果%prec结构被使用了，就会重写这种默认机制。有些语法贵哦可能没有优先级和结合性跟它们关联。

3. 当发现reduce/reduce冲突，或者有shift/reduce冲突，并且输入标识和语法规则都没有优先级和结合性的时候，然后章节开头的两个消除二义性的规则就会被使用，并且冲突会被报告出来。

4. 如果有shift/reduce冲突，并且语法规则和输入字符都有优先级和结合性相关联，则冲突会被解决成有利于那个关联了更高优先级的动作（shift 或者reduce）。如果优先级相同，则使用结合性来；左结合意味着reduce，右结合意味着shift，非结合性意味着报错。

被优先级解决的冲突不会被算进yacc对 shift/reduce 和 reduce/reduce冲突报告中的数量。这意味着优先级规范中的错误可能会隐藏关输入语法中的错误；保留优先级是个好主意，把它们当做食谱来使用，直至已经获得一些经验。y.output文件对于决定解析器是否真的在做预期的事情是非常有用的。

7：错误捕获（Error Handling）

错误捕获是一个极难的领域，很多问题是语义上的问题。当一个错误被发现时，例如，开拓一个解析树内存可能是必要的，删除或者修改标识表入口，并且，很典型的是，设置开关来避免生成任何更深入的输出。

当发现一个错误就停止所有的进程是很少被接受的；继续扫描输入来发现更深的语法错误是更有用的。这导致在出现错误后重新启动解析器的问题。实现这一点的通用算法类包括从输入的字符串中丢弃一些token，然后试图调整解析器以便可以继续输入。

为了允许用户控制这一过程，yacc提供了一个简单但是有原因的通用特性。token名称为"error"被保留为错误捕获。这个名称可以被使用在语法规则；实际上，它建议错误被期望发生的地方，会发生恢复。解析器出栈，除非它进入了一个token"error"是合法的一个状态中。随后它表现得好像token "error"是当前的先行token一样，然后执行遇到的操作。先行token然后充值未引发错误的token。如果没有指定特殊的错误规则，进程会在错误被侦查到的时候突然停住。

为了避免级联的错误信息，解析器在侦查到一个错误后，会保留在错误状态，直到三个token已经成功读取并且shift移位。如果一个错误被检测到的时候，解析器已经处于错误状态了，那么不会有信息提示，输入的token被悄悄地删除。

举一个例子，格式中的一个规则：

stat
:
error

影响是，意味着在一个语法错误上，解析器会试图去略过错误的语句。更准确得说，解析器会提前扫描，寻找三个可以合法地跟随一个语句的token，然后开始处理这里面的第一个；如果语句的开头不是十分明显，可能会在语句的中间造成一个错误的开始，最终报告第二个错误，而实际上并没有错误。

动作可以跟这些特殊的错误规则一起使用。这些动作可能试图重新初始化表，回收符号表空间等等。

像上面这些错误规则是非常普遍的，但是很难控制。稍微更简单的规则比如说：

stat
:
error
";"

这里有一个错误，解析器尝试去略过这个语句，但是会通过跳到下一个";"来做到。所有在error之后的，下一个";"之前的token都不能被shift，然后被丢弃。当看到";"分号时，这个规则将执行reduce操作，然后任何跟它相关的清除操作被执行。

另一种错误规则的格式出现在非交互式的应用中，期望允许一行在一个错误发生后被重新进入。一个可能是错误规则可能是：

input
:
error
'n'
{
printf( "Reenter last line: " );
}
input
{
$$
=
$4;
}

这种方式存在一个潜在的困难；解析器在它承认它错误后正确地重新同步之前，必须正确地处理三个输入的token。如果在可重入的行的前两个token包含一个错误，解析器会删除不合法的token，然后不会给出提示信息；这是明显无法接受的。由于这个原因，有一种机制可以用来强制解析器去相信错误已经完全被恢复了。这个语句：

yyerrok ;

这个语句在一个操作中把解析器重置到常规模式。上一个例子最好写成这样：

input
:
error
'n'
{
yyerrok;
printf( "Reenter last line: " );
}
input
{
$$
=
$4;
}
;

跟上面提到的一样，在error标识之后立刻被看见的token是输入错误的发现标记。有时候，这是不合适的；举个例子，一个错误恢复操作可能要承担它自行寻找错误的位置来恢复输入的工作。在这个案例中，前一个先行token必须被清除。这个语句：

yyclearin ;

在一个动作操作中的这个语句具有这种影响。例如，假设错误后的动作是去调用一些用户提供的复杂的重新同步程序，试图将输入提前到下一个有效语句的开头。在这个程序被调用后，下一个由yylex返回的token将会大概是一个合法语句的第一个token；旧的，不合法的token必须被丢弃，然后错误状态重置。这可以被一个规则来完成，就像：

stat
:
error
{
resynch();
yyerrok ;
yyclearin ;
}
;

这些机制是被承认有些粗糙的，但是确实允许一个简单，相当高效的恢复让解析器从很多错误中恢复出来；甚至，用户可以获得处理由程序其他部分预期的错误操作的控制权。

8：yacc环境（The Yacc Environment）

当用户输入一个规范给yacc时，output是C程序的文件，在大多数系统中叫做y.tab.c（由于本地文件系统的约定，不同安装文件名称可能不同）。yacc生成的函数叫做yyparse；这是一个数字值的函数。当它被调用时，它轮流重复调用用户提供的词法分析器的yylex(第三章)来获得输入的token。最终，要么检测到一个错误，yyparse返回1（如果不可能恢复错误）；要么词法分析器返回结束标识符token，然后解析器接受。在这里，yyparse返回0.

用户必须给解析器提供一个确定的环境数量，为了获取一个工作中的程序。比如，在每个C语言程序，一个程序被调用的main方法必须被定义，最终调用yyparse。此外，一个叫做yyerror的程序会在侦测到语法错误后打印错误日志。

这两个程序必须被用户以某种方式提供。为了减轻使用yacc的初始化消耗，一个库已经被提供在默认的默认的main和yyerror的版本中。这个库的名称是system dependent；在很多系统中，这个库被通过一个 -ly的参数访问到加载器loader中。为了展示这些默认程序的片段，源代码在下面给出了：

main(){
return( yyparse() );
}
and
# include <stdio.h>
yyerror(s) char *s; {
fprintf( stderr, "%sn", s );
}

yyerror的参数是一个包含错误信息的字符串，经常是字符串”syntax error“。一般的应用想要做得比这个号。普遍来说，程序应该保持追踪输入的行号，然后在当语法错误被侦查出来的时候跟错误信息一起打印出来。外部的整形变量yychar在错误被检测到的时候会包含先行token号；这可以提供更好的诊断。由于主程序可能是由用户提供的（用户读取参数等），因此yacc库只在小型项目或者大型项目的早期阶段有用。

外部变量yydebug经常被设置成0.如果它被设置为非零，解析器将会给它的操作输出一个冗长的描述，包括哪个输入标识已经被读取的论述，还有解析器做了什么动作。依赖了操作环境，通过使用一个调试系统来设置这个变量是可能的。

9: Hints for Preparing Specifications

这个章节包含着各种各样的提示，以提高准备效率，容易修改，明确规范。这个独特子章节或多或少比较独立。

输入规范

很难提供一些包含大量操作的规则然后还有一个可读的规范文件。接下来的风格提示大多数归功于Brian Kernighan。

a. token名称使用所有的大写字母，所有的小写字母是非终止符号的名称。这条规则属于："当事情出问题的时候知道应该怪谁"。

b. 把语法规则和操作放到分开的行。这允许在不自动更改另一个的情况下更改其中一个。

c. 把所有的规则一起放在同一左手边。主需要设置左手边一次，然后让所有后续的规则以一个竖线开始。

d. 只有在左侧的最后一条规则设置一个分号，然后把分号设置在单独一行。这允许新的规则很容易添加。

e. 缩进规则的主体用两次tab退格，动作主体使用三个tab退格

附录A的例子是根据这种风格写的，本文中的例子也是如此（空间允许的地方）。用户必须组织他自己的想法关于这些格式问题；然而，核心问题是通过混乱的操作代码让规则可见。

左递归

yacc解析器使用的算法鼓励这个叫做"左递归"语法规则：下面这种格式的规则

name
:
name
rest_of_rule
;

这些规则频繁出现在写序列和列表的规范：

list
:
item
|
list
','
item
;
and
seq
:
item
|
seq
item
;

在这些案例的每一个，第一个规则将会只被reduce第一个item，第二个规则将会被reduce第二个和所有随后的项目。

至于右循环规则，比如说：

seq
:
item
|
item
seq
;

解析器将会大一些，items会被看到，并且reduce，从右到左。更严重的是，在解析器中的内部栈将会有溢出的风险，如果有一个非常长的序列被读取的话。因此，用户应该使用坐递归无论何种原因。

值得考虑一下是否一个序列带有0个元素有什么意义，如果真的有，考虑写这个序列规范带有一个空的规则：

seq
:
/* empty */
|
seq
item
;

再一次，第一个规则将会一直被只reduce一次，在第一个项目被读取之前，然后第二个规则将在每个item读取的时候被reduce一次。允许空序列经常带来更高的普遍性。然而，如果yacc被要求去决定已经看见哪个空序列可能会出现冲突，这时候它还没有看到足够的信息。

词法改编（Lexical Tie-ins）

有一些词法决策依赖上下文。例如，词法分析器可能想正常删除空格，但不是那种引号括起来的字符串。或者名称可以在声明中输入到符号表中，但是不是在表达式中。

处理这种情况的一种方式是创建一个全局的标记，这个标记能被词法解析器校验，并且通过actions动作设置。例如，假设一个程序由0或者更多声明组成，接着是0或者更多声明。考虑一下：

%{
int dflag;
%}
...
other declarations ...
%%
prog
:
decls
stats
;
decls
:
/* empty */
{
dflag = 1;
}
|
decls
declaration
;
stats
:
/* empty */
{
dflag = 0;
}
|
stats
statement
;
...
other rules ...

dflag标识现在读取到statements时是0，读取到declarations时是1，除了第一个statement的第一个token。这个token必须在它能说明声明模块已经结束并且statements已经开始之前被解析器看见。在很多案例中，这个单一的token无法影响到词法扫描。

这种“后门”的处理可以静心涉及到有害的程度。然而，它代表了一种处理很难的事情的方法，即如果有可能就去做别的事情。

保留字（Reserved Words）

有些编程语言允许用户使用类似"if"的单词，这种通常是保留的，作为标签或者变量名称，前提是这样的是用哪个不与这些名称在编程语言中的合法使用相冲突。在yacc框架中这是极其难以完成的；很难传递信息给词法分析器告诉它：这个"if"的实例是一个关键字，那个实例是一个变量。用户可以尝试一下，使用最后一个子章节的机制，但是很难。

很多方法来让这种实现更简单都会考虑周全。直到那时候，最好关键字得到保留；那就是禁止当做变量名称使用。无论如何，有很多格式上的原因来偏向这种。

10：高级主题（Advanced Topics）

这个章节讨论一些yacc的高级特性。

Simulating Error and Accept in Actions

错误和接受的解析动作可以被模拟成一个使用宏命令YYACCEPT和YYERROR的动作。YYACCEPT引起yyparse防范返回0值；YYERROR引起解析器表现得就像当前输入符号已经是一个语法错误；yyerror方法会被调用，然后错误恢复发生。可以使用这些机制来模拟具有多个结束标记或者上下文敏感语法检查的解析器。

Accessing Values in Enclosing Rules.

操作可以引用当前规则左侧操作返回的值。这种机制简单得跟普通的操作一样，美元符号跟着一个数字，但是这种情况数字可能是0或者负数。看看这个例子：

sent
:
adj
noun
verb
adj
noun
{
look at the sentence . . .
}
;
adj
:
THE
{
$$ = THE;
}
|
YOUNG
{
$$ = YOUNG;
}
. . .
;
noun
:
DOG
{
$$ = DOG;
}
|
CRONE
{
if( $0 == YOUNG ){
printf( "what?n" );
}
$$ = CRONE;
}
;
. . .

在单词CRONE后面的动作，做了一个校验前面的移位token不是YOUNG。很明显，这只可能在关于输入中的noun符号前面可能有什么，我们已经知道很多了。还有一种非结构化的味道在里面。然而，这种机制同时会带来很多麻烦，特别是当一些组合将被排除在常规结构之外。

Support for Arbitrary Value Types（支持任意值类型）

默认情况下，动作和词法分析器返回的值是数字类型。yacc也支持其他类型的值，包括结构体。yacc保持类型追踪，插入了恰当的联盟成员名称以致于结果解析器会被严格地类型校验。yacc值堆栈（参见第四节）被声明为所需的各种类型值的联合。用户声明了这个联合，然后每一个关联的联合成员名称的token和非终止符就拥有了一个值。当这个值被一个$$或者$n的结构引用，yacc会自动插入恰当的联合名称，保证了没有非预期的转换会发生。另外，类型校验命令例如lint5会更静默。

有三种机制被使用来提供这种类型。首先，有一种方式来定义这种联合；这必须由用户完成，因为其他程序（尤其是词法分析器）必须知道联合成员的命名。其次，需要有一种方式来关联一个tokens和非终止符号之间的联合成员名称。最后，有一种机制可以描述这几个值的类型，而yacc不容易确定类型。

为了生命这种联合，用户需要在声明模块包括下面这种：

%union
{
body of union ...
}

这里声明了yacc值堆栈，和外部变量yylval和yyval，拥有了和这个联合类型相同的类型。如果yacc被调用使用了-d参数，这个联合声明会被复制到y.tab.h的文件中。或者，这个联合会被声明在一个头部文件中，一个typedef被用来定义变量YYSTYPE来代表这种联合。因此，头部文件可能已经说明了：

typedef union {
body of union ...
} YYSTYPE;

这个头部文件必须被包括在声明模块，通过使用%{和%}。

一旦YYSTYLE被定义，联合成员名称必须被关联上不同的终端和非终止符号命令。这种构造：

< name >

被用来表明一个联合成员名称。如果这里跟着这些关键字的其中一个，%token，%left，%right，%nonassoc等，这个联合成员名称被关联上这些tokens。因此，如果这样说明：

%left
<optype>
'+'
'-'

会导致任何指向这两个tokens返回的值会被标记成联合成员名称optype。另外一个关键字%type类似地同来关联联合成员名称到非终端符号上。因此，必须声明成这样：

%type
<nodetype>
expr
stat

还存在着一些场景是这些机制不生效的。如果在一个规则中有一个操作，此操作返回的值没有先验类型，对左边上下文的引用使yacc无法轻松地了解类型。在这种情况下，一个类型可以在引用上通过插入一个联合成员名称，在$后面的移开，用尖括号"<"和">"包围。这种用法的一个例子是：

rule
:
aaa
{
$<intval>$
=
3;
} bbb
{
fun( $<intval>2, $<other>0 );
}
;

这种语法不是很推荐，但是这种情况出现得很少。

在附录C中有一个样例规范。本子章节中的设施在使用前不会被触发：尤其，%type的使用将会打开这些机制。当使用这种机制时，有一个相关严格的级别的校验。例如，使用$n或者$$来应用一些没有定义类型的东西被诊断。如果这些设施没有被触发，yacc值堆栈用于保存int值，这在历来是正确的。

11：Acknowledgements

yacc归功于一群令人兴奋的用户，在他们无边的探索再来一个功能中，把我刺激得超过了我的意愿，并且频繁超过了我的能力。他们不愿意学习如何按我的方式做事，这让我很恼火，而这通常导致我按他们的方式做事；大多数情况下，他们是对的。B. W. Kernighan, P. J. Plauger, S. I. Feldman, C. Imagna, M. E. Lesk和A. Snyder将会在Yacc的当前版本中认可他们的一些观点。C. B. Haley贡献了错误恢复算法。D. M. Ritchie, B. W. Kernighan, and M. O. Harris 帮助把文档翻译成英文。Al Aho也应该得到特别的赞扬，因为他把这座山带给了穆罕默德和其他的好处。

更多内容：可以看：http://dinosaur.compilertools.net/

最后

以上就是知性百合为你收集整理的YACC介绍（译文）术语简介0：介绍1：基本规范2: Actions动作4：Parser如何工作？6：Precedence（优先级）7：错误捕获（Error Handling）8：yacc环境（The Yacc Environment）9: Hints for Preparing Specifications10：高级主题（Advanced Topics）11：Acknowledgements的全部内容，希望文章能够帮你解决YACC介绍（译文）术语简介0：介绍1：基本规范2: Actions动作4：Parser如何工作？6：Precedence（优先级）7：错误捕获（Error Handling）8：yacc环境（The Yacc Environment）9: Hints for Preparing Specifications10：高级主题（Advanced Topics）11：Acknowledgements所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。