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