Recursive descent parser: Difference between revisions

Revision as of 17:12, 7 March 2006

Revision as of 18:38, 7 March 2006

Line 1:

A '''recursive descent parser''' is a top-down [[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.

RecursiveA '''predictive parser''' is a recursive descent parsersparser recognizewith no backup. Predictive parsing is possible only for the class of [[LL parser|LL(k)]] grammars, forwhich unboundedare ''k''.defined as In less formal terms, they recognize allthe context-free grammars exceptfor thosewhich thatthere areexists [[leftsome recursion|leftpositive recursive]].integer k Thethat running time ofallows a recursive descent parser into thedecide generalwhich caseproduction isto [[exponentialuse time|exponential]],by althoughexamining thereonly isthe anext modificationk totokens theof algorithminput. called aThe [[packratLL parser|LL(k)]] grammars therefore exclude all ambiguous grammars, whichas tradeswell memoryas forall [[lineargrammars time]]that contain left recursion. For a(Any largecontext-free classgrammar ofcan grammars,be ittransformed isinto alsoan possibleequivalent togrammar eliminatethat has no left recursion, andbut backtrackingremoval of left recursion does not always yield an [[LL parser|LL(k)]] grammar.) A predictive parser runs in [[linear time]].

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 even when the grammar is [[LL parser|LL(k)]]. Even when they terminate, parsers that use recursive descent with backup may run in [[exponential time]].

Recursive descent parsers are used less often in practice than [[LR parser|LR]] or [[LALR parser|LALR]] parsers which are easier to write using parser generators. However, recursive descent parsers have the advantage that they can pass information down to subrules, allowing for parameterized [[nonterminal]]s. This allows these parsers to match a certain class of non-[[context-free grammar|context-free]] languages.

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 may require 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 [[packrat parser|packrat parsers]] and parsers that rely on recursive descent with backup.

== Example parser ==