《编译原理》习题参考答案(二)
第三章
3.15(a) 用习题 3.1 的文法构造( a , ( a , a ) )的最右推导,说出每个右
句型的句柄.
(b) 给出对应(a)的最右推导的移进—归约分析器的步骤.
(c) 对照(b)的移进—归约,给出自下而上构造分析树的步骤.
Solution:
(a): S—>( L )—>( L , S )—>( L , ( L ) )—>( L , ( L , S ) )—>( L , ( L ,
a ) )—>( L , ( S , a ) ) —>( L , ( a , a ) ) —>( S , ( a , a ) ) —>( a , ( a ,
a ) )
其中加下划线的为句柄.
(b)
栈 输入 动作
$ (a,(a,a))$ 移进
$( a,(a,a))$ 移进
$(a ,(a,a))$ 按S—>a 归约
$(S ,(a,a))$ 按L—>S 归约
$(L ,(a,a))$ 移进
$(L, (a,a))$ 移进
$(L,( a,a))$ 移进
$(L,(a ,a))$ 按S—>a 归约
$(L,(S ,a))$ 按L—>S 归约
$(L,(L ,a))$ 移进
$(L,(L, a))$ 移进
$(L,(L,a ))$ 按S—>a 归约
$(L,(L,S ))$ 按L—>L , S 归约
$(L,(L ))$ 移进
$(L,(L) )$ 按S—>( L )归约
$(L,S )$ 按L—>L , S 归约
$(L )$ 移进
$(L) $ 按S—>( L )归约
$S $ 接受
(c) 步骤:
( → ( a → ( S → ( L → ( L , → ( L , ( → ( L , ( a → ( L , ( S → ( L , ( L
a S S S S S a S S
a a a a a a a
//以下将省略一些枝、叶结点
→ ( L , ( L , → ( L , ( L , a → ( L , ( L , S → ( L , ( L → ( L , ( L , a
L , S
→ ( L , ( L , S → ( L , ( L → ( L , ( L ) → ( L , S → ( L → ( L ) → S
3.19 考虑下面的文法

下一页