編譯原理試題及答案二市公開課一等獎省賽課微課金獎課件

編譯原理參考答案程序設計語言

Chapter4.自上而下語法分析2024/5/7第1頁CH.4.練習題1(P81.)1.考慮下面文法G1:

S→a|^|(T)T→T，S|S(1)消去G1左遞歸。然后對每個非終止符,寫出不帶回溯遞歸子程序。解(1)消左后文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε2024/5/7第2頁CH.4.練習題1(P81.)解(1)不帶回溯遞歸子程序:S→a|^|(T)ProcedureS;Beginifsym=‘a’orsym=‘^’thenadvanceelseifsym=‘(‘thenbeginadvance;T;ifsym=‘)’thenadvance

elseerrorendelseerrorEnd;第3頁CH.4.練習題1(P81.)解(1)不帶回溯遞歸子程序:T→ST’ProcedureT;BeginS;T’end;

解(1)不帶回溯遞歸子程序:T’→,ST’|εprocedureT’;beginifsym=‘,’thenbeginadvance;

S;T’endEnd;第4頁CH.4.練習題1(P81.)(2)經改寫后文法是否是LL(1)?給出它預測分析表。消左后文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε(2)因為G1’:①文法不含左遞歸;②對S→a|^|(T)FIRST(a)={a},FIRST(^)={^},FIRST((T))={(},集合互不相交且不含ε;③對T’→,ST’|εFIRST(,ST’)={,},FIRST(ε)={ε},其交集為空。

但ε∈FIRST(T’)=FIRST(,ST’)∩FIRST(ε)={，,ε},

然而，F(xiàn)OLLOW(T’)={)}FIRST(T’)={，,ε}，二者不相交。所以，G1’是LL(1)文法。第5頁CH.4.練習題1(P81.)(2)結構G1’預測分析表:①對S→a|^|(T)②對T→ST’

FIRST(a)={a}FIRST(ST’)={a,^,(}FIRST(^)={^}③對T’→,ST’|εFIRST((T))={(}FIRST(,ST’)={,}預測分析表:

FOLLOW(T’)={)}

a^(),#

SS→aS→^S→(T)

TT→ST’T→ST’T→ST’

T’T’→εT’→,ST’2024/5/7第6頁CH4.1.(3)給出對符號串(a，^)分析過程步驟符號棧輸入串動作,所用產生式.0#S(a,^)#初始；用S,(查表1#)T((a,^)#S→(T),展開S2#)Ta,^)#匹配(；用T,a查表3#)T’Sa,^)#T→ST’,展開T;用S,a查表4#)T’aa,^)#S→a,展開S5#)T’,^)#匹配a;用T’,,查表6#)T’S,,^)#T’→,ST’,展開T’7#)T’S^)#匹配,；用S,^查表8#)T’^^)#S→^,展開S9#)T’)#匹配^；用T’,)查表10#))#T’→ε,展開T’11##匹配)12##分析成功,結束分析第7頁CH.4.練習題3(P82.)3.下面文法中,哪些是LL(1),說明理由。(1)

S→ABcA→a|εB→b|ε。解，因為FOLLOW(S)={#}

①文法不含左遞歸;FIRST(S)={a,b,c}

②對A→a|ε

候選式FIRST集合互不相交;ε∈

FIRST(A)

但,FOLLOW(A)={b,c}FIRST(A)={a,ε}二者不相交。③B→b|ε其候選式FIRST集合互不相交;ε∈

FIRST(B)

但，F(xiàn)OLLOW(B)={c}FIRST(B)={b,ε}二者也不相交。

所以，文法是LL(1)文法。第8頁CH.4.練習題3(P82.)3.下面文法中,哪些是LL(1),說明理由。(2)

S→AbA→a|B|εB→b|ε。解(1)

因為FOLLOW(S)={#}

對A→a|B|ε;FIRST(S)={a,b}

FIRST(B)={b,ε}與FIRST(ε)={ε}相交;所以文法不是LL(1)文法。解(2)對A→a|ε因為ε∈FIRST(A)={a,b,ε}，F(xiàn)OLLOW(A)=,FOLLOW和FIRST二者相交。所以文法不是LL(1)文法。第9頁CH.4.練習題3(P82.)3.下面文法中,哪些是LL(1),說明理由。(3)

S→ABBAA→a|εB→b|ε。解，即使FOLLOW(S)={#}

①文法不含左遞歸;FIRST(S)={a,b,ε}

②對A→a|ε，其候選式FIRST集合不相交;對B→b|ε，其候選式FIRST集合也不相交;但對A→a|ε（由B→b|ε出發(fā)證實也可）FOLLOW(A)={a,b,#},FIRST(A)={a,ε}

二者相交。所以，文法不是LL(1)文法。第10頁CH.4.練習題3(P82.)3.下面文法中,哪些是LL(1),說明理由。(4)

S→aSe|BB→bBe|CC→cCe|d。解，

因為

①文法不含左遞歸;②對S→aSe|B、B→bBe|C和C→cCe|d

各產生式候選式FIRST集合均不相交;即FIRST(aSe)∩FIRST(B)=

；FIRST(bBe)∩FIRST(C)=

；FIRST(cCe)∩FIRST(d)=

；

③FIRST(S)={a,b,c,d}，F(xiàn)IRST(B)={b,c,d}FIRST(C)={c,d}均不含ε。所以，文法是LL(1)文法。第11頁編譯原理參考答案程序設計語言

Chapter7.語義分析和中間代碼產生2024/5/7第12頁P217-1a*（-b+c）后綴式：ab-c+*a+b*（c+d/e）后綴式：abcde/+*+-a+b*（-c+d）后綴式：a-bc-d+*+notAornot（CornotD）后綴式：AnotCDnotornotor（AandB）or（notCorD）后綴式：ABandCnotDoror2024/5/7第13頁P217-3-（a+b）*（c+d）-（a+b+c）

四元式序列：（1）(+，a，b，T1)（2）(-，T1，-，T2)（3）(+，c，d，T3)（4）(*，T2，T3，T4)（5）(+，a，b，T5)（6）(+，T5，c，T6)（7）(-，T4，T6，T7)2024/5/7第14頁P218-4自下而上分析過程中把賦值語句A:=B*（-C+D）翻譯成三地址碼步驟：

（參看p179語義子程序）2024/5/7第15頁語法分析 翻譯過程：A:=B*(-C+D)A:=E1*(-C+D) E1.place=k2A:=E1*(-E2+D) E2.place=k3A:=E1*(E3+D)A:=E1*(E3+E4)A:=E1*(E5)A:=E1*E6A:=E7

S

.

.

.

.

.

.

.

.產生一個新中間變量T1E3.place=k5產生代碼

k5:=uminusk3……名字屬性地址ABCDT1T2T3……k1K2k3k4k5k6k7符號表2024/5/7第16頁A:=B*(-C+D)三地址碼k5:=uminusk3k6:=k5+k4k7:=k2*k6k1:=k7名字屬性地址ABCDT1T2T3……k1K2k3k4k5k6k7符號表（參看p179語義子程序）2024/5/7第17頁P218-6：用7.4.2節(jié)方法，把Aor（Bandnot（CorD））翻譯成四元式序列100：（jnz，A，-，0）101：（j，-，-，102）102：（jnz，B，-，104）103：（j，-，-，0）104：（jnz，C，-，.）105：（j，-，-，106）106：（jnz，D，-，.）107：（j，-，-，.）TCFC2024/5/7第18頁P218-7100：（j<，A，C，102）101：（j，-，-，115）102：（j<，B，D，104）103：（j，-，-，115）104：（j=，A，‘1’，106）105：（j，-，-，109）106：（+，C，‘1’，T1）107：（:=，T1，-，C）108：（j，-，-，100）109：（j≤，A，D，111）110：（j，-，-，100）111：（+，A，‘2’，T2）112：（:=，T2，-，A）113：（j，-，-，109）114：（j，-，-，100）115：用7.5.1節(jié)方法，把下面語句翻譯成四元式序列：whileA<CandB<DdoifA=1thenC:=C+1elsewhileA≤DdoA:=A+2;2024/5/7第19頁編譯原理參考答案程序設計語言

Chapter8.–Chapter11.2024/5/7第20頁CH8.–CH11.1.什么是符號表？符號表有哪些主要作用？2.符號表表項常包含哪些部分？各描述什么？3.有哪些存放分配策略？并敘述何時用何種存放分配策略？4.代碼優(yōu)化慣用辦法和優(yōu)化三個層次。2024/5/7第21頁編譯原理參考答案程序設計語言

補充題2024/5/7第22頁補充題1.畫出編譯程序總體邏輯結構圖，簡述各部分主要功效。2024/5/7第23頁補充題2.已知文法G[Z]:Z→0U|1VU→1Z|1V→0Z|0請寫出此文法描述只含有４個符號全部句子。G[Z]產生語言是什么？該文法在Chomsky文法分類中屬于幾型文法？2024/5/7第24頁【解】（1）0101，0110，1010，1001（2）分析G[Z]所推導出句子特點：由Z開始推導不外乎圖1所表示四種情形。由Z推導出10或01后就終止或進入遞歸，而Z每次遞歸將推導出相同符號串：10或01。所以G[Z]產生語言L(G[Z])={x|x∈(10|01)+}(3)該文法屬于3型文法。Z→0U|1VU→1Z|1V→0Z|02024/5/7第25頁補充題3.已知文法和它LR分析表以下，給出串dbdb#LR分析過程。

G[S]：(1)S→AdB(2)A→a(3)A→ε(4)B→b(5)B→Bdb(6)B→εACTIONGOTOadb#SAB0s3r3121acc2s43r24r6s5r665r4r46s7r17s88r5r5LR分析表2024/5/7第26頁【解】串dbdb#LR分析過程以下：步驟狀態(tài)符號輸入串下一步動作00#dbdb#

r3歸約102#Adbdb#

s4移進2024#A