搜索
Yacc:另一个编译器的编译器StephenC.JohnsonBellLaboratoriesMurrayHill,NewJersey07974翻译：寒蝉退士译者声明：译者对译文不做任何担保，译者对译文不拥有任何权利并且不负担任何责任和义务。原文：摘要计算机程序的输入通常有某种结构；实际上，可以认为每个需要输入的计算机程序都定义了一门它所接受的“输入语言”。输入语言可以像编程语言那么复杂，或者像一序列的数那么简单。不幸的是，通常的输入设施是有限的、难于使用的，并经常疏于检查它们的输入的有效性。Yacc提供了一个通用工具来描述计算机程序的输入。Yacc用户规定它的输入的结构，连同在识别每个这种结构的时候调用的代码。Yacc把这样的规定转换成操作输入处理的一个子例程；用这个子例程处理用户应用中的多数控制流经常是方便和适当的。Yacc生成的输入子例程调用用户提供的一个例程来返回下一个基本输入项目(item)。所以，用户可以以单个的输入字符的方式，或以更高层构造如名字和数的方式来规定它的输入。通过用户提供的例程还可以处理惯用的特征如注释和(行)接续约定，这些东西典型的违反容易的文法规定。Yacc是用可移植的C语言写成的。接受的规定类别是非常一般性的:带有去歧义规则的LALR(1)文法。除了用于C、APL、Pascal、RATFOR等编译器之外，Yacc还用于非常规语言，包括一个照相排版机语言、一些桌面计算器语言、一个文档检索系统、和一个Fortran调试系统。July31,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:支持但不鼓励的旧特征0:介绍Yacc提供了一个通用工具来在计算机程序的输入上施加结构。Yacc用户准备输入处理的规定；它包括描述输入结构的规则，在识别了这些规则的时候调用的代码，和做基本输入的一个低层例程。Yacc接着生成一个函数来控制输入处理。这个函数叫做解析器(parser)，它调用用户提供的低层输入例程(词法分析器(analyzer))来从输入流中选取基本项目(叫做记号(token))。依据叫做文法规则的输入结构规则来组织这些记号；在识别了这些规则中的某一个的时候，接着调用为这个规则提供的叫做动作的用户代码；动作有能力返回值并使用其他动作的值。Yacc是用C[1]语言的一个可移植方言写成的，并且动作和输出的例程也一样使用C语言。此外，Yacc的很多语法约定依从C语言。输入规定的心脏是一组文法规则。每个规则描述一个允许的结构并给它一个名字。例如，下面的文法规则date:month_nameday','year;这里的date、month_name、day、和year表示在输入处理中它感兴趣的那些结构；month_name、day和year大概是在其他地方定义的。逗号“,”包围在单引号之中；这暗示了逗号在输入中是作为文字(literal)出现的。冒号和分号只是充当规则中的标点符号，而对控制输入没有意义。所以，有着正确定义的输入July4,1776可以匹配上述规则。输入处理的一个重要部分是完成词法分析器。这个用户例程读取输入流，识别低层结构，并把这些记号传达到解析器。出于历史原因，词法分析器识别的结构叫做终结符(terminalsymbol)，而解析器识别的结构叫做非终结符(nonterminalsymbol)。为了避免混淆，终结符通常会称呼为记号。在使用词法分析器还是使用文法解析器之间有相当可观的回旋余地。例如，规则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作为July4,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'formfeed'\xxx'``xxx''八进制数出于一些技术原因，NUL字符('\0'或0)在文法规则中不应该使用。如果有一些文法规则有相同的左手端，可以使用竖杠“|”来避免重写左手端。此外，在规则末端的分号如果在竖杠之前则可以去掉。所以给Yacc的文法规则A:BCD;A:EF;A:G;可以写为A:BCD|EF|G;在文法规则段中有相同左手端的所有文法规则出现在一起不是必须的，但是这使输入更加可读并易于改变。如果一个非终结符匹配空字符串，则可以用明显的方式来指示:empty:;代表记号的名字必须被声明；最简单的就是在声明段中写%tokenname1name2...。(更多的讨论参见章节3、5和6)。假定没有在声明段中定义的每个名字都是非终结符。每个非终结符都必须至少在一个规则的左手端出现。在所有非终结符中，有一个叫做开始符号的特别重要。解析器就是设计用来识别这个开始符号；所以这个符号代表文法规则描述的最大的最一般的结构。缺省的，在规则段中使用这个开始符号作为第一个文法规则。在声明段中使用%start关键字显式的声明这个开始字符是可能的，并在实际上是需要的:%startsymbol通过叫做结束标记(endmarker)的特殊记号向解析器通知输入结束。如果直到但不包括这个结束标记的记号形成了同开始符号相匹配的一个结构，则解析器函数在见到结束标记之后返回到它的调用者。如果在任何其他上下文中见到这个结束标记，都是一个错误。在适当的时候返回结束标记是用户提供的词法分析器的工作；参见下面的第3节。通常结束标记代表某种相当明显的I/O状态，比如“文件结束”或“记录结束”。2:动作对于每个文法规则，用户都可以关联上在输入处理中每次识别了这个规则的时候进行的动作。这些动作可以返回值，并可以获得从前面动作返回的值。此外，词法分析器可以返回记号的值，如果需要的话。动作是任意的C语句，同样可以做输入输出，调用子程序，和更改外部向量和变量。动作被指定为包围在花括号“{”和“}”中的一个或多个语句。例如，A:'('B')'{hello(1,abc);}和XXX:YYYZZZ{printf(amessage\n);flag=25;}是带有动作的文法规则。为了便利在动作和解析器之间的通信，对动作语句要做稍微的改动。在这个上下文中使用美元符号“$”作为给Yacc的一个信号。要返回值，动作通常把伪变量(pseudo-variable)“$$”设置为某个值。例如，不做任何事但返回值1的动作是{$$=1;}要获得前面动作和词法分析器的返回值，动作必须使用伪变量$1、$2、...，它们提及的是规则右手端的部件(component)的返回值，它们是从左至右读取的。所以，如果规则是A:BCD;例如，这里的$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$ACTC{x=$2;y=$3;