编译原理 第二版 第三章课后答案.pdf

第三章作业

第三章作业答案

P47练习

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

S-Ac|aBA-abB-bc

写出L（G[S]）的全部元素。

S=Ac=abc

或S=aB=abc

所以L(G[S])={abc}

2、文法G[N]为：

N-D|ND

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

G[N]的语言是什么？

【解】

N=ND=NDD=NDDDD...D=DD

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}

或：

解:NNDn-1

Dn

+

{0,1,3,4,5,6,7,8,9}

+

∴L(G[N])={0,1,3,4,5,6,7,8,9}

5.写一文法，使其语言是偶正数的集合。

要求：

(1)允许0打头

(2)不允许0打头

【解】

(1)允许0开头的偶正整数集合的文法

E-NT|G|SFM

T-NT|G

N-D|1|3|5|7|9

D-0|G

G-2|4|6|8

S-NS|ε

F-1|3|5|7|9|G

M-M0|0

(2)不允许0开头的偶正整数集合的文法

E-NT|D

T-FT|G

N-D|1|3|5|7|9

D-2|4|6|8

F-N|0

G-D|0

9.考虑下面上下文无关文法：

S→SS*|SS+|a

(1)表明通过此文法如何生成串aa+a*，并为该串构造推导树。

(2)该文法生成的语言是什么？

【解】

(1)S=SS*

=SS+S*

aa+a*

该串的推导树如下：

(2)该文法生成的语言是只含+、*的算术表达式的逆波兰表示。

11.令文法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*F是文法G[E]的一个句型

句型E+T*F的语法树如下：

∴此句型相对于E的短语有:E+T*F；相对于T的短语有T*F,

直接短语为：T*F；。

句柄为：T*F

16、给出生成下列语言的三型文法。

n

(1){a|n=0}

nm

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

nmk

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

[答案]

n

(1){a|n=0}的三型文法为：

S-aS|ε

nm

(2){ab|n,m=1}的三型文法为：

S-aA

A-aA|bB

B-bB|ε

nmk

(3){abc|n,m,k=0}的三型文法为:

A-aA|bB|cC|ε

B-bB|cC|ε

C-cC|ε

【其他习题解答】

7.为句子i+i*i构造两棵语法树，从而证明下述文法G[表达式]是二义的。

〈表达式〉-〈表达式〉〈运算符〉〈表达式〉|(〈表达式〉)|i

〈运算符〉-+|-|*|/

【答案】

可为句子i+i*i构造两个不同的最右推导:

最右推导1

〈表达式〉=〈表达式〉〈运算符〉〈表达式〉

=〈表达式〉〈运算符〉i