第11讲编译原理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,3.7,分析器的生成器,3.7.1,分析器的生成器,Yacc,Yacc,编译器,Yacc,源程序,translate.y,y.tab.c,C,编译器,y.tab.c,a.out,a.out,输入,输出,Lex,编译器,Lex,源程序,lex.l,lex.yy.c,C,编译器,lex.yy.c,a.out,a.out,输入流,记号序列,用,Lex,建立词法分析器的步骤,Yacc,程序包括三个部分,声明,翻译规则,支持例程,3.7 分析器的生成器,例,-,声明部分,%,#include,/,*,常量、变量的声明,*,/,%,%token DIGIT,%,3.7,分析器的生成器,E,E+T|T,TT*F|F,F(E)|digit,例,-,翻译规则部分,line:,expr,n,printf(“%dn,”,$1);,;,expr,:,expr,+term$=$1+$3;,|term,;,term:term*factor$=$1*$3;,|factor,;,factor:(,expr,)$=$2;,|DIGIT,;,%,3.7,分析器的生成器,E,E+T|T,TT*F|F,F(E)|digit,例,-,支持例程部分,yylex,(),int,c;,c=,getchar,();,if(,isdigit(c,),yylval,=c 0;,return DIGIT;,return c;,3.7,分析器的生成器,E,E+T|T,TT*F|F,F(E)|digit,3.7,分析器的生成器,3.7.2,用,Yacc,处理二义文法,解决分析动作冲突的两大默认规则：,对于归约,-,归约冲突，选择在,Yacc,程序中最先出现的那个产生式归约,对于移进,-,规约冲突，优先移进,3.7,分析器的生成器,3.7.2,用,Yacc,处理二义文法,例,台式计算器,输入一个表达式并回车，显示计算结果。,也可以输入一个空白行。,lines,lines,expr,n|lines n|e,E E+E|E E|E*E|E/E|(E)|-E|number,3.7,分析器的生成器,%,#,include ,#include ,#define YYSTYPE double /,*,将栈定义为,double,类型,*,/,%,%,token NUMBER,%left +,%left ,*,/,%right UMINUS,%,lines,lines,expr,n|lines n|e,E E+E|E E|E*E|E/E|(E)|-E|number,3.7,分析器的生成器,lines:lines,expr,n ,printf,(“%g n”,$2),|lines n,|/,*,*,/,;,expr,:,expr,+,expr,$=$1+$3;,|,expr,expr,$=$1,$3;,|,expr,*,expr,$=$1,*,$3;,|,expr,/,expr,$=$1/$3;,|(,expr,)$=$2;,|,expr,%,prec,UMINUS$=,$2;,|NUMBER,;,%,lines,lines,expr,n|lines n|e,E E+E|E E|E*E|E/E|(E)|-E|number,3.7,分析器的生成器,yylex,(),int,c;,while(c=,getchar,()=);,if(c=.)|(,isdigit,(c),ungetc,(c,stdin,);,scanf,(“%lf”,&,yylval,);,return NUMBER;,return c;,lines,lines,expr,n|lines n|e,E E+E|E E|E*E|E/E|(E)|-E|number,3.7,分析器的生成器,3.7.3,Yacc,的错误恢复,编译器设计者,的工作,决定哪些“主要的”非终结符将有错误恢复与它们相关联,加入,A,error,的,错误产生式,，其中,A,是主要非终结符，,是文法符号串,为这样的产生式配上语义动作,Yacc,把错误产生式当作普通产生式处理,3.7,分析器的生成器,遇到语法错误时,从栈中弹出状态，直到发现栈顶状态的项目集包含形为,A,error,的项目为止,把虚构的终结符,error,“,移进”栈,若,为,，,直接进行产生式规约，并执行相关的语义动作,，,忽略若干输入符号，直至发现能回到正常处理的符号为止。,若,不为,，,找到,，,把,移进栈,把,error,归约为,A,，,恢复正常分析。,s,.,.,.,.,.,.,栈,.,.,a.,A,发现错误,s,:,C,1,A,2,A,b,A,error,.,C,1,A,2,.,A,A,b,.,b,3.7,分析器的生成器,lines:lines,expr,n,printf,(“%g n”,$2),|lines n,|/,/,|error n,printf,(“,重新输入上一行”);,yyerrok,;,;,语法分析内容总结,文法和语言的基本知识,自上而下的分析方法：预测分析，非递归的预测分析，,LL(1),文法,自下而上的分析方法：,SLR(1),方法，规范,LR(1),方法和,LALR(1),方法,语法分析内容总结,自上而下分析,LL(1),文法判定原则,FIRST,、,FOLLOW,集的计算,（重点）,LL(1),文法判定方法,LL(1),分析实现方法,递归函数实现,非递归的预测分析实现,先求,FIRST,、,FOLLOW,集,画预测分析表,语法分析内容总结,书后,3.19,，,3.20,等题目都是判断是否属于某类文法，判定文法是否是,LL(1),文法步骤如下：,如果有以下两种情况一定不是,左递归,公共左因子,如果不是，则改写文法,消除左递归,提取左因子,改写后进行,LL(1),分析,语法分析内容总结,例,1,文法,GS:,S-,aSb,|P,P-,bPc,|,bQc,Q-,Qa,|a,(1),判断这个文法是不是,LL(1),的？,(2),消除左递归、提取左因子之后的文法,G,是否是,LL(1),的？,语法分析内容总结,解答：,首先，,GS,不是,LL(1),的,!,GS:,S-,aSb,|P,P-,bPc,|,bQc,Q-,Qa,|a,语法分析内容总结,例,1,解答：,提取左因子，,将,P-,bPc,|,bQc,变为,P-,bP,P-Pc|Qc,消除左递归，将,Q-,Qa,|a,变为,Q-,aQ,Q-,aQ,|,GS:,S-,aSb,|P,P-,bPc,|,bQc,Q-,Qa,|a,语法分析内容总结,例,1,解答：,判定文法,GS,是否,LL(1),步骤：,计算,FIRST,FOLLOW,集,GS:,S-,aSb,|P,P-,bP,P-Pc|Qc,Q-,aQ,Q-,aQ,|,语法分析内容总结,FIRST(S)=a,b,FIRST(P)=b,FIRST(P)=a,b,FIRST(Q)=a,FIRST(Q)=a,FOLLOW(S)=b,$,FOLLOW(P)=,b,c,$,FOLLOW(P)=,b,c,$,FOLLOW(Q)=c,FOLLOW(Q)=c,GS:,S-,aSb,|P,P-,bP,P-Pc|Qc,Q-,aQ,Q-,aQ,|,是,LL(1),的,语法分析内容总结,例,2,文法,GE:,E-T,T-TE|F,F-a|,aF,(1),判断这个文法是不是,LL(1),的？,(2),消除左递归、提取左因子之后的文法,G,是否是,LL(1),的？,语法分析内容总结,例,1,解答：,提取左因子，消除左递归后,文法变为,GE:,E-T,T-F T,T-ET|,F-,aF,F-F|,GS:,E-T,T-TE|F,F-a|,aF,语法分析内容总结,FIRST(E)=,FIRST(T)=a,FIRST(T)=,FIRST(F)=a,FIRST(F)=a,FOLLOW(E)=,$,FOLLOW(T)=,$,FOLLOW(T)=,$,FOLLOW(F)=,FOLLOW(F)=,GE:,E-T,T-F T,T-ET|,F-,aF,F-F|,不是,LL(1),文法！,通过提取左因子和消除左递归的方法，并不一定能够把文法改写为一个,LL(1),文法,语法分析内容总结,左递归的消除,GS:,S-,Qc|c,Q-,Sa|a,间接左递归,语法分析内容总结,左递归的消除,GS:,S-,Qc|c,Q-,Sa|a,这是一类间接左递归,S-,Sac|ac|c,Q-,Sa|a,语法分析内容总结,左递归的消除,GS:,S-,Qc|c,Q-,Sa|a,间接左递归,S-,Sac|ac|c,Q-,Sa|a,S-,acS,|,cS,S-,acS,|,Q-,Sa|a,语法分析内容总结,自下而上分析部分知识点,SLR,的,DFA,的构造及分析表的构成,初始项目集合的产生（拓广文法）,能够识别同一符号的项目都转移到同一集合中,求闭包过程中每一个“,.”,后面的非终结符都要重新考虑是否已经在状态中列出,对产生式,A-,规约，,“,r,i,”,写在,FOLLOW(A),集合中元素对应的位置。,语法分析内容总结,LR,LALR,的构造方法（在,SLR,的基础上加上搜索符）,搜索符的求法，根据造成目前项目出现的那个父项目来求。,求闭包的过程中可能出现要添加的项目已经存在，但是搜索符不同的情况，相当于其父项目已经改变，此时需要再求一遍搜索符。,SLR,LR,LALR,的区别及判别方法,通过构造,DFA,，看其中的状态是否有冲突（“移进,规约”或“规约,规约”）若有冲突则不属于该文法类型。,通过构造分析表，看其中某项是否有冲突。,语法分析内容总结,文法,GS:,S-,AaS,|,bAe,|,BeS,|,bBa,A-d,B-d,判断这个文法类型是,SLR(1),、,LR(1),还是,LALR(1),？,补充题 1,下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法,S,S and S|S or S|not S|p|q|(S),非二义文法的产生式如下：,E,E or T|T,T,T and F|F,F,not F|(E)|p|q,补充题 1,下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法,S,S and S|S or S|not S|p|q|(S),非二义文法的产生式如下：,E,E or T|T,T,T and F|F,F,not,E,|(E)|p|q,补充题 1,下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法,S,S and S|S or S|not S|p|q|(S),非二义文法的产生式如下：,E,E or T|T,T,T and F|F,F,not,E,|(E)|p|q,not p and q,有两种不同的最左推导,补充题,2,设计一个文法:字母表,a,b,上,a,和,b,的个数相等的所有串,的集合,二义文法：,S,a S b S,|,b S a S,|,ab,ab,a,ba,b,补充题,2,设计一个文法:字母表,a,b,上,a,和,b,的个数相等的所有串,的集合,二义文法：,S,a S b S,|,b S a S,|,ab,ab,a,ba,b,二义文法：,S,a B,|,b A,|,A,a S,|,b A A,B,b S,|,a B B,补充题,2,设计一个文法:字母表,a,b,上,a,和,b,的个数相等的所有串,的集合,二义文法：,S,a S b S,|,b S a S,|,ab,ab,a,ba,b,二义文法：,S,a B,|,b A,|,A,a S,|,b A A,B,b S,|,a B B,BB,bSbS,的选择,b,ba,b,bb,ab,非二义文法：,S,a B S,|,b A S,|,A,a,|,b A A,a,abb,abab,B,b,|,a B B,补充题,3,试说明下面文法不是,LR(1),的：,L,M L b|a,M,M,b,L,L,L,L,a,M,b,M,b,句子,abbb,的分析树