编译器设计 - 解析类型

语法分析器遵循通过上下文无关语法定义的产生式规则。 产生式规则的实现（推导）方式将解析分为两种类型：自顶向下解析和自底向上解析。

自顶向下解析

当解析器从起始符号开始构建解析树，然后尝试将起始符号转换为输入时，称为自顶向下解析。

• 递归下降解析：这是自顶向下解析的常见形式。 它被称为递归，因为它使用递归过程来处理输入。 递归下降解析会受到回溯的影响。

• 回溯：这意味着，如果一个产生式的推导失败，语法分析器会使用同一产生式的不同规则重新启动该过程。 该技术可以多次处理输入字符串以确定正确的产生式。

自下而上解析

顾名思义，自下而上的解析从输入符号开始，并尝试构建解析树直到起始符号。

示例：

输入字符串：a + b * c

生产规则：

S → E
E → E + T
E → E * T
E → T
T → id

让我们开始自下而上的解析

a + b * c

读取输入并检查是否有与输入匹配的产生式：

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S