Recursive descent parser: Difference between revisions

Revision as of 09:09, 14 November 2018

Revision as of 18:10, 29 November 2018

Line 1:

{{More footnotes|date=February 2009}}

In [[computer science]], a '''recursive descent parser''' is a kind of [[top-down parsing|top-down parser]] built from a set of [[mutual recursion|mutually recursive]] procedures (or a non-recursive equivalent) where each such [[procedure (computer science)|procedure]] usually implements one of the [[ProductionTerminal and (computernonterminal science)symbols|productionsnonterminals]] of the [[formal grammar|grammar]]. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.<ref>{{cite book | title=Recursive Programming Techniques | author=Burge, W.H. | year=1975 | isbn=0-201-14450-6}}</ref>

A ''predictive parser'' is a recursive descent parser that does not require [[backtracking]]. Predictive parsing is possible only for the class of [[LL parser|LL(''k'')]] grammars, which are the [[context-free grammar]]s 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(''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(''k'') grammar. A predictive parser runs in [[linear time]].