Search CTRL + K

Recursive Descent Parsing

递归下降分析(recursive descent parsing) 是一种 自顶向下分析 算法,它由一组相互递归的程序构建而成,每个程序都实现了 形式文法 中的一个 非终结符

RD 分析器 是最常见的 自顶向下分析器 实现,也是最常见的手写 语法分析器 方案,但它需要回溯,导致很难正确、高效地编写代码。


In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.[1]

Eli Bendersky's website

RD parsers are the most general form of top-down parsing, and the most popular type of parsers to write by hand. However, being so general, they have several problems, like requiring backtracking (which is difficult to code correctly and efficiently).

Usually, it is enough to use less general and powerful parsers for all practical needs, like parsing programming languages (and domain specific languages). This is where LL parsers come in.[2]

  1. ↩︎

  2. ↩︎