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