《编译原理》复习题
个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。 22．对于文法G(S)：
S → (L) | aS | a L → L, S | S
(1) 画出句型(S, (a))的语法树。
(2) 写出上述句型的所有短语、直接短语和句柄。 解：
(1) 句型(S, (a))的语法树如下图所示：
S 解：（1）逆波兰式： abc-*@d+ 其中使用@代表一目减运算 （2）四元式： ① (-, b, c, T1) ② (*, a, T1, T2) ③ (@, T2, _, T3) ④ (+, T3, d, T4)
25．把下列语句翻译为四元式序列： while (A > B) if (C > D)
X = Y * Z
else
( L ) X = Y + Z 解：
L , S S ( L ) (1) (j>, A, B, 3) (2) (j, _, _, 11)
S (3) (j>, C, D, 5) (4) (j, _, _, 8)
a (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分）
17
(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 的逆波兰表示和四元式表示。
《编译原理》复习题
3 21 = 3 41 = 3状态均属于集合{3}，所以对于输入符号1也不能区分开1，2，4三个状态；因此最终的状态划分即为: {3} {1, 2, 4}，其对应的DFA如下图所示：
0 X ε 0 ε 1 1 2 ②子集法确定化 I {X, 0, 1, 3, Y} {0, 1, 3, Y} {2} {1, 3, Y} {0, 1, 3, Y} {1, 3, Y} {1, 3, Y} I0 {0, 1, 3, Y} 0 ε 3 0 ε Y 0 0 1 I1 {2} 27．已知文法G(S)： S→S*aP| aP| *aP {2} - {2} P→+aP| +a (1) 将文法G(S)改写为LL(1)文法G’(S)； (2) 写出文法G’(S)的预测分析表。 解： （1）消除左递归，文法变为：
0 0 1 重新命名状态，即得：
S 1 2 3 4 ③ 最小化
0 2 2 4 4 1 3 3 - 3 S→aPS’| *aPS’ S’→ *aPS’ | ε
P→+aP| +a
提取公共左因子，文法变为G’(S)： S→aPS’| *aPS’
S’→ *aPS’ |ε
P→+aP’ P’→P| ε