《哈工大編譯原理4-5》由會員分享，可在線閱讀，更多相關(guān)《哈工大編譯原理4-5（19頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、,單擊此處編輯母版標(biāo)題樣式,計算機學(xué)院,辛明影,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第四章 語法分析,1,4.5,LR,分析方法對二義文法的應(yīng)用,任何二義文法都不是,LR,文法,某些二義文法對語言的說明和實現(xiàn)非常有用，如描述表達式的文法：,E,E,E|E*E|(E)|id,規(guī)定優(yōu)先級和結(jié)合率,無二義文法：,EE+T|T,TT*F|F,F(E)|,id,計算機學(xué)院,2,辛明影,例：,描述,if,語句的文法：,stmt,if,expr,then,stmt,|,if,expr,then,stmt,else,stmt,|,other,規(guī)定匹,配原則,無二義文法,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,計算機學(xué)院,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,*,),+,計算機學(xué)院,4,辛明影,FOLLOW(E)=$,FOLLOW(E)=$,+,*,),E,E+E,I,7,E,E,+E,E,E,*E,在,I,7,狀態(tài)，遇,+,，根據(jù)左結(jié)合率，應(yīng)對棧內(nèi),+,歸約,規(guī)定*優(yōu)先級高于,
4、+,*,、,+,為左結(jié)合率,在,I,7,狀態(tài)，遇*，根據(jù)優(yōu)先級，應(yīng)將*移入棧內(nèi),E,E*E,I,8,E,E,+E,E,E,*E,在,I,8,狀態(tài)，遇*，根據(jù)左結(jié)合率，應(yīng)對棧內(nèi)*歸約,在,I,8,狀態(tài)，遇,+,，根據(jù)優(yōu)先級，應(yīng)對棧內(nèi)*歸約,計算機學(xué)院,5,辛明影,表4.11 文法,G,4.,4,的,SLR,分析表,計算機學(xué)院,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,計算機學(xué)院,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,狀態(tài)遇,e,，,棧內(nèi)符號為,iS,，,根據(jù)最近匹配原則應(yīng)移入,e,Follow(S)=$,e,計算機學(xué)院,8,辛明影,計算機學(xué)院,9,辛明影,LR(k),和,LL(k),的比較,1.A,1,2,LL(k),根據(jù)
6、FIRST(,i,),確定使用哪條產(chǎn)生式；而,LR(k),是在識別出整個,后,再往后看,k,個符號,然后,確定使用哪條產(chǎn)生式。,w,A,w,A,計算機學(xué)院,10,辛明影,LL(k),文法都是,LR(k),文法。,2.,都能用形式化方法實現(xiàn)；,3.,非,LR,結(jié)構(gòu),例：,L=,ww,R,wa,b*,GS:,SaSa,bSb,4.,LR(k),分析,用,手工構(gòu)造是不可能的。類,Pascal,語言的,LR(1),分析表，估計要數(shù)千 個狀態(tài)；由于有軟件工具，,LR,分析,受,到廣泛重視。,計算機學(xué)院,11,辛明影,4.5,分析器的生成器,Yacc,一,.,用,生成器,Yacc,構(gòu)造翻譯器的過程,Yac
7、c,編,譯器,yacc,源程序,translate.y,y.tab.c,C,編,譯器,y.tab.c,a.out,a.out,源程序,輸出,計算機學(xué)院,12,辛明影,二,.,Yacc,源程序有三部分組成 聲明 翻譯規(guī)則,C,寫的支持例程,三,.,例,4.21,臺式計算器,GE:E,E+T T,T T*F F,F(E)digit,讀入一個表達式，計算它的值并輸出,。,計算機學(xué)院,13,辛明影,%,#,include ,%,%token digit,%,line :,exprn,printf(“%dn”,$1);,;,expr,:,expr,+term$=$1+$3;,:term,;,計算機學(xué)院,
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 ;,計算機學(xué)院,15,辛明影,聲明部分,有任選的兩節(jié)。,第一節(jié)處于分界符,%,和,%,之間，它是一 些普通的,C,的聲明；,第二節(jié)是文法記號的聲明。,翻譯規(guī)則部分,每條翻譯規(guī)則由一個文法產(chǎn)生式和有關(guān)的語義動作組成。,支持例程部分,一些,C,寫的支持例程。,例：,詞法分析器，錯誤恢復(fù)例程等。,計算機學(xué)院,16,辛明影,總結(jié)：,自頂向下分析,遞歸預(yù)測分析（遞歸子程序法）,非遞歸預(yù)測分析,LL(1),注,意：首先消除左遞歸和提取左公因子。,自底向上分析,算符優(yōu)先分析,LR,分析,:LR(0),SLR(1),LR(1),LALR(1),計算機學(xué)院,17,辛明影,LL(0),LR(0),SLR,LALR,LR(1),LR(k),LL(1),LL(k),Unambiguous Grammars,Ambiguous,Grammars,文法類的譜系,計算機學(xué)院,18,辛明影,作業(yè)：,4-40,第 一問,3-37,第 一問,計算機學(xué)院,19,辛明影,
哈工大編譯原理4-5
