# 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 呢？ 在扫描过程中，如何正确地识别出产生式的右侧部分并及时进行规约，是自底向上解析的核心问题，同自顶向下推导一样，我们也需要为自底向上推导构建一个预测表。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://gocompiler.shizhz.me/3.b-yu-fa-fen-xi-li-lun-zhi-shi/3.3.4-zi-di-xiang-shang-bottomup.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.