《編譯原理》課程試卷A及答案

編譯原理課程試卷A專業(yè)：考試日期： 時間： 總分：100分閉卷一大題：簡答題（每小題6分，共30分）:號學什么是文法，按Chomsky文法分類方法，把文法分成了哪幾類？:號學編譯程序可以分為哪幾個階段，每個階段的任務是什么？在編譯程序中，符號表的功能是什么？什么是代碼優(yōu)化？代碼優(yōu)化的主要技術有哪些？..名姓自底向上語法分析方法的基本思想是什么？..名姓二大題：若表達式文法G[E]為：E—E+TIE-TITT—T*FIT/FIFF—（E）li請構造句型E+T*F對應的語法樹。（4分）?級班業(yè)專請寫出該句型的所有的短語、直接短語、句柄和素短語。（6分）?級班業(yè)專三大題：已知如圖1所示NFAM,請將M轉換成與其等價的DFAo（10分）?.系院?.系院四大題：已知文法G[S]：S—a丨b丨（T）T—ST'tj,stq￡計算該文法的FIRST、FOLLOW、SELECT集合。（10分）上述文法是LL（1）文法嗎?若是，則構造LL（1）分析表。（10分）五大題：已知文法G[S]：A—aAb|aAd|￡構造該文法的識別LR（0）活前綴的DFAo（10分）說明該文法不是LR（0）文法，是SLR⑴文法，并構造SLR⑴分析表。（10分）六大題：根據(jù)以下的基本塊：B:=3D:二A+CE:二A*CF:二D+EG:二E*FH:二A+CI:=A*CJ:二H+IK:=B*5L:二K+JM:=L構造基本塊對應的DAG圖。（5分）若G,M,L在基本塊后要引用，寫出優(yōu)化后的代碼（5分）。..號學..名姓?級班業(yè)專代碼或匯編指令代碼。階段地址分配的依據(jù)。..號學..名姓?級班業(yè)專代碼或匯編指令代碼。階段地址分配的依據(jù)。編譯原理試卷A答案一大題：或1.答：詞法分析階段：讀源程序，對字符流進行掃描和分解，識別出一個個單詞。I 語法分析階段：將單詞分解成各類語法短語。I 語義分析階段：審查源程序有無語義錯誤，為代碼生成階段收集類型信息。i 中間代碼生成階段：半源程序變成一種內部表示形式。j 代碼優(yōu)化階段：對中間代碼進行變換或改造，使生成的目標代碼更為高效。目標代碼生成階段：把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令答：文法是一個四元組（VN,VT,P,S）,其中Vn為非終結符號集，V］為終結符號集，P為產(chǎn)生式集，s為開始符號。按喬姆斯基分類，把文法分成四種類型：0型（短語文法）、1型訂 （上下文有關文法）、2型（上下文無關文法）、3型（正規(guī)文法）。答：對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，就用該產(chǎn)生式的左部非終結符代替相應右部的文法符號串，重復這一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，也就確認輸入串是文法的句子。答：符號表的功能：收集符號屬性；上下文語義的合法性檢查的依據(jù)；作為目標代碼生成答：優(yōu)化就是對代碼進行等價變換，使得變換后的代碼運行把那間與變換前代碼運行結果相同，而運行速度加大或占用存儲空間少，或兩者都有。優(yōu)化技術有：刪除多余運算、代裝碼外提、強度削弱、變換循環(huán)控制條件、合并已知量與復寫傳播、刪除無用賦值。二大題：E+T?.系院解： EE+T?.系院直接短語：T*F素短語：T*F短語：直接短語：T*F素短語：T*F句柄：T*F三大題：解:abA{0}{0,1}{1}B{0,1}{0,1}{1}C{1}{0}①解:是否=>￡First集Follow集s否{a,b,(}{，,),#}T否{a,b,(}{)}V是{{)}Select(S—a)={a}select(Sfb)=select(Sf(T))={(}Select(TfST')={a,b,(}select(T'f,ST')={,} select(T'f￡)={)}???改寫后文法中，相同左部非終結符對應的兩條不同產(chǎn)生式的select集交集均為空???改寫后文法是LL(1)文法(2)LL(1)分析表為：ab()#S—a—b-(T)TfST'T，—ST，—ST，fST，f￡五大題：解：(1)拓廣文法為:(0)A'^A (l)A-aAb(2)A—aAd(3)A—￡構造LR(0)識別活唇的DFA：???在I。丄項目集中，存在移進歸約沖突，故不是LR(0)文法。又{a}Plfollow(A)二{a}Pl{b,d,#}二①移歸沖突可以用SLR(1)的簡單的向右查看一個符號的方法解決???該文法是SLR(1)文法(2)改進的SLR⑴分析表為：狀態(tài)A