第四章 语法分析
4.14 仍考虑练习 4.6 中的文法 S ( L ) | a
L L, S | S
(a) 给出句子(a, ((a, a), (a, a)))的一个最右推导，并指出右句型的句柄；
(b) 按照(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), (a, a))) (S, ((a, a), (a, a))) (a, ((a, a), (a, a)))
(注：下划线部分为句柄)
(b)
步骤 栈 输 入 动 作
1 $ (a, ((a, a), (a, a)))$ 移进
2 $( a, ((a, a), (a, a)))$ 移进
3 $(a , ((a, a), (a, a)))$ 归约，Sa
4 $(S , ((a, a), (a, a)))$ 归约，LS
5 $(L , ((a, a), (a, a)))$ 移进
6 $(L, ((a, a), (a, a)))$ 移进
7 $(L, ( (a, a), (a, a)))$ 移进
8 $(L, (( a, a), (a, a)))$ 移进
9 $(L, ((a , a), (a, a)))$ 归约，Sa
10 $(L, ((S , a), (a, a)))$ 归约，LS
11 $(L, ((L , a), (a, a)))$ 移进
12 $(L, ((L, a), (a, a)))$ 移进
13 $(L, ((L, a ), (a, a)))$ 归约，Sa
14 $(L, ((L, S ), (a, a)))$ 归约，LL, S
15 $(L, ((L ), (a, a)))$ 移进
16 $(L, ((L) , (a, a)))$ 归约，S(L)
17 $(L, (S , (a, a)))$ 归约，LS
18 $(L, (L , (a, a)))$ 移进
19 $(L, (L, (a, a)))$ 移进
20 $(L, (L, ( a, a)))$ 移进
21 $(L, (L, (a , a)))$ 归约，Sa
22 $(L, (L, (S , a)))$ 归约，LS
23 $(L, (L, (L , a)))$ 移进
24 $(L, (L, (L, a)))$ 移进
