華南農(nóng)業(yè)大學(xué)編譯原理題庫

1、標(biāo)準(zhǔn)華南農(nóng)業(yè)大學(xué)期末考試題庫(含參考答案)考試科目： 編譯原理考試時間： 120 分鐘得分學(xué)號姓名年級專業(yè)題號一二三四五總分得分評閱人得分一、本題共 6小題，每小題 5分，共 30 分1、寫出下面右線性正規(guī)文法所對應(yīng)的正規(guī)式。S aDD bD | aA | b文法所對應(yīng)的正規(guī)式為：A aDa(b|aa)*b2、給出下面語言集合的上下文無關(guān)文法。 (2010 2014)L1= anbm | nm 1文法：S aS | DD aDb | ab2、為正規(guī)集 L 2=a nbm ck | n1, m1,k 1構(gòu)造一右線性正規(guī)文法 (2010)S aS | aAA bA | bBB cB | c3、按照

2、編譯過程的 5 個階段得到編譯程序的邏輯結(jié)構(gòu)框圖如下：文案標(biāo)準(zhǔn)文案標(biāo)準(zhǔn)4、簡述編譯過程的 5個階段及各階段的主要功能。 （多年必考）編譯過程即編譯程序的工作過程，是指從輸入源程序開始到輸出目標(biāo)程序為 止的整個過程，是非常復(fù)雜的，就其過程而言，一般可以劃分為五個工作階 段：詞法分析，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個個的 單詞；語法分析，根據(jù)語言的語法規(guī)則，把單詞符號串組合成各類語法單 位；語義分析與中間代碼產(chǎn)生，即對各類語法單位，分析其含義并進(jìn)行初 步翻譯；代碼優(yōu)化，對代碼進(jìn)行等價變換，以期產(chǎn)生更高效的代碼；目 標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級語言指令形式。5、“含有優(yōu)

3、化部分的編譯程序的執(zhí)行效率更高。 ”這句話對嗎？為什么？ 這句話是錯的。優(yōu)化不是編譯程序必須的一個部分，含有優(yōu)化的編譯程序 功能更強(qiáng)、算法更復(fù)雜，因而開發(fā)效率和執(zhí)行效率低些，但得到的目標(biāo)代 碼的效率通常更高。6、簡述語法制導(dǎo)翻譯技術(shù)的基本思想。 （2013）語法制導(dǎo)翻譯技術(shù)的基本思想是，對文法中的每個產(chǎn)生式都附加一個語義 動作或語義子程序，在執(zhí)行語法分析的過程中，當(dāng)運用該產(chǎn)生式進(jìn)行推導(dǎo) 或歸約時，就執(zhí)行相應(yīng)的語義動作，從而完成預(yù)定的翻譯工作。7、簡述算符優(yōu)先分析方法。 （ 2013）算符優(yōu)先分析方法是一種移進(jìn) -歸約的語法分析方法， 這種分析方法首先要 根據(jù)文法來確定終結(jié)符之間的優(yōu)先關(guān)系，然后

4、借助這種優(yōu)先關(guān)系，在移進(jìn) -歸約過程中通過比較相鄰終結(jié)符之間的優(yōu)先關(guān)系來確定句型的可歸約串 （最左素短語）并進(jìn)行歸約。它不是一種規(guī)范歸約的分析方法，只適用于 分析算符優(yōu)先文法。8、簡要說明翻譯程序與編譯程序的異同、 編譯程序與解釋程序的異同。 （2011）翻譯程序是將一種語言程序（源）轉(zhuǎn)換成另一種語言程序（目標(biāo)） ，對源語言和 目標(biāo)語言沒特別要求， 編譯程序特指將高級語言的源程序轉(zhuǎn)換成低級語言程序， 是翻譯程序的一種。編譯程序與解釋程序都是將高級語言翻譯成低級語言，但編譯程序要先編譯生 成目標(biāo)代碼、再執(zhí)行目標(biāo)代碼，解釋程序邊轉(zhuǎn)換邊執(zhí)行，不生成目標(biāo)代碼。9、判斷下圖 FA 是 NFA 還是 DF

5、A，并用正規(guī)式來描述它所識別的語言文案11是 DFA(1 分 ) ，對應(yīng)的正規(guī)式為：1*01*(01*01*)* (4 分)10、判斷下圖 FA 是 NFA 還是 DFA，并用正規(guī)式來描述它所識別的語言。 (2011)是 NFA,因為 A狀態(tài)輸入 0可以轉(zhuǎn)換到 A或 B兩狀態(tài)。 等價正規(guī)式： 0*(0|1)(00*(0|1)*11、有文法及其語義子程序如下：S T print(T.h) T T 1*E T.h= T 1.h +E.h T E T.h=E.h E(T)E.h= T.hE a E.h= 1 采用移進(jìn)歸約的分析方法，當(dāng)分析器的輸入為 (a)*(a*a) 時，畫出其語法樹 可以帶注釋、

6、也可以不帶注釋) ，并求輸出的結(jié)果。語法樹(略)，輸入為 (a)*(a*a) 時，輸出的結(jié)果為： 312(2014)、空心圓柱體的表面積計算公式如S=2*3.1416*(R+r)*(R-r)+ 2*3.1416*(R+r)*h采用 LR 語法制導(dǎo)翻譯技術(shù)生成相應(yīng)的三地址代碼，然后運用 DAG 對其進(jìn) 行局部優(yōu)化，試寫出能生成最優(yōu)目標(biāo)代碼的優(yōu)化后的三地址代碼序列?？梢圆捎煤喜⒁阎?、刪除公共子表達(dá)式、刪除無用賦值、交換語句位置等優(yōu)化方法，得到三地址代碼序列如下：(1) T1=R+r(2) T2=6.2832*T1(3) T3=T2*h(4) T4=R-r(5) T5=T2*T4(6) S=T5+

7、T3L1: read C;A=0;B=1;(2). 流圖：2011)13、試求表達(dá)式 A+B*(-C)+B/(-C) 對應(yīng)的后綴式和三地址代碼后綴式： ABC-*+BC-/+三地址代碼：T1=-CT4=-CT2=B*T1T5=B/T4T3=A+T2T6=T3+T514、考慮如下的三地址語句序列： (2011)B1(1) . 將該代碼序列劃分成基本塊，并給每個基本塊一個序號(2) . 畫出該代碼序列的流圖，每個基本塊用 (1) 的序號表(3) . 若有循環(huán)，列出構(gòu)成循環(huán)的節(jié)點 (基本塊) 。(10 分)(1) . 如圖分成四個基本塊 B1、B2、B3、B4(3). 構(gòu)成循環(huán)的基本塊是 B2, B

8、315、有翻譯模式如下：S' S print(S.h) S a S.h=0 S( T )S.h= T.h+1T T 1，S T.h= T 1.h +S.h T S T.h= S.h 采用移進(jìn)歸約的分析方法， 當(dāng)分析器的輸入為 (a,(a) 時，畫出其語法樹 (可 以帶注釋、也可以不帶注釋) ，并求輸出的結(jié)果。(2011)語法樹：S a S輸出結(jié)果是： 2得分、構(gòu)造識別下列語言的最小 DFA （共 20 分）：求出 NFA 得 4 分，確定化了得 6 分，最小 DFA 的 狀態(tài)錯漏一個扣 1 分，弧錯漏一條扣 0.5 分。2、以 101結(jié)尾的二進(jìn)制串；（8 分）求出 NFA得 4分，確定

9、化了得 6分，最小 DFA的 狀態(tài)錯漏一個扣 1 分，弧錯漏一條扣 0.5分。3、不以 101 結(jié)尾的二進(jìn)制串。（5 分）得分構(gòu)造識別下列語言的最小 DFA （共 15 分）：（2011）4、正規(guī)式（ 0|1）* （00 | 11 ）（0|1）* ；（5 分）5、含有奇數(shù)個 1或奇數(shù)個 0 的二進(jìn)制串；（5 分）6、能被 2 整除的二進(jìn)制串。（5 分）1、2、00003、構(gòu)造下列正規(guī)式相應(yīng)的 DFA （用狀態(tài)轉(zhuǎn)換圖表示） （15）（2008）7) 1(0 | 1) *1(9)8）得分8、將下圖 DFA 化簡。（5 分）（2013）首先將 DFA的狀態(tài)集劃分成終態(tài)集和非終態(tài)集 E 、A,B,C,

10、D;得分7、將下圖 NFA 確定化。（10 分）（2013）由于 A,B,C,D 0=B,C,C,E ，所以再分劃成 A,B,C 、D; 對于輸入符號 1，A,B,C 1= ,D,D ，所以再次分劃成 A 、B,C; B,C 0=C,C ，B,C 1=D,D ，所以不用再分， B、 C是等價狀態(tài)。9有文法如下：S a | b | (T) T TeS | S語法樹：（5 分）請給出 （Sebe（a） 的 語法樹、短語、 S直接短語、素短語、句柄。 （10 分）TeT)（2 分）短語：（Sebe（a） 、Sebe（a） 、 Seb、（a） 、 S、 b、 a（1 分） 直接短語： S、b、a（1

11、分） 素短語： b、a（1 分）句柄： S(T)SaSe10有定義算術(shù)表達(dá)式的文法如下： （2011）E E+T | E-T | TT T*F | T/F | FF P F | PP （E） | i語法分析樹：構(gòu)造句型 E+T*P P-i 的語法樹；并指出該句型的所有短語、直接短語、素短 語、句柄。（10 分）所有的短語： E+T*P P-i 、E+T*P P、i 、T*P P、 P P、 PE - T直接短語： P、i 素短語： P P、 i 句柄： P11、有文法如下： （共 15 分）S aSe | ae P（1）構(gòu)造文法的識別規(guī)范句型活前綴的 DFA；（2）分別寫出上一步 DFA各狀態(tài)

12、所識別的活前綴；（3）給出符號串？的 LR移進(jìn)-歸約過程（包括狀態(tài)棧、 符號棧、輸入 串、分析動作）。（1）.（6 分）拓廣文法并給產(chǎn)生式編號：S'S S aSe Sae文法的識別規(guī)范句型活前綴的 DFA：（2）. 文法的所有規(guī)范句型的活前綴就是上一步 DFA各狀態(tài)所識別的符號串： | S | aa* | a*aS | a*ae | a*aSe（3 分）（3）. LR （0）分析表如下 （6 分）：ACTIONGOTOae#S0S211acc空白處表示出錯2S2S433S54r2r2r25r1r1r1得分12有定義算術(shù)表達(dá)式的文法如下：E E+T | E-T | TT T*F | T/

13、F | FF P F | PP （E） | i構(gòu)造句型 P i*（E+F-T） 的語法樹；并指出該句型所有的短語、直接短語、素短語以及句柄。（10 分）語法樹： （5 分）E短語： （2 分）P i*（E+F-T） 、 P i 、 i 、 （E+F-T） 、E+F-T、 E+F、F 直接短語： i 、F （1 分 ） 素短語： i 、E+F （1 分 ） 句柄： i （1 分 ）13、給出下面語言的相應(yīng)文法： L 1=a 2n+1 bn+1 | n1G1：SaaSb|ab10）（2008）L2=a nbm+nam | n1，m0G1：SABA aAb | ab B bBa | 14、設(shè)有文法

14、GA ：（ 2008） A BCc | gDB BbCDE | C DaB | ca DdD |EgAf | c（1） 計算該文法的每一個非終結(jié)符的 FIRST 集和 FOLLOW 集；（2） 試判斷該文法是否為 LL （ 1）文法。（ 10）FIRSTFOLLOWAa,b,c,d,gfBb，a,c,d ， f ，gCa,c,dc,d,gDd，a,b,c,f,gEc,ga,c,d,f,g是 LL（ 1 ）文法。15、對表達(dá)式文法 G：（ 2008） E E+T | T T T*F | F F （E） | I（ 1）造各非終結(jié)符的 FIRSTVT 和 LASTVT 集合； （ 2）構(gòu)造文法的算符

15、優(yōu)先關(guān)系表。 （ 15）FIRSTVTLASTVTE*，+，（，i*，+，），iT*，（，i*，），iF（，i），i算符優(yōu)先關(guān)系表+I（）#+I （ ）#>>><><<>><><<<<<<<<<>>>>>>>>16、對下述文法： （10） （ 2008）Sa | （T）T T ， S | S 構(gòu)造一個翻譯模式，統(tǒng)計輸出配對的括號個數(shù)。引入 S、T的綜合屬性 h 來統(tǒng)計配對的括號個數(shù)，得到翻譯模式如下： S' S prin

16、t（S.h）S a S.h=0 S（ T） S.h= T.h+1T T 1， S T.h= T 1.h +S.h T S T.h= S.h 17、有文法如下： (共 15 分)S aBB aDd | dD Ab | A aD | e(1) 計算文法的每個非終結(jié)符的 FIRST 集合和 FOLLOW集合；(2) 計算文法的每個候選產(chǎn)生式的 SELECT集合；(3) 說明文法是 LL( 1)文法的理由，并給出其預(yù)測分析表；(4) 給出符號串 aaebd 的預(yù)測分析過程(即最左推導(dǎo)過程)(1) . (4 分) FIRST(S)= a FOLLOW(S)= # FIRST(B)= a,d FOLLOW

17、(B)= # FIRST(D)= a,e, FOLLOW(D)= b,d FIRST(A)= a,e FOLLOW(A)= b d)= d )= b,d e)= e (2) . (4分) SELECT(S aB)= a SELECT(B aDd)= a SELECT(B SELECT(D Ab)= a,e SELECT(D SELECT(A aD)= a SELECT(A(3) . (4 分)如上所求結(jié)果，定義非終結(jié)符 B( 或 D或 A)的兩個規(guī)則的 SELECT集合 無交集，所以文法是 LL(1) 文法，其預(yù)測分析表如下：(3). (3分) 符號串 aaebd 的預(yù)測分析過程：分析棧輸入串

18、所用規(guī)則#Saaebd#Baaaebd#SaB#Baebd#dDaaebd#BaDd#dDebd#dbAebd#DAb#dbeebd#Ae#dbbd#dd#結(jié)束符號串 aaebd 的最 左推導(dǎo)過程： S aB aaDd a aAbd aaebdabde#SS aBBB aDdB dDD AbDDDAbAA aDA e18、有文法如下： (共 10 分)(2013)S aABB a | dA bB | eA |(1) 計算文法的每個候選產(chǎn)生式的 SELECT集合； (5 分)(2) 說明文法是 LL(1)文法的理由，并給出其預(yù)測分析表。 (5 分)(1)SELECT(S aAB)=a SELEC

19、T(B a )= a SELECT(B d )=dSELECT(A bB )= b SELECT(A eA )= e SELECT(A )=a，d(2) 文法不含左遞歸， 定義 B的兩條產(chǎn)生式的 SELECT集沒有交集， 定義 A的三條產(chǎn)生式 的 SELECT集兩兩不相交，所以文法是 LL( 1)文法，預(yù)測分析表如下：abde#SS aABBB aB dAA A bBA AeA19、有文法如下： (共 15 分)(2011)S T LT int | floatL id RR ,id R | (1) 計算文法的每個候選產(chǎn)生式的 SELECT集合； (5 分)(2) 說明文法是 LL(1)文法的理

20、由，并給出其預(yù)測分析表； (6 分)(3) 給出符號串 int id,id 的預(yù)測分析過程(包括分析棧、輸入串、所用規(guī)則) 。(4 分) (1) SELECT(S T L )=int ， floatSELECT(T int )=int SELECT(T float )=floatSELECT(L id R )=id SELECT(R ,id R )= ，SELECT(R )=$(2) 文法不含左遞歸，并且 SELECT(T int ) SELECT(T float )= SELECT(R ,id R )SELECT(R )= 所以文法是 LL(1)文法，預(yù)測分析表如下：intfloatid$S

21、S T LS T LTTintT floatLL id RRR ,id RR (3) 符號串 int id,id 的預(yù)測分析過程：分析棧輸入串所用規(guī)則$Sint id,id$S TL$LTint id,id$Tint$Lintint id,id$int 與 int 匹配$Lid,id$L id R$Ridid,id$id 與 id 匹配$R,id$R ,id R標(biāo)準(zhǔn)文案$Rid, $ Rid $R$,id$id$，與，匹配id 與 id 匹配R 分析結(jié)束標(biāo)準(zhǔn)得分20、有定義二進(jìn)制串的文法如下： (共 15 分)S L L 0L1L 01 (1) 構(gòu)造文法的識別規(guī)范句型活前綴的 DFA； (2)

22、 分別寫出上一步 DFA各狀態(tài)所識別的活前綴；(3) 說明該文法是 SLR(1)文法的理由，并給出 SLR(1)分析表；(4) 給出符號串 0011的 LR移進(jìn)-歸約過程(包括狀態(tài)棧、符號棧、輸入串、 分析動作)。(2). 上一步 DFA各狀態(tài)所識別的活前綴( 3 分)分別是：I0:； I1:L； I2:00*； I 3:0*0L ； I4:0*01； I5: 0*0L1 ；(3) . (4 分)因為上面 DFA各狀態(tài)都不含沖突，所以文法是 LR(0)文法，也是 SLR(1)文法。 FOLLOW(L)=1,#，SLR(1)分析表如下：(4) 符號串 a00a1e1e的LR分析過程( 43分)：

23、符號棧狀態(tài)棧輸入串動作#00011#S2#002011#S2#0002211#S4#00102241#r2#0L0231#S5#0L10235#r1文案#L01#acc21、有定義二進(jìn)制串的文法如下： (共 20 分)(2011)L LB | BB 0 | 1 (1) 構(gòu)造文法的識別規(guī)范句型活前綴的 DFA； (2) 分別寫出上一步 DFA各狀態(tài)所識別的活前綴；(3) 說明該文法是 SLR(1)文法的理由，并給出 SLR( 1)分析表；(4) 給出符號串 10的 LR移進(jìn)-歸約過程(包括狀態(tài)棧、符號棧、輸入串、 分析動作)。對文法進(jìn)行拓廣并為產(chǎn)生式編號：(0) S' L (1)L LB

24、 (2)L B (3)B 0 (4)B 1 (1)(6 分) 構(gòu)造文法的識別活前綴的 DFA如圖：(2) (4 分 )DFA 各狀態(tài)所識別的活前綴：I0: I1: L I2: BI3: 0 | L0I4: 1 | L1 I5: LB(3) (6 分) I 1中含移進(jìn) -歸約沖突 , 但 FOLLOW('S ) =$, 與待移進(jìn)的符號集合 0，1沒 有交集，所以是 SLR(1) 文法。 FOLLOW(L)=FOLLOW(B) =0,1,$, SLR(1) 分析表如下：狀態(tài)ACTIONGOTO01$LB0S3S4121S3S4acc52r2r2r23r3r3r34r4r4r45r1r1r1

25、(4) (4 分)符號串 10的 LR分析過程 :狀態(tài)棧符號棧輸入串分析動作0$10$S404$10$r402$B0$r201$L0$S3013$L0$r3文案標(biāo)準(zhǔn)文案01501$LB$r1$L$acc標(biāo)準(zhǔn)文案六、證明題(本題共 2 小題，每小題 5分，共 10分)1、證明正規(guī)式 b(ab)* 與 (ba)*b 是等價的。 (5 分)證明：因為兩個正規(guī)式描述的正規(guī)集都是 b， bab ， babab ， bababab ， babababab ， , 所以等價。(用文字描述正規(guī)集也可以。 ) 或用等價的最小 DFA 一樣來證明也可以，都是：2、有文法如： GS: S (AS) | (b) A (SaA) | (