编译原理 龙书答案

编译原理 龙书答案

第四章部分习题解答

Aho：《编译原理技术与工具》书中习题 （Aho）4.1 考虑文法 S → ( L ) | a L → L, S | S

a) 列出终结符、非终结符和开始符号 解：

终结符：(、)、a、， 非终结符：S、L 开始符号：S

b) 给出下列句子的语法树

i) (a, a) ii) (a, (a, a)) iii)

(a, ((a, a), (a, a)))

c) 构造b)中句子的最左推导

i) ii) iii)

S (L) (L, S) (S, S) (a, S) (a, a)

S (L) (L, S) (S, S) (a, S) (a, (L)) (a, (L, S)) (a, (S, S)) (a, (a, S) (a, (a, a))

S (L) (L, S) (S, S) (a, S) (a, (L)) (a, (L, S)) (a, (S, S)) (a, ((L), S)) (a, ((L, S), S)) (a, ((S, S), S)) (a, ((a, S), S)) (a, ((a, a), S)) (a, ((a, a), (L))) (a, ((a, a), (L, S))) (a, ((a, a), (S, S))) (a, ((a, a), (a, S))) (a, ((a, a), (a, a)))

d) 构造b)中句子的最右推导

编译原理 龙书答案

i) ii) iii)

S (L) (L, S) (L, a) (S, a) (a, a)

S (L) (L, S) (L, (L)) (L, (L, S)) (L, (L, a)) (L, (S, a)) (L, (a, a)) (S, (a, a)) (a, (a, a))

S (L) (L, S) (L, (L)) (L, (L, S)) (L, (L, (L))) (L, (L, (L, S))) (L, (L, (L, a))) (L, (L, (S, a))) (L, (L, (a, a))) (L, (S, (a, a))) (L, ((L), (a, a))) (L, ((L, S), (a, a))) (L, ((L, a), (a, a))) (L, ((S, a), (a, a))) (L, ((a, a), (S, S))) (S, ((a, a), (a, a))) (a, ((a, a), (a, a)))

e) 该文法产生的语言是什么

解：设该文法产生语言（符号串集合）L，则

L = { (A1, A2, …, An) | n是任意正整数，Ai=a，或Ai∈L，i是1～n之间的整数}

（Aho）4.2考虑文法 S→aSbS | bSaS |

a) 为句子构造两个不同的最左推导，以证明它是二义性的 S aSbS abS abaSbS ababS abab

S aSbS abSaSbS abaSbS ababS abab

b) 构造abab对应的最右推导

S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab

c) 构造abab对应语法树

d) 该文法产生什么样的语言？

解：生成的语言：a、b个数相等的a、b串的集合

（Aho）4.3 考虑文法

bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor

bfactor → not bfactor | ( bexpr ) | true | false a) 试为句子not ( true or false) 构造分析树 解：

编译原理 龙书答案

b) 试证明该文法产生所有布尔表达式 证明：

一、首先证明文法产生的所有符号串都是布尔表达式

变换命题形式——以bexpr、bterm、bfactor开始的推导得到的所有符号串都是布尔表达式 最短的推导过程得到true、false，显然成立 假定对步数小于n的推导命题都成立

考虑步数等于n 的推导，其开始推导步骤必为以下情况之一 bexpr bexpr or bterm bexpr bterm

bterm bterm and bfactor bexpr bfactor

bfactor not bfactor bfactor ( bexpr )

而后继推导的步数显然<n，因此由归纳假设，第二步句型中的NT推导出的串均为布尔表达式，这些布尔表达式经过or、and、not运算或加括号，得到的仍是布尔表达式 因此命题一得证。

二、证明所有布尔表达式均可由文法生成

变换命题——所有析取式均可由bexpr推导出来，所有合取式均可由bterm（bexpr）推导出来，所有对子布尔表达式施加not运算或加括号或简单true、false都可由bfactor（bexpr、bterm）推导出来

最简单的布尔表达式true和false显然成立

假定对长度小于n的布尔表达式，均可由文法推导出来

考虑长度等于n的布尔表达式B，显然，B只能是以下形式之一 B = B1 or B2 B = B1 and B2 B = not B1 B = ( B1 )

以上几种情况，B1、B2的长度均小于n

对于情况1：B为析取式，B1可为析取式也可为合取式，B2为合取式，根据假设可由bexpr合bterm推导出来，显然可构造推导过程，由bexpr推导出B 其他情况类似，命题二得证

综合一、二，可知文法产生的语言就是布尔表达式 c)

编译原理 龙书答案

（Aho）4.4考虑文法

R→R ‘|’ R | RR | R* | (R) | a | b c) 构造等价的非二义性文法 R→R ‘|’ A | A A→A B | B B→B* | C C→( R ) | a | b

（Aho）4.5下面if-then-else文法试图消除空悬else的二义性，证明它仍是二义性的 stmt→if expr then stmt | matched_stmt

matched_stmt→if expr then matched_stmt else stmt | other 解：

用S、M、E表示stmt、matched_stmt和expr，用i、t、e、o表示if、then、else和other 则句子i E t i E t o e i E t o e o对应两个最左推导：

i E t i E t o e i E t o e o

i E t i E t o e i E t o e o 因此文法是二义性文法

直接构造比较困难，可从SLR分析表的构造角度考虑，LR(0)项目集规范族中，项目 I8={M→i E t M e S, S→ M}，有移进/归约冲突，这就是是二义性所在。

显然，存在句型...i E t M e S...和...i E t S e S...，当M位于栈顶时，产生移进/归约冲突。 按此思路，构造形如... i E t S e S...的句型即可

（Aho）4.6 为下列语言设计上下文无关文法。哪些语言是正规式？ a) 满足这样条件的二进制串：每个0之后都紧跟着至少一个1 S→0 A | 1 S | A→1 S

正规式：(1 | 01)*

b) 0和1个数相等的二进制串 S→0 S 1 S | 1 S 0 S |

d) 不含011子串的二进制串 S→0 A | 1 S | A→0 A | 1 B | B→0 A |

编译原理 龙书答案

正规式：1*(0 | 01)*

e) 具有形式xy的二进制串，x≠y S→ A | B | A B | B A A→ D A D | 0 B→ D B D | 1 D→ 0 | 1

A、B分别表示中心符号为0、1的长度为奇数的二进制串

将AB串接，长度为偶数，将它从中间分为长度相等的两部分，x、y

虽然A、B长度可能不一样，但容易得到，A的中心0在x中的位置，与B的中心1在y中的位置是相同的，因此x≠y BA的情况类似

f) 形如xx的0、1串

解：此语言无法用上下文无关文法描述

（Aho）4.11 对习题4.1中文法 a) 消除左递归 S→( L ) | a L→S L’ L’→, S L’ |

b) 构造预测分析表，对4.1(b)中句子，给出预测分析器的运行过程 FIRST(S) = { (, a ) FIRST(L) = { (, a } FIRST(L’) = { ‘,’, } FOLLOW(S) = {‘,’, ), $} FOLLOW(L) = { ) } FOLLOW(L’) = { ) } 预测分析表：

编译原理 龙书答案

其他两个句子的分析过程类似

（Aho）4.13 下面文法产生除

外所有长度为偶数的a的串

S → a S a | a a

a）试为该文法构造一个带回溯的递归下降语法分析器，对S的两个候选式首先考虑aSa。证明：S所对应的过程可以成功分析2、4、8个a的串，但6个a的串不行。

解：aa的分析过程，其中√表示匹配成功，×表示匹配失败，匹配失败则尝试下个候选式

aaaa分析过程：

aaaaaa分析过程：

aaaaaaaa分析过程：

编译原理 龙书答案

b）此语法分析器能识别什么样的语言？

解：由a）的解可以看出，2N个a的串分析过程中，步骤如下

1） 产生2N+1个S的语法树，对第2N+1个S进行扩展时输入缓冲已空，失败 2） 对第2N个S尝试候选式aa，第二个a匹配失败

3） 对第2N-1个S尝试候选式aa，左边N-1个a匹配，右边最后一个a匹配，倒数第二个

a失败

4） 对第2N-2个S尝试候选式aa，左边N-2个a匹配，右边最后一个a和倒数第二个a匹

配，倒数第三个a失败

5） 对第2N-4个S尝试候选式aa，左边N-4个a匹配，右边最后一个a～倒数第四个a匹

配，倒数第五个a失败

6） 对第2N-8个S尝试候选式aa，…

最后正确识别的情况必然是：对第N个S尝试aa，左边N个a和右边N个a恰与输入匹配 显然，可以正确识别的符号串的N满足 2N – 1 – 1 – 2 – 4 - … = N N=2i

（Aho）4.25 试给出图4－60中的优先关系表对应的优先级函数 解：有向图如下

优先级函数为

（Aho）4.26 对习题4.1中文法，利用讲义中给出的算法计算终结符之间的优先关系 解： S → ( L ) | a L → L, S | S 由于S → ( L )，因此 ( )

S → ( L )，而L L , S，L S ( L )，L S a 因此 ( , ，( (，( a；, )，) )，a )

由于L → L, S，而L L , S，L S ( L )，L S a，因此 , ,，) ,，a ,

编译原理 龙书答案

而S ( L )，S a，因此 , ( ，, a 非终结符与$优先关系的计算方法： 如果存在S a…，或S Qa…，则$ a， 若存在S …a，或S …aQ，则a $ 因此，$ (，$ a，) $，a $ 算符优先关系表为：

（Aho）4.27 试给下列文法构造算符优先关系 a） 练习4.2中文法 解：

S→aSbS | bSaS | 由S→aSbS可得a b 由S→bSaS可得b a

由S→aSbS，和S bSaS可得a b、b b、a b，和S aSbS可得a a、b a、b b 由S→bSaS，和S bSaS可得b b、a b、a a，和S aSbS可得b a、a a、a a 文法不是算符优先文法，二义性文法，很自然 b） 练习4.3中文法

bexpr → bexpr or bterm | bterm

bterm → bterm and bfactor | bfactor

bfactor → not bfactor | ( bexpr ) | true | false

编译原理 龙书答案

（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

编译原理 龙书答案

goto(I6, S) = I7, goto(I6, A) = I2, goto(I6, a) = I3, goto(I7, S) = I5, goto(I7, A) = I6, goto(I7, a) = I3,

c) 构造SLR分析表 解：

FIRST(S) = FIRST(A) = {a, b} FOLLOW(S) = {$, a, b} FOLLOW(A) = {a, b}

goto(I6, b) = I4 goto(I7, b) = I4

SLR分析表冲突，分析过程有多种可能路径，选择其中一种导致正确结果的即可。

e) 构造规范LR分析表 解：

I0 = { [S’→ S, $], [S→ AS, $/a/b], [S→ b, $/a/b], [A→ SA, a/b], [A→ a, a/b] }

goto(I0, S) = {[S’→S , $], [A→S A, a/b], [A→ SA, a/b], [A→ a, a/b], [S→ AS, a/b], [S→ b, a/b]} = I1

goto(I0, A) = {[S→A S, $/a/b] , [S→ AS, $/a/b], [S→ b, $/a/b], [A→ SA, a/b], [A→ a, a/b] } = I2 goto(I0, a) = { [A→a , a/b] } = I3, goto(I0, b) = {[S→b , $/a/b]} = I4

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

goto(I1, A) = { [A→SA , a/b], [S→A S, a/b], [S→ AS, a/b], [S→ b, a/b], [A→ SA, a/b], [A→ a,

编译原理 龙书答案

a/b] } = I6

goto(I1, a) = I3, goto(I1, b) = {[S→b , a/b]} = I7

goto(I2, S) = {[S→AS , $/a/b], [A→S A, a/b], [A→ SA, a/b], [A→ a, a/b], [S→ AS, a/b], [S→ b, a/b] } = I8

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) = I7

goto(I6, S) = {[S→AS , a/b], [A→S A, a/b], [A→ SA, a/b], [A→ a, a/b], [S→ AS, a/b], [S→ b, a/b] } = I9

goto(I6, A) = {[S→A S, a/b] , [S→ AS, a/b], [S→ b, a/b], [A→ SA, a/b], [A→ a, a/b] } = I10 goto(I6, a) = I3, goto(I6, b) = I7 goto(I8, S) = I5, goto(I8, A) = I6, goto(I8, a) = I3, goto(I8, b) = I7 goto(I9, S) = I5, goto(I9, A) = I6, goto(I9, a) = I3, goto(I9, b) = I7 goto(I10, S) = I9, goto(I10, A) = I10, goto(I10, a) = I3, goto(I10, b) = I7 规范LR分析表为：

f) 利用LR(1)项目集合并的方法构造LALR分析表 解：

同心集合并：

I2 10 = {[S→A S, $/a/b] , [S→ AS, $/a/b], [S→

b, $/a/b], [A→ SA, a/b], [A→ a, a/b] } I47 = {[S→b , $/a/b]}

I89 = {[S→AS , $/a/b], [A→S A, a/b], [A→ SA, a/b], [A→ a, a/b], [S→ AS, a/b], [S→ b, a/b] }

编译原理 龙书答案

g) 利用高效构造方法构造LALR分析表 解：LR(0)项目集的核： I0 = { S’→ S }

I1 = { S’→S , A→S A } I2 = { S→A S } I3 = { A→a } I4 = { S→b } I5 = { A→S A }

I6 = { A→SA , S→A S } I7 = { S→AS , A→S A }

closure([S’→ S, #]) = { [S’→ S, #], [S→ AS, #/a/b], [S→ b, #/a/b], [A→ SA, a/b], [A→ a, a/b] } I0:S’→ S传播到I1: S’→S ，I2: S→A S，I4: S→b

自生搜索符a/b：I1: A→S A，I2: S→A S，I3: A→a ，I4: S→b

closure([A→S A, #])={[A→S A, #], [A→ SA, #/a/b], [A→ a, #/a/b], [S→ AS, a/b], [S→ b, a/b]} I1:A→S A传播到I6: A→SA ，I5: A→S A，I3: A→a

自生搜索符a/b：I5: A→S A，I6: S→A S，I3: A→a ，I4: S→b

closure([S→A S, #])={[S→A S, #] , [S→ AS, #/a/b], [S→ b, #/a/b], [A→ SA, a/b], [A→ a, a/b] } I2: S→A S传播到I7: S→AS ，I4: S→b

自生搜索符a/b：I2: S→A S，I7: A→S A，I3: A→a ，I4: S→b

I5:A→S A传播到I6: A→SA ，I3: A→a

自生搜索符a/b：I5: A→S A，I6: S→A S，I3: A→a ，I4: S→b

I6: S→A S传播到I7: S→AS ，I2: S→A S，I4: S→b

自生搜索符a/b：I2: S→A S，I7: A→S A，I3: A→a ，I4: S→b

closure([A→S A, #])={[A→S A, #], [A→ SA, #/a/b], [A→ a, #/a/b], [S→ AS, a/b], [S→ b, a/b]} I7:A→S A传播到I6: A→SA ，I5: A→S A，I3: A→a

自生搜索符a/b：I5: A→S A，I6: S→A S，I3: A→a ，I4: S→b

编译原理 龙书答案

（Aho）4.35 考虑下面文法 E → E + T | T T → T F | F F → F *| a | b

a） 构造SLR分析表 解：拓广文法 E' → E

I0={ E' → E, E → E + T, E → T, T → T F, T → F, F → F *, F → a, F → b } goto(I0, E) = { E' → E , E → E + T } = I1

goto(I0, T) = { E → T , T → T F, F → F *, F → a, F → b } = I2 goto(I0, F) = { T → F , F → F * } = I3 goto(I0, a) = { F → a } = I4 goto(I0, b) = { F → b } = I5

goto(I1, +) = { E → E + T, T → T F, T → F, F → F *, F → a, F → b } = I6 goto(I2, F) = { T → T F , F → F * } = I7 goto(I2, a) = I4 goto(I2, b) = I5

goto(I3, *) = { F → F * } = I8

goto(I6, T) = { E → E + T , T → T F, F → F *, F → a, F → b } = I9 goto(I6, F) = I3 goto(I6, a) = I4 goto(I6, b) = I5

编译原理 龙书答案

goto(I7, *) = I8 goto(I9, F) = I7 goto(I9, a) = I4 goto(I9, b) = I5

follow(E) = { +, $ } follow(T) = { a, b, +, $ } follow(F) = { a, b, *, +, $ }

b） 构造LALR分析表

解：LR(0)项目集规范族的核 I0 = { E' → E }

I1 = { E' → E , E → E + T } I2 = { E → T , T → T F } I3 = { T → F , F → F * } I4 = { F → a } I5 = { F → b } I6 = { E → E + T }

I7 = { T → T F , F → F * } I8 = { F → F * }

I9 = { E → E + T , T → T F }

closure({[E' → E , #]}) = { [E' → E , #], [E → E + T, #], [E → T, +], [T → T F, +/a/b], [T → F, +/a/b], [F → F *, +/a/b/*], [F → a, +/a/b/*], [F → b, +/a/b/*] } 传播：I0：E' → E I1：E' → E , I1：E → E + T

自生：I2：E → T ，I2：T → T F，I3：T → F ，I3：F → F *，I4：F → a ，I5：F → b

传播：I1：E → E + T I6：E → E + T

closure({[T → T F, #] }) = {[T → T F, #], [F → F *, #/*], [F → a, #/*], [F → b, #/*] } 传播：I2：T → T F I7：T → T F ，I7：F → F *，I4：F → a ，I5：F → b 自生：I7：F → F *，I4：F → a ，I5：F → b

编译原理 龙书答案

传播：I3：F → F * I8：F → F *

closure({[E → E + T, #]}) = {[E → E + T, #], [T → T F, #/a/b], [T → F, #/a/b], [F → F *, #/a/b/*], [F → a, #/a/b/*], [F → b, #/a/b/*] }

传播：I6：E → E + T I9：E → E + T ，I9：T → T F，I3：T → F ，I3：F → F *，I4：F → a ，I5：F → b

自生：I9：T → T F，I3：T → F ，I3：F → F *，I4：F → a ，I5：F → b

传播：I7：F → F * I8：F → F *

closure({[T → T F, #]}) = {[T → T F, #], [F → F *, #/*], [F → a, #/*], [F → b, #/*] } 传播：I9：T → T F I7：T → T F ，I7：F → F *，I4：F → a ，I5：F → b 自生：I3：F → F *，I4：F → a ，I5：F → b

计算搜索符：

编译原理 龙书答案

（Aho）4.37 对文法

S→AaAb | BbBa A→ B→

a) 证明它是LL(1)文法但不是SLR(1)文法 解：

构造预测分析表： FIRST(S) = {a, b}, FIRST(A)=FIRST(B)={ }

所以，文法是LL(1)文法 构造SLR分析表：

LR(0)项目集I0={S’→ S, S→ AaAb, S→ BbBa, A→ , B→ }

而FOLLOW(A)=FOLLOW(B)={a, b}，因此action[0, a] = action[0, b] = r3/r4，冲突！ 所有，文法不是SLR(1)文法

（Aho）4.39 证明文法 S→Aa | bAc | dc | bda A→d

是LALR(1)文法但不是SLR(1)文法 解：

构造SLR分析表：

项目集I4={ S→d c, A→d }，而FOLLOW(A)={a, c}，因此action[4, c]=s8/r5，冲突！ I7={ S→bd a, A→d }，因此action[7, a]=s10/r5，冲突！ 这是SLR分析表仅有的两个冲突的地方 因此文法不是SLR(1)文法

高效构造LALR分析表：

通过计算搜索符，所有项目都具有搜索符$，I4：A→d 具有搜索符a，I7：A→d 具有搜索符c，因此action[4, c]=s8，action[7, a]=s10，LALR分析表不冲突 因此文法是LALR(1)文法

（Aho）4.40 证明文法 S→Aa | bAc | Bc | bBa

编译原理 龙书答案

A→d B→d

是LR(1)文法但不是LALR(1)文法 解：

构造规范LR分析表：

I0 = { [S’→ S, $], [S→ Aa, $], [S→ bAc, $], [S→ Bc, $], [S→ bBa, $], [A→ d, a], [B→ d, c]} goto(I0, S)={ [S’→S , $] } = I1 goto(I0, A)={ [S→A a, $]} = I2 goto(I0, B)={ [S→B c, $]} = I3

goto(I0, b)={ [S→b Ac, $], [S→b Ba, $], [A→ d, c], [B→ d, a]} = I4 goto(I0, d)={ [A→d , a], [B→d , c]} = I5 goto(I2, a)={ [S→Aa , $]} = I6 goto(I3, c)={ [S→Bc , $]} = I7 goto(I4, A)={ [S→bA c, $]} = I8 goto(I4, B)={ [S→bB a, $]} = I9

goto(I4, d)={ [A→d , c], [B→d , a]} = I10 goto(I8, c)={ [S→bAc , $]} = I11 goto(I9, a)={ [S→bBa , $]} = I12 规范LR分析表为：

构造LALR分析表，同心集I5和I10合并，显然会造成归约/归约冲突。 因此，文法是LR(1)文法，但不是LALR(1)文法

（Aho）4.42 试编写一个算法，为文法中每个NT A计算集合{B | A* B , 其中B是NT， 文法符号串} 解：算法描述如下

1． 设置一个栈，保存NT，初始栈中只有A，将结果集合设置为空 2． 若栈空，算法结束，否则执行以下步骤 3． 将栈顶NT B弹出，将B加入结果集合

编译原理 龙书答案

4． 对所有形如B→C 的产生式，将C压栈 5． 返回2

（Aho）4.44 为练习4.4文法构造SLR分析表，解决冲突 解：拓广文法 R'→R

R→R ‘|’ R | RR | R* | (R) | a | b

I0={ R'→ R, R→ R ‘|’ R, R→ RR, R→ R*, R→ (R), R→ a, R→ b }

goto(I0, R) = { R'→R , R→R ‘|’ R, R→R R, R→R *, R→ R ‘|’ R, R→ RR, R→ R*, R→ (R), R→ a, R→ b } = I1

goto(I0, () = { R→( R), R→ R ‘|’ R, R→ RR, R→ R*, R→ (R), R→ a, R→ b } = I2 goto(I0, a) = { R→a } = I3 goto(I0, b) = { R→b } = I4

goto(I1, R) = { R→RR , R→R ‘|’ R, R→R R, R→R *, R→ R ‘|’ R, R→ RR, R→ R*, R→ (R), R→ a, R→ b } = I5

goto(I1, |) = { R→R ‘|’ R, R→ R ‘|’ R, R→ RR, R→ R*, R→ (R), R→ a, R→ b } = I6 goto(I1, *) = { R→R * } = I7 goto(I1, () = I2 goto(I1, a) = I3 goto(I1, b) = I4

goto(I2, R) = { R→(R ), R→R ‘|’ R, R→R R, R→R *, R→ R ‘|’ R, R→ RR, R→ R*, R→ (R), R→ a, R→ b } = I8 goto(I2, () = I2 goto(I2, a) = I3 goto(I2, b) = I4 goto(I5, R) = I5 goto(I5, |) = I6 goto(I5, *) = I7 goto(I5, () = I2 goto(I5, a) = I3 goto(I5, b) = I4

goto(I6, R) = { R→R ‘|’ R , R→R ‘|’ R, R→R R, R→R *, R→ R ‘|’ R, R→ RR, R→ R*, R→ (R), R→ a, R→ b } = I9 goto(I6, () = I2 goto(I6, a) = I3 goto(I6, b) = I4 goto(I8, R) = I5 goto(I8, |) = I6 goto(I8, *) = I7 goto(I8, () = I2

goto(I8, )) = { R→(R) } = I10 goto(I8, a) = I3 goto(I8, b) = I4 goto(I9, R) = I5

编译原理 龙书答案

goto(I9, *) = I7 goto(I9, () = I2 goto(I9, a) = I3 goto(I9, b) = I4

FOLLOW(R)={ |, *, (, ), a, b, $}

对于状态5，几种冲突分别表示以下含义（用 表示连接操作）： …R R|…，…R R*…，…R R (…，…R R a…，…R R a… 显然，除了第二种情况，均应选择归约操作 对于状态9，冲突含义为：

…R|R|…，…R|R*…，…R|R (…，…R|R a…，…R|R a… 除了第一种情况，均应选择移进操作

（Aho）4.46 a) 为下面文法构造SLR分析表，解决冲突，使得与图4-52同样方式分析 E→E sub R | E sup E | { E } | c R→E sup E | E 解：拓广 E'→E

构造LR(0)项目集规范族

I0={ E'→ E, E→ E sub R, E→ E sup E, E→ { E }, E→ c } goto(I0, E)= { E'→E , E→E sub R, E→E sup E }=I1

goto(I0, {)= { E→{ E }, E→ E sub R, E→ E sup E, E→ { E }, E→ c }=I2 goto(I0, c)= { E→c }=I3

goto(I1, sub)= { E→E sub R, R→ E sup E, R→ E, E→ E sub R, E→ E sup E, E→ { E }, E→ c }=I4

goto(I1, sup)= { E→E sup E, E→ E sub R, E→ E sup E, E→ { E }, E→ c }=I5 goto(I2, E)= { E→{ E }, E→E sub R, E→E sup E }=I6 goto(I2, {)= I2

编译原理 龙书答案

goto(I4, E)= { R→E sup E, R→E , E→E sub R, E→E sup E }=I7 goto(I4, R)= { E→E sub R }=I8 goto(I4, {)= I2

goto(I4, c)= { E→c }=I3

goto(I5, E)= { E→E sup E , E→E sub R, E→E sup E }=I9 goto(I5, {)= I2 goto(I5, c)= I3

goto(I6, })= { E→{ E } }=I10 goto(I6, sub) =I4 goto(I6, sup) =I5 goto(I7, sub)= I4

goto(I7, sup)= { R→E sup E, E→E sup E, E→ E sub R, E→ E sup E, E→ { E }, E→ c }=I11 goto(I9, sub) =I4 goto(I9, sup) =I5

goto(I11, E) ={ R→E sup E , E→E sup E , E→E sub R, E→E sup E }=I12 goto(I11, {)= I2 goto(I11, c)= I3 goto(I12, sub) =I4 goto(I13, sup) =I5

FOLLOW(E)=FOLLOW(R)={ sub, sup, }, $ }

（Aho）4.48 考虑下面n个二元中缀操作符的二义性文法： E → E E | E E | … | E n E | ( E ) | id

假设所有操作符都是左结合的，而且若i > j，则 i的优先级高于 j。 a） 试为该文法构造SLR项目集。共有多少个项目集？是n的函数吗？

本文来源：https://www.bwwdw.com/article/zaw4.html