第三章 文法和语言课后习题参考答案

1. L(G)={abc}

2. L(G[N])是无符号整数。 3. G3: E→D+E | D-E | D

D→0|1|2|3|4|5|6|7|8|9 4. L(G[Z])={anbn | n>0}

5. 写一文法，使其语言是偶正整数的集合 要求：

(1) 允许0打头 (2) 不允许0打头 解：

(1) G[S]=({S,P,D,N},{0,1,2,…,9},P,S)

P:

SPD|D P->NP|N

D0|2|4|6|8

N->0|1|2|3|4|5|6|7|8|9

(2) G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)

P:

SPD|P0|D P->NR|N R->QR|Q D2|4|6|8

N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9

6. 已知文法G：

<表达式>::=<项>|<表达式>+<项>|<表达式>-<项> <项>::=<因子>|<项>*<因子>|<项>/<因子> <因子>::=(<表达式>)|i。

试给出下述表达式的推导及语法树。

(1)i; (2)(i) (3)i*i; (4)i*i+i; (5)i+(i+i); (6)i+i*i。

解：

(1) <表达式>=><项>=><因子>=>i

(2) <表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i) (3) <表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i

(4) <表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>

=><因子>*<因子>+<因子>=>i*i+i=w

(5) <表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)

=> i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i) (6) <表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>

=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i

语法树见下图:

(1) i <表达式> <项> <因子> i

(2) (i) <表达式> <项> <因子> ( <表达式> )

<项> <因子> i

(4) i*i+i <表达式>

<表达式> + <项> <项> <项> * <因子> <因子> i

i

<因子> i

(5) i+(i+i) <表达式>

<表达式> + <项> <项> <因子> i

<因子> ( <表达式> ) <表达式> + <项> <项> <因子>

<因子> i

(6) i+i*i <表达式>

<表达式> + <项> <项> <因子> i

<项> * <因子> <因子> i

i

(3) i*i <表达式> <项>

<项> * <因子> <因子> i

i

i

7. 为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。 <表达式>::=i|(<表达式>)|<表达式><运算符><表达式> <运算符>::=+|-|*|/

解：为句子i+i*i构造的两棵语法树如下： 所以，该文法是二义的。

<表达式> <表达式>

<表达式> + <表达式> <表达式> * <表达式>

i <表达式> * <表达式> <表达式> + <表达式> i

i i i i

8. 习题1中的文法G[S]是二义的吗？为什么？ 答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=>Ac=>abc和S=>aB=>abc 11. 令文法G[E]为： ET|E+T|E-T TF|T*F|T/F F(E)|i

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 解：可为E+T*F构造一棵语法树（见下图），所以它是句型。 E

E + T

T * F

从语法树中容易看出，E+T*F的短语有：

T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*F的直接短语。 E+T*F是句型E+T*F的相对于E的短语。 句型E+T*F的句柄（最左直接短语）是T*F。

12. 下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：是G[]的句型，并指出该句型的所有短语、直接短语和句柄。 | | a|b|c +|- *|/ 解：

(1)计算文法G[E]的语言：

n

由于L(T)={(a|b|c)((a|b|c)(*|/))|n>=0}

n

所以L(E)={L(T)(L(T)(+|-))|n>=0}

(2)该文法的一个句子是aab*+,它的语法树是：

+

b *

a a

(3) 证明：是G[]的句型，并指出该句型的所有短语、直接短语和

句柄。

由于下面的语法树可以生成，所以它是G[]的句型。

由于 => ,且 => ,所以是句型相对于的短语，也是相对于规则  的直接短语。

由于 => 且 => ,所以是句型相对于的短语。

显然，句型的句柄是。 13、 一个上下文无关文法生成句子abbaa的语法树如下

（1）给出该句子相应的最左、最右推导。 （2）该文法产生式的集合可能有哪些元素？ （3）找出该句子所有短语、直接短语、句柄。 解：

(1) 最左推导：S => ABS => aBS => aSBBS => aBBS => abBS => abbS => abbAa => abbaa (2) S—>ABS | Aa |ε A—>a

B—>SBB | b

(3) 首先为了区别句子abbaa中的a和b，把它写成a1b1b2a2a3

该句子的短语有：a1b1b2a2a3，b1b2，a2a3，a1，a2，b1，b2，ε 直接短语有：a1，a2，b1，b2，ε 句柄：a1

14. 给出生成下述语言的上下文无关文法：

nnmm

（1）{abab|n,m>=0}

nmmn

（2）{1010|n,m>=0}

t*t

（3）{WaW|W属于{0|a},W表示W的逆} 解：

（1）所求文法为G[S]=({S,A},{a,b},P,S),其中P为： SAA AaAb|ε

（2）所求文法为G[S]=({S,A},{0,1},P,S),其中P为： S1S0|A

A0A1|ε

*

（3）W属于{0|a}是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}

t

如果W=aa0a00,则W=00a0aa。

所求文法为G[S]=({S,P,Q},{0,a},P,S),其中P为： S0S0|aSa|a

nmnm

15. 语言{WaW}和{abcd}是上下文无关的吗？能看出它们反映程序设计语言的什么特性吗？

答：生成语言{WaW}的文法非常简单，如 G[S]: SWaW

WaW|bW|ε

可见G[S]是上下文无关的。

nmnm

生成语言{abcd}的文法非常复杂，用上下文无关文法不可能办到，只能用上下文有关

nnmm

文法。这是因为要在ac的中间插入b而同时要在其后面插入d。即a,c相关联，b,d相关联。

这说明对语言的限定越多（特别是语言中的符号前后关联越多），生成它的文法越复杂，甚至于很难找到一个上下文法无关文法。 16．给出生成下述语言的三型文法：

n

(1){a|n>=0}

nm

(2){ab|n,m>=1}

nmk

(3){abc|n,m,k>=0} 解：

(1) 生成的3型文法是：

G[S]：SaS|ε

(2) 生成的2型文法是：

G[S]: SAB AaA|a BbB|b 生成的3型文法是： G[S]： SaP PaP|bD DbD|ε (3) 生成的2型文法是：

G[S]: SABC AaA|ε BbB|ε C->cC|ε

生成的3型方法是： G[S]： AaA|bB|cC|ε BbB|cC|ε CcC|ε

17、习题6、习题7和习题7中的文法所描述的语言都是由变量i、+、-、*、/、（和）组成算术表达式，因此它们之间是等价的。

19. 刻画语言的语法有文法、正则式和自动机等方式。