Recursive descent parser: Difference between revisions

Revision as of 20:37, 12 August 2005

Revision as of 07:57, 20 October 2005

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.

Recursive descent parsers recognize the class of [[LL parser|LL(k)]] grammars for unbounded ''k''. In less formal terms, they recognize all grammars except those that are [[left recursion|left recursive]]. The running time of a recursive descent parser in the general case is [[exponential time|exponential]], although there is a modification to the algorithm called a [[packrat parser]], which trades memory for [[linear time]]. For a large class of grammars, it is also possible to eliminate left recursion and backtracking.

Recursive descent parsers are used less often in practice than [[LR parser|LR]] or [[LALR parser|LALR]] parsers becausewhich ofare theireasier lackto ofwrite speedusing 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.

== Example parser ==