Yacc: 另一个编译器的编译器

文章翻译：寒蝉退士
信息来源：http://mhss.nease.net/unix/yacc.html

source code:
http://mhss.nease.net/unix/yacc.tar.gz

Yacc: 另一个编译器的编译器
Stephen C. Johnson
Bell Laboratories
Murray Hill, New Jersey 07974

译者声明：
译者对译文不做任何担保，译者对译文不拥有任何权利并且不负担任何责任和义务。
原文：http://cm.bell-labs.com/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: 对准备规定的提示
输入样式
左递归
词法搭配
保留字
10: 高级主题
在动作中模拟错误和接受
访问外围规则中的值
支持任意的值类型
11: 致谢
引用
附录 A: 简单的例子
附录 B: Yacc 输入语法
附录 C: 高级的例子
附录 D: 支持但不鼓励的旧特征

--------------------------------------------------------------------------------

0: 介绍
Yacc 提供了一个通用工具来在计算机程序的输入上施加结构。Yacc 用户准备输入处理的规定；它包括描述输入结构的规则，在识别了这些规则的时候调用的代码，和做基本输入的一个低层例程。Yacc 接着生成一个函数来控制输入处理。这个函数叫做解析器(parser)，它调用用户提供的低层输入例程(词法分析器(analyzer))来从输入流中选取基本项目(叫做记号(token))。依据叫做文法规则的输入结构规则来组织这些记号；在识别了这些规则中的某一个的时候，接着调用为这个规则提供的叫做动作的用户代码；动作有能力返回值并使用其他动作的值。
Yacc 是用 C[1] 语言的一个可移植方言写成的，并且动作和输出的例程也一样使用 C 语言。此外，Yacc 的很多语法约定依从 C 语言。

输入规定的心脏是一组文法规则。每个规则描述一个允许的结构并给它一个名字。例如，下面的文法规则

    date : month_name day ',' year  ;

这里的 date、month_name、day、和 year 表示在输入处理中它感兴趣的那些结构；month_name、day 和 year 大概是在其他地方定义的。逗号“,”包围在单引号之中；这暗示了逗号在输入中是作为文字(literal)出现的。冒号和分号只是充当规则中的标点符号，而对控制输入没有意义。所以，有着正确定义的输入
    July 4, 1776

可以匹配上述规则。
输入处理的一个重要部分是完成词法分析器。这个用户例程读取输入流，识别低层结构，并把这些记号传达到解析器。出于历史原因，词法分析器识别的结构叫做终结符(terminal symbol)，而解析器识别的结构叫做非终结符(nonterminal symbol)。为了避免混淆，终结符通常会称呼为记号。

在使用词法分析器还是使用文法解析器之间有相当可观的回旋余地。例如，规则

    month_name : 'J' 'a' 'n'  ;
    month_name : 'F' 'e' 'b'  ;

         . . .

    month_name : 'D' 'e' 'c'  ;

可以用于上述例子。这个文法解析器只需要识别单个字母，而 month_name 将是一个非终结符。这种低层规则趋向于浪费时间和空间，并可能使规则复杂得超越了 Yacc 的处理能力。通常的，词法分析器将识别月份名字，并返回见到了 month_name 的一个指示；在这种情况下，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)。假定没有在声明段中定义的每个名字都是非终结符。每个非终结符都必须至少在一