哈工大编译原理4-5

《哈工大编译原理4-5》由会员分享，可在线阅读，更多相关《哈工大编译原理4-5（19页珍藏版）》请在装配图网上搜索。

1、,单击此处编辑母版标题样式,计算机学院,辛明影,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 语法分析,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,ma

2、tched_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+,

3、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,状态，遇,+,，根据左结合率，应对栈内,+,归约,规定*优先级高于,

4、+,*,、,+,为左结合率,在,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,文

5、法可改为：,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),根据

6、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,构造翻译器的过程,Yac

7、c,编,译器,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,;,计算机学院,

8、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,辛明影,