语法分析器生成器YACC

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.2 语法分析器生成器YACC,分析器的构造步骤：,产生式识别活前缀的DFA分析表驱动器,2.2.1,YACC,概述,工作方式：,2.2.1 YACC概述,2YACC生成的语法分析器框架,利用YACC进行语法分析器设计的关键，也是如何编写YACC源程序下边首先介绍YACC源程序的根本结构，然后着重讨论YACC的产生式、YACC解决产生式冲突的方法、以及YACC对语义的支持和对错误的处理等2.2.2 YACC源程序的根本结构,声明declarations,%,翻译规那么(translation rules),%,用户定义子程序user defined routines,与LEX的区别：,至少一条翻译规那么,（1）声明与定义,（2）分析表,（3）分析表的驱动器（parser()）,（4）用户定义子程序,2.2.2 YACC源程序的根本结构续1,例2.10,简单的YACC源程序include,#include,%,%token num,%left -,%left *,%,LS ：LS E n printf(%dn，$2)；,|E n printf(%dn，$1)；,;,E ：E-E$=$1-$3；,|E*E$=$1*$3；,|num,;,%,int yylex(),int c;,while(c=getchar()=);,if (isdigit(c),ungetc(c,stdin);,scanf(yytext,%d;$yylval);,return num;,return c,main()parser();,用户编写的词法分析器应与,LEX,产生的词法分析器有相同的界面，以供语法分析器使用，它们包括：,yylex()、yylval、yytext和yyleng,等。

2.2.2.1 声明,C语言局部%.%,Yacc的说明局部 目的是为翻译规那么效劳文法的开始符号：,%start n_name 默认第一个产生式的左部是开始符号,终结符：,直接表示：-和*等；无需说明,名字：%token t_name内部编码，LEX中使用,说明终结符的优先级与结合性：非终结符下节讨论,结合性：,左结合%left,右结合%right,无结合性%nonassoc,优先级：从上到下依次递增,%left +-,%left */,重新定义语义栈类型下节讨论2.2.2.2 用户定义子程序,这局部与LEX的第三局部作用相同，所有语义动作中的C源程序均可定义在此如例2.10中的yylex()，假设采用LEX生成yylex()，那么可编写LEX源程序如下：,%,nt；,0-9+scanf(yytext，%d，&yylval)；return NUMBER；,.return yytext0；,而例2.10中yylex()的定义相应改为#include lex.yy.c即可2.2.2.3 翻译规那么,规那么 非终结符:候选项集;,候选项集 ,|候选项,|候选项集|候选项,候选项 文法符号序列 右部语义动作,文法符号序列 ,|文法符号序列 文法符号,文法符号 终结符|非终结符|嵌入语义动作,右部语义动作 ,|C语言语句序列,嵌入语义动作 C语言语句序列,E ：E-E$=$1-$3；,|E*E$=$1*$3；,|num,;,2.2.3 YACC程序设计,2.2.3.1 YACC解决冲突的方法二义文法时产生的冲突,分析表中的两类冲突,移进/归约冲突：在一个状态中，面对相同的下一文法符号，可以同时有移进和归约两个动作与其匹配；,归约/归约冲突：在一个状态中，面对相同的下一文法符号，有两个或两个以上的产生式可以进行归约。

YACC,的默认解决方案,移进/归约冲突时，执行移进动作，即移进先于归约；,归约/归约冲突时，用,YACC,源程序中第一个出现的产生式进行归约用户解决方案：规定优先级和结合性,例2.11 对于如下产生式：,%left+-,%left*/,%right uminus,E ：E+E$=$1+$3；,|E-E$=$1-$3；,|E*E$=$1*$3；,|E/E$=$1/$3；,|-E%prec uminus$=-$2；,|num$=$1；,；,产生式的优先级和结合性与产生式右部最右边的终结符一致假设不一致时，采用占位符(place holder)的方法解决如上边的%prec uminus如果不说明%prec uminus，那么产生式E:-E对于输入序列-3*6，处理结果是-(3*6)，即在-的情况下遇到*时先移进而说明之后，处理结果是(-3)*62.2.3.2 YACC对语义的支持,分析器工作原理：,语义栈对语法制导翻译提供直接支持语义栈的类型决定了文法符号的属性，语义栈类型表示能力的强弱决定了YACC的能力YACC默认的语义值类型,YACC语义栈与yylval同类型，并以终结符的yylval值作为栈中的初值。

因为yylval的默认类型为整型，所以，当用户所需文法符号的语义类型是整型时，无需定义它的类型如在下述表达式的产生式中：,E：E+E$=$1+$3；,|E*E$=$1*$3；,|num,；,所需语义值不是整型,用,#define YYSTYPE new_type,冲去默认的,int,类型，然后通过,YACC,所生成分析器中的变量声明语句使,yylval,获得新的类型例如：,YYSTYPE yylval;,使得,yylval,具有,new_type,类型例2.11,#define YYSTYPE treeptr,typedef struct tnode int data；,struct tnode*left；,struct tnode*right；,treenode，*treeptr；,E ：E+E$=node(+，$1，$3)；,|E*E$=node(*，$1，$3)；,|num$=leaf($1)；,；,就会为,E,构造一棵语法树,所需语义值不止一个类型,YACC源程序中文法符号的语义值往往需要具有不止一种类型，通过C语言提供的,union,机制来解决这一问题定义不同的语义值类型：,%,union,int ival,；,double,dval,；,treeptr tval,；,在声明文法符号的同时说明它们的语义值类型：,%,token num,%token real,%token id,%type E,(,非终结符的说明用,%,type,),注意:,%type,用于说明非终结符的语义值类型,%prec,用于说明非终结符的优先级与结合性,2.2.3.3 YACC源程序的一般书写习惯,设计YACC的产生式时，尽量采用左递归形式。

由于左递归意味着归约先于移进，所以左递归产生式构造的分析器可以使移进/归约分析栈的内容总是保持最少，而右递归意味着移进先于归约，所以右递归产生式构造的分析器，在极端的输入情况下，会使分析栈溢出充分利用优先级和结合性，而不是引进非终结符来解决文法中的冲突，以减少产生式个数特别是尽量防止形如ET的单非产生式，以提高分析速度终结符和非终结符在书写上最好有明确区分，例如分别用大、小写来表示非终结符和终结符，以便于程序的阅读lex与yacc实例看演示,2.2.3.4 YACC对语法错误的处理,没有处理语法错误功能的语法分析器对含有语法错误的输入序列进行分析时，遇到第一个语法错误时分析器就会停止分析这给用户带来极大不便，同时也是不实用的因此，,YACC,提供处理语法错误的机制，它采用的方法是所谓的出错产生式方法不引入出错产生式的情况,在没有适当的语法错误处理的情况下，YACC生成的语法分析器对输入序列进行分析时，遇到语法错误时会由于在栈顶形不成该语言的活前缀形不成产生式的右部，而找不到适当的产生式与之匹配，从而造成栈中元素被连续弹出，直到栈被弹空，迫使分析过程终止一条没有出错处理机制的产生式,%left+,%,E:E+E|num;,(b),分析表的正文形式,(c)图形表示的DFA,(d)在DFA上分析3+5,栈顶内容剩余输入分析器动作,#0 3+5#移进num，转向state 2,#0 num 2+5#按(2)“E:num归约，goto state 1,#0 E 1+5#移进+，转向3,#0 E 1+3 error+5#输入序列中插入error，弹出state 3,#0 E 1error+5#弹出state 1,#0error+5#弹出state 0,#error+5#?,2005年3月4日,引入出错产生式的情况,参加出错产生式：E:E+E|num|error;,图形表示的DFA：,为了解决这一问题，YACC引入了对特殊终结符error的处理，利用它在适当的地方参加假设干出错产生式，即含有特殊终结符error的产生式。

此时有了error的状态转移！,引入出错产生式的情况续,栈顶内容 剩余输入分析器动作,#0 3+5#移进 num，转向state 3,#0 num 3 +5#按(2)“E:num归约，goto State 1,#0 E 1 +5#移进+，转向State 4,#0 E 1+4 error+5#移进error，转向 state 2,#0 E 1+4 error 2+5#按(3)“E:error归约，goto State 5,#0 E 1+4 E 5+5#按(1)“E:E+E归约，goto State 1,#0 E 1+5#移进+，转向State 4,#0 E 1+45#移进 num，转向 State 3,#0 E 1+4 num 3#按(2)“E:num归约，goto State 5,#0 E 1+4 E 5#按(1)“E:E+E归约，goto State 1,#0 E 1#接受,再分析3+5,YACC生成的分析器处理错误的一般原那么,当认为当前有错时栈顶不匹配，即找不到下一个可匹配的终结符，就插入一个error到输入中，并从栈中弹出假设干状态对也可能无需弹出，直到找到含有工程 A.error 的状态如状态4，此时移进 error 可能为空，例如状态4下E.error；移进,按Aerror.归约后，抛弃假设干输入字符可能无需抛弃，最多可能抛弃3个，直到发现一个能回到正常分析的终结符称为同步记号为止。

归约,是否弹栈和是否抛弃假设干输入，视输入序列而定一般模式：,出错插入error在当前输入弹出栈中假设干对也可能不弹出，直到与error匹配归约后抛弃假设干输入也可能不抛弃分析继续进行YACC生成的分析器处理错误的一般原那么续1,4.分析5 5+5，既从栈中弹出假设干状态对，又在归约后抛弃假设,干字符栈顶内容剩余输入分析器动作,#05 5+5#s2,#0 num 25+5#r2，goto State 1,#0 E 1error 5+5#,pop(E,1),#0 error 5+5#s2,#0 error 25+5#r3，goto State 1,#0 E 15+5#,抛弃,5,#0 E 1+5#s4,#0 E 1+45#s3,#0 E 1+4 num 3#r2,goto state 5,#0 E 1+4 E 5#r1,goto state 1,#0 E 1#$end,accept,YACC生成的分析器处理错误的一般原那么续2,为使分析器尽快从错误中恢复过来，YACC提供一个过程yyerrok，执行它后，分析器不再抛弃输入序列中的终结符，使分析器回到正常操作方式在使用yyerrok时应注意，如果产生式形如Aerror，其后语义动作中参加yyerrok时，会使分析器不再抛弃终结符，而这时分析器也不会移进任何终结符，从而使分析器陷入死循环。

如何设计出错产生式,初学者感觉困难的原因,语法错误出现的随机性和文法的复杂性，使得在文法中参加出错产生式去预置对语法错误的处理带有一定的盲目性；,处理机制没有统一标准；,过多地参加error会人为造成冲突，使得有。