《編譯原理》課后習題答案第三章

第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開頭的非負整數？

第3題

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

答案：

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])的全部元素。

盛威網(www.snw)專業的計算機學習網站1

《編譯原理》課后習題答案第三章

答案：

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

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

第5題

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

⑴允許0打頭；

⑵不允許0打頭。

答案：

⑴允許0開頭的偶正整數集合的文法

E-NT|D

T-NT|D

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

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

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

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

試給出下述表達式的推導及語法樹。

（5）i+（i+i）

（6）i+i*i

盛威網（）專業的計算機學習網站2

《編譯原理》課后習題答案第三章

答案；

〈表達式〉

〈表達式＞+＜項＞

〈因子＞

〈表達式〉

〈表達式〉+＜項＞

〈因子〉

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

盛威網（）專業的計算機學習網站3

《編譯原理》課后習題答案第三章

第7題

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

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

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

答案：

可為句子a+a*a構造兩個不同的最右推導：

最有推導1〈表達式〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉（運算符〉a

〈表達式〉*a

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

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

〈表達式〉+a*a

最右推導2〈表達式〉〈表達式〉〈運算符〉〈表達式）

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

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

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

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

〈表達式〉+a*a

a+a*a

盛威網（）專業的計算機學習網站4

《編譯原理》課后習題答案第三章

第8題

文法G⑸為：

答案：

此句型對應語法樹如右，牧為此文法一個句型。

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

以E+T*F句型

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

有T*F

直接短語為：T*F

句柄為：T*F

第13題

一個上下文無關文法生成句子abbaa的推導樹如下：

⑴給出串abbaa最左推導、最右推導。

⑵該文法的產生式集合P可能有哪些元素？

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

B

a

S

ABS

a

SBA

ebba

盛威網()專業的計算機學習網站6

《編譯原理》課后習題答案第三章

答案：

⑴串abbaa最左推導:

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

最右推導：

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

⑵產生式有：S-*ABS|Aa|￡A-aB-SBB|b

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

⑶該句子的短語有：

a是相對A的短語

￡是相對S的短語

b是相對B的短語

￡bb是相對B的短語

aa是相對S的短語

aebbaa是相對S的短語

直接短語有：a￡b

句柄是：a

第14題

給出生成下述語言的上下文無關文法：

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

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

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

答案：

(1)

S—AA

A-*aAb|￡

(2)

S-*1SO|A

A-*OA1|￡

(3)

S-*OSO|1S1|E

盛威網(www.snw)專業的計算機學習網站7

《編譯原理》課后習題答案第三章

第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題

習題7和習胭11中的文法等價嗎？

答案：

等價。

第18題

解釋下列術語和概念：

(1)字母表

(2)串、字和句子

(3)語言、語法和語義

答案：

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

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

字：字母表中的元素。

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

盛威網(www.snw)專業的計算機學習網站8

《編譯原理》課后習題答案第三章

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

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

則構成的一切基本符號串組成的集合。

語法：表示構成語言句子的各個記號之間的組合規律。程序的結構或形式。

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

盛威網(www.snw)專業的計算機學習網站9

《編譯原理》課后習題答案第三章

附加題

問題1：

給出下述文法所對應的正規式：

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的個數相同.

問題3：

給出語言描述，構造文法.

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

答案一：

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)專業的計算機學習網站10

《編譯原理》課后習題答案第三章

A-*aA|a

B-￡|bB

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

答案：

正規式是daa*b*；

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

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

試給出下述表達式的推導及語法樹

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

盛威網()專業的計算機學習網站11

《編譯原理》課后習題答案第三章

問題6：

已知文法G[E]:

EfET+|T

T—TF*|F

F-*FA|a

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

答案：

該句型對應的語法樹如下：

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

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

相對于F的短語有FA;FAA

簡單短語有F;FA

句柄為F.

問題7：

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

S-SaSSbSScSd

答案：

該文法的形式很典型，可以先采用優先級聯規則變換文法，然后再規定結合性對文法做

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

設a、b和c的優先級別依次增高，根據優先級聯規則將文法變換為：

S-*SaSA

A-*AbAC

C-*CcCd

規定結合性為左結合，進一步將文法變換為：

SfSaAA

AfAbCC

C一CcFF

F-d

該文法為非二義的。

盛威網()專業的計算機學習網站12

《編譯原理》課后習題答案第三章

問題8：

構造產生如下語言的上下文無關文法：

(1){anb2ncm|n,m2。}

(2){anbmc2m|n,m20}

(3){ambnm2n}

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

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

答案：

（1）根據上下文無關文法的特點，要產生形如anb2ncm的串，可以分別產生形如anb2n和

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

特別指明，通常可以忽略這一點。

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

S-*AB

A-*EaAbb

Bf￡cB

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

語

言，存在一個由以下產生式定義的上下文無關文法G⑸：

S—AB

A-*EaA

B-*￡bBcc

（3）考慮在先產生同樣數目的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。前一種情形通過

對應A,后一種情形對應D。

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

S-Ab

A—BABa

盛威網（）專業的計算機學習網站13

《編譯原理》課后習題答案第三章

Bfab

問題9：

下面的文法G⑸描述由命題變量p、q,聯結詞八（合取）、V（析取）、-（否定）構

成的命題公式集合：

S-SVTT

T-*TAFF

F——Fpq

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

答案：

直接短語:p，q，-F

句柄：rF

問題10：

設字母表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,請寫出全部由此文

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

盛威網(www.snw)專業的計算機學習網站14

《編譯原理》課后習題答案第三章

答案：

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,寫出該文法的開

始符號、終結符號集合VT、非終結符號集合VN。

答案：

開始符號：E

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

VN={E,F,T}

問題15：

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

答案：

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

盛威網(www.snw)專業的計算機學習網站15

《編譯原理》課后習題答案第三章

S

s*s

S+Sa

aa

S

S+S

aS*S

aa

問題16：

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

答案：

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

盛威網()專業的計算機學習網站16

《編譯原理》課后習題答案第四章

第4章詞法分析

第1題

構造下列正規式相應的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)先構造NFA：

用子集法將NFA確定化

,01

X.A

AAAB

ABACAB

ACAABY

ABYACAB

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

的終態)，所以D為終態。

.01

X.A

AAB

BCB

CAD

DCB

DFA的狀態圖：：

盛威網()專業的計算機學習網站1

《編譯原理》課后習題答案第四章

⑵先構造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

盛威網(www.snw)專業的計算機學習網站2

《編譯原理》課后習題答案第四章

將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,

所以它們都為終態。

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

盛威網()專業的計算機學習網站3

《編譯原理》課后習題答案第四章

⑶先構造NFA：

先構造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,

所以它們都為終態。

ab

01

123

245

323

445

545

Oalb3

2

a

5

a4

b

a

b

a

b

a

b

盛威網(www.snw)專業的計算機學習網站4

《編譯原理》課后習題答案第四章

(4)先構造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,

所以它為終態。

ab

01

123

24

35

423

523

DFA的狀態圖：

盛威網(www.snw)專業的計算機學習網站5

《編譯原理》課后習題答案第四章

Oblb

2

a

4

5

3

b

b

a

b

a

b

盛威網(www.snw)專業的計算機學習網站6

《編譯原理》課后習題答案第四章

第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},構造相應的DFA。

答案：

先構造其矩陣

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,所以它為終態。

01

ABA

BCD

CCE

DE

EFA

FFE

DFA的狀態圖：

盛威網()專業的計算機學習網站7

A

01

0

F

E

D

0

B

1

0

1

0

1

0

1

C

《編譯原理》課后習題答案第四章

第3題

將下圖確定化：

答案：

用子集法將NFA確定化：

.01

SVQQU

VQVZQU

QUVQUZ

VZZZ

VZ.

QUZVZQUZ

ZZZ

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

.01

SAB

ACB

BDE

CFF

DF.

ECE

FFF

DFA的狀態圖：

盛威網()專業的計算機學習網站8

《編譯原理》課后習題答案第四章

第4題

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

答案：

初始分劃得

110：終態組{0},非終態組{1,2,3,4,5}

對非終態組進行審查：

(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},故狀態2和狀態3不等價，得到新分劃

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

這是最后分劃了

盛威網()專業的計算機學習網站9

《編譯原理》課后習題答案第四章

最小DFA：

第5題

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

右邊。并給出該語言的正規式。

答案：

按題意相應的正規表達式是(0*10)*0*，或0*(0|10)*0*構造相應的DFA,首先構造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}

重新命名狀態集：

SOI

1

2

3

4

2

2

4

4

3

3

3

DFA的狀態圖：

盛威網()專業的計算機學習網站10

《編譯原理》課后習題答案第四章

可將該DFA最小化：

終態組為{1,2,4},非終態組為{3},{1,2,4}0{1,2,4},{1,2,4}1{3},所以1,2,4為等價狀

態，可合并。

第6題

設無符號數的正規式為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={+,-)

答案：

先構造NFA：

X

d

.B

d

FG

d

H

10

d

A

c

10

d

D

s

e

Ed

Y

d

d

用子集法將NFA確定化：

盛威網()專業的計算機學習網站11

《編譯原理》課后習題答案第四章

￡?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表示。終態有0、3、4、6、9。

?slOd

0123

14

256

3123

474

56

66

789

89

99

DFA的狀態圖：

盛威網()專業的計算機學習網站12

《編譯原理》課后習題答案第四章

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

構造相應的最小的DFAo

答案：

先構造其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確定化：

盛威網()專業的計算機學習網站13

《編譯原理》課后習題答案第四章

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,所以它們為終態。

ab

012

113

224

325

416

516

625

DFA的狀態圖:

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。

最小化為：

盛威網(www.snw)專業的計算機學習網站14

《編譯原理》課后習題答案第四章

A

a,b

DC

a

a

B

b

a

b

b

第8題

給出下述文法所對應的正規式：

S-OA|1B

A-*1S|1

B-OS|O

答案：

解方程組s的解：

S=OA|1B

A=1S|1

B=OS|O

將A、B產生式的右部代入S中

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

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

第9題

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

1

a

2

6

c

3

C

b

5

47

b

b

ab

b

b

d

d

a

盛威網(www.snw)專業的計算機學習網站15

《編譯原理》課后習題答案第四章

答案：

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

盛威網()專業的計算機學習網站16

《編譯原理》課后習題答案第四章

附加題

問題1：

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

a)以ab結尾的所有串

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

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

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

e)包含ab子串的所有串

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

答案：

注意正規式不唯一

a)(a|b)*ab

b)(bb)*

c)(a*ba*ba*)*

d)b*ab*

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

f)b*a*

問題2：

請描述下面正規式定義的串.字母表｛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結尾的串

問題3

構造有窮自動機.

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

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

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

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

價的DFA.以及最小狀態DFA

盛威網()專業的計算機學習網站17

《編譯原理》課后習題答案第四章

答案：

b)

c)

盛威網()專業的計算機學習網站18

《編譯原理》課后習題答案第四章

最小化的DFA

問題4：

設有如圖所示狀態轉換圖，求其對應的正規表達式。

可通過消結法得出正規式

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

也可通過轉換為正則文法，解方程得到正規式。

問題5：

己知正規式：

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

(2)(a|b)*b.

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

分析：

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

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

答案：

盛威網()1?業的計算機學習網站19

《編譯原理》課后習題答案第四章

狀態轉換表1

ab

X1241234124Y

12341234124Y

124Y1234124Y

狀態轉換表2

aB

123

223

323

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

ab

123

23

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

ab

X121212Y

121212Y

12Y1212Y

盛威網()專業的計算機學習網站20

《編譯原理》課后習題答案第四章

可化簡得下表

ab

123

223

得DFA圖

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

對相應正規文法，令A對應1,B對應2

故為：

A-*aA|bB|b

B-*aA|bB|b

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

問題6：

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

答案：

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

所以，一個可能的正規文法為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

(適當等價變換也可以，但要作說明，即要有步驟)

盛威網()專業的計算機學習網站21

《編譯原理》課后習題答案第四章

問題7：

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

答案：

G[P]：

P-OP1P1Q

Q-*0R1R

R-￡

問題8：

考慮如下文法G⑸：

S-OSIS1A

A—OB1B

B一￡

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

b)試構造語言為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);

所以，一個可能的正規表達式為：

盛威網(www.snwei.com)專業的計算機學習網站22

《編譯原理》課后習題答案第四章

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

b)

盛威網(www.snwei.com)專業的計算機學習網站23

《編譯原理》課后習題答案第五章

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

第1題

對文法G[S]

S-*a|A|(T)

T-*T,S|S

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

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

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

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

答案；

⑴對(a,(a,a)的最左推導為：

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)的最左推導為:

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)

盛威網(www.snw)專業的計算機學習網站1

《編譯原理》課后習題答案第五章

(((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

非終結符FIRST集FOLLOW集

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

T{a,A,(}OU

N{〃DM)}....

對左部為N的產生式可知：

FIRST(f,SN)={,}

FIRST(…)={c}

FOLLOW(N)={)}

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

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

aA(),#

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

T—SN—SN—SN

N一￡一，SN

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

盛威網(www.snw)專業的計算機學習網站2

《編譯原理》課后習題答案第五章

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

棧(STACK)

當前輸入符

(CUR_CHAR)

剩余輸入符

(INOUT_STRING)

所用產生式

(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)#是文法的句子。

盛威網()專業的計算機學習網站3

《編譯原理》課后習題答案第五章

第3題

已知文法G[S]：

S-*MH|a

H-*LSo|￡

K-dML|e

L-*eHf

M-K|bLM

判斷G是否是LL⑴文法，如果是，構造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

非終結符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}……

對相同左部的產生式可知：

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

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

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

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

所以文法是LL(1)的。

盛威網(www.snw)專業的計算機學習網站4

《編譯原理》課后習題答案第五章

預測分析表：

aodefb#

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

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

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

L-*eHf

K-e-dML-￡一￡

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

盛威網(www.snw)專業的計算機學習網站5

《編譯原理》課后習題答案第五章

第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{b,a}{札b}

N{b,a}{札b}

預測分析表：

ab#

A-*baB-*￡

B-*a-bN

N-*aBbb-*b

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

(2)文法：

A-*aABe|a

B-*Bb|d

提取左公共因子和消除左遞歸后文法變為：

0)A-*aN

l)N-*ABe

盛威網()專業的計算機學習網站6

《編譯原理》課后習題答案第五章

2)N-￡

3)B-*dNl

4)N1-bNl

5)N1-*E

非終結符FIRST集FOLLOW集

A{a}…{禮d}

B⑹…{e}..

N{a,e}{#,d}

Nl{b,￡}{e}..

對相同左部的產生式可知：

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

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

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

aebd#

A-*aN

B~dNl

N"E-bNl

N-*ABe-*￡-*￡

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

(3)文法：

S-*Aa|b

AfSB

B*ab

第1種改寫：

用A的產生式右部代替S的產生式右部的A得：

S-*SBa|b

B-*ab

消除左遞歸后文法變為：

O)S-bN

1)N-BaN

2)N-E

3)B-*ab

盛威網()專業的計算機學習網站7

《編譯原理》課后習題答案第五章

非終結符FIRST集FOLLOW集

S{b}...{#}

B{a}...{a}

N{5}{#}

對相同左部的產生式可知：

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

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

ab#

S—bN

B-*ab

N—BaN-￡

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

第2種改寫：

川S的產生式右部代替A的產生式右部的S得：

S-*Aa|b

A-*AaB|bB

B-*ab

消除左遞歸后文法變為：

0)S-Aa

l)S-*b

2)A—bBN

3)N-*aBN

4)N-￡

5)B-*ab

非終結符:FIRST集FOLLOW集

S{b}?.{#}

A{b}…{a}

B{a}...{a}

N{a,￡}{a}

盛威網(www.snw)專業的計算機學習網站8

對相同左部的產生式可知：

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

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

所以文法不是LL⑴的。

《編譯原理》課后習題答案第五章

預測分析表：

ab#

S-*Aa..

fb….

A-bBN

B-*ab..

N-*aBN

-*e...

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

盛威網()專業的計算機學習網站9

《編譯原理》課后習題答案第五章

附加題

問題1：

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

寫)

G[A]:A-[B

B-*X]{A}

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

答案：

不妨約定:在進入一個非終結符號相應的子程序前，已讀到一個單詞.word：存放當前讀

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

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

類C程序如下：

voidA()

{

ifword=='['

|

Getsym();

B()；

)

elseerror();

)

void