編譯原理-練習(xí)參考

程序設(shè)計語言

Chapter2.高級語言及其語法描述編譯原理參考答案2023/2/5CH.2.練習(xí)題6(P36.)6.令文法G6為:

N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G6的語言L(G6)是什么?注意：集合的寫法不正確解：L(G6)={0,1,2,3,4,5,6,7,8,9}+

={09數(shù)字構(gòu)成的所有數(shù)字串，可以0開頭}(2)給出句子0127、34和568的最左和最右推導(dǎo)。注意：1)步驟，和的區(qū)別；2)不能寫為→解：0127的最左推導(dǎo)：NNDNDDNDDDDDDD0DDD01DD012D01270127的最右推導(dǎo)：NNDN7ND7N27ND27

N127D1270127+CH.2.練習(xí)題8(P36.)8.令文法為

E→T|E+T|E-TT→F|T*F|T/FF→(E)|i

(1)給出i+i*i、i*(i+i)的最左推導(dǎo)和最右推導(dǎo)。解：此處僅以i*(i+i)為例給出答案最左推導(dǎo)ETT*FF*F

i*Fi*(E)i*(E+T)

i*(T+T)

i*(F+T)

i*(i+T)

i*(i+F)

i*(i+i)

最右推導(dǎo)ETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)

T*(i+i)

F*(i+i)

i*(i+i)

CH.2.練習(xí)題8(P36.)8.令文法為

E→T|E+T|E-T

T→F|T*F|T/FF→(E)|iEE-TE-TTFFiFiii-i-i

的語法樹(2)給出i+i+i、i+i*i和i-i-i的語法樹。EE+TE+TTFFiFiii+i+i

的語法樹i+i*i的語法樹EE+TTTFFiFii*注意：樹枝和符號均不可隨意增減！CH.2.練習(xí)題9(P36.)9.證明下面的文法是二義的：

S→iSeS|iS|i證明:因為存在句子iiiei，它對應(yīng)兩棵不同的語法樹,如右圖:

所以該文法是二義文法。說明：按定義只要能給出一個反例即可，iiiei不是唯一的反例。SiSiSeSiiiSiSeSiSi2023/2/5程序設(shè)計語言

Chapter3.詞法分析編譯原理參考答案2023/2/5CH.3.練習(xí)題8(P64.)8.給出下面的正規(guī)表達(dá)式。(1)以01結(jié)尾的二進(jìn)制數(shù)串;正規(guī)式(0|1)*01(2)能被5整除的十進(jìn)制整數(shù);允許任意0開頭：

(0|1|2|3|4|5|6|7|8|9)*(0|5)不允許0開頭（0本身除外）：(0|5)|(1|2|3|…|9)(0|1|2|3|…|9)*(0|5)2023/2/5CH.3.練習(xí)題7(P64.)7.構(gòu)造下列正規(guī)式相應(yīng)的DFA。(1)1(0|1)*101

解2:正規(guī)式對應(yīng)的NFA:04123110110

I

I0I1{0}初0{1}1{1}1{1}1{1,2}2{1,2}2{1,3}3{1,2}2{1,3}3{1}1{1,2,4}4{1,2,4}終4{1,3}3{1,2}210423110110010DFA:2023/2/57.構(gòu)造下列正規(guī)式相應(yīng)的NFA。(P64.)(2)1(1010*|1(010)*1)*0XY20ε113ε1010*1(010)*1XY20ε113ε6451100*7811(010)*2023/2/57.構(gòu)造下列正規(guī)式相應(yīng)的NFA。(P64.)(2)1(1010*|1(010)*1)*0XY20ε113ε645110078119εε10010εεXY20ε113ε645110078119εε100εε1211017.

(2)1(1010*|1(010)*1)*0的NFA。2023/2/5CH.3.練習(xí)題14(P64.)(1)正規(guī)式:(10|0)*

(2)NFA:確定化:YX10ε0ε1201001012

I

I0I1{X,1,Y}{1,Y}{2}

{1,Y}{1,Y}{2}{2}{1,Y}

I

I0I1初終0

12

終11

2

2

1

DFA:2023/2/5CH.3.練習(xí)題14(P64.)(1)正規(guī)式:(10|0)*

(2)NFA:YX10ε0ε1201001012DFA:構(gòu)造一個DFA，它接受S＝{0,1}上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。10010DFA:(最簡)2023/2/5編譯原理參考答案程序設(shè)計語言

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

S→a|^|(T)T→T，S|S(1)消去G1的左遞歸。然后對每個非終結(jié)符,寫出不帶回溯的遞歸子程序。解(1)消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε2023/2/5CH.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.)解(1)不帶回溯的遞歸子程序:T→ST’ProcedureT;BeginS;T’end;

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

S;T’endEnd;CH.4.練習(xí)題1(P81.)(2)經(jīng)改寫后的文法是否是LL(1)的?給出它的預(yù)測分析表。消左后的文法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)文法。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’2023/2/5CH4.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|ε。解，因為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)文法。CH.4.練習(xí)題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)文法。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)文法。CH.4.練習(xí)題3(P82.)3.下面文法中,哪些是LL(1)的,說明理由。(4)

S→aSe|B

B→bBe|C

C→cCe|d。解，

因為

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

和C→cCe|d

各產(chǎn)生式的候選式的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)文法。編譯原理參考答案程序設(shè)計語言

Chapter5.自下而上語法分析2023/2/5CH.5.練習(xí)題1(P133.)1.令文法G1為：E→E+T|TT→T*F|FF→(E)|i

證明E+T*F是它的一個句型,指出這個句型的所有短語、直接短語和句柄。證明1:∵存在從開始符號E出發(fā)到E+T*F的推導(dǎo)：EE+TE+T*F∴E+T*F是G1的一個句型。短語:E+T*F是句型相對于非終結(jié)符E的短語;T*F是句型相對于非終結(jié)符T的短語。直接短語:T*F是句型相對于規(guī)則T→T*F的直接短語句柄:T*FEE+TT*F語法樹2023/2/5CH.5.練習(xí)題1(P133.)1.令文法G1為：E→E+T|TT→T*F|FF→(E)|i

證明E+T*F是它的一個句型,指出這個句型的所有短語、直接短語和句柄。證明2:∵可構(gòu)造出E+T*F的語法樹，如右圖所示，∴E+T*F是G1的一個句型。證明3:(也可用歸約來證明)（概念熟悉后，短語、直接短語和句柄可直接列出而不用說明）短語:E+T*F，T*F直接短語:T*F句柄:T*FEE+TT*F語法樹2023/2/5CH.5.練習(xí)題2(P133.)2.考慮下面的表格結(jié)構(gòu)文法G2：S→a||(T)T→T,S|S

(1)給出(a,(a,a))的最左和最右推導(dǎo)。(1)解:(a,(a,a))的最左推導(dǎo)：S(T)

(T,S)(S,S)

(a,S)(a,(T))

(a,(T,S))

(a,(S,S))

(a,(a,S))(a,(a,a))

最右推導(dǎo)：S(T)

(T,S)(T,(T))

(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))

(S,(a,a))(a,(a,a))

2023/2/5CH.5.練習(xí)題2(P133.)2.(2)指出(a,(a,a))的規(guī)范歸約及每一步的句柄。根據(jù)這個規(guī)范歸約，給出“移進(jìn)-歸約”的過程，并給出它的語法樹自下而上的構(gòu)造過程。(2)解:(a,(a,a))的規(guī)范歸約及每一步的句柄:

(a,(a,a))(S,(a,a))(T,(a,a))(T,(S,a))(T,(T,a))(T,(T,S))(T,(T))

(T,S)(T)

S.........2023/2/5CH.5.練習(xí)題2(P133.)2.(2).給出(a,(a,a))“移進(jìn)-歸約”的過程。(2)解:(a,(a,a))的“移進(jìn)-歸約”過程:步驟符號棧輸入串動作句柄1#

(a,(a,a))#a2#(a,(a,a))#移進(jìn)(3#(a

,(a,a))#移進(jìn)a4#(S,(a,a))#歸約S→aS5#(T,(a,a))#歸約T→Sa6#(T,(a,a))#移進(jìn),7#(T,(a,a))#

移進(jìn)(8#(T,(a

,a))#移進(jìn)a2023/2/5CH.5.練習(xí)題2(P133.)2.(2).給出(a,(a,a))“移進(jìn)-歸約”的過程。(2)解:(a,(a,a))的“移進(jìn)-歸約”過程:步驟符號棧輸入串動作句柄9#(T,(S

,a))#歸約S→aS10#(T,(T,a))#歸約T→Sa

11#(T,(T,a))#移進(jìn),12#(T,(T,a))#

移進(jìn)a13#(T,(T,S))#歸約S→aT,S14#(T,(T

))#歸約T→T,S(T)15#(T,(T))#

移進(jìn))16#(T,S

)#歸約S→(T)T,S2023/2/5CH.5.練習(xí)題2(P133.)2.(2).給出(a,(a,a))“移進(jìn)-歸約”的過程。(2)解:(a,(a,a))的“移進(jìn)-歸約”過程:步驟符號棧輸入串動作句柄

17#(T

)#歸約T→T,S(T)18#(T)#

移進(jìn))19#S#歸約S→(T)20成功,分析結(jié)束,接受輸入串2023/2/5CH.5.練習(xí)題2(P133.)2.(2).給出(a,(a,a))的語法樹自下而上構(gòu)造過程。(2)解:

(a,(a,a))的語法樹自下而上構(gòu)造過程:用序號表示S(T)T,S①(T)T,SSaSaa②③④⑤⑥⑦⑧⑨2023/2/5CH.5.練習(xí)題3(P133.)3.(1)計算練習(xí)2文法G2的FIRSTVT和LASTVT。S→a||(T)T→T,S|S(1)解:（執(zhí)行相應(yīng)的算法可求得）

FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,

a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)},2023/2/5CH.5.練習(xí)題3(P133.)3.(2)計算文法G2的優(yōu)先關(guān)系,G2是一個算符優(yōu)先文法嗎?S→a||(T)T→T,S|S(2)解:

FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,,a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)}逐一考察S→(T)

和T→T,S

兩兩相鄰的符號，得到算符優(yōu)先關(guān)系,如右圖；G2是算符優(yōu)先文法。

a∧(),#

a>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=.......................2023/2/53.(4)給出輸入串(a,(a,a))的算符優(yōu)先分析過程。S→a||(T)T→T,S|S序號符號棧輸入串優(yōu)先關(guān)系下一步的動作0#(a,(a,a))##<(移進(jìn)(1#(

a,(a,a))#(<a移進(jìn)a2#(a,(a,a))#(<aa>,歸約S→a3#(S,(a,a))#(<,移進(jìn),4#(S,(a,a))#,<(移進(jìn)(5#(S,(

a,a))#(<a移進(jìn)a6#(S,(a,a))#(<aa>,歸約S→a7#(S,(S,a))#(<,移進(jìn),8#(S,(S,

a))#,<a移進(jìn)a

a∧(),#

a>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=最左素短語..................................2023/2/5序號符號棧輸入串優(yōu)先關(guān)系下一步的動作9#(S,(S,a))#,<(a>)歸約S→a10#(S,(S,S

))#(<,,>)歸約T→S,S11#(S,(T))#(=)移進(jìn))12#(S,(T)

)#,<()>)歸約S→(T)13#(S,S

)#(<,,>)歸約T→S,S14#(T

)#(=)移進(jìn))15#(T)

#*<()>#歸約S→(T)16#S

##=#接受17#S

#停.............3.(4)給出輸入串(a,(a,a))的算符優(yōu)先分析過程。S→a||(T)T→T,S|S

a∧(),#

a>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=最左素短語.......................2023/2/55.(1)考慮文法S→AS|bA→SA|a

列出這個文法的所有LR(0)項目。CH.5.練習(xí)題5(P134.)解(1):拓廣文法，加入S’→S

拓廣文法的LR(0)項目有:

S’→.SS’→S.

S→.ASS→A.SS→AS.S→.bS→b.A→.SAA→S.AA→SA.A→.aA→a.2023/2/55.(2)構(gòu)造文法S→AS|bA→SA|a的LR(0)項目集規(guī)范族及識別活前綴的DFA。1）拓廣文法，加入S’→S2）畫出DFA2023/2/55.(2)構(gòu)造文法S→AS|bA→SA|a的LR(0)項目集規(guī)范族及識別活前綴的DFA。0:S’→.S

S→.ASS→.bA→.SAA→.a5:A→SA.S→A.SS→.ASS→.bA→.SAA→.a 7:S→AS.A→S.AA→.SAA→.aS→.ASS→.b 1:S’→S.A→S.AA→.SAA→.aS→.ASS→.b 3:S→b.4:A→a.2:S→A.S

S→.ASS→.bA→.SAA→.a6:A→S.A

A→.SAA→.aS→.ASS→.bSbaAASbaASabSabASAbaSabA2023/2/55.(3)

文法S→AS|bA→SA|a

是LR(0)文法嗎？0:S’→.S

S→.ASS→.bA→.SAA→.a5:A→SA.S→A.SS→.ASS→.bA→.SAA→.a 7:S→AS.A→S.AA→.SAA→.aS→.ASS→.b 1:S’→S.A→S.AA→.SAA→.aS→.ASS→.b 3:S→b.4:A→a.2:S→A.S

S→.ASS→.bA→.SAA→.a6:A→S.A

A→.SAA→.aS→.ASS→.bSbaAASbaASabSabASAbaSabA不是LR(0)文法！因為存在沖突，例如狀態(tài)1、狀態(tài)52023/2/5編譯原理參考答案程序設(shè)計語言

Chapter7.語義分析和中間代碼產(chǎn)生2023/2/5P217-1a*（-b+c）后綴式：ab-c+*a+b*（c+d/e）后綴式：abcde/+*+-a+b*（-c+d）后綴式：a-bc-d+*+notAornot（CornotD）后綴式：AnotCDnotornotor（AandB）or（notCorD）后綴式：ABandCnotDoror2023/2/5P217-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)2023/2/5P218-4自下而上分析過程中把賦值語句A:=B*（-C+D）翻譯成三地址碼的步驟：

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

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

Chapter8.–Chapter11.2023/2/