華南農(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 一 aD文法所對應(yīng)的正規(guī)式為:a(b|aa)*bD 一 bD | aA | b A - aD2、給出下面語言集合的上下文無關(guān)文法。(2010 2014)Li= anbm | n m 1 文法： S - aS | D D - aDb|ab2、為正規(guī)集L2=anbm ck | nn 1, mn 1,k n 1構(gòu)造一右線性正規(guī)文法 (2010)S 一 aS | aA A 一 bA

2、| bB B 一 cB | c3、按照編譯過程的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)代碼生成，把中間代碼變換成特定機器上的

3、低級語言指令形式。5、”含有優(yōu)化部分的編譯程序的執(zhí)行效率更高?！边@句話對嗎？為什么？ 這句話是錯的。優(yōu)化不是編譯程序必須的一個部分，含有優(yōu)化的編譯程序 功能更強、算法更復(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é)符之

4、間的優(yōu)先關(guān)系，然后借助這種優(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ī)式來描述它所識別的語言文案是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文案 T4=R-r(5) T5=T2叮4(6) S=T5+T3(2011)13、試求表達(dá)式A+B*(-

7、C)+B/(-C)對應(yīng)的后綴式和三地址代碼后綴式：ABC-*+BC-/+三地址代碼：T1=-CT2=B*T1T3=A+T2T4=-CT5=B/T4T6=T3+T514、考慮如下的三地址語句序列：(2011)L1: read C;A=0;B=1;B1L2: A=A+B;if BC goto L3;B2B=B+1;goto L2;B3.多余的語句，刪去goto L1;L3: write A; halt;B4(1).將該代碼序列劃分成基本塊，并給每個基本塊一個序號(2) .畫出該代碼序列的流圖，每個基本塊用(1)的序號表(3) .若有循環(huán)，列出構(gòu)成循環(huán)的節(jié)點(基本塊)。(10分)(1) .如圖分成四

8、個基本塊 B1、B2、B& B4(2) .流圖：(3) .構(gòu)成循環(huán)的基本塊是B2, B3(4) 有翻譯模式如下：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 標(biāo)準(zhǔn)采用移進(jìn)歸約的分析方法，當(dāng)分析器的輸入為（a,（a） 時，畫出其語法樹（可 以帶注釋、也可以不帶注釋），并求輸出的結(jié)果。（2011）文案語法樹:Sa輸出結(jié)果是：2得分、構(gòu)造識別下列語言的最小 DFA （共20分）:1、正規(guī)式 1 (0|1 )*0 | 0 ; (7 分)求出NFA得4分，確定化了得6分，最小DFA的 狀

9、態(tài)錯漏一個扣1分，弧錯漏一條扣0.5分。2、以101結(jié)尾的二進(jìn)制用；（8分）求出NFA得4分，確定化了得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分）3、1 (0 | 1) *1(8)2構(gòu)造下列正規(guī)式相應(yīng)的DFA （用狀態(tài)轉(zhuǎn)換圖表示）（15 ） （2008 ）(8)(9)得分7、將下圖NFA確定化。（10分）（2013）

10、8、將下圖DFA化簡。（5分）（2013）首先將DFA勺狀態(tài)集劃分成終態(tài)集和非終態(tài)集E、A,B,C,D；由于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 I b I (T) T - TeS | S請給出（Sebe（a）的語法樹、短語、STeI吾法樹:（5分）T )直接短語、素短語、句柄。（10分）（2 分）短語：（Sebe（a）、Sebe（a）、SeB （a）、S b、a（1分）直接短語：S、b、a（

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

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

13、 F | PP - （E） I i構(gòu)造句型P i*（E+F-T）的語法樹；并指出該句型所有的短語、直接短語、素短語以及句柄。（10分）語法樹：（5分）短語：（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)文法:L1=a2n+1 bn+1 | n1(10) (2008) L2=anbm+nam| n1, m0G1 :Sf aaSb|abG1 :S-ABA -aAb | abB -bBa | 14、設(shè)有文法 GA : (2008) A fBCc | gDBB

14、fbCDE | CfDaB | ca D-dD | EfgAf | c(1)計算該文法的每一個非終結(jié)符的FIRST集和FOLLOW 集;(2)試判斷該文法是否為LL (1)文法。(10)FIRSTFOLLOWAa,b,c,d,gfBb, ea,c,d , f , gCa,c,dc,d,gDd, ea,b,c,f,gEc,ga,c,d,f,g是LL (1)文法。15、對表達(dá)式文法 G: (2008)E E+T | TT 一 T*F | FF -(E) I I(1)造各非終結(jié)符的 FIRSTVT和LASTVT集合;(2)構(gòu)造文法的算符優(yōu)先關(guān)系表。(15)FIRSTVTLASTVTE*, +, (,

15、 i*, +,), iT*, (, i*,), iF(,i),i算符優(yōu)先關(guān)系表+*I()#+*I(#=16、對下述文法：(10)(2008)S - a I(T)T 一 T , S | S構(gòu)造一個翻譯模式，統(tǒng)計輸出配對的括號個數(shù)。引入S、T的綜合屬性h來統(tǒng)計配對的括號個數(shù)，得到翻譯模式如下:S 一 S print(S.h)Sf a S.h=0 Sf (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集合

16、和FOLLOW1合;(2)計算文法的每個候選產(chǎn)生式的 SELECT1合；(3)說明文法是LL (1)文法的理由，并給出其預(yù)測分析表； 給出符號用aaebd的預(yù)測分析過程(即最左推導(dǎo)過程)(1) . (4 分)FIRST(S)= a FOLLOW(S)= # FIRST(B)= a,d FOLLOW(B)= # FIRST(D)= a,e, FOLLOW(D)= b,d FIRST(A)= a,e FOLLOW(A)= b (2) .(4 分) SELECT(S- aB)= a SELECT(B aDd)= a SELECT(B-d)= d SELECT。- Ab)= a,e SELECT(D-

17、& )= b,d SELECT(A - aD)= a SELECT(A-e)= e (3) .(4分)如上所求結(jié)果，定義非終結(jié)符 B(或D或A)的兩個規(guī)則的SELECT1合無交集，所以文法是LL(1)文法，其預(yù)測分析表如下：(3).(3分)符號用aaebd的預(yù)測分析過程:分析棧輸入用所用規(guī)則#Saaebd#Baaaebd# S一 aB#Baebd#dDaaebd# B一 aDd#dDebd#dbAebd# D一 Ab#dbeebd# A-e#dbbd#dd#結(jié)束符號用aaebd的最 左推導(dǎo)過程：S aB aaDd aaAbd aaebdabde#SS 一 aBBB faDdB 一 dDD -

18、AbD CH* A AbAA - aDAf e18、有文法如下： (共10分)(2013)S 一 aABB 一 a | dA 一 bB | eA |(1)計算文法的每個候選產(chǎn)生式的SELECT1合；(5分)(2)說明文法是LL (1)文法的理由，并給出其預(yù)測分析表。(5分)(1)SELECT(S - aAB尸a SELECT(B - a )= a SELECT(B - d )=dSELECTA - bB)=b SELECT(A - eA)=e SELECT(A 一 8 )=a , d(2)文法不含左遞歸，定義B的兩條產(chǎn)生式的SELECT!沒有交集，定義A的三條產(chǎn)生式的SELECTS兩兩不相交，

19、所以文法是LL (1)文法，預(yù)測分析表如下：abde#SS 一 aABBB 一 aB 一 dAA 一 eA - bBA 一 eA- eA19、有文法如下：(共15分)(2011)S 一 T LT - int | float L - id R R 一 ,id R |(1)計算文法的每個候選產(chǎn)生式的SELECTS合；(5分)(2)說明文法是LL (1)文法的理由，并給出其預(yù)測分析表；(6分)給出符號用int id,id的預(yù)測分析過程(包括分析棧、輸入用、所用規(guī)則)。(4分) SELECT(S 一 T L 尸int , floatSELECT(T - int )=int SELECT(T - flo

20、at 尸floatSELECT(L - id R )=id SELECT(R - ,id R )= , SELECT(R f & )=$(2)文法不含左遞歸，并且 SELECT(T 一 int )ASELECT(T - float 尸 SELECT(R - ,id R ) n SELECT(R - e )=所以文法是LL (1)文法，預(yù)測分析表如下:intfloatid$SS 一 T LS 一 T LTT-intT 一 floatLL 一 id RRR 一 ,id RR 一 e(3)符號用 int id,id的預(yù)測分析過程：分析棧輸入用所用規(guī)則$Sint id,id$S 一 TL$LTint

21、id,id$T - int$Lintint id,id$int與int匹配$Lid,id$L 一 id R$Ridid,id$id與id匹配$R,id$R 一 ,id R標(biāo)準(zhǔn)$Rid,id$,與，匹配$ Ridid$id與id匹配$R$R 一$分析結(jié)束文案標(biāo)準(zhǔn)得分20、有定義二進(jìn)制用的文法如下：(共15分)S LL 0L1L 01(1)構(gòu)造文法的識別規(guī)范句型活前綴的 DFA(2)分別寫出上一步DFA各狀態(tài)所識別的活前綴；(3)說明該文法是SLR (1)文法的理由，并給出SLR (1)分析表；(4)給出符號用0011的LR移進(jìn)-歸約過程(包括狀態(tài)棧、符號棧、輸入申、 分析動作)。(2).上一步D

22、F-狀態(tài)所識別的活前綴(3分)分別是：10： ；I1：L； I2：00*; I 3：0*0L ；I4：0*01 ;I5： 0*0L1 ；(3).(4分)因為上面DFA各狀態(tài)都不含沖突,所以文法是 LR(0)文法，也是 符號用aa1e的lr分析過程(4分):符號棧狀態(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)所識別

23、的活前綴；(3)說明該文法是SLR (1)文法的理由，并給出SLR (1)分析表；(4)給出符號用10的LR移進(jìn)-歸約過程(包括狀態(tài)棧、符號棧、輸入申、 分析動作)。對文法進(jìn)行拓廣并為產(chǎn)生式編號:LB (2)L(1)(6分)構(gòu)造文法的識別活前綴的一 B (3)BDFA如圖：0 (4)B 1(0) S 一 L (1)L(4分)DFA各狀態(tài)所識別的活前綴：I0：I1: L I2: B I3: 0 | L0 I4:1 | L1 LB(6分)I1中含移進(jìn)-歸約沖突，但FOLLOW(S )=$,與待移進(jìn)的符號集合0, 1沒有交集,所以是 SLR(1)文法。FOLLOW(L尸F(xiàn)OLLOW(B) =0,1,

24、$, SLR(1) 分析表如下：狀態(tài)ACTIONGOTO01$LB0S3S4121S3S4acc52r2r2r23r3r3r34r4r4r45r1r1r1(4分)符號用10的LR分析過程：狀態(tài)棧符號棧輸入用分析動作0$10$S404$10$r402$B0$r201$L0$S3013$L0$r3文案標(biāo)準(zhǔn)文案015$LB$01$L$riacc標(biāo)準(zhǔn)文案(2013) (5 分)/ /S ASS(2013)(5 分)GS: S 一 D0 | 0D 一 S1六、證明題(本題共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)