Recursive descent parser: Difference between revisions

Revision as of 18:46, 7 March 2006

Revision as of 20:51, 7 March 2006

Line 3:

A '''predictive parser''' is a recursive descent parser with no backup. Predictive parsing is possible only for the class of [[LL parser|LL(k)]] grammars, which are the context-free grammars 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 parser|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 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 inrequire [[exponential time]].

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.

Line 12:

== Example parser ==

Given theThe following [[EBNF]] [[grammar]] (for [[Niklaus Wirth]]'s [[PL/0]] programming language, from

[[Algorithms + Data Structures = Programs]]) is in [[LL parser|LL(1)]] form:

<pre>

Line 46:

and ''number''). Each [[nonterminal]] is defined by a rule in the grammar.

Notice how closely the codepredictive parser below mirrors the grammar above. There is a procedure for each nonterminal in the grammar. Parsing descends in a top-down manner, until the final nonterminal has been processed. The program fragment depends on a global variable, ''sym'', which contains the next symbol from the input, and the global function ''getsym'', which updates ''sym'' when called.

<pre>