本文格式為Word版，下載可任意編輯——杭電編譯原理試卷三及答案試卷（三）：一、選擇

1.下面說法正確的是：A

A一個正規文法也一定是二型文法

B一個二型文法也一定能有一個等價的正規文法

2.文法G[A]：A→bA→ABB→AbB→a是(A)：A二型文法B正規文法

3.下面說法正確的是(B)：Alex是一個詞法分析器

Byacc是一個語法分析器的生成器

4.一個LR（1）文法合并同心集后,假使不是LALR(1)文法必定存在(B)：A移進--歸約沖突B歸約--歸約沖突

5PL/0語言編譯程序使用遞歸子程序法進行語法分析，他的文法必需滿足(A)：ALL（1）文法BSLR(1)文法

二、問答題問答第1題

（6分）試對repeatx:=buntilb>aor(bagoto()()真出口鏈()(3)goto()()(4)ifbagoto(8)(6)真出口鏈(6,2)(3)goto(4)(1)(4)ifb問答第2題

(10分)某語言的拓廣文法G′為：(0)S′→S(1)S→Db|B(2)D→d|ε(3)B→Ba|ε

證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。解：

拓廣文法G'，增加產生式S'→S在項目集I0中：有移進項目D→·d歸約項目D→·和B→·

存在移進-歸約和歸約-歸約沖突，所以G不是LR(0)文法。若產生式排序為：(0)S'→S(1)S→Db(2)S→B(3)D→d(4)D→ε(5)B→Ba(6)B→ε

G′的LR(0)項目集族及識別活前綴的DFA如下圖：識別G′活前綴的DFA

由產生式知：Follow(S)={#}Follow(D)={b}Follow(B)={a,#}在I0中:

Follow(D)∩bunwpu6={b}∩umift4m=Follow(B)∩1v14gqm={a,#}∩gnrfgdn=

Follow(D)∩Follow(B)={b}∩{a,#}=在I3中:

Follow(S)∩{a}={#}∩{a}=

所以在I0，I3中的移進-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法,構造的SLR(1)分析表如下表。SLR(1)分析表

問答第3題

(5分)給出文法G[S]的LR(1)項目集規范族中I0項目集的全體項目。G[S]為：S→S;V|VV→VaA|AA→b(S)|εI0:

解：I0:

問答第4題

(5分)文法G[M]及其LR分析表如下，請給出對串dada#的分析過程。G[M]:1)S→VdB2)V→e3)V→ε4)B→a5)B→Bda6)B→ε

解：對串dada#的分析過程如下表對輸入串dada#的分析過程

狀態文法符剩余輸入步驟

棧號棧符號10#dada#202#Vdada#3024#Vdada#40245#Vdada#50246#VdBda#602467#VdBda#

動作用V→ε歸約

移進移進用B→a歸約

移進移進

702467#VdBda88#VdB90246#S01

###用B→Bda歸約用S→VdB歸約

接受

問答第5題

(7分)(1)給出以下PL/0示意程序中當程序執行到D過程調用A過程后（即執行A過程體時）的棧式存儲分派布局和用Display顯示表時A過程最新活動記錄的內容。(2)說明Display表和全局Display的作用。PL/0示意程序為：varx;procedureA;vard;

begin(*A*)write(x);end(*A*);procedureB;constn=7;vare,g;

procedureD;varj,k;

begin(*D*)read(j,k);x:=x+j*n;callA;end;(*D*)begin(*B*)callD;end;(*B*)begin(*main*)read(x);callB;

end.(*main*)解：（1）PL