,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,復習要點,第,1,章 引論,編譯程序、解釋程序,編譯程序的,5,個階段,遍,編譯前端與后端,復習要點,高級語言極其語法描述（,P2.3,節(jié)）,上下文無關(guān)文法、最左推導、最右推導、句子、句型、語言、語法分析樹、二義性文、形式語言分類,復習要點,詞法分析,正規(guī)式、正規(guī)集、有限自動機（確定的有限自動機、非確定的有限自動機）,三者之間的相互轉(zhuǎn)化,自動機的確定化、化簡,復習要點,語法分析,-,自上而下分析,遞歸下降分析法,LL,（,1,）分析法,消除左遞歸、提左因子、,FIRST,集、,FOLLOW,集,P73:LL(1),文法的判定條件,LL(1),分析器的構(gòu)造：,P76-79,復習要點,語法分析,-,自下而上分析,移進,-,歸約、規(guī)范規(guī)約、短語、直接短語、句柄,算符優(yōu)先分析,算符文法、素短語、最左素短語,LR,分析法,LR(0),、,SLR,LR,分析法考核要點,構(gòu)造文法,GS,的,LR(0),項目集規(guī)范族及相應(yīng)的,DFA,。,構(gòu)造文法的,LR(0),或,SLR,分析表,對于輸入串,xxxxxxx,，給出,LR(0),或,SLR,分析器所作出的動作。,復習要點,屬性文法和語法制導翻譯,屬性文法、繼承屬性、綜合屬性、,S-,屬性文法、,L-,屬性文法、翻譯模式,S-,屬性文法的自下而上計算,復習要點,語義分析和中間代碼產(chǎn)生,中間語言形式：后綴式、三地址代碼（主要是四元式）,控制語句的翻譯,字母表,0,1,2,3,對給定正則表達式,0*,（,1|23,）（,0|12,）,0,（,1|13,）,*,構(gòu)造與之等價的,NFA M,。,習題舉例,設(shè)文法,G(S):SS+aF|aF|+aFF*aF|*a,消除左遞歸和回溯；,構(gòu)造非終結(jié)符的,FIRST,和,FOLLOW,集合；,構(gòu)造預測分析表,(4),給出句子,a*a+a*a,的,LL(1),分析過程,（格式：棧，輸入緩沖區(qū)，動作）,習題舉例,解：,SaFS|+aFSS+aFS|F*aFFF|,FIRST(S)=a,+FOLLOW(S)=#FIRST(S)=+,FOLLOW(S)=#FIRST(F)=*FOLLOW(F)=+,#FIRST(F)=*,)FOLLOW(F)=+,#,習題舉例,-,a,+,*,#,S,SaFS,S+aFS,-,-,S,-,S+aFS,-,S,F,-,-,F*aF,-,F,-,F,FF,F,習題舉例,文法,GS,的產(chǎn)生式為：,S,S+A|A,A,A*S|B,B,a|,（,S,）,給出（,a+a,）,*,a,的最左推導、最右推導及相應(yīng)的分析樹；,列出句型,B+A*B,的所有短語、直接短語和句柄。,習題舉例,已知文法,G=(b,e,f,S,S,R,T,S,P),其中,P:,(0)SS (1)SbRST (2)SbR,(3)Re (4)Tf,構(gòu)造 文法的,LR,（,0,）項目集規(guī)范族,構(gòu)造 識別活前綴的,DFA,這個文法哪類,LR,文法并說明理由,習題舉例,S,S,S,bRST,S,bR,I,0,S S,I,1,S,Sb,RST,R,e,Sb,R,I,2,b,Re,I,4,e,SbR,ST,SbR,S,bRST,S,bR,I,3,R,b,S,SbRS,T,T,f,I,5,Tf,I,7,f,SbRST,I,6,T,狀態(tài),action,goto,b,e,f,#,S,R,T,0,S,2,1,1,acc,2,S,4,3,3,S,2,r,2,r,2,5,4,r,3,r,3,r,3,5,S,7,6,6,r,1,r,1,7,r,4,r,4,狀態(tài)棧,符號棧,輸入緩沖區(qū),動作,0,#,bebef#,S,2,02,#b,ebef#,S,4,024,#be,bef#,r,3,023,#bR,bef#,S,2,0232,#bRb,ef#,S,4,02324,#bRbe,f#,r,3,02323,#bRbR,f#,r,2,0235,#bRS,f#,S,7,02357,#bRSf,#,r,4,02356,#bRST,#,r,1,01,#S,#,acc,