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

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