递归下降分析器

在计算机科学中，递归下降解析器是一种，由一组相互递归的程序（或等价的非递归程序）构建而成，其中每个程序都实现了文法中的一个非终结符。因此，这些程序的结构密切反映了它所识别的文法结构。 预测性解析器是一种不需要回溯的递归下降解析器。预测性解析只适用于 LL(k) 文法。这是一种上下文无关文法。这种文法允许递归下降解析器仅通过检测之后 k 个标记决定当前标记（token）所使用的。LL(k) 文法由此排除了所有包含歧义和左递归的文法。虽然任何一种上下文无关文法都可以转化为没有左递归的等效文法，但是去除了左递归却不一定能够得到 LL(k) 文法。预测性解析器能够在线性时间内运行。 具有回溯的递归下降是一种通过依次尝试生成规则来生成结果的技术。具有回溯的递归下降不限于 LL(k) 文法，但只在文法是 LL(k) 文法的情况下才保证能够停机。具有回溯的递归下降对于其他文法即使能够停机，也可能需要指数时间运行。 尽管预测性解析器被广泛使用，也经常被选择用于手工编写解析器，但程序员通常更愿意使用由文法解析器生成器产生的基于表的解析器，无论是对于 LL(k) 语言还是使用替代解析器，比如 LALR 或 LR。如果一个文法不是 LL(k) 文法，情况尤其如此，因为要把文法转化为 LL 形式，使其适合预测性解析。预测性解析器也可以使用 ANTLR 之类的工具自动生成。 预测性解析器可以用每个非终结符号的过渡图来描述，其中初始状态和最终状态之间的界限由生成规则右侧的符号（终结符和非终结符）来界定。