《编译原理》复习题
（7）出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。 22．对于文法G(S)：
S → (L) | aS | a L → L, S | S
(1) 画出句型(S, (a))的语法树。
(2) 写出上述句型的所有短语、直接短语和句柄。 解：
(1) 句型(S, (a))的语法树如下图所示：
S ( L ) L , S S ( L ) S a
(2) 从语法树中可以找到（3分）短语：a; (a); S; S,(a); (S, (a)) 直接短语： a; S 句柄： S
23．构造一文法，使其描述的语言L = {ω |ω ∈ (a, b)*，且ω中含有相同个数的a和b}。解：
S→ ε| aA|bB A→ b| bS| aAA B→ a| aS| bBB
24．分别给出表达式 –(a*(b-c))+d 的逆波兰表示和四元式表示。 解：（1）逆波兰式： abc-*@d+ 其中使用@代表一目减运算 （2）四元式： ① (-, b, c, T1)
25
《编译原理》复习题
② (*, a, T1, T2) ③ (@, T2, _, T3) ④ (+, T3, d, T4)
25．把下列语句翻译为四元式序列： while (A > B) if (C > D)
X = Y * Z
else
X = Y + Z 解：
(1) (j>, A, B, 3) (2) (j, _, _, 11) (3) (j>, C, D, 5) (4) (j, _, _, 8) (5) (*, Y, Z, T1) (6) (=, T1, _, X) (7) (j, _, _, 1) (8) (+, Y, Z, T2) (9) (=, T2, _, X) (10) (j, _, _, 1) (11)
26．构造一个DFA，它接受Σ = {0, 1}上所有满足如下条件的字符串：每个1后面都有0直接跟在右边。 解：（1）0*(0|10)*0* 或者 (0|10)*
（2）
①NFA （2分）
0 X ε 0 ε 1 1 2
0 ε 3 0 ε Y 0 26
《编译原理》复习题
②子集法确定化
I {X, 0, 1, 3, Y} {0, 1, 3, Y} {2} {1, 3, Y} 重新命名状态，即得：
S 1 2 3 4 ③ 最小化
首先分为终态集和非终态集 {3} {1, 2, 4} 因为10 = 2 20 = 2 40 = 4 状态均属于集合{1, 2, 4}，所以对于输入符号0不能区分开1，2，4三个状态；11 = 3 21 = 3 41 = 3状态均属于集合{3}，所以对于输入符号1也不能区分开1，2，4三个状态；因此最终的状态划分即为: {3} {1, 2, 4}，其对应的DFA如下图所示：
0 1 0 0
27．已知文法G(S)：
S→S*aP| aP| *aP P→+aP| +a
(1) 将文法G(S)改写为LL(1)文法G’(S)； (2) 写出文法G’(S)的预测分析表。 解：
（1）消除左递归，文法变为： S→aPS’| *aPS’ S’→ *aPS’ | ε
27
I0 {0, 1, 3, Y} {0, 1, 3, Y} {1, 3, Y} {1, 3, Y} I1 {2} {2} - {2} 0 2 2 4 4 1 3 3 - 3 1
《编译原理》复习题
P→+aP| +a
提取公共左因子，文法变为G’(S)： S→aPS’| *aPS’
S’→ *aPS’ |ε
P→+aP’ P’→P| ε
（2）计算每个非终结符的FIRST集和FOLLOW集： FIRST(S) = {a, *}
FOLLOW(S) = {#}
FIRST(S’) = {*, ε} FOLLOW(S’) = {#} FIRST(P) = {+} FOLLOW(P) = {*, #} FIRST(P’) = {+, ε}
FOLLOW(P’) = {*, #}
构造该文法的预测分析表如下： （5分）
* + a # S S→*aPS’ S→aPS’ S’ S’→ *aP S’→ ε P P→+aP’ P’ P’→ε P’→P P’→ε 28．已知文法G(S)：
S→aS | bS | a
(1) 构造识别该文法所产生的活前缀的DFA；
(2) 判断该文法是LR(0)还是SLR(1)，并构造所属文法的LR分析表。 解：
（1）将文法G(S)拓广为G’(S’)：
(0) S’→S (1) S→aS (2) S→bS (3) S→a
识别该文法所产生的活前缀的DFA：
28