編譯原理考試習(xí)題及答案

程序設(shè)計(jì)語(yǔ)言

Chapter3.詞法分析編譯原理參考答案2025/1/8CH.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)2025/1/8CH.3.練習(xí)題7(P64.)7.

(1)1(0|1)*101構(gòu)造DFA。解1:正規(guī)式對(duì)應(yīng)的NFA:XY345110ε112ε10

I

I0I1{X}{1,3,2}{1,3,2}

{3,2}{3,4,2}{3,2}{3,2}{3,4,2}{3,4,2}{3,5,2}{3,4,2}{3,5,2}{3,2}{3,Y,4,2}{3,Y,4,2}{3,5,2}{3,4,2}

I

I0I1初01

123

223

343

425終5432025/1/8(1)正規(guī)式1(0|1)*101DFA:x3,Y,4,23,4,23,5,211011,3,23,20100101

I

I0I1{X}{1,3,2}{1,3,2}

{3,2}{3,4,2}{3,2}{3,2}{3,4,2}{3,4,2}{3,5,2}{3,4,2}{3,5,2}{3,2}{3,Y,4,2}{3,Y,4,2}{3,5,2}{3,4,2}

I

I0I1初01

123

223

343

425終5432025/1/8(1)正規(guī)式1(0|1)*101DFA:

I

I0I1{X}{1,3,2}{1,3,2}

{3,2}{3,4,2}{3,2}{3,2}{3,4,2}{3,4,2}{3,5,2}{3,4,2}{3,5,2}{3,2}{3,Y,4,2}{3,Y,4,2}{3,5,2}{3,4,2}

I

I0I1初01

123

223

343

425終543053411011201001012025/1/8CH.3.練習(xí)題7(P64.)7.構(gòu)造下列正規(guī)式相應(yīng)的DFA。(1)1(0|1)*101

解2:正規(guī)式對(duì)應(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:2025/1/87.構(gòu)造下列正規(guī)式相應(yīng)的NFA。(P64.)(2)1(1010*|1(010)*1)*0XY20ε113ε1010*1(010)*1XY20ε113ε6451100*7811(010)*2025/1/87.構(gòu)造下列正規(guī)式相應(yīng)的NFA。(P64.)(2)1(1010*|1(010)*1)*0XY20ε113ε6451100*7811(010)*XY20ε113ε645110078119εε10010εε2025/1/8XY20ε113ε645110078119εε10010εεXY20ε113ε645110078119εε100εε1211017.

(2)1(1010*|1(010)*1)*0的NFA。2025/1/8CH.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:2025/1/8CH.3.練習(xí)題14(P64.)(1)正規(guī)式:(10|0)*

(2)NFA:YX10ε0ε1201001012DFA:構(gòu)造一個(gè)DFA，它接受S＝{0,1}上所有滿足如下條件的字符串：每個(gè)1都有0直接跟在右邊。10010DFA:(最簡(jiǎn))2025/1/8程序設(shè)計(jì)語(yǔ)言

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

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

={0

9數(shù)字構(gòu)成的所有數(shù)字串，可以0開頭}(2)給出句子0127、34和568的最左和最右推導(dǎo)。注意：1)步驟，

和

的區(qū)別；2)

不能寫為→解：0127的最左推導(dǎo)：NNDNDDNDDDDDDD0DDD01DD012D01270127的最右推導(dǎo)：NNDN7ND7N27ND27

N127

D1270127+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

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

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

S→iSeS|iS|i證明:因?yàn)榇嬖诰渥觟iiei，它對(duì)應(yīng)兩棵不同的語(yǔ)法樹,如右圖:

所以該文法是二義文法。說(shuō)明：按定義只要能給出一個(gè)反例即可，iiiei不是唯一的反例。SiSiSeSiiiSiSeSiSi2025/1/8編譯原理參考答案程序設(shè)計(jì)語(yǔ)言

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

證明E+T*F是它的一個(gè)句型,指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。證明1:∵存在從開始符號(hào)E出發(fā)到E+T*F的推導(dǎo)：E

E+TE+T*F∴E+T*F是G1的一個(gè)句型。短語(yǔ):E+T*F是句型相對(duì)于非終結(jié)符E的短語(yǔ);T*F是句型相對(duì)于非終結(jié)符T的短語(yǔ)。直接短語(yǔ):T*F是句型相對(duì)于規(guī)則T→T*F的直接短語(yǔ)句柄:T*FEE+TT*F語(yǔ)法樹2025/1/8CH.5.練習(xí)題1(P133.)1.令文法G1為：E→E+T|TT→T*F|FF→(E)|i

證明E+T*F是它的一個(gè)句型,指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。證明2:∵可構(gòu)造出E+T*F的語(yǔ)法樹，如右圖所示，∴E+T*F是G1的一個(gè)句型。證明3:(也可用歸約來(lái)證明)（概念熟悉后，短語(yǔ)、直接短語(yǔ)和句柄可直接列出而不用說(shuō)明）短語(yǔ):E+T*F，T*F直接短語(yǔ):T*F句柄:T*FEE+TT*F語(yǔ)法樹2025/1/8CH.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))

2025/1/8CH.5.練習(xí)題2(P133.)2.(2)指出(a,(a,a))的規(guī)范歸約及每一步的句柄。根據(jù)這個(gè)規(guī)范歸約，給出“移進(jìn)-歸約”的過(guò)程，并給出它的語(yǔ)法樹自下而上的構(gòu)造過(guò)程。(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.........2025/1/8CH.5.練習(xí)題2(P133.)2.(2).給出(a,(a,a))“移進(jìn)-歸約”的過(guò)程。(2)解:(a,(a,a))的“移進(jìn)-歸約”過(guò)程:步驟符號(hào)棧輸入串動(dòng)作句柄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)a2025/1/8CH.5.練習(xí)題2(P133.)2.(2).給出(a,(a,a))“移進(jìn)-歸約”的過(guò)程。(2)解:(a,(a,a))的“移進(jìn)-歸約”過(guò)程:步驟符號(hào)棧輸入串動(dòng)作句柄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,S2025/1/8CH.5.練習(xí)題2(P133.)2.(2).給出(a,(a,a))“移進(jìn)-歸約”的過(guò)程。(2)解:(a,(a,a))的“移進(jìn)-歸約”過(guò)程:步驟符號(hào)棧輸入串動(dòng)作句柄

17#(T

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

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

(a,(a,a))的語(yǔ)法樹自下而上構(gòu)造過(guò)程:用序號(hào)表示S(T)T,S①(T)T,SSaSaa②③④⑤⑥⑦⑧⑨2025/1/8CH.5.練習(xí)題3(P133.)3.(1)計(jì)算練習(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,∧,)},2025/1/8CH.5.練習(xí)題3(P133.)3.(2)計(jì)算文法G2的優(yōu)先關(guān)系,G2是一個(gè)算符優(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

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

a∧(),#

a>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=.......................2025/1/83.(4)給出輸入串(a,(a,a))的算符優(yōu)先分析過(guò)程。S→a|

|(T)T→T,S|S序號(hào)符號(hào)棧輸入串優(yōu)先關(guān)系下一步的動(dòng)作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>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=最左素短語(yǔ)..................................2025/1/8序號(hào)符號(hào)棧輸入串優(yōu)先關(guān)系下一步的動(dòng)作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)先分析過(guò)程。S→a|

|(T)T→T,S|S

a∧(),#

a>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=最左素短語(yǔ).......................2025/1/85.(1)考慮文法S→AS|bA→SA|a

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

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

S’→.SS’→S.

S→.ASS→A.SS→AS.S→.bS→b.A→.SAA→S.AA→SA.A→.aA→a.2025/1/85.(2)構(gòu)造文法S→AS|bA→SA|a的LR(0)項(xiàng)目集規(guī)范族及識(shí)別活前綴的DFA。1）拓廣文法，加入S’→S2）畫出DFA2025/1/85.(2)構(gòu)造文法S→AS|bA→SA|a的LR(0)項(xiàng)目集規(guī)范族及識(shí)別活前綴的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→.bSbaAASbaASabSabASAbaSabA2025/1/85.(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)文法！因?yàn)榇嬖跊_突，例如狀態(tài)1、狀態(tài)52025/1/8編譯原理參考答案程序設(shè)計(jì)語(yǔ)言

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

S→a|^|(T)T→T，S|S(1)消去G1的左遞歸。然后對(duì)每個(gè)非終結(jié)符,寫出不帶回溯的遞歸子程序。解(1)消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε2025/1/8CH.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ù)測(cè)分析表。消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε(2)因?yàn)镚1’

:①文法不含左遞歸;②對(duì)S→a|^|(T)

FIRST(a)={a},FIRST(^)={^},FIRST((T))={(},集合互不相交且不含ε;③對(duì)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ù)測(cè)分析表:①對(duì)S→a|^|(T)②對(duì)T→ST’

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

FOLLOW(T’)={)}

a^(),#

SS→aS→^S→(T)

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

T’T’→εT’→,ST’2025/1/8CH4.1.(3)給出對(duì)符號(hào)串(a，^)的分析過(guò)程步驟符號(hào)棧輸入串動(dòng)作,所用產(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)的,說(shuō)明理由。(1)

S→ABcA→a|εB→b|ε。解，因?yàn)镕OLLOW(S)={#}

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

②對(duì)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)的,說(shuō)明理由。(2)

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

因?yàn)镕OLLOW(S)={#}

對(duì)A→a|B|ε

;FIRST(S)={a,b}

FIRST(B)={b,ε}與FIRST(ε)={ε}相交;所以文法不是LL(1)文法。解(2)對(duì)A→a|ε因?yàn)棣拧蔉IRST(A)={a,b,ε}，F(xiàn)OLLOW(A)=,FOLLOW和FIRST兩者相交。所以文法不是LL(1)文法。CH.4.練習(xí)題3(P82.)3.下面文法中,哪些是LL(1)的,說(shuō)明理由。(3)

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

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

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

兩者相交。所以，文法不是LL(1)文法。CH.4.練習(xí)題3(P82.)3.下面文法中,哪些是LL(1)的,說(shuō)明理由。(4)

S→aSe|B

B→bBe|C

C→cCe|d。解，

因?yàn)?/p>

①文法不含左遞歸;②對(duì)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è)計(jì)語(yǔ)言

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

（參看p179的語(yǔ)義子程序）2025/1/8語(yǔ)法分析 翻譯過(guò)程：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符號(hào)表2025/1/8A:=B*(-C+D)的三地址碼k5:=uminusk3k6:=k5+k4k7:=k2*k6k1:=k7名字屬性地址ABCDT1T2T3……k1K2k3k4k5k6k7符號(hào)表（參看p179的語(yǔ)義子程序）2025/1/8P218-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，-，-，.）TCFC2025/1/8P218-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é)的辦法，把下面的語(yǔ)句翻譯成四元式序列：whileA<CandB<DdoifA=1thenC:=C+1