编译原理作业题 （孙悦红版）

--------------------------------------编译原理复习资料----------------------------------------06 软件工程四班------------------------------------

第二章

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

0

,xx,x

5

以及 A

+

和

A*

.

x

xx=aaaaaa |xx|=6

2.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

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

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

2.4 已知文法 G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文法描述的只

--------------------------------------编译原理复习资料----------------------------------------06 软件工程四班------------------------------------

2.5 已知文法 G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。

2.7 对 2.6 题的文法，写出句型 T+T*F+i 的短语、简单短语以及句柄。

短语：T+T*F+i T+T*F

i i

T T*F

简单短语：i T*F

iFT *T

--------------------------------------编译原理复习资料----------------------------------------06 软件工程四班------------------------------------

根据所给文法推导出句子 a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。

2.9 写一文法，使其语言是奇正整数集合。

2.10 给出语言{a

n

m

|n,m≥1}的文法。

--------------------------------------编译原理复习资料----------------------------------------06 软件工程四班------------------------------------

n

t

A::=Aa|a A::=aA|b

1(1|0)*|0

1(1010*|1(010)*1)*0

S U

a

a

a

b

b

b

图3-35状态图