Content deleted Content added
Jan Hidders (talk | contribs) |
speed -> lack of speed |
||
Line 3:
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 is [[exponential time|exponential]], although there is a modification to the algorithm called a [[packrat parser]], which trades memory for [[linear time]].
Recursive descent parsers are used less often in practice than [[LR parser|LR]] or [[LALR parser|LALR]] parsers because of their lack of speed. 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 ==
| |||