編譯原理參考答案程序設(shè)計(jì)語言

Chapter4.自上而下語法分析2022/12/21CH.4.練習(xí)題1(P81.)1.考慮下面文法G1:

S→a|^|(T)T→T，S|S(1)消去G1的左遞歸。然后對每個(gè)非終結(jié)符,寫出不帶回溯的遞歸子程序。解(1)消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε2022/12/21CH.4.練習(xí)題1(P81.)解(1)不帶回溯的遞歸子程序:S→a|^|(T)ProcedureS;Beginifsym=‘a(chǎn)’orsym=‘^’thenadvanceelseifsym=‘(‘thenbeginadvance;T;ifsym=‘)’thenadvance

elseerrorendelseerrorEnd;CH.4.練習(xí)題1(P81.)(2)經(jīng)改寫后的文法是否是LL(1)的?給出它的預(yù)測分析表。消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε(2)因?yàn)镚1’:①文法不含左遞歸;②對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)文法。CH.4.練習(xí)題1(P81.)(2)構(gòu)造G1’的預(yù)測分析表:①對S→a|^|(T)②對T→ST’

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

FOLLOW(T’)={)}

a^(),#

SS→aS→^S→(T)

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

T’T’→εT’→,ST’2022/12/21CH4.1.(3)給出對符號串(a，^)的分析過程步驟符號棧輸入串動作,所用產(chǎn)生式.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##分析成功,結(jié)束分析CH.4.練習(xí)題3(P82.)3.下面文法中,哪些是LL(1)的,說明理由。(1)

S→ABcA→a|εB→b|ε。解，因?yàn)镕OLLOW(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)文法。CH.4.練習(xí)題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)文法。編譯原理參考答案程序設(shè)計(jì)語言

Chapter7.語義分析和中間代碼產(chǎn)生2022/12/21P217-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)2022/12/21P218-4自下而上分析過程中把賦值語句A:=B*（-C+D）翻譯成三地址碼的步驟：

（參看p179的語義子程序）2022/12/21語法分析 翻譯過程：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........產(chǎn)生一個(gè)新的中間變量T1E3.place=k5產(chǎn)生代碼

k5:=uminusk3……名字屬性地址ABCDT1T2T3……k1K2k3k4k5k6k7符號表2022/12/21A:=B*(-C+D)的三地址碼k5:=uminusk3k6:=k5+k4k7:=k2*k6k1:=k7名字屬性地址ABCDT1T2T3……k1K2k3k4k5k6k7符號表（參看p179的語義子程序）2022/12/21P218-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，-，-，.）TCFC2022/12/21編譯原理參考答案程序設(shè)計(jì)語言

Chapter8.–Chapter11.2022/12/21CH8.–CH11.1.什么是符號表？符號表有哪些重要作用？2.符號表的表項(xiàng)常包括哪些部分？各描述什么？3.有哪些存儲分配策略？并敘述何時(shí)用何種存儲分配策略？4.代碼優(yōu)化的常用措施和優(yōu)化的三個(gè)層次。2022/12/21補(bǔ)充題1.畫出編譯程序的總體邏輯結(jié)構(gòu)圖，簡述各部分的主要功能。2022/12/21補(bǔ)充題2.已知文法G[Z]:Z→0U|1VU→1Z|1V→0Z|0請寫出此文法描述的只含有４個(gè)符號的全部句子。G[Z]產(chǎn)生的語言是什么？該文法在Chomsky文法分類中屬于幾型文法？2022/12/21補(bǔ)充題3.已知文法和它的LR分析表如下，給出串dbdb#的LR分析過程。

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

r3歸約102#Adbdb#

s4移進(jìn)2024#Adbdb#s5移進(jìn)30245#Adbdb#

r4歸約40246#AdBdb#s7移進(jìn)502467#AdBdb#s8移進(jìn)6024678#AdBdb#r5歸約90246#AdB#r1歸約1001#S#

acc11

停2022/12/21補(bǔ)充題4.給定文法和語義動作如下：

A→aB{print“0”}

A→c{print“1”}

B

→Ab{print“2”}

問：按照以上的語義子程序，aacbb經(jīng)翻譯后的輸出結(jié)果是什么？請給出翻譯過程。

翻譯過程和翻譯結(jié)果語法分析：aacbb

aaAbb(1)aaBb(2)aAb(3)aB(4)

A