蒋立源编译原理第三版第二章习题与答案(修改后).pdf

蒋立源编译原理第三版第二章习题与答案(修改后)--第1页

可编辑修改

第2章习题

2-1设有字母表A={a,b,c,…,z}，A={0,1,…,9}，试回答下列问题：

12

(1)字母表A上长度为2的符号串有多少个？

1

(2)集合AA含有多少个元素？

12

*

(3)列出集合A(A∪A)中的全部长度不大于3的符号串。

112

2-2试分别构造产生下列语言的文法：

nbn|n≥0}；

（1）{a

nbmcp|n,m,p≥0}；

（2）{a

nnnn

（3）{a#b|n≥0}∪{c#d|n≥0}；

r*r

（4）{w#w#|w∈{0,1},w是w的逆序排列}；

（5）任何不是以0打头的所有奇整数所组成的集合；

（6）所有由偶数个0和偶数个1所组成的符号串的集合。

2-3试描述由下列文法所产生的语言的特点：

（1）S→10S0S→aAA→bAA→a

（2）S→SSS→1A0A→1A0A→ε

（3）S→1AS→B0A→1AA→C

B→B0B→CC→1C0C→ε

（4）S→aSSS→a

2-4试证明文法

S→AB|DCA→aA|aB→bBc|bcC→cC|cD→aDb|ab

为二义性文法。

2-5对于下列的文法

S→AB|cA→bA|aB→aSb|c

试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全

部短语。

精选doc

蒋立源编译原理第三版第二章习题与答案(修改后)--第1页

蒋立源编译原理第三版第二章习题与答案(修改后)--第2页

可编辑修改

2-6化简下列各个文法

(1)S→aABS|bCACdA→bAB|cSA|cCCB→bAB|cSBC→cS|c

(2)S→aAB|EA→dDA|eB→bE|f

C→cAB|dSD|aD→eAE→fA|g

(3)S→ac|bAA→cBCB→SAC→bC|d