Content deleted Content added
Brynosaurus (talk | contribs) added pointer to parsing expression grammars |
Brynosaurus (talk | contribs) m fix section headers, add category |
||
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.
Consider the following [[formal grammar|grammar]] in [[Backus-Naur form|BNF]]:
Line 28:
To determine which rule should be applied in case of a certain terminal the same algorithm can be used as the one for constructing the parsing table of an [[LL parser]].
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.
Recursive descent parsers are particularly easy to implement in functional languages such as [[Haskell programming language|Haskell]]. See [http://www.cs.nott.ac.uk/~gmh/pearl.pdf Functional Pearls: Monadic Parsing in Haskell] (pdf format).
* ''Recursive Programming Techniques'', W.H. Burge, 1975, ISBN 0-201-14450-6
* The [[Dragon book]]
----
''This article (or an earlier version of it) contains material from [[FOLDOC]], used with [[Public Domain Resources/Foldoc license|permission]].''
[[Category:Parsing algorithms]]
| |||