Compilers Principles, Techniques, & Tools (purple dragon book) second edition exercise answers

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 $ 接受