语法分析程序的自动生成工具

1、5.10 语法分析程序的自动生成工具迄今为止，读者已经学习了语法分析和语义翻译的基本知识。从理论上讲，对于常见的程序设计语言的语法结构，我们已能构造相应的处理程序，以完成语法分析和语义翻译工作。本节，我们将介绍几种语法分析器的自动生成工具，这些工具可将用户输入的文法自动转换成LL或LR语法分析程序，除此之外，它们还允许用户在产生式中插入语义处理动作 (语义子程序)，并在分析程序中的适当位置安排调用语义子程序的代码。目前，这些工具已在许多领域的软件系统研制过程中得到广泛的使用。5.10.1 LALR(1)分析器的自动生成工具YACC和OCCSYACC (Yet Another CompilerC

2、ompiler)是LALR(1)分析器的自动生成工具，它的第1版于70年代初发表，是美国贝尔实验室的软件产品 (作者为S.C.Johnson)。这个工具目前在UNIX，DOS等系统平台上广泛流行。OCCS (Other Compiler Compiler System)是由A.I.Holub开发的与YACC类似的工具28。与YACC不同的是，OCCS给用户提供了一个功能较为完善，基于窗口的调试系统yydebug.c，此调试系统能使用户实际观察分析动作中的处理过程和分析栈的变化情况，以及根据不同的栈状态及指定的输入符号设置断点等等。此外，OCCS比YACC有更完善的错误诊断机制，其输出的代码也比

3、YACC有更好的可维护性。不过，二者的用法基本相同，本节主要介绍国内十分流行的YACC的用法，对于OCCS所特有的功能，则只作简要的说明。使用YACC构造语法分析程序非常简便，它要求用户按一定规则编写出“文法处理说明文件”，简称YSP (Yacc SPecification)文件，文件的扩展名为“.y”。当输入YSP文件时，YACC就会自动构造出相应的C语言形式的语法分析器。该分析器主要包括由YACC提供的标准总控程序和一个LALR(1)语法分析表。其使用过程如图5 13所示。在DOS系统下，使用YACC的格式为：YACC选择项filename.y此命令根据用户输入的名为filename.y的

4、YSP文件，使YACC自动生成相应的C语言形式的语法分析器源文件ytab.c (有的YACC系统生成的文件名为y.tab.c)。然后。用户可在C环境下将其编译成可执行文件。其工作过程如图5 14所示。    一、 YSP文件的结构一个完整的YSP文件由说明、规则、程序三个部分组成，各部分之间以双百分号“%”隔开：说明部分%规则部分%程序部分其中，用方括号括起来的说明部分和程序部分可以空缺，但规则部分则是必须的。因此，YSP文件的最简形式是：%规则部分首先，我们以一个简单台式计算器中的处理程序的自动生成为例，说明怎样编写YSP文件。该计算器的功能为：读入一行算术表达

5、式，然后计算并打印它的值。算术表达式的文法如下：Expr Expr + Term | TermTerm Term * Factor | FactorFactor ( Expr ) | digit其中，终结符号digit是09中的任何一个数字。该文法的YSP文件可编写如下：%/*说明部分*/#include <stdio.h>#include <ctype.h>%tokendigit300%/*规则部分*/Line:Expr nprintf("%dn",$1);/*打印表达式值*/;Expr:Expr + Term $=$1+$3;/*Expr=Exp

6、r+Term*/|Term/*Expr=Term*/;Term:Term * Factor $=$1*$3;/*Term=Term*Factor*/|Factor/*Term=Factor*/;Factor:( Expr )$=$2;/*Factor=Expr*/|digit/*Factor=digit的属性值*/;%/*程序部分*/int yylex(void)/*词法分析程序*/int c;c=getchar( );/*读入一个字符*/if(isdigit(c)/*判别c是否为数字*/yylval=c-0;return digit;return c;void yyerror( )/*出错处

7、理程序*/printf("Syntax errorn");void main( )yyparse( );/*调用语法分析程序*/下面分别论述YSP文件各部分的组成规则。    二、 YSP说明部分的组成YSP文件中的说明部分用于定义规则部分所使用的变量及语法符号。它可以包含以下几类信息。1变量定义变量定义需要用一对特殊括号“%”和“%”括起来，其内容包括规则部分中的语义动作及程序部分所需使用的有关文件 (如C语言的有关头文件)的引用说明、数据结构的定义、全局和外部变量的定义以及函数原型的定义等等，这部分内容应遵守C语言的规定。例如：%#incl

8、ude <stdio.h>.int count;extern double value;.int addedfunction(int a,float b);.%2. 开始符号定义文法的开始符号由说明符号%start指明(请注意，YACC中的所有说明符号均由“%”引出)，例如：%startStartSymbol指明StartSymbol为文法开始符号。若未给出开始符号的定义，则系统将自动以第1条语法规则的左部符号作为开始符号。例如，前面所给出的YSP文件例子中，就没有给出开始符号的定义，所以，系统将认为非终结符号Line是开始符号。3. 词汇表定义在这部分，用户可以给出终结符号表、联

9、合 (union)和类型 (type)说明。YACC要求所用到的所有文字形式的终结符号都应明确加以说明；对于未说明者，则均按非终结符号处理。终结符号说明由说明符号%token或%term引出，其书写格式有两种。第1种书写格式为%tokenTname1 Tname2 .各个终结符号之间用空格分隔。在一行写不下时，可用%token另起一行继续定义。在前例中，仅说明了一个终结符号digit。第2种书写格式允许用户自行定义终结符号的内部编码值，其格式为：%tokenTname <integer>其中，<integer>应为大于256的整数。前例中的digit就是采用这种格式定义

10、的，其内部码为300。当用户未给出终结符号的内部码时，系统将按终结符号的出现顺序，从257开始，依次为其定义内部码值：257，258，。 YACC内部约定，当词法分析程序从输入字符串中识别出一个终结符号时，将返回该终结符号的内部码值。还需指出，除文字型的终结符号外，对于程序设计语言中的单字符运算符、分隔符等终结符号，可在文法中用单引号括起来直接使用，不必用%token定义，其内部码值就是它的ASCII码 (其值将不会大于256，这也是用户自定义的终结符号内部码之值不能小于257的原因)。在词汇表定义中，还可以通过使用联合 (%Union)和类型说明 (%type)，对每个文法符号定义其语义属性

11、应具有的数据类型。例如，假定非终结符号A具有属性attra，其值为整型；非终结符号B具有两个属性b1和b2，其中b1为整数，b2为实数；则可用联合说明告诉YACC，文法符号具有两种类型：%Unionint attra;structint b1;float b2; attrb然后再用%type说明非终结符号A和B所具有的类型：%type <attra>A%type <attrb>B其中，尖括号<>中的名字是联合定义中的成员。一般说来，若使用了联合定义，则须用类型说明(%type)对每个文法符号的数据类型进行定义 (每个符号有且仅有一种类型)，否则，YACC将会

12、报错。使用上述方式，允许在一行中定义多个文法符号，只需用空格将其隔开即可，若在一行写不下时，则需另起一行后重新用%type命令继续定义。若在说明部分未用联合进行说明，则YACC自动使用缺省类型。YACC约定，每个文法符号的缺省类型均为整型。4优先级与结合性定义为了能够解决文法中出现的一些二义性和部分语法分析冲突，YACC提供了定义优先级和结合性等手段。在后面我们将对此进行详述。    三、 YSP文件语法规则部分的组成语法规则部分是整个YSP文件的主体，它由文法的一组产生式及每一产生式相应的语义动作组成。对于文法中的每个产生式A1 | 2 | n在YSP文件中将相

13、应地写成：A ：1语义动作1；| 2语义动作2；.| n语义动作n；其中，A为产生式左部非终结符号，冒号“：”是产生式左部与右部的分界符 (相当于“” )，对于未在说明部分说明过的文字终结符号需要用单引号括起来。每个产生式必须用分号“；”作为结束标志 (注意，若分号是产生式右部中的终结符号时，需用单引号括起来)。对于一个产生式左部非终结符号的每个候选式，用户都可以用C语言为其编写一段相关的语义处理程序，它们需用花括号 括起来。在生成语法分析程序时，YACC将自动把它们嵌入到LALR分析表相应的位置。尔后进行语法分析时，当按某非终结符号的候选式归约句柄时，就自动执行相应的语义处理程序。为了与语法

14、分析有机地结合，在语义处理程序中往往需要使用YACC提供的伪变量来表示产生式中相应文法符号的语义动作返回值。YACC约定，产生式左部符号的属性值用$表示，而右部第k个符号的属性值用$k表示 (事实上，这种格式我们已在前面的章节中多次见到了)。例如，对于产生式ExprExpr+Term|Term在YSP文件中将相应地写成：Expr: Expr + Term $=$1+$3;| Term;它表示按第1个候选式归约时，左部符号Expr的属性值为该产生式右部第一符号Expr与第三符号Term的属性值之和；按第2个产生式归约时，由于语义动作缺省，YACC自动按$=$1；处理 (不论右部有多少符号)。最后

15、需指出，当候选式为时，将不写任何符号，例如，将写成 A：动作，若动作缺省，系统将仍执行动作$=$1，只是此时$1所代表的是按A归约之前栈顶符号的属性。    四、 YSP文件程序部分的组成YSP文件的程序部分是可选的。它由例行C语言程序 (函数)组成，主要包括主程序main( )、词法分析子程序yylex( )、出错处理子程序yyerror( )、语法规则部分语义动作中所调用的用户自定义函数以及其它辅助函数等等。下面对它们的格式、功能和用法作概括地说明。(1) YACC在处理YSP文件之后，将输出一个名为y.tab.c的C程序文件，此文件含有名为yyparse(

16、)的语法分析程序 (函数)。主程序main( )的主要作用，在于调用函数yypase( )对源程序进行语法分析。当语法分析成功结束时，yyparse( )返回值为0；而在发现源程序有语法错误时，除返回值为1外，它还调用yyerror( )函数输出出错信息。函数main( )和yyerror( )可由YACC库提供 (只需在编译命令行中加入选择项ly即可)，其格式分别为main( )return (yyparse( )；及#include stdio.hyyerror(s)char*s；fprintf(stderr,"%sn",s);如果用户认为上述函数的功能不满足要求，例如

17、还需要在主程序中做其它的辅助处理，或需要yyerror输出更详细的出错信息，也可以自行编写这两个函数。但须注意，在main( )函数中至少要有一条调用yyparse( )函数的语句。(2) YACC系统规定，在语法分析程序yyparse( )运行时，须有一个名为yylex( )的词法分析程序对其支持。每当yyparse( )调用yylex( )时，yylex( )就从输入字符流中识别出一个单词，并将该单词的内部码及其语义值 (若有的话)分别通过return语句及全局变量yylval回送给yyparse( )。可见，yyparse( )的输入来源于yylex( )的返回信息。词法分析程序需由用户

18、提供。它可由用户手工编写或通过LEX工具自动生成。由LEX生成的词法分析程序包含在文件lex.yy.c中，LEX为其确定的名字正好也是yylex( )。为了使yyparse( )能使用LEX所生成的yylex( )函数，最简便的方法是在YSP文件的程序部分写上一条形如#include "lex.yy.c"的语句即可。在YSP文件中，整个程序部分都可缺省。用户可将所需的程序 (函数)在某个C文件中进行定义，再将它与YACC生成的y.tab.c文件编译、连接在一起即可。联合使用LEX和YACC来自动生成语法分析器的处理流程如图5 15所示。设用户已准备好的LEX源文件和YSP文

19、件分别为scanner.l和parser.y，并假定main( )和yyerror( )由YACC库提供，则在UNIX环境下依次执行下列三条命令：lex scanner.l/* 生成含有yylex( )的lex.yy.c文件*/yacc parser.y/*生成含有yyparse( )的y.tab.c文件*/cc y.tab.c lyll/*对文件y.tab.c进行编译*/便可得到可执行的语法分析器。如果用户在YSP文件中提供了自己编写的main( )函数和yyerror( )函数，则选择项ly不用给出。    五、 二义性文法的处理由于LALR分析要求文法是非二

20、义性的，因此，当一文法有二义性时，YACC构造的分析表必然会含有分析动作冲突，此时YACC会报告冲突动作的数目。若需了解冲突项目更详尽的内容，可在调用YACC对YSP文件进行处理的命令中使用选择项V。这样，YACC会产生一个附加文件YOUT.PUT。该文件含有关于冲突的进一步描述信息，以及YACC按照“缺省规则”自行解决的冲突信息。YACC系统内约定解决冲突的原则为：(1) 当发生归约归约冲突时，按照YSP文件中排列在前面的产生式进行归约；(2) 当发生移进归约冲突时，按照移进优先于归约的原则进行处理。这条规则正确地解决了由于悬空else的二义性所产生的移进归约冲突，即保证了使else总是与其

21、左侧尚未被匹配的then配对。然而，上述缺省规则不能保证总与用户的要求一致。因此，YACC通过为文法中某些运算符定义优先级和结合性等手段，提供了一些可能解决移进-归约冲突的途径。在YSP文件的说明部分，用户可使用命令%left (%right)来指明跟在其后的所有运算符具有相同的优先级和左 (右)结合性质。例如，命令%left+-%left*/使得上述运算符均具有左结合性质。用户还可用%nonassoc命令告诉YACC，其后所跟的运算符不具有结合性。例如%nonassoc<>= .指明<、>等符号不具有结合性质 (即该运算符的相邻两次出现不能结合)。YACC规定，出现在

22、同一结合性说明中的各个符号具有相同的优先级；说明排列的次序决定了优先级的高低，排列在前者优先级较低，而排列在后者则较高。例如，在上面的例子中，+、 - 的优先级低于 *、/。有时，处于某些产生式右部的最左终结符号的优先级难以说明 (如一元减运算符)，则可通过给该产生式附加说明的方式，强制定义这类运算符的优先级。其格式为：%prec<终结符号>这种说明告诉YACC，该产生式右部最左终结符号与上述说明中的终结符号具有相同的优先级和结合性。例如，在后面的YACC应用实例中，有如下说明：%left*/ %left UMINUS/*一元减运算符*/Expr: - Expr%prec UMIN

23、US$=-$2;前者指明终结符号UMINUS具有左结合性，且优先级最高 (因在“*”，“/”等之后定义)；后者则强制定义表达式中的一元减运算符与UMINUS具有相同的优先级和结合性。当然，上述说明方式也可通过在词法分析程序中，当识别出一元减运算符时，返回终结符号UMINUS的内部码的方式来实现。另外，还可通过给产生式定义优先级和结合性的手段来解决移进归约冲突。YACC规定，对于规则部分中的每个产生式，若无任何附加的强制性说明，则其优先级和结合性与该产生式右部的最右终结符号的优先级和结合性相同 (自然，该终结符号的优先级和结合性应在说明部分加以定义)。于是，当需在“移进输入符号a”和“按产生式A

24、进行归约”这两个动作之间进行选择时，YACC将按下述规则解决冲突：若产生式A的优先级高于a，或两者优先级相同但产生式A是左结合的，则选取归约动作；否则选取移进动作。实践表明，这种解决移进归约冲突的策略是合理的，在绝大多数情况下都是与实际情况相吻合的。有了优先级和结合性的定义，可简化文法的产生式结构。例如，在前面的表达式文法中可省去非终结符号Term和Factor，仅使用一个非终结符Expr即可。在一文法中，文法符号的多少直接影响到语法分析程序的运行效率。一般说来，减少文法符号的个数，可减少分析表的状态数，从而可节省内存空间并提高分析速度。还需要指出，在使用YACC时，应尽量使用左递归形式定义产

25、生式，这样做同样可以从时间和空间上提高语法分析程序的效率。    六、 关于嵌入动作与语法变换前面说过，YACC允许在规则部分每个产生式的最右侧，附加上进行语义处理的语义动作，以便在以后执行语法分析程序的过程中，每当使用一个产生式进行归约 (也只有在进行归约)时，将自动执行相应的语义动作。这是S属性翻译文法的特征之一。但有时我们也希望把一个动作放在产生式的其它地方，而不是最右端。例如，在对条件语句Stmtif Expr then /*action1*/Stmt/*action2*/进行处理时，为了能够及时回填Expr的真出口，需在then后“嵌入”语义动作 (参见

26、5.6节)。一般说来，解决此类问题的方法，是对原文法进行如5.6节中那样的语法变换。除此而外，YACC (及OCCS，下同)还提供了一种更简单的处理方法，即允许用户自由地在产生式右部的任何位置嵌入所希望的语义动作。但需指出，YACC将自动为其增加产生式，以保证“动作”在进行“归约”时才被执行 (即保持S属性文法的特征)。例如，产生式A action1 action2将被YACC处理为A 001 action2001 action1其中，001是YACC内部自动引入的虚拟非终结符号 (实际上，001并不存在，这里使用这个名字只是为了说明其原理)。当然，上述处理方法也许会带来副作用，即可能引起新的

27、移进归约冲突，若发生这样的问题，则只能由用户自行设法解决。还需要指出，在产生式中嵌入语义动作之后，代码段中出现的、代表文法符号属性的$，$1，$2等符号的意义有可能会被改变。例如，在下面产生式中，$i与文法符号的对应关系为A:ab$=$1+$2;/*A1*/ c$=$1+$2+$3+$4;$1$2$3 $4因为动作A1对应了一个隐含的非终结符号001，它将在上面的产生式中占一个符号的位置，因此其语义值只能通过$3来引用，同时，文法符号c的语义值则应由$4来引用。另外，在动作A1中不能出现对$3和$4的引用，这是因为，在执行该动作时，$3和$4对应的文法符号尚未在分析栈中形成。在OCCS中，还允

28、许用户对文法进行另一种变换，即允许用户使用方括号 定义产生式的可选部分。例如，对形如A: a b c ；的产生式，系统内部将其变换为A: a 001 c ；001: b|/*/；在这种情况下，用户在编写语义子程序时，应特别注意对产生式中各文法符号属性的正确引用。例如，对产生式A：a b c $=$1+$2; d $=$1+$2+$3; ；其中，方括号内的文法符号和语义动作实际上对应用于产生式001: b c $=$1+$2; ；因此，对上述产生式而言，只能将方括号内的部分视为一个文法符号，从而，需用$3而不是用$4来引用文法符号d的语义属性。如果归约过程使用了产生式001: $=$1+$2;/

29、*产生式*/；则在动作$=$1+$2+$3;中$2无意义，处理过程可能出现难以预料的结果。因此，当用户需传送语义值时，应在此处避免使用 定义产生式。OCCS还提供了一种允许用户使用自反传递闭包的语法变换手段，例如，对于产生式A :a b* c ；OCCS内部将其变换为A：a 001 c ；001:001 b |/*产生式*/；其属性引用的原理与可选情形类似，这里就不再讨论了。    七、 YACC应用实例为了便于学习编写YSP文件，下面给出一个生成具有较强功能计算器的完整YSP文件实例。此计算器能进行加、减、乘、除和赋值等运算，并且还有26个寄存器 (变量)，分别用26个小写英文字母表示。当给寄存器 (变量)赋值时，不打印计算结果，其它情况则打印出表达式的值。%/*下面是说明部分*/#include <stdio.h>#include <ctype.h>int reg26;int base;%startList%tokendigitletterUMINUS%left|%left&%right!%left+-%left*/%le