递归下降分析

定义

递归下降分析(Recursive Descent Parsing)是一种自顶向下的语法分析技术:为文法中每个非终结符编写一个解析函数,函数之间按产生式相互递归调用,从起始符号出发推导出整个输入。

原理

最常见的形式是预测分析,借助向前看一个记号(LL(1))决定选用哪条产生式,无需回溯。左递归文法会导致无限递归,需先改写为右递归或用循环消除。

优点

结构直观、与文法一一对应,便于手写与调试;容易嵌入语义动作、产生高质量错误信息;配合算符优先(Pratt 解析)可优雅处理表达式优先级。

应用

GCC、Clang、V8、Go、Rust 等主流编译器的语法分析器大多为手写递归下降,而非解析器生成器产物,原因正是其错误恢复与可维护性优势。