# 3A.3.4 自底向上（Bottom-Up）

从解析树的叶子节点开始，逐步向上构建出整颗解析树的过程叫着自底向上解析。自底向上解析是一个最右推导的逆过程。

考虑如下文法 G：

> E -> E + T | T \
> T -> T \* F | F \
> F -> (E) | id

输入字符串 w: id + id \* id

 对 w 自底向上的解析为（为了便于显示，已扫描部分字体是***加粗斜体***，另外使用 | 标记解析器当前位置）：

> 1. ***`id`*** |+ id \* id                 扫描 id
> 2. -> ***`F`*** |+ id \* id               规约 id 到 F
> 3. -> ***`T`*** |+ id \* id               规约 F 到 T
> 4. -> ***`E`*** |+ id \* id               规约 T 到 E
> 5. -> ***`E +`*** |id \* id              扫描 +
> 6. -> ***`E + id`*** |\* id            扫描 id
> 7. -> ***`E + F`*** |\* id              规约 id 到 F
> 8. -> ***`E + T`*** |\* id              规约 F 到 T
> 9. -> ***`E + T *`*** |id             扫描 \*
> 10. -> ***`E + T * id`***|    扫描 id
> 11. -> ***`E + T * F`***|             规约 id 到 F
> 12. -> ***`E + T`***|                     规约 T \* F 到 T
> 13. -> ***`E`***|                             规约 E + T 到 E, 解析结束

 该示例中体现了自底向上解析过程中的两个核心动作：

*  规约（Reduction）

   解析器在从左向右扫描输入符号串的过程中，在合适的位置识别出一个产生式的右边部分，并将其替换为产生式的左边字符；第 11 步进行的操作就是规约
*  移入（Shift）

   如果所扫描的部分还无法完成规约，则继续扫描并将新符号加入进去，这个过程叫着移入（Shift）；上例中彩色部分符号串就是已经扫描的部分，第 10 步所做的操作便是移入。

 不管是自顶向下还是自底向上，其面临的核心问题都是如何选择产生式：

* 自顶向下解析中，该问题体现在面临产生式左边的非终结符号时，如何选择合适的产生式右边；
* 而在自底向上解析中，是如何识别出产生式的右侧部分，然后将其规约成产生式的左侧符号。 例如上例第 11 步时，如何知道需要将 id 规约成 F, 然后进一步将 T \* F 规约成 T, 而不是直接将 T 规约成 E 呢？

 在扫描过程中，如何正确地识别出产生式的右侧部分并及时进行规约，是自底向上解析的核心问题，同自顶向下推导一样，我们也需要为自底向上推导构建一个预测表。