编译原理（紫龙书）中文第2版习题答案

 主页   资讯   文章   代码   电子书 

4.5 节的练习

4.5.1

对于练习 4.2.2（a）中的文法 S -> 0 S 1 | 0 1，指出下面各个最右句型的句柄。

  1. 000111
  2. 00S11

解答

  1. 01
  2. 0S1

4.5.2

对于练习 4.2.1 的文法 S -> S S + | S S * | a 和下面各个最右句型，重复练习 4.5.1 。

  1. SSS+a*+
  2. SS+a*a+
  3. aaa*a++

解答

  1. SS+
  2. SS+
  3. a

4.5.3

对于下面的输入符号串和文法，说明相应的自底向上语法分析过程。

  1. 练习 4.5.1 的文法的串 000111 。
  2. 练习 4.5.2 的文法的串 aaa*a++ 。

解答

1、 000111

栈 输入 句柄 动作
$ 000111$ 移入
$0 00111$ 移入
$00 0111$ 移入
$000 111$ 移入
$0001 11$ 01 规约：S -> 01
$00S 11$ 移入
$00S1 1$ 0S1 规约：S -> 0S1
$0S 1$ 移入
$0S1 $ 0S1 规约：S -> 0S1
$S $ 接受

2、 aaa*a++

栈 输入 句柄 动作
$ aaa*a++$ 移入
$a aa*a++$ a 规约: S -> a
$S aa*a++$ 移入
$Sa a*a++$ a 规约: S -> a
$SS a*a++$ 移入
$SSa *a++$ a 规约: S -> a
$SSS *a++$ 移入
$SSS* a++$ SS* 规约: S -> SS*
$SS a++$ 移入
$SSa ++$ a 规约: S -> a
$SSS ++$ 移入
$SSS+ +$ SS+ 规约: S -> SS+
$SS +$ 移入
$SS+ $ SS+ 规约: S -> SS+
$S $ 接受