1、10/10編譯原理 課程試卷A專業(yè)： 考試日期： 時間： 總分：100分 閉卷一大題：簡答題(每小題6分，共30分)1.什么是文法，按Chomsky文法分類方法，把文法分成了哪幾類？2.編譯程序可以分為哪幾個階段，每個階段的任務(wù)是什么？3. 在編譯程序中，符號表的功能是什么？4. 什么是代碼優(yōu)化？代碼優(yōu)化的主要技術(shù)有哪些？5. 自底向上語法分析方法的基本思想是什么？二大題：若表達式文法GE為：E E+T|E-T |TT T*F | T/F | FF (E)|i1. 請構(gòu)造句型E+T*F 對應(yīng)的語法樹。(4分)2. 請寫出該句型的所有的短語、直接短語、句柄和素短語。(6分)三大題：已知如圖1所示

2、NFA M，請將M轉(zhuǎn)換成與其等價的DFA。(10分)圖1四大題：已知文法GS：S a | b | (T) T STT ，ST| 1. 計算該文法的FIRST、FOLLOW、SELECT集合。(10分)2. 上述文法是LL(1)文法嗎?若是，則構(gòu)造LL(1)分析表。(10分)五大題：已知文法GS：A aAb | aAd | 1. 構(gòu)造該文法的識別LR(0)活前綴的DFA。(10分)2. 說明該文法不是LR(0)文法，是SLR(1)文法，并構(gòu)造SLR(1)分析表。(10分)六大題：根據(jù)以下的基本塊：B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B

3、*5L:=K+JM:=L1構(gòu)造基本塊對應(yīng)的DAG圖。(5分)2若G，M，L在基本塊后要引用，寫出優(yōu)化后的代碼(5分)。編譯原理試卷A答案一大題：1.答：詞法分析階段：讀源程序，對字符流進行掃描和分解，識別出一個個單詞。語法分析階段：將單詞分解成各類語法短語。語義分析階段：審查源程序有無語義錯誤，為代碼生成階段收集類型信息。中間代碼生成階段：半源程序變成一種內(nèi)部表示形式。代碼優(yōu)化階段：對中間代碼進行變換或改造，使生成的目標(biāo)代碼更為高效。目標(biāo)代碼生成階段：把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。2.答：文法是一個四元組（VN,VT,P,S），其中VN為非終結(jié)符號

4、集，VT為終結(jié)符號集，P為產(chǎn)生式集，S為開始符號。按喬姆斯基分類，把文法分成四種類型：0型（短語文法）、型（上下文有關(guān)文法）、型（上下文無關(guān)文法）、型（正規(guī)文法）。3.答：對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串，重復(fù)這一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，也就確認輸入串是文法的句子。4.答：符號表的功能：收集符號屬性；上下文語義的合法性檢查的依據(jù)；作為目標(biāo)代碼生成階段地址分配的依據(jù)。5.答：優(yōu)化就是對代碼進行等價變換，使得變換后的代碼運行把那間與變換前

5、代碼運行結(jié)果相同，而運行速度加大或占用存儲空間少，或兩者都有。優(yōu)化技術(shù)有：刪除多余運算、代碼外提、強度削弱、變換循環(huán)控制條件、合并已知量與復(fù)寫傳播、刪除無用賦值。二大題： 解： E E + TT * F短語：T*F,E+T*F 直接短語：T*F句柄：T*F 素短語：T*F三大題：解：abA00,11B0,10,11C10a得DFA為： 四大題：解：是否=First集Follow集S否a,b,（，,）,#T否a,b,（）T是，,）Select(Sa)=a select(Sb)=b select(S(T)=（Select(TST)=a,b,（ select(T，ST )=， select(T)=）改寫后文法中，相同左部非終結(jié)符對應(yīng)的兩條不同產(chǎn)生式的select集交集均為空改寫后文法是LL（1）文法（2）LL（1）分析表為：ab（），#Sab(T)T，STTSTSTST五大題：解：（1）拓廣文法為:(1)AA (1)AaAb (2)AaAd (3)A 構(gòu)造LR(0)識別活前綴的DFA：=在I0、I2項目集中，存在移進歸約沖突，故不是LR（0）文法。又afollow(A)=ab,d,#=移歸沖突可以用SLR（）的簡單的向右查看一個符號的方法解決該文法是SLR（1）文法(2)改進的SLR(1)分析表為：狀態(tài)ACTIONGOTOabd#A0S2r3r3r31