编译器设计——解析类型

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

自顶向下解析

如果解析器开始使用起始符构建解析树，然后尝试将起始符转换为输入，则称之为自顶向下解析。

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

• 回溯：这意味着，如果某个产生规则的导出失败，语法分析器会使用同一产生规则的不同规则重新开始这一过程。此技巧可能会多次处理输入字符串以确定正确的产生规则。

自底向上解析

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

示例

输入字符串：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