Content deleted Content added
→Example parser: Made it clearer that ident and number are assumed to be terminals |
m parser link |
||
Line 1:
A '''recursive descent parser''' is a top-down [[parsing|parser]] built from a set of [[Mutual recursion|mutually-recursive]] procedures (or a non-recursive equivalent) where each such [[procedure]] usually implements one of the production rules of the [[formal grammar|grammar]]. Thus the structure of the resulting program closely mirrors that of the grammar it recognises.
A '''predictive parser''' is a recursive descent parser with no backup. Predictive parsing is possible only for the class of [[LL parser|LL(k)]] grammars, which are the context-free grammars for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input. (The [[LL parser|LL(k)]] grammars therefore exclude all ambiguous grammars, as well as all grammars that contain left recursion. Any context-free grammar can be transformed into an equivalent grammar that has no left recursion, but removal of left recursion does not always yield an [[LL parser|LL(k)]] grammar.) A predictive parser runs in [[linear time]].
Line 9:
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
== Example parser ==
| |||