递归下降语法分析

自顶向下的语法分析

为输入串构造语法分析树：

• 从分析树的根节点（即文法的起始符号）开始，自顶向下，按照先根次序，深度优先地创建各个节点

• 对应于最左推导

• 关键步骤：应用产生式创建新的子节点

递归下降的语法分析

一种自顶向下的语法分析，每个非终结符号对应于一个过程/函数，该过程负责扫描此非终结符号对应的结构。程序执行从开始符号对应的过程开始，当扫描整个输入串时宣布分析成功完成。

递归下降分析的特点

• 优点：易于实现（手写）

• 缺点：需要回溯（影响效率）

基于预测的语法分析

与递归下降的语法分析不同的是，根据下一字符，预测正确的产生式，避免回溯。

• 试图从开始符号推导出输入符号串

• 每次为最左边的非终结符号选择适当的产生式，通过查看下一个输入符号来选择这个产生式