编译原理（第3版）第二章部分习题答案

您所在的位置：网站首页 › 编译原理第3版陈火旺答案 › 编译原理（第3版）第二章部分习题答案

编译原理（第3版）第二章部分习题答案

2024-03-25 12:03| 来源: 网络整理| 查看: 265

1. 文法G=({A,B,C},{a,b,c},P,S)，其中P为

S->Ac|aB

A->ab

B-bc

写出L(G[S])的全部元素。

解：L(G[S])的全部元素为{a,b,c}。

2. 文法G[N]为

N->D|ND

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

G[N]的语言是什么？

解：G[N]的语言是以数字表示的数字串。

3.为只包含数字、加号和减号的表达式，例如9-2+5、3-1、7等构造一个文法。

解：A->ATA

A->D|BD

B->BD|C

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

T->+|-

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

5.已知文法G[Z]:

Z: := a Z b

Z: :=a b

写出L(G[Z])的全部元素。

解：L(G[Z])的全部元素为{ $a^{n}b^{n}$ | n $\geq$ 1}

6.已知文法G：

: := | +

: := | *

: := () | i

试给出下列表达式的推导和语法树。

（4）i * i + i

（5）i + ( i+ i )

解：（4）i * i + i

最左推导： => + => +

=> * + => * +

=> i * + => i * i +

=> i * i + => i * i + i

最右推导： => + => + => + i

=> + i = > * + i => * i + i => * i + i => i * i + i

语法树：

（5）i + ( i+ i )

最左推导： => + => + => + => i +

=> i + => i + () => i + ( + ) => i + ( + )

=> i + ( + ) => i + (i + ) => i + (i + ) => i + (i + i)

最右推导： => + => + => + ()

=> + ( + ) => + （ + ）

=> + ( + i) => + ( + i) => + ( + i)

=> + (i + i) => + (i + i) => + (i + i) => i + (i + i)

语法树：

8.考虑下面的上下无关文法：

S->SS * | SS+ | a

（1）表明通过此文法如何生成串aa+a*,并为该串构造语法树。

（2）该文法生成的语言是什么？

解：（1）最左推导：S => SS* => SS+S* => aS+S* =>aa+S* =>aa+a*。

语法树：

（2）该文法生成的语言是由+、*、a构成的表达式。

9.已知文法S->S(S)S| $\varepsilon$ 。

（1）该文法生成的语言是什么？

（2）该文法是二义的吗？说明理由。

解：（1）该文法生成的语言是嵌套的小括号。

（2）该文法是二义的，该文法有两棵不同的语法树。

10.令文法G[E]为

E->T|E+T|E-T

T->F|T*F|T/F

F->(E)|i

证明E+T*F是它的一个右句型，指出这个句型的所有短语、直接短语和句柄。

解：最右推导：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

直接短语：T*F

句柄：T*F

11.一个上下无关文法生成句子abbaa的唯一语法树如下：

（1）给出该句子相应的最左推导和最右推导。

（2）该文法的产生式集合P可能有哪些元素？

（3）找出句子的所有短语、简单短语、句柄。

解：（1）最左推导：S => ABS => aBS => aSBBS => a $\varepsilon$ BBS => abBS => abbS => abbAa => abbaa

最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => A $\varepsilon$ bbaa => abbaa

（2）产生式集合P的元素有：S->ABS|Aa| $\varepsilon$ ，B->SBB|b，A->a。

（3）短语：a， $\varepsilon$ ，b，bb，aa，abbaa...

直接短语：a， $\varepsilon$ ，b

句柄：a

12.构造产生如下语言的上下文无关文法各一个：

（1）{ $a^{n}b^{n}$ | n $\geq$ 0}

（2）{ $a^{m}b^{n}$ | m $\geq$ n $\geq$ 0}

（3）{ua $\omega$ b | u, $\omega$ $\in$ {a,b}* $\wedge$ |u| = | $\omega$ |}

（4）{ $a^{n}b^{m}$ | n $\geq$ 2m $\geq$ 0}

解：（1）A->aAb| $\varepsilon$

（2）S-AB

A->aA| $\varepsilon$

B->aBb| $\varepsilon$

（3）S->Ab

A->aAb|aAa|bAa|bAb|a

（4）S->aaSb|A

A->aA| $\varepsilon$

13.构造产生如下语言的上下文无关文法各一个：

（1）{ $a^{n}b^{m}c^{2m}$ | n,m $\geq$ 0}

（2）{ $\omega c\omega ^{R}$ | $\omega \in$ {a,b} *}

解：（1）S->AB

A->aSbb| $\varepsilon$

B-CB| $\varepsilon$

C->c| $\varepsilon$

（2）S->aSa|bSb|c

15.分以下两种情形，各写一个文法，使其语言是十进制非负偶数的集合：

（1）允许0打头。

（2）不允许0打头。

解：（1）S->D|NT

T->NT|D

D->0|2|4|6|8

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

（2）S->D|NT

T->0|D|FT

F->0|N

D->0|2|4|6|8

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

18.给出生下述语言的一个3型文法：

（1）{ $a^{n}$ | n $\geq$ 0}

（2）{ $a^{n}b^{m}$ | n,m $\geq$ 0}

（3）{ $a^{n}b^{m}c^{k}$ | n,m,k $\geq$ 0}

解：（1）S->aS| $\varepsilon$

（2）S->aS|aB

B->Bb|b

（3）A->aA|bB|cC| $\varepsilon$

B->bB|cC| $\varepsilon$

C->cC| $\varepsilon$

【本文地址】

编译原理（第3版）第二章部分习题答案

编译原理（第3版）第二章部分习题答案

今日新闻

推荐新闻