《编译原理》复习题
个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。 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| ε
首先分为终态集和非终态集 {3} {1, 2, 4} 因为
（2）计算每个非终结符的FIRST集和
10 = 2 20 = 2 40 = 4 状态均属于集合{1, 2, 4}，所以对于输入符号0不能区分开1，2，4三个状态；11 =
18
FOLLOW集：
FIRST(S) = {a, *}
《编译原理》复习题
FOLLOW(S) = {#} FIRST(S’) = {*, ε}
I4: S’→ aS? S FOLLOW(S’) = {#} FIRST(P) = {+}
a I0: S’→ ?S S→ ?aS S→ ?bS S→ ?a b I2: S→ a?S S→ ?aS S→ ?bS S→ ?a S→ a? a FOLLOW(P) = {*, #} FIRST(P’) = {+, ε}
S I1: S’→ S? b a FOLLOW(P’) = {*, #}
构造该文法的预测分析表如下： （5分） * S→*aS PS’ S’→ S’ *aP P→+aP P’ P’ P’→ε P’→P P’→ε S’→ ε ’ + a S→aPS # I5: S’→ bS? I3: S→ b?S S→ ?aS S→ ?bS S→ ?a S b （2）在状态I2存在“移近-归约”冲突，因此该文法不是LR(0)文法。
计算S的FOLLOW集合： FOLLOW(S)= {#}
I2中的冲突用FOLLOW集合可以解决，
所以该文法是SLR(1)文法。
构造SLR(1)分析表如下：
ACTION GOT O 状态 a b # S 0 s2 s3 1 1 acc 2 s2 s3 r3 4 3 s2 s3 5 4 r1
5 r2
29．将下图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。其中，X为初态，Y为终态。
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：
19
《编译原理》复习题
31． 下面的文法产生0和1的串，即二进制的正整数，请给出决定每个二进制数的值（十进制形式）的语法制导定义。 2a?【解】定义值属性为.val，翻译方案如下：
1ba B ? B1 0 { B.val = B1.val ? 2 } aYa B ? B1 1 { B.val = B1.val ? 2 + 1 } Xbb B ? 1 { B.val = 1 }
bB ? 0 { B.val = 0 } 3432．把算术表达式?(a + b) ? (c + d) + (e+ f) 翻译成?等价的四元式序列（序号从0开始）。 a? 【解】
0（+，a, b ,T1） 【解】 用子集法将NFA确定化，如图所示。 1（uminus，T1，-，T2）
2（+，c, d , T3）
IIaIbSab3（*，T2，T3，T4）
4（+，e，f，T5） {X}{1}{3}0125（+，T4，T5，T6）
{1}{2,3,Y}{3,Y}13433．设有文法G[S]:
{3}—{3,4}重新命名2—5S→a|（T）|?
T→T,S|S {2,3,Y}{2,3,Y}{2,3,4,Y}336试给出句子(a,a,a)的最左推导。
{3,Y}{2,3,Y]{3,4}435【解】(1) (a,a,a)的最左推导
{3,4}{3,4}{3,4,Y}557S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) {2,3,4,Y}{2,3,4,Y}{2,3,4,Y}666=>(a,a,S) =>(a,a,a)
34．已知文法Ｇ： {3,4,Y}{2,3,4,Y}{3,4,Y}767 S → ( L | a
确定化的DFA如下图所示： L → S , L | )
判断是不是LL（1）文法，如果是请构造文法 Ｇ 的a预测分析表，如果不是请说明理由。
a【解】 3ba 1）求各非终结符的 FISRT 集和 FOLLOW 集：
1a = { (, a ) 6abb0b2bb4a5ab7b
30．对正规式(a|b)*abb构造其等价的NFA。 【解】
20
b
FIRST(L) = { a }? FIRST(S) = { (, ), a } FOLLOW(S) = {, # }
FOLLOW(L) = FOLLOW(S) ={ , # } FIRST(( L)∩{a}=Φ FIRST(S , L)∩{)}=Φ 所以是LL（1）文法 2）预测分析表： S L
( a , } # S→ S→ ( L a L→ L→ S , L S , L L → )