《編譯原理》課后習(xí)題答案第三章

第3章文法和語言

第1題

文法G=({A,B,S},{a,b,c},叫其中P為：

S-*Ac|aB

A-ab

B-be

寫出L(G⑸)的全部元素。

答案：

L(G[S])={abc}

第2題

文法G[N]為:

N-D|ND

D->0|l|2|3|4|5|6|7|8|9

G[N]的語言是什么？

答案：

G[N]的語言是V+oV={0,1,2,3,456,7,8,9}

N=>ND=>NDD....=>NDDDD...D=>D……D

或者：允許0開頭的非負整數(shù)？

第3題

為只包含數(shù)字、加號和減號的表達式，例如9-2+5,3-1,7等構(gòu)造一個文法。

答案：

G[S]:

S->S+D|S-D|D

D->0|l|2|3|4|5|6|7|8|9

第4題

已知文法G[Z]:

Z-*aZb|ab

寫出L(G[Z])的全部元素。

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站1

《編譯原理》課后習(xí)題答案第三章

答案：

Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb

L(G[Z])={anbn|n>=l}

第5題

寫一文法，使其語言是偶正整數(shù)的集合。要求：

⑴允許0打頭；

⑵不允許0打頭。

答案：

⑴允許0開頭的偶正整數(shù)集合的文法

E-NT|D

T-NT|D

N-*D|1|3|5|7|9

D->0|2|4|6|8

⑵不允許0開頭的偶正整數(shù)集合的文法

E—NT|D

T-*FT|G

N-*D|1|3|5|7|9

D-2|4|6|8

F-*N|O

G-D|O

第6題

已知文法G：

（表達式＞：：=＜項＞I＜表達式＞+＜項＞

＜項＞::=＜因子＞I＜項＞*＜因子＞

〈因子〉:"（〈表達式＞）Ii

試給出下述表達式的推導(dǎo)及語法樹。

（5）i+（i+i）

（6）i+i*i

盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站2

《編譯原理》課后習(xí)題答案第三章

答案；

〈表達式〉

〈表達式＞+＜項＞

〈因子＞

〈表達式〉

〈表達式〉+＜項＞

〈因子〉

i

〈項〉

（因子＞

i

〈項〉

〈因子〉

（）

⑸〈表達式〉

=＞＜表達式＞+＜項＞

=＞＜表達式＞+＜因子＞

=＞＜表達式＞+（〈表達式＞）

=＞＜表達式＞+（〈表達式＞+＜項＞）

=＞＜表達式＞+（〈表達式＞+＜因子》）

=＞＜表達式＞+（〈表達式〉+i）

=＞＜表達式＞+（＜項＞+i）

=＞＜表達式＞+（〈因子〉+i）

=＞＜表達式＞+（i+i）

=><項>+(i+i)

=><因子>+(i+i)

=＞i+（i+i）

〈表達式〉

〈表達式〉+＜項＞

＜項＞?（因子〉

〈因子＞i

〈項〉

〈因子〉

⑹〈表達式〉

=＞＜表達式＞+＜項＞

=＞＜表達式＞+＜項＞*＜因子＞

=＞＜表達式＞+＜項＞*i

=＞＜表達式＞+＜因子＞*i

=＞＜表達式＞+i*i

=＞＜項〉+i*i

=＞＜因子〉+i*i

=＞iIi*i

盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站3

《編譯原理》課后習(xí)題答案第三章

第7題

證明下述文法G［〈表達式〉］是二義的。

〈表達式〉：：=a|（〈表達式））|〈表達式〉〈運算符〉〈表達式〉

（運算符〉：：=+|-|*|/

答案：

可為句子a+a*a構(gòu)造兩個不同的最右推導(dǎo)：

最有推導(dǎo)1〈表達式〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉（運算符〉a

〈表達式〉*a

〈表達式〉〈運算符〉〈表達式〉*a

〈表達式〉（運算符〉a*a

〈表達式〉+a*a

最右推導(dǎo)2〈表達式〉〈表達式〉〈運算符〉〈表達式）

〈表達式〉（運算符〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉（運算符〉〈表達式〉〈運算符〉a

〈表達式〉（運算符〉〈表達式〉*a

〈表達式〉（運算符〉a*a

〈表達式〉+a*a

a+a*a

盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站4

《編譯原理》課后習(xí)題答案第三章

第8題

文法G⑸為：

答案：

此句型對應(yīng)語法樹如右，牧為此文法一個句型。

或者：因為存在推導(dǎo)序列:E=>E+T=>E+T*F,所

以E+T*F句型

此句型相對于E的短語有:E+T*F：相對于T的短語

有T*F

直接短語為：T*F

句柄為：T*F

第13題

一個上下文無關(guān)文法生成句子abbaa的推導(dǎo)樹如下：

⑴給出串a(chǎn)bbaa最左推導(dǎo)、最右推導(dǎo)。

⑵該文法的產(chǎn)生式集合P可能有哪些元素？

⑶找出該句子的所有短語、直接短語、句柄。

B

a

S

ABS

a

SBA

ebba

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站6

《編譯原理》課后習(xí)題答案第三章

答案：

⑴串a(chǎn)bbaa最左推導(dǎo):

S=>ABS=>aBS=>aSBBS=>aB3S=>abBS=>abbS=>abbAa=>abbaa

最右推導(dǎo)：

S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa

⑵產(chǎn)生式有：S-*ABS|Aa|￡A-aB-SBB|b

可能元素有:￡aaababbaaaaabbaa.......

⑶該句子的短語有：

a是相對A的短語

￡是相對S的短語

b是相對B的短語

￡bb是相對B的短語

aa是相對S的短語

aebbaa是相對S的短語

直接短語有：a￡b

句柄是：a

第14題

給出生成下述語言的上下文無關(guān)文法：

(1){anbnambm|n,m>=0}

(2){InOmlmOn|n,m>=0}

(3){WaWr|W屬于{0|a}*,Wr表示W(wǎng)的逆}

答案：

(1)

S—AA

A-*aAb|￡

(2)

S-*1SO|A

A-*OA1|￡

(3)

S-*OSO|1S1|E

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站7

《編譯原理》課后習(xí)題答案第三章

第16題

給出生成下述語言的三型文法：

(l){an|n>=0}

(2){anbm|nzm>=l}

⑶{anbmck|n,m,k>=0}

答案：

(l)S-*aS|￡

(2)

S-*aA

A-*aA|B

B-bB|b

⑶

AfaA|B

B-*bB|C

C-cC|e

第17題

習(xí)題7和習(xí)胭11中的文法等價嗎？

答案：

等價。

第18題

解釋下列術(shù)語和概念：

(1)字母表

(2)串、字和句子

(3)語言、語法和語義

答案：

(1)字母表：是一個非空有窮集合。

(2)串：符號的有窮序列。

字：字母表中的元素。

句子：如果Zx,x￡V*T則稱x是文法G的一個句子。+

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站8

《編譯原理》課后習(xí)題答案第三章

(3)語言：它是由句子組成的集合，是由?組記號所構(gòu)成的集合。程序設(shè)計的語言就是所

有該語言的程序的全體。語言可以看成在一個基本符號集上定義的，按一定規(guī)

則構(gòu)成的一切基本符號串組成的集合。

語法：表示構(gòu)成語言句子的各個記號之間的組合規(guī)律。程序的結(jié)構(gòu)或形式。

語義：表示按照各種表示方法所表示的各個記號的特定含義。語言所代表的含義。

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站9

《編譯原理》課后習(xí)題答案第三章

附加題

問題1：

給出下述文法所對應(yīng)的正規(guī)式：

S-*OA|1B

A^1S|1

B-*0S|0

答案：

R=(01|10)(01|10)*

問題2：

已知文法G[A],寫出它定義的語言描述

G[A]:A->OB|1C

B-1|1A|OBB

C-*O|OA|1CC

答案：

G[A]定義的語言由0、1符號串組成，串中0和1的個數(shù)相同.

問題3：

給出語言描述，構(gòu)造文法.

構(gòu)造一文法，其定義的語言是由算符+,*,(,)和運算對象a構(gòu)成的算術(shù)表達式的集合.

答案一：

G[E]E->E+T|T

T—T*F|F

F-(E)|a

答案一：

G[E]E-E+E|E*E|(E)|a

問題4：

已知文法G[S]:

S-*dAB

盛威網(wǎng)(w)專業(yè)的計算機學(xué)習(xí)網(wǎng)站10

《編譯原理》課后習(xí)題答案第三章

A-*aA|a

B-￡|bB

相應(yīng)的正規(guī)式是什么？G[S]能否改寫成為等價的正規(guī)文法？

答案：

正規(guī)式是daa*b*；

相應(yīng)的正規(guī)文法為(由自動機化簡來)：

G[S]:S->dAA-*a|aBB-*aB|a|b|bCC-*bC|b

也可為(觀察得來):G[S]:S—dAA-*a|aA|aBBfbB|t

問題5：

己知文法G：

E-E+T|E-T|T

TfT*F|T/F|F

FfE)|i

試給出下述表達式的推導(dǎo)及語法樹

⑴i；

⑵i*i+i

(3)i+i*i

(4)i+(i+i)

答案：

(l)E=>T=>F=>i

(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i

(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)

=>i+(i+T)=>i+(i+F)=>i+(i+i)

EE

E+T

T

T*F

Fi

i

E+T

i

T

F

i

F

i

E

E+T

E+T

i

T

F

F

(E)

i

T

Fi

F

T

F

i

F

⑴

⑵

(3)

(4)

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站11

《編譯原理》課后習(xí)題答案第三章

問題6：

已知文法G[E]:

EfET+|T

T—TF*|F

F-*FA|a

試證：FFM*是文法的句型，指出該句型的短語、簡單短語和句柄.

答案：

該句型對應(yīng)的語法樹如下：

該句型相對于E的短語有FF"*

相對于T的短語有FF"*,F

相對于F的短語有FA;FAA

簡單短語有F;FA

句柄為F.

問題7：

適當(dāng)變換文法，找到下列文法所定義語言的一個無二義的文法：

S-SaSSbSScSd

答案：

該文法的形式很典型，可以先采用優(yōu)先級聯(lián)規(guī)則變換文法，然后再規(guī)定結(jié)合性對文法做

進一步變換，即可消除二義性。

設(shè)a、b和c的優(yōu)先級別依次增高，根據(jù)優(yōu)先級聯(lián)規(guī)則將文法變換為：

S-*SaSA

A-*AbAC

C-*CcCd

規(guī)定結(jié)合性為左結(jié)合，進一步將文法變換為：

SfSaAA

AfAbCC

C一CcFF

F-d

該文法為非二義的。

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站12

《編譯原理》課后習(xí)題答案第三章

問題8：

構(gòu)造產(chǎn)生如下語言的上下文無關(guān)文法：

(1){anb2ncm|n,m2。}

(2){anbmc2m|n,m20}

(3){ambnm2n}

(4){ambncpdqm+n=p+q)

(5){uawbu,wG{a,t}*A|u|=|w||

答案：

（1）根據(jù)上下文無關(guān)文法的特點，要產(chǎn)生形如anb2ncm的串，可以分別產(chǎn)生形如anb2n和

形如cm的串。設(shè)計好的文法是否就是該語言的文法？嚴格地說，應(yīng)該給出證明。但若不是

特別指明，通?？梢院雎赃@一點。

對于該語言，存在一個由以下產(chǎn)生式定義的上下文無關(guān)文法G[S]：

S-*AB

A-*EaAbb

Bf￡cB

（2）同樣，要產(chǎn)生形如anbmc2m的串，可以分別產(chǎn)生形如an和形如bmc2m的串。對于該

語

言，存在一個由以下產(chǎn)生式定義的上下文無關(guān)文法G⑸：

S—AB

A-*EaA

B-*￡bBcc

（3）考慮在先產(chǎn)生同樣數(shù)目的a,b,然后再生成多余的a。以下G⑸是一種解法：

S-*aSbaS￡

（4）以下G[S]是一種解法：

S-*aSdAD

A?bAdB

D—aDcB

B-*bBc￡

注：a不多于d時，b不少于c：反之，a不少于d時，b不多于c。前一種情形通過

對應(yīng)A,后一種情形對應(yīng)D。

（5）以下G[S]是一種解法：

S-Ab

A—BABa

盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站13

《編譯原理》課后習(xí)題答案第三章

Bfab

問題9：

下面的文法G⑸描述由命題變量p、q,聯(lián)結(jié)詞八（合?。?、V（析?。?、-（否定）構(gòu)

成的命題公式集合：

S-SVTT

T-*TAFF

F——Fpq

試指出句型rFVrq八p的直接短語（全部）以及句柄。

答案：

直接短語:p，q，-F

句柄：rF

問題10：

設(shè)字母表A={a},符號串x=aaa,寫出下列符號串及其長度：x0,xx,x5以及A+.

答案：

x0=（aaa）0=E|x0|=0

xx=aaaaaa|xx|=6

x5=aaaaaaaaaaaaaaa|x5|=15

A+=A1UA2U….UAnU???={a,aa/aaazaaaa,aaaaa---}

A*=AOUAlUA2U….JAnU…乂￡,a,aa,aaa,aaaa,aaaaa…}

問題11：

令2={a,b.c},乂令x=abc,y=b,z=aab>寫出如下符號串及它們的長度：xy,xyz,

(xy)3

答案：

xy=abcb|xy|=4

xyz=abcbaab|xyz|=7

(xy)3=(abcb)3=abcbabcbabcb|(xy)3|=12

問題12：

已知文法G[Z]：Z：：=UO|V1、U：：=Z1|1、V：：=ZOI0,請寫出全部由此文

法描述的只含有四個符號為句子。

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站14

《編譯原理》課后習(xí)題答案第三章

答案：

Z=>U0=>Z10=>U010=>101Q

Z=>U0=>Z10=>V110=>0110

z=>vi=>zoo=>uooo=>iooo

Z=>Vl=>Z00=>V100=>0100

問題13：

已知文法G⑸：S：：=ABA：：=aAI￡B：：=bBcIbe,寫出該文法描述的語言。

答案：

A：：=aA|￡描述的語言:{an|n>=0}

B：：=bBcIbe描述的語言:{,bncn|n>=l}

L(G[S])={anbmcm|n>=0/m>=l}

問題14：

已知文法E：：=TIE+TIE?T、T：：=F|T*F|T/F、F；；=(E)|i,寫出該文法的開

始符號、終結(jié)符號集合VT、非終結(jié)符號集合VN。

答案：

開始符號：E

VT={+,?，*,/,(,),1)

VN={E,F,T}

問題15：

設(shè)有文法G[S]：S：：=S*S|S+S|⑸|a,該文法是二義性文法嗎？

答案：

根據(jù)所給文法推導(dǎo)出句子a+a*a,畫出了兩棵不同的語法樹，所以該文法是二義性文法。

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站15

《編譯原理》課后習(xí)題答案第三章

S

s*s

S+Sa

aa

S

S+S

aS*S

aa

問題16：

寫一文法，使其語言是奇正整數(shù)集合。

答案：

A::=1|3|5|7|9|NA

N::=N0|Nl|N2|N3|N4|N5|N6|N7|N8|N9|

N::=0|l|2|3|4|5|6|7|8|9

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站16

《編譯原理》課后習(xí)題答案第四章

第4章詞法分析

第1題

構(gòu)造下列正規(guī)式相應(yīng)的DFA.

(1)1(0|1)*101

(2)1(1010*11(010)*1)*0

(3)a((a|b)*|ab*a)*b

(4)b((ab)*lbb)*ab

答案：

(1)先構(gòu)造NFA：

用子集法將NFA確定化

,01

X.A

AAAB

ABACAB

ACAABY

ABYACAB

除X,A外，重新命名其他狀態(tài)，令A(yù)B為B、AC為C、ABY為D,因為D含有Y(NFA

的終態(tài))，所以D為終態(tài)。

.01

X.A

AAB

BCB

CAD

DCB

DFA的狀態(tài)圖：：

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站1

《編譯原理》課后習(xí)題答案第四章

⑵先構(gòu)造NFA：

XIA

￡B

1C0D1E

0

F1G0H1I0J1K

0

用子集法將NFA確定化

￡01

XX

TO=XA

AABFL

Tl=ABFLYCG

YY

CGCGJ

T2=Y

T3=CGJDlll<

DHDH

KABFKL

T4=DH日

ElABEFIL

T5=ABFKLYCG

T6=ABEFILEJYCG

EJYABEFGJLY

T7=ABEFGJLYEHYCGK

EHYABEFHLY

CGKABCFGJKL

T8=ABEFHLYEYCGI

EYABEFLY

CGICGJI

T9=ABCFGJKLDHYCGK

DHYDHY

T10=ABEFLYEYCG

T11=CGJIDHJK

DHJDHJ

T12=DHY日

T13=DHJEIK

日KABEFIKL

T14=ABEFIKLEJYCG

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站2

《編譯原理》課后習(xí)題答案第四章

將TO、Tl>T2、T3、T4、T5、T6、T7、T8、T9、T10、Til、T12、T13、T14重新命名,分別

用0、

1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因為2、7、8、10、12中含有Y,

所以它們都為終態(tài)。

01

01

123

2

345

46

523

673

789

81011

9129

10103

11135

126

1314

1473

010

12

12

7

108

3

4

5

6

9

111314

1

1

0

1

0

1

0

1

1

0

1

1

0

1

0

1

01

0

1

0

1

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站3

《編譯原理》課后習(xí)題答案第四章

⑶先構(gòu)造NFA：

先構(gòu)造NFA：

XaA

￡B

a,b

E

DaEaF

C

b

e

b

用子集法將NFA確定化

eab

XX

T0=XA

AABCD

T1=ABCDBEBY

BEABCDE

BYABCDY

T2=ABCDEBEFBEY

BEFABCDEF

BEYABCDEY

T3=ABCDYBEBY

T4=ABCDEFBEFBEY

T5=ABCDEYBEFBEY

將TO、Tl、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5表示。因為3、5中含有

Y,

所以它們都為終態(tài)。

ab

01

123

245

323

445

545

Oalb3

2

a

5

a4

b

a

b

a

b

a

b

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站4

《編譯原理》課后習(xí)題答案第四章

(4)先構(gòu)造NFA：

XA

b

￡B

a

FbGbH

E

e

Y

a

E

CDb￡

lb

用子集法將NFA確定化:

eab

XX

T0=XA

AABDEF

T1=ABDEFClG

ClCl

GG

T2=CIDY

DYABDEFY

T3=GH

HABEFH

T4=ABDEFYCIG

T5=ABEFHClG

將TO、Tl、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5表示。因為4中含有Y,

所以它為終態(tài)。

ab

01

123

24

35

423

523

DFA的狀態(tài)圖：

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站5

《編譯原理》課后習(xí)題答案第四章

Oblb

2

a

4

5

3

b

b

a

b

a

b

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站6

《編譯原理》課后習(xí)題答案第四章

第2題

已知NFA=({x,y,z},{O,l},M,{x},{z}),其中：M(x,O)={z},M(y,O)={x,y},,M(z,O)={x,z},

M(x,l)={x},M(y,l)=4),M(z,l)={y},構(gòu)造相應(yīng)的DFA。

答案：

先構(gòu)造其矩陣

01

XzX

yx,y

zx,zy

用子集法將NFA確定化：

01

XzX

zxzy

xzxzxy

yxy

xyxyzx

xyzxyzxy

將X、z、xz^y^xy^xyz重新命名，分別用A、B、C、D、E、F表示。因為B、C、F

中含有z,所以它為終態(tài)。

01

ABA

BCD

CCE

DE

EFA

FFE

DFA的狀態(tài)圖：

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站7

A

01

0

F

E

D

0

B

1

0

1

0

1

0

1

C

《編譯原理》課后習(xí)題答案第四章

第3題

將下圖確定化：

答案：

用子集法將NFA確定化：

.01

SVQQU

VQVZQU

QUVQUZ

VZZZ

VZ.

QUZVZQUZ

ZZZ

重新命名狀態(tài)子集，令VQ為A、QU為B、VZ為C、V為D、QUZ為E、Z為F。

.01

SAB

ACB

BDE

CFF

DF.

ECE

FFF

DFA的狀態(tài)圖：

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站8

《編譯原理》課后習(xí)題答案第四章

第4題

將下圖的(a)和(b)分別確定化和最小化：

答案：

初始分劃得

110：終態(tài)組{0},非終態(tài)組{1,2,3,4,5}

對非終態(tài)組進行審查：

(1,2,3,4,51a{0,1,3,5}

而{0,135}既不屬于{0},也不屬于{1,234,5}

V{4}a{0},所以得到新分劃

ni：{0},{4},{1,2,3,5}

對{1,235}進行審查:

???{1,5}b{4}

{2,3}b{1,2,3,5},故得到新分劃

口2：{0},{4},{1,5},{2,3}

{1,5}a{l,5}

{2,3}a{1,3},故狀態(tài)2和狀態(tài)3不等價，得到新分劃

口3：{0},⑵，⑶，{4},(1,5)

這是最后分劃了

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站9

《編譯原理》課后習(xí)題答案第四章

最小DFA：

第5題

構(gòu)造一個DFA,它接收X={0,l}上所有滿足如下條件的字符串：每個1都有0直接跟在

右邊。并給出該語言的正規(guī)式。

答案：

按題意相應(yīng)的正規(guī)表達式是(0*10)*0*，或0*(0|10)*0*構(gòu)造相應(yīng)的DFA,首先構(gòu)造NFA為

用子集法確定化：

110II

{X,0,l,3,Y}

{0,13,Y)

{2}

{13/}

{0,1,3,Y}

{0,l,3,Y}

{1,3,Y}

{1,3,Y}

{2}

{2}

{2}

重新命名狀態(tài)集：

SOI

1

2

3

4

2

2

4

4

3

3

3

DFA的狀態(tài)圖：

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站10

《編譯原理》課后習(xí)題答案第四章

可將該DFA最小化：

終態(tài)組為{1,2,4},非終態(tài)組為{3},{1,2,4}0{1,2,4},{1,2,4}1{3},所以1,2,4為等價狀

態(tài)，可合并。

第6題

設(shè)無符號數(shù)的正規(guī)式為0:

0=dd*|dd*.dd*|.dd*|dd*10(s|￡)dd*

|10(s|e)dd*|.dd*10(s|￡)dd*

|dd*.dd*10(s|￡)dd*

化簡0,畫出。的DFA,其中d={0,l,2,???,9},s={+,-)

答案：

先構(gòu)造NFA：

X

d

.B

d

FG

d

H

10

d

A

c

10

d

D

s

e

Ed

Y

d

d

用子集法將NFA確定化：

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站11

《編譯原理》課后習(xí)題答案第四章

￡?s10d

XXA

T0=XADFA

BB

FFG

AA

T1=BC

CC

T2=FGGH

GG

HH

T3=ABFA

T4=CDC

DDE

T5=GH

T6=HH

T7=DEEY

EE

YY

T8=EY

T9=YY

將XA、B、FG、A、C、G、H、DE、E、Y重新命名，分別用0、1、2、3、4、5、6、

7、8、9表示。終態(tài)有0、3、4、6、9。

?slOd

0123

14

256

3123

474

56

66

789

89

99

DFA的狀態(tài)圖：

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站12

《編譯原理》課后習(xí)題答案第四章

d

6

25

d

3

d

d

47

8

9

0

1

10

d

10

10

d

d

s

d

d

d

第7題

給文法G⑸：

S-*aA|bQ

A-*aA|bB|b

B-*bD|aQ

Q-*aQ|bD|b

D^bB|aA

E^aB|bF

F-*bD|aE|b

構(gòu)造相應(yīng)的最小的DFAo

答案：

先構(gòu)造其NFA：

S

a

A

a

Z

Q

b

B

D

a

E

b

F

b

b

a

b

a

a

b

bb

b

a

b

用子集法將NFA確定化：

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站13

《編譯原理》課后習(xí)題答案第四章

ab

SAQ

AABZ

QQDZ

BZQD

DZAB

DAB

BQD

將S、A、Q、BZ、DZ、D、B重新命名，分別用0、1、2、3、4、5、6表示。因為3、

4中含有z,所以它們?yōu)榻K態(tài)。

ab

012

113

224

325

416

516

625

DFA的狀態(tài)圖:

0

a

a

5

2

b

3

a

a

b

4

1

6

b

b

b

b

a

b

令P0=({0,125,6},{3,4})用b進行分割：

Pl=({0,5,6},{1,2},{3,4})再用b進行分割:

P2=({0},{5,6},{1,2},{3,4})再用a、b進行分割,仍不變。

再令{0}為A,{1,2}為B,{3,4}為C,{5,6}為D。

最小化為：

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站14

《編譯原理》課后習(xí)題答案第四章

A

a,b

DC

a

a

B

b

a

b

b

第8題

給出下述文法所對應(yīng)的正規(guī)式：

S-OA|1B

A-*1S|1

B-OS|O

答案：

解方程組s的解：

S=OA|1B

A=1S|1

B=OS|O

將A、B產(chǎn)生式的右部代入S中

S=01S|01|10S|10=(01|10)S|(01|10)

所以：S=(01110)*(01|10)

第9題

將下圖的DFA最小化，并用正規(guī)式描述它所識別的語言。

1

a

2

6

c

3

C

b

5

47

b

b

ab

b

b

d

d

a

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站15

《編譯原理》課后習(xí)題答案第四章

答案：

令P0=({1,234,5},{6.7})用b進行分割：

Pl=({1,2},{3,4},{5},{6,7})再用a、b、c、d進行分割，仍不變。

再令{1,2}為A,{3,4}為B,(5}為C,{6,7}為D,

最小化為：

A

a

CD

b

d

B

b

c

b

r=b*a(c|da)*bb*=b*a(c|da)*b+

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站16

《編譯原理》課后習(xí)題答案第四章

附加題

問題1：

為下邊所描述的串寫正規(guī)式，字母表是｛a,b｝.

a)以ab結(jié)尾的所有串

b)包含偶數(shù)個b但不含a的所有串

c)包含偶數(shù)個b且含任意數(shù)目a的所有事

d)只包含一個a的所有串

e)包含ab子串的所有串

f)不包含ab子串的所有串

答案：

注意正規(guī)式不唯一

a)(a|b)*ab

b)(bb)*

c)(a*ba*ba*)*

d)b*ab*

e)(a|b)*ab(a|b)*

f)b*a*

問題2：

請描述下面正規(guī)式定義的串.字母表｛0,1｝.

a)0*(10+)*0*

b)(0|1)*(00|11)(0|1)*

c)1(0|1)*0

答案：

a)每個1至少有一個0跟在后邊的串

b)所有含兩個相繼的0或兩個相繼的1的串

c)必須以1開頭和0結(jié)尾的串

問題3

構(gòu)造有窮自動機.

a)構(gòu)造一個DFA,接受字母表。1｝上的以01結(jié)尾的所有申

b)構(gòu)造一個DFA,接受字母表｛0,1｝上的不包含0.子串的所有串.

c)構(gòu)造一個NFA,接受字母表｛x,y｝上的正規(guī)式x(x|y)*x描述的集合

d)構(gòu)造一個NFA,接受字母表｛a,b｝上的正規(guī)式(ab|a)*b+描述的集合并將其轉(zhuǎn)換為等

價的DFA.以及最小狀態(tài)DFA

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站17

《編譯原理》課后習(xí)題答案第四章

答案：

b)

c)

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站18

《編譯原理》課后習(xí)題答案第四章

最小化的DFA

問題4：

設(shè)有如圖所示狀態(tài)轉(zhuǎn)換圖，求其對應(yīng)的正規(guī)表達式。

可通過消結(jié)法得出正規(guī)式

R=(01)*((00|l)(0|l)*|0)

也可通過轉(zhuǎn)換為正則文法，解方程得到正規(guī)式。

問題5：

己知正規(guī)式：

(l)((a|b)*|aa)*b;

(2)(a|b)*b.

試用有限自動機的等價性證明正規(guī)式⑴和(2)是等價的，并給出相應(yīng)的正規(guī)文法。

分析：

基本思路是對兩個正規(guī)式，分別經(jīng)過確定化、最小化、化簡為兩個最小DFA,如這兩

個最小DFA一樣，也就證明了這兩個正規(guī)式是等價的。

答案：

盛威網(wǎng)()1?業(yè)的計算機學(xué)習(xí)網(wǎng)站19

《編譯原理》課后習(xí)題答案第四章

狀態(tài)轉(zhuǎn)換表1

ab

X1241234124Y

12341234124Y

124Y1234124Y

狀態(tài)轉(zhuǎn)換表2

aB

123

223

323

由于2與3完全一樣，將兩者合并，即見下表

ab

123

23

而對正規(guī)式(2)可畫NFA圖，如圖所示。

ab

X121212Y

121212Y

12Y1212Y

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站20

《編譯原理》課后習(xí)題答案第四章

可化簡得下表

ab

123

223

得DFA圖

兩圖完全一樣，故兩個自動機完全一樣，所以兩個正規(guī)文法等價。

對相應(yīng)正規(guī)文法，令A(yù)對應(yīng)1,B對應(yīng)2

故為：

A-*aA|bB|b

B-*aA|bB|b

即為S-aS|bS|B,此即為所求正規(guī)文法。

問題6：

考慮正規(guī)表達式r=a*b(a|b),構(gòu)造可以生成語言L(r)的一個正規(guī)文法。

答案：

S-a*b(a|b)

變換為S-*aA,S-*b(a|b),A-*aA,A-*b(a|b)

變換為S-*aA,S-*bB,B-*(a|b),A-*aA,A-*bC,C—(a|b)

變換為SfaA,SfbB,Bfa,B-*b,AfaA,AbC,Cfa,Cfb

所以，一個可能的正規(guī)文法為G⑸：

S-aA,S—bB,B-a,B-b,A-aA,A—bC,C—a,Cfb

或表示為：

S*aA|bB,B-a|b,A*aA|bC,C*a|b

(適當(dāng)?shù)葍r變換也可以，但要作說明，即要有步驟)

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站21

《編譯原理》課后習(xí)題答案第四章

問題7：

考慮下圖所示的NFAN,構(gòu)造可以生成語言L(N)的一個正規(guī)文法。

答案：

G[P]：

P-OP1P1Q

Q-*0R1R

R-￡

問題8：

考慮如下文法G⑸：

S-OSIS1A

A—OB1B

B一￡

a)試構(gòu)造語言為L(G)的一個正規(guī)表達式。

b)試構(gòu)造語言為L(G)的一個有限自動機。

答案：

a)

由A—OB,B-*￡得A-*0;

由A—IB,B￡得A-*1;

由A-*0,A-1得A-01;

由S~1A,A-01得S/1(01);

由S-1A,A-*01得S-*1(01);

由S—OS,1(01)得S-*0*l(01);

由S-IS,S-1(01)得S-1*1(01);

由Sf0*1(01),S-1*1(01)得Sf0*l(01)1*1(01);

所以，一個可能的正規(guī)表達式為：

盛威網(wǎng)(www.snwei.com)專業(yè)的計算機學(xué)習(xí)網(wǎng)站22

《編譯原理》課后習(xí)題答案第四章

0*1(01)1*1(01)

b)

盛威網(wǎng)(www.snwei.com)專業(yè)的計算機學(xué)習(xí)網(wǎng)站23

《編譯原理》課后習(xí)題答案第五章

第5章自頂向下語法分析方法

第1題

對文法G[S]

S-*a|A|(T)

T-*T,S|S

⑴給出(a,(a,a))和(((a,a),八,(a)),a)的最左推導(dǎo)。

⑵對文法G,進行改寫，然后對每個非終結(jié)符寫出不帶回溯的遞歸子程序。

⑶經(jīng)改寫后的文法是否是LL(1)的?給出它的預(yù)測分析表。

⑷給出輸入串(a,a)#的分析過程，并說明該串是否為G的句子。

答案；

⑴對(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))

對(((a,a),八,(a)),a)的最左推導(dǎo)為:

S(T)

(T,S)

(S,S)

((T),S)

((T,S),S)

((T,S,S),S)

((S,S,S),S)

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

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

(((S,S)5S),S)

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

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

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

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

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

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站1

《編譯原理》課后習(xí)題答案第五章

(((a,a),A,(a)LS)

(((a,a),八,(a)),a)

⑵改寫文法為：

0)S-*a

l)Sf八

2)S->(T)

3)T—SN

4)N->,SN

5)N—e

非終結(jié)符FIRST集FOLLOW集

S{a,△,(}{#〃,)}

T{a,A,(}OU

N{〃DM)}....

對左部為N的產(chǎn)生式可知：

FIRST(f,SN)={,}

FIRST(…)={c}

FOLLOW(N)={)}

由于SELECT(N-*ZSN)ASELECT(N-*e)={,}H{)}=

所以文法是LL(1)的。

預(yù)測分析表(PredictingAnalysisTable)

aA(),#

S-*a-*A-*(T)

T—SN—SN—SN

N一￡一，SN

也可由預(yù)測分析表中無多重入口判定文法是LLQ)的。

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站2

《編譯原理》課后習(xí)題答案第五章

⑶對輸入串(a,a)#的分析過程為：

棧(STACK)

當(dāng)前輸入符

(CUR_CHAR)

剩余輸入符

(INOUT_STRING)

所用產(chǎn)生式

(OPERATION)

#S

#)T(

#)T

#)NS

#)Na

#)N

#)NS,

#)NS

#)Na

#)N

#)

#

(

(

a

a

a

/

/

a

a

)

)

#

a,a)#…

,a)#…

,a)#…

a)#...

a)#...

)#...

)#...

#...

It...

S-*(T)

T-SN

S-a

N-*,SN

S-*a

N-*e

可見輸入串(a,a)#是文法的句子。

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站3

《編譯原理》課后習(xí)題答案第五章

第3題

已知文法G[S]：

S-*MH|a

H-*LSo|￡

K-dML|e

L-*eHf

M-K|bLM

判斷G是否是LL⑴文法，如果是，構(gòu)造LL⑴分析表。

答案：

文法展開為：

0)S-*MH

1)S—a

2)HTSo

3)H-€

4)K-dML

5)K-*E

6)L-*eHf

7)M-*K

8)M-*bLM

非終結(jié)符FIRST集FOLLOW集

S{a,d,b,c,e}{#,o}.......

M{d,￡{e,#,o}.....

H{e,e}......{#,f,o}……

L{e}.........{a,d,b,e,o,#}

K{d,￡}……{e,#,o}……

對相同左部的產(chǎn)生式可知：

SELECT(S->MH)nSELECT(S->a)={d,bze,#,o}n{a}=

SELECT*LSo)ASELECT(H-￡)={e}A{#,f,o}二

SELECT(K-*dML)ASELECT(K^￡)=i4s422y0{e,#,o}=

SELECT(M-*K)FlSELECT(M-*bLM)={d,e,#,o}Fl=

所以文法是LL(1)的。

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站4

《編譯原理》課后習(xí)題答案第五章

預(yù)測分析表：

aodefb#

S-*a-*MH-*MH-MH-MH-MH

M-*K-*K-*K-*bLM-*K

H-*E-*LSo-*E-*E

L-*eHf

K-e-dML-￡一￡

由預(yù)測分析表中無多重入口也可判定文法是LL(1)的。

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站5

《編譯原理》課后習(xí)題答案第五章

第7題

對于?個文法若消除了左遞歸，提取了左公共因子后是否?定為LL⑴文法?試對下面

文法進行改寫，并對改寫后的文法進行判斷。

(1)AfbaB|E

B-*Abb|a

(2)A->aABe|a

B-?Bb|d

(3)S-*Aa|b

A-SB

B-*ab

答案：

(1)先改寫文法為：

0)A-baB

1)A-*E

2)B-*baBbb

3)B-*bb

4)B-*a

再改寫文法為：

0)A-*baB

1)A-€

2)B-*bN

3)B?a

4)N-*aBbb

5)N-*b

FIRSTFOLLOW

A{#}

B{b,a}{札b}

N{b,a}{札b}

預(yù)測分析表：

ab#

A-*baB-*￡

B-*a-bN

N-*aBbb-*b

由預(yù)測分析表中無多重入口判定文法是11(1)的。

(2)文法：

A-*aABe|a

B-*Bb|d

提取左公共因子和消除左遞歸后文法變?yōu)椋?/p>

0)A-*aN

l)N-*ABe

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站6

《編譯原理》課后習(xí)題答案第五章

2)N-￡

3)B-*dNl

4)N1-bNl

5)N1-*E

非終結(jié)符FIRST集FOLLOW集

A{a}…{禮d}

B⑹…{e}..

N{a,e}{#,d}

Nl{b,￡}{e}..

對相同左部的產(chǎn)生式可知：

SELECT(N-ABe)nSELECT(N-E)={a}D{札d}=

SELECTfNl-bNl)ASELECT(N1-*e)=D{e}=

所以文法是LL(1)的。

預(yù)測分析表(PredictingAnalysisTable)

aebd#

A-*aN

B~dNl

N"E-bNl

N-*ABe-*￡-*￡

也可由預(yù)測分析表中無多重入口判定文法是LL(1)的。

(3)文法：

S-*Aa|b

AfSB

B*ab

第1種改寫：

用A的產(chǎn)生式右部代替S的產(chǎn)生式右部的A得：

S-*SBa|b

B-*ab

消除左遞歸后文法變?yōu)椋?/p>

O)S-bN

1)N-BaN

2)N-E

3)B-*ab

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站7

《編譯原理》課后習(xí)題答案第五章

非終結(jié)符FIRST集FOLLOW集

S...{#}

B{a}...{a}

N{5}{#}

對相同左部的產(chǎn)生式可知：

SELECT(N-*BaN)nSELECT(N^c)={a}A{#}=

所以文法是LL(1)的。

預(yù)測分析表(PredictingAnalysisTable)

ab#

S—bN

B-*ab

N—BaN-￡

也可由預(yù)測分析表中無多重入口判定文法是LL(1)的。

第2種改寫：

川S的產(chǎn)生式右部代替A的產(chǎn)生式右部的S得：

S-*Aa|b

A-*AaB|bB

B-*ab

消除左遞歸后文法變?yōu)椋?/p>

0)S-Aa

l)S-*b

2)A—bBN

3)N-*aBN

4)N-￡

5)B-*ab

非終結(jié)符:FIRST集FOLLOW集

S?.{#}

A…{a}

B{a}...{a}

N{a,￡}{a}

盛威網(wǎng)(www.snw)專業(yè)的計算機學(xué)習(xí)網(wǎng)站8

對相同左部的產(chǎn)生式可知：

SELECT(S-Aa)nSELECT(S>b)=A=K

SELECT(N-aBN)nSELECT(N-￡)={a}Cl{a}={a}W

所以文法不是LL⑴的。

《編譯原理》課后習(xí)題答案第五章

預(yù)測分析表：

ab#

S-*Aa..

fb….

A-bBN

B-*ab..

N-*aBN

-*e...

也可由預(yù)測分析表中含有多重入口判定文法不是LL⑴的。

盛威網(wǎng)()專業(yè)的計算機學(xué)習(xí)網(wǎng)站9

《編譯原理》課后習(xí)題答案第五章

附加題

問題1：

已知文法G[A]如下，試用類C或類PASCAL語言寫出其遞歸下降子程序.(主程序不需

寫)

G[A]:A-[B

B-*X]{A}

X-*(a|b){a|b}

答案：

不妨約定:在進入一個非終結(jié)符號相應(yīng)的子程序前，已讀到一個單詞.word：存放當(dāng)前讀

到的單詞，Getsym()為一子程序，每調(diào)用一次，完成讀取一單詞的工作。error。為出錯處理

程序.FIRST(A)為終結(jié)符A的FIRST集.

類C程序如下：

voidA()

{

ifword=='['

|

Getsym();

B()；

)

elseerror();

)

void