编译原理习题答案 编译程序设计原理 第二版

第四章 文法与语法分析

1． 形如 A-->Aa 的产生式称为左递归的，类似地称 B-->βB 的产生式为右递归的。

又有右递归式，则文法一定有二义性。

(答案)

设文法的非终极符 A，有产生式

A→Aα|α

β α

因此非终极符既有左递归式，又有右递归式，则一定有二义性。

(关闭)

2． 形如 A-->B 的产生式称为单位产生式，其中 B 是其终级符。

生式的等价文法。

(答案)

(关闭)

3． A-->λ 产生式为空产生式，证明任何含空产生式的文法均可转换成无空产生式的等价文法（

(答案)

(1). 构造集合 β,令 β= {A|A→ε 是 G1 的产生式}

(2). 递归构造 β

β=β {D|D∪ ->x 是 G1 中的产生式，且 x 是集合 β 上的符号串}

Created with novaPDF Printer (www.novaPDF.com). Please register to remove this message.

如果 Ci 是集合 β 中的元素，则因为删去了所有的空产生式，因此

应该扩充一产生式：A->C1...Ci-1Ci+1...Cp。

重复这个过程直至不出现新的产生式为止。

(关闭)

4． 试给出一个算法，它判定文法中有无非终极符，它不出现于任何句型中，称这种非终极符为不可到达符号

否则 oldV 中即为所有可到达的非终极符，即若非终极符集!=oldV,则有不可到达的非终极符；

(关闭)

5． 写出正则文法 DFA，DFA 到正则文法的转换文法。

(答案)

将正则文法中的非终极符作为 NFA的状态, 将正则文法中的初始非终极符作为 NFA的初始状态, 对于形如

DFA 的状态集合 SS.作为正则文法的非终极符集; DFA 的初始状态 S0 作为正则文法的初始符集 S; DFA

正则文法的终极符集 VT,正则文法的产生式集 P,如下构造:若 DFA 中有

Created with novaPDF Printer (www.novaPDF.com). Please register to remove this message.

,则 P 中加入产生式 A→a;这样即构造出正则文法.

(关闭)

B-->λ

B-->λ

b.

S-->Ab

A-->a

A-->B

A-->λ

B-->b

B-->λ

d.

S-->aSe

S-->B

B-->bBe

B-->C

C-->cCc

D-->d

(答案)

Created with novaPDF Printer (www.novaPDF.com). Please register to remove this message.

所以不是 LL(1)文法

predict(B->b)={b},predict(B->λ)={a,b,#} (**)

由(*)和(**)两行知，不是 LL(1)文法.

(d) 1)没有非终极符可导出空

2)first(C)={c,d},first(B)={b,c,c},first(S)={a,b,c,d}

follow(S)={e,#},follow(B)={e,#},follow(C)={c,e,#}

predict(S->aSe)={a},predict(S->B)={b,c,d}

predict(B->bBe)={b},predict(B->C)={c,d}

predict(C->cCc)={c},predict(C->d)={d}

Created with novaPDF Printer (www.novaPDF.com). Please register to remove this message.

E -->(E)

E -->Var Etail

Etail -->-E

Etail -->λ

Var -->id Vtail

Vtail -->(E)

Vtail -->λ

(答案)

First(E)={-, (, id} Follow(E)={＃,)}

First(Etail)={-, λ} Follow(Etail)={＃,)}

First(Var)={ id } Follow(Var)={-,＃,)}

Created with novaPDF Printer (www.novaPDF.com). Please register to remove this message.