完整2014上學(xué)期編譯原理試題及答案中南大學(xué),推薦文檔

1、中南大學(xué)測(cè)試試卷2021-2021 學(xué)年 二 學(xué)期時(shí)間100分鐘編譯原理課程64學(xué)時(shí)4學(xué)分測(cè)試形式：開卷專業(yè)年級(jí)：計(jì)算機(jī),信安,物聯(lián)網(wǎng)11 總分100分,占總評(píng)成績70%注：此頁不作做題紙,請(qǐng)將答案寫在做題紙上1 .文法GS5- (L)| aL-L,S| S給出句子(a,a),a)的最右寸t導(dǎo)；(此題共10分)2 .證實(shí)文法GSS-aS |aSbS | £是二義性的.(此題共10分)3 .寫出正規(guī)表達(dá)式b(ab)*等價(jià)的文法.(此題共10分)4 .寫一個(gè)文法使其語言為L=a2m-1, ba2n| m, nN1 題共10分)5 .以下兩題目任選擇一題目,如果兩題都做以第一題計(jì)分.(此題

2、共10分)(1)將正規(guī)表達(dá)式1(0|1)*101轉(zhuǎn)化為NFA, DFA并最小化.(2)設(shè)有根本塊：T1=3T2=D+ET3=G - BT4=T1 / 2X=T294Y=XT5=D + ET6=T3 / T5Y=T6畫出該根本塊的DAG圖,根據(jù)DAG圖寫出其等價(jià)的根本塊.6 .文法GS:5- (L)| aL-L,S| S試為每個(gè)產(chǎn)生式配語義動(dòng)作,輸出配對(duì)括號(hào)個(gè)數(shù).例如對(duì)于句子(a,(a,a),輸出2 (此題共10分)7 .文法GSSfSaASfbBAfaBAfcBfBbB-d(1)消除左遞歸；(5分)(2)構(gòu)造相應(yīng)的FIRST和FOLLOW 集合；(5分)(3)構(gòu)造LL(1)分析表.(5分)(此

3、題共15分)8 .把語句while a<b and c>d doif x>y then z:=z+1else z:=z*x;譯成三地址代碼,假設(shè)三地址代碼語句標(biāo)號(hào)從100開始.(此題共10分)9 .以下兩題目任選擇一題目,如果兩題都做以第一題計(jì)分.(此題共15分)(1)文法GS(0)S ' f(1)S -V=E(2)S - E(3) E -V(4)V f(5)V - *E構(gòu)造LR(1)分析表.(2)令文法GS為：S-S ; B| BB-B * T | TT-a|(S)(a)請(qǐng)寫出文法GS的FIRSTVT 集和LASTVT集.(b)構(gòu)造優(yōu)先關(guān)系表(c)分析符號(hào)用a;a*

4、a是否為文法的句子?編譯原理?試卷參考答案1 .文法GS5- (L)| aL-L,S| S給出句子(a,a),a)的最右才t導(dǎo).(此題共10分)S=>(L)=(L,S)=>(L,a)=>(S,a)=>(L),a)=>(L,S),a)=>(L,a),a)=>(a,a),a)2 .證實(shí)文法GS5- aS | aSbS |£是二義性的.(此題共5分)由于對(duì)于句子aab有兩個(gè)不同的最左推導(dǎo)S=>aS=>aaSbS=>aabS=>aabS=aSbS=>aaSbS=>aabS=>aab因此,文法是二義性的.3 .

5、寫出與正規(guī)表達(dá)式b(ab)*等價(jià)的文法.(此題共10分)GSS一 bAAf abAA- £4 .寫一個(gè)文法使其語言為L=a2m-1, ba2n| m, nN1 題共10分)GSSfASf bBAf aaAAfaBf aaBBf aa5 .(1)將正規(guī)表達(dá)式1(0|1)101轉(zhuǎn)化為NFA, DFA并最小化.(此題共10分)狀態(tài)輸入01XAAABBCBCADDCBX:初態(tài)D :終態(tài)(1)文法GS:(2)設(shè)有根本塊：T1=3T2=D+ET3=G - BT4=T1 / 2X=T2*T4Y=XT5=D + ET6=T3 / T5Y=T6畫出該根本塊的DAG圖根據(jù)DAG圖寫出其等價(jià)的根本塊.等價(jià)

6、的根本塊T1=3T2=D+ET3=G - BT4=1.5X=T2*T4T6=T3 / T2Y=T66 .文法GS:S' 一 S5- (L)| aL-L,S| S試為每個(gè)產(chǎn)生式配語義動(dòng)作,輸出配對(duì)括號(hào)個(gè)數(shù).例如對(duì)于句子(a,(a,a),輸出2(此題共10分)S' fS- (L)SfaL-L1,SLfprint(S.num)S.num:=L.num+1S.num:=0L.num:=L1.num+S.numL.num:=S.num7 .文法GSSf SaASf bBAf aBAtcBf BbBfd(1)消除左遞歸；(5分)(2)構(gòu)造相應(yīng)的FIRST和FOLLOW 集合；(5分)(3)

7、構(gòu)造LL(1)分析表.(5分)(此題共15分)(1)消除左遞歸(5分)Sf bBS'S' - aASS' f eAf aBAfc8- dB'B' fB'B' f e(2)構(gòu)造相應(yīng)的FIRST和FOLLOW集合；(5分) FIRST(S)=bFIRST(S'尸a, eFIRST(A)=a, cFIRST(B)=dFIRST(B'尸b, £ FOLLOW(S)=#FOLLOW( S')=#FOLLOW(A)=a. #FOLLOW(B)=a, #FOLLOWB '厘 # 3構(gòu)造預(yù)測(cè)分析表5分abcd#S

8、S- bBS'S,S' - aAS'S' 一 £AA- aBA 一 cBF-aF'B- dB'B,B' - eB' - bB'B' - e8 .把語句while a<b or c>d doif x>y then z:=z+1else z:=z*x;譯成三地址代碼,假設(shè)三地址代碼語句標(biāo)號(hào)從100開始.(此題共15分)100 if a<b goto 104101 goto 102102 if c>d goto 104103 goto 111104 if x>y goto 1

9、06105 goto108105 t1:=z+1106 z:=t1107 goto 100108 t2:=z*x109 z:=t2110 goto 1001119 . (1)文法GS(0)S ' - S(1)S -V=E(2)S - E(3) E -V(4)V -x(5)V 一*E構(gòu)造LR(1)分析表.(此題共15分)狀態(tài)ActionGotox*=$SEV1s8s62532acc3s4r34s11s13975r26s8s610127r38r4r49r110r5r511r412r3r313s11s1214714r5LR(1)分析表(2)令文法GS為：S-S ; B| BBB * T | TT-a|(S)(a)請(qǐng)寫出文法GS的FIRSTVT集和LASTVT集(b)構(gòu)造優(yōu)先關(guān)系表(c)分析符號(hào)用a;a*a是否為文法的句子(a)文法 G(S)的 FIRSTVT 集和 LASTVT 集. FIRSTVT(S)=;,*,a,( LASTVT(S)= ;,*,a,) FIRSTVT(B尸*,a,(,LASTVT(B)= *,a,)FIRSTVT(T)=a, (LASTVT(T)= a,)(b)優(yōu)先關(guān)系表a;*()a>><><><<>*<&g