第四章部分习题解答
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) S(L)(L, S) (S, S) (a, S) (a, a)
ii) S(L)(L, S) (S, S) (a, S) (a, (L)) (a, (L, S)) (a, (S, S)) (a, (a, S) (a, (a,
a))
iii) 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) S(L)(L, S) (L, a) (S, a) (a, a)
ii) S(L)(L, S) (L, (L)) (L, (L, S)) (L, (L, a)) (L, (S, a)) (L, (a, a)) (S, (a,
a)) (a, (a, a))
iii) 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 = { (A
1
, A
2
, …, A
n
) | n 是任意正整数，A
i
=a，或 A
i
∈L，i 是 1～n 之间的整数}
（Aho）4.2 考虑文法
S→aSbS | bSaS |
a) 为句子构造两个不同的最左推导，以证明它是二义性的
SaSbSabSabaSbSababSabab
SaSbSabSaSbSabaSbSababSabab
b) 构造 abab 对应的最右推导
SaSbSaSbaSbSaSbaSbaSbababab
SaSbSaSbabSaSbabSababab
c) 构造 abab 对应语法树
d) 该文法产生什么样的语言？
解：生成的语言：a、b 个数相等的 a、b 串的集合
（Aho）4.3 考虑文法
bexpr → bexpr or bterm | bterm
bterm → bterm and bfac tor | 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 = B
1
or B
2
B = B
1
and B
2
B = not B
1
B = ( B
1
)
以上几种情况，B
1
、B
2
的长度均小于 n
对于情况 1：B 为析取式，B
1
可为析取式也可为合取式，B
2
为合取式，根据假设可由 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 对应两个最左推导：
Si E t Si E t Mi E t i E t M e Si E t i E t o e Si E t i E t o e M
i E t i E t o e i E t M e Si E t i E t o e i E t o e S i E t i E t o e i E t o e M
i E t i E t o e i E t o e o
SMi E t M e S i E t i E t M e S e S i E t i E t o e S e S i E t i E t o e i E t S e S
i E t i E t o e i E t M e S i E t i E t o e i E t o e S i E t i E t o e i E t o e M
i E t i E t o e i E t o e o
因此文法是二义性文法
直接构造比较困难，可从 SLR 分析表的构造角度考虑，LR(0)项目集规范族中，项目
I
8
={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’) = { ) }
预测分析表：
a ( ) , $
S
S→a S→( L )
L
L→S L’ L→S L’
L’
L’→ L’→, S L’
(a, a)的分析过程
栈 输入 输出
$S (a, a)$
$) L ( (a, a)$
S→( L )
