单击此处编辑母版标题样式,计算机学院,辛明影,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 语法分析,1,4.5,LR,分析方法对二义文法的应用,任何二义文法都不是,LR,文法,某些二义文法对语言的说明和实现非常有用，如描述表达式的文法：,E,E,E|E*E|(E)|id,规定优先级和结合率,无二义文法：,EE+T|T,TT*F|F,F(E)|,id,计算机学院,2,辛明影,例：,描述,if,语句的文法：,stmt,if,expr,then,stmt,|,if,expr,then,stmt,else,stmt,|,other,规定匹,配原则,无二义文法,stmt,matched_stmt,|,unmatched_stmt,matched_stmt,if,expr,then,matched_stmt,else,matched_stmt,|,other,unmatched_stmt,if,expr,then,matched_stmt,else,unmatched_stmt,|if,expr,then,_stmt,计算机学院,3,辛明影,E,E,I,0,E,E+E,E,E*E,E,(E),E,id,E,E,I,1,E,E,+E,E,E,*E,E,E,(E),E,E+E,E,E*E,E,(E),E,id,I,2,(,E,id,I,3,id,id,(,+,E,E+,E,E,E+E,E,E*E,E,(E),E,id,I,4,E,E,E*E,E,E,+E,E,E,*E,例,：,E,E,E|E*E|(E)|id,E,(E.),I,6,E,E,+E,E,E,*E,E,E+E,E,E,+E,E,E,*E,E,(E).,I,9,E,E*,E,E,E+E,E,E*E,E,(E),E,id,I,5,I,7,I,8,(,id,I,3,*,E,(,id,*,),+,计算机学院,4,辛明影,FOLLOW(E)=$,FOLLOW(E)=$,+,*,),E,E+E,I,7,E,E,+E,E,E,*E,在,I,7,状态，遇,+,，根据左结合率，应对栈内,+,归约,规定*优先级高于,+,*,、,+,为左结合率,在,I,7,状态，遇*，根据优先级，应将*移入栈内,E,E*E,I,8,E,E,+E,E,E,*E,在,I,8,状态，遇*，根据左结合率，应对栈内*归约,在,I,8,状态，遇,+,，根据优先级，应对栈内*归约,计算机学院,5,辛明影,表4.11 文法,G,4.,4,的,SLR,分析表,计算机学院,6,辛明影,描述,if,语句的文法：,stmt,if,expr,then,stmt,|,if,expr,then,stmt,else,stmt,|,other,悬空,else,的二义性,用,I,表示,if,expr,then,，,e,表示,else,a,表示,other,文法可改为：,S,S,S,iSeS|iS|a,计算机学院,7,辛明影,S,S,I,0,S,iSeS,S,iS,S,a,S,S,I,1,S,i,SeS,I,2,S,i,S,S,iSeS,S,iS,S,a,S,a,I,3,S,i S,eS,I,4,S,i S,S,i Se,S,I,5,S,iSeS,S,iS,S,a,S,i S,eS,I,6,S,i,a,S,i,a,e,S,i,a,在,I,4,状态遇,e,，,栈内符号为,iS,，,根据最近匹配原则应移入,e,Follow(S)=$,e,计算机学院,8,辛明影,计算机学院,9,辛明影,LR(k),和,LL(k),的比较,1.A,1,2,LL(k),根据FIRST(,i,),确定使用哪条产生式；而,LR(k),是在识别出整个,后,再往后看,k,个符号,然后,确定使用哪条产生式。
w,A,w,A,计算机学院,10,辛明影,LL(k),文法都是,LR(k),文法2.,都能用形式化方法实现；,3.,非,LR,结构,例：,L=,ww,R,wa,b*,GS:,SaSa,bSb,4.,LR(k),分析,用,手工构造是不可能的类,Pascal,语言的,LR(1),分析表，估计要数千 个状态；由于有软件工具，,LR,分析,受,到广泛重视计算机学院,11,辛明影,4.5,分析器的生成器,Yacc,一,.,用,生成器,Yacc,构造翻译器的过程,Yacc,编,译器,yacc,源程序,translate.y,y.tab.c,C,编,译器,y.tab.c,a.out,a.out,源程序,输出,计算机学院,12,辛明影,二,.,Yacc,源程序有三部分组成 声明 翻译规则,C,写的支持例程,三,.,例,4.21,台式计算器,GE:E,E+T T,T T*F F,F(E)digit,读入一个表达式，计算它的值并输出,计算机学院,13,辛明影,%,#,include ,%,%token digit,%,line :,exprn,printf(“%dn”,$1);,;,expr,:,expr,+term$=$1+$3;,:term,;,计算机学院,14,辛明影,term :term*,facter,$=$1*$3;,:,facter,;,facter,:(,expr,)$=$2;,:digit,;,%,yylex,(),int,c;,c=,getchar,();,if (,isdigit,(c),yylval,=c-0;,return digit ;,return c ;,计算机学院,15,辛明影,声明部分,有任选的两节。
第一节处于分界符,%,和,%,之间，它是一 些普通的,C,的声明；,第二节是文法记号的声明翻译规则部分,每条翻译规则由一个文法产生式和有关的语义动作组成支持例程部分,一些,C,写的支持例程例：,词法分析器，错误恢复例程等计算机学院,16,辛明影,总结：,自顶向下分析,递归预测分析（递归子程序法）,非递归预测分析,LL(1),注,意：首先消除左递归和提取左公因子自底向上分析,算符优先分析,LR,分析,:LR(0),SLR(1),LR(1),LALR(1),计算机学院,17,辛明影,LL(0),LR(0),SLR,LALR,LR(1),LR(k),LL(1),LL(k),Unambiguous Grammars,Ambiguous,Grammars,文法类的谱系,计算机学院,18,辛明影,作业：,4-40,第 一问,3-37,第 一问,计算机学院,19,辛明影,。
