Recursive descent parser: Difference between revisions

Revision as of 03:59, 3 September 2006

Revision as of 04:28, 11 October 2006

Line 4:

Recursive descent with backup is a technique that determines which production to use by trying each production in turn. Recursive descent with backup is not limited to [[LL parser|LL(k)]] grammars, but is not guaranteed to terminate unless the grammar is [[LL parser|LL(k)]]. Even when they terminate, parsers that use recursive descent with backup may require [[exponential time]].

A [[packrat parser]] is a modification of recursive descent with backup that avoids nontermination by remembering its choices, so as not to make exactly the same choice twice. A [[packrat parser]] runs in [[linear time]], but usually requires more space than a predictive parser.

Although predictive parsers are widely used, programmers often prefer to create [[LR parser|LR]] or [[LALR parser|LALR]] parsers via parser generators without transforming the grammar into [[LL parser|LL(k)]] form.

Some authors define the recursive descent parsers as the predictive parsers. Other authors use the term more broadly, to include backed-up recursive descent and packrat parsers.{{citationneeded}}

== Example parser ==

Line 175 ⟶ 173:

}

</pre>

== Formalizing recursive descent parsers ==

Although [[context-free grammar]]s are commonly used to [[formal|formalize]] the syntax of the language recognized by a recursive descent parser (as in the example above), an alternate and more direct way to formalize recursive descent parsing is via [[parsing expression grammar]]s, which model the structure and behavior of typical recursive descent parsers directly.

== Implementation in functional languages ==