(完整版)编译原理及实现课后习题答案.pdf

编译原理及实现课后习题解答

2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以

+和A*

及A.

x=(aaa)=ε|x|=0

000

xx=aaaaaa|xx|=6

x=aaaaaaaaaaaaaaa|x|=15

55

A=A

+1∪A2∪….∪An∪…={a,aa,aaa,aaaa,aaaaa…}

A*=A0∪A1∪A2∪….∪An∪…={ε,a,aa,aaa,aaaa,aaaaa…}

2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的

长度：xy，xyz，（xy）3

xy=abcb|xy|=4

xyz=abcbaab|xyz|=7

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

333

2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语

法树。

S=SS*=Sa*=SS+a*=Sa+a*=aa+a*

So

s

SS*r

o

f

d

SS+ao

o

aag

e

2.4已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写

r

a

出全部由此文法描述的只含有四个符号的句子。

Z=U0=Z10=U010=1010g

n

i

e

Z