陈火旺编译原理(第三版)课后习题答案

第二章

P36-6

⑴

L(G)是o~9组成的数字串

⑵

最左推导：

N= ND= NDD= NDDD= DDDD= ODDD= 01DD= 012D= 0127

N= ND= DD= 3D= 34

N= ND= NDD= DDD= 5DD = 56D= 568

最右推导:

N= ND= N7= ND7= N27= ND 27= N127= D127= 0127

N= ND= N 4= D4= 34

N= ND= N8= ND8= N 68= D68= 568

P36-7

G(S)

O > 1|3|5|7|9 N > 2∣4∣6∣8∣O D > 0|N S > OlAo

A—； AD |N

P36-8

文法：

E τ T E +T|E —T TT F T* F|T/ F F > (E)|i

最左推导:

E= E T= T T= F T= i T= i T* F= i F*F = i i*F= i i*i

E=T=T* F 二 F * F 二 i * F = i*( E)= i *( E T)二 i *( T T)二 i *( F T) =i*( i τ)= i*( i F)= i*( i i)

最右推导:

E= E T- E T*F= E T*i= E F*i= E i*i= T i*i= F i*i= i i*i E=T= F*T = F * F=

F*( E)= F *( E T)= F *( E F)= F *( E i) =F*( T i)= F*( F i)= F*( i i)= i*(i i)

^语法树. /********************************

E

T F i

i

i+i+i

*************P36-9****

/

句子iiiei 有两个语法树：

S= iSeS= iSei = iiSei = iiiei S= iS= iiSeS= iiSei = iiiei

P36-10

/**************

S > TS |T T > (S)∣()

***************/

P36-11

/*************** L1:

S > AC

A— aAb |ab C — CC | ；

L2:

S > AB

A—： aA| ；

B — bBc|bc

E

F F

i

i-i-i

E

T F i

i

i+i*i

L3:

S > AB

Ar aAb | L4B > aBb| :

S > A| B A》

；

；

0A1∣ ；

************ B > 1B0| A*** /

第三章习题参考答案

P64 — 7

1(01)*101

0

确定化: 0 {X} 1 {1,2,3} {1,2,3} {2,3} {2,3,4} {2,3,5} {2,3,4,Y}

φ φ {2,3} {2,3} {2,3,5} {2,3} {2,3,5} φ {2,3,4} {2,3,4} {2,3,4} {2,3,4,Y} {2,3,4,} φ最小化:

2 3

0

4