Links
Comment on page

3A.3.4 自底向上(Bottom-Up)

从解析树的叶子节点开始,逐步向上构建出整颗解析树的过程叫着自底向上解析。自底向上解析是一个最右推导的逆过程。
考虑如下文法 G:
E -> E + T | T T -> T * F | F F -> (E) | id
输入字符串 w: id + id * id
对 w 自底向上的解析为(为了便于显示,已扫描部分字体是加粗斜体,另外使用 | 标记解析器当前位置):
  1. 1.
    id |+ id * id 扫描 id
  2. 2.
    -> F |+ id * id 规约 id 到 F
  3. 3.
    -> T |+ id * id 规约 F 到 T
  4. 4.
    -> E |+ id * id 规约 T 到 E
  5. 5.
    -> E + |id * id 扫描 +
  6. 6.
    -> E + id |* id 扫描 id
  7. 7.
    -> E + F |* id 规约 id 到 F
  8. 8.
    -> E + T |* id 规约 F 到 T
  9. 9.
    -> E + T * |id 扫描 *
  10. 10.
    -> E + T * id| 扫描 id
  11. 11.
    -> E + T * F| 规约 id 到 F
  12. 12.
    -> E + T| 规约 T * F 到 T
  13. 13.
    -> E| 规约 E + T 到 E, 解析结束
该示例中体现了自底向上解析过程中的两个核心动作:
  • 规约(Reduction)
    解析器在从左向右扫描输入符号串的过程中,在合适的位置识别出一个产生式的右边部分,并将其替换为产生式的左边字符;第 11 步进行的操作就是规约
  • 移入(Shift)
    如果所扫描的部分还无法完成规约,则继续扫描并将新符号加入进去,这个过程叫着移入(Shift);上例中彩色部分符号串就是已经扫描的部分,第 10 步所做的操作便是移入。
不管是自顶向下还是自底向上,其面临的核心问题都是如何选择产生式:
  • 自顶向下解析中,该问题体现在面临产生式左边的非终结符号时,如何选择合适的产生式右边;
  • 而在自底向上解析中,是如何识别出产生式的右侧部分,然后将其规约成产生式的左侧符号。 例如上例第 11 步时,如何知道需要将 id 规约成 F, 然后进一步将 T * F 规约成 T, 而不是直接将 T 规约成 E 呢?
在扫描过程中,如何正确地识别出产生式的右侧部分并及时进行规约,是自底向上解析的核心问题,同自顶向下推导一样,我们也需要为自底向上推导构建一个预测表。