编译原理 龙书答案

（Aho）4.30 一个文法称为Greibach范式（GNF）文法，如果它无 产生式，且每个产生式（S→ 除外）均形如A→a ，其中，a是终结符， 是非终结符串，也可能为空。 a） 试编写一个算法，将给定文法转换为Greibach范式 解：算法步骤如下

1． 先将文法消除左递归、消除 产生式、删除无用符号，然后对每个非终结符A的每个产

生式，执行2

2． 若产生式右部以终结符开始，则略过，考虑其他产生式，否则产生式必为A→A1 的形

式，A1为≠A的NT，a为语法符号串，对它执行以下操作

i. 将A1的所有产生式的右部替换A1，产生新的关于A的产生式 ii. 对于这些产生式，若右部以T开始，略过，不予处理，考虑那些以NT开始的

产生式，反复执行i、ii

iii. 由于文法的NT个数是有限的（设为k），且已消除左递归，则最多k个步骤

后，处理完毕，此时，A的产生式右部应该均以T开始。否则，若某个产生式右部以NT开始，表明A无论经过怎样的推导过程，均不可能得到一个以终结符开始的串，当然也就不可能得到一个终结符串，这显然是一个错误的文法，矛盾。这样，A的某个产生式处理完毕，其右部均以T开始。转向2，继续考虑其他产生式，所有产生式处理完毕，则转向3

3． 此时，每个产生式均为A→a 的形成，a为NT， 为语法符号串，若 中包含T，则进

行如下处理

i. 假定 中包含k个T，则产生式形为A→a a1 …ak k，其中ai为T， i为NT

串或 ii. 引入k个新的NT A1、A2、…Ak，和k个新的产生式

A1→a1 1A2 A2→a2 2A3 …

Ak-1→ak-1 k-1Ak

编译原理 龙书答案

Ak→ak k

而将原产生式改为A→a

4． 经过2、3处理，所有产生式必然满足Greibach范式的格式 b） 将你的算法应用到表达式文法4-10上

解：文法4－10消除左递归、消除 产生式后得到 E→T E' | T E'→+ T E' | + T T→F T' | F T'→* F T' | * F F→( E ) | id

将每个产生式转换为以T开始的形式，得到

E→( E ) T' E' | id T' E' | ( E ) E' | id E' | ( E ) T' | id T' | ( E ) | id E'→+ T E' | + T

T→( E ) T' | id T' | ( E ) | id T'→* F T' | * F F→( E ) | id

将每个产生式右部转换为T NT*的形式，最后结果为： E→( E E''| id T' E' | ( E E''' | id E' | ( E | id T' | ( E E''''' | id E''→) T' E' E'''→) E' E''''→) T' E'''''→)

E'→+ T E' | + T

T→( E E'''' | id T' | ( E E''''' | id T'→* F T' | * F F→( E E''''' | id

（Aho）4.33 考虑文法 S→AS | b A→SA | a

a) 构造此文法的LR(0)项目集规范族 解：

I0 = { S’→ S, S→ AS, S→ b, A→ SA, A→ a }

goto(I0, S) = { S’→S , A→S A, A→ SA, A→ a, S→ AS, S→ b } = I1 goto(I0, A) = { S→A S, S→ AS, S→ b, A→ SA, A→ a } = I2 goto(I0, a) = { A→a } = I3 goto(I0, b) = { S→b } = I4

goto(I1, S) = { A→S A, A→ SA, A→ a, S→ AS, S→ b } = I5

goto(I1, A) = { A→SA , S→A S, S→ AS, S→ b, A→ SA, A→ a } = I6 goto(I1, a) = I3, goto(I1, b) = I4

goto(I2, S) = { S→AS , A→S A, A→ SA, A→ a, S→ AS, S→ b } = I7 goto(I2, A) = I2, goto(I2, a) = I3, goto(I2, b) = I4 goto(I5, S) = I5, goto(I5, A) = I6, goto(I5, a) = I3, goto(I5, b) = I4