Recursive descent parser


Recursive descent parser

A recursive descent parser is a top-down parser built from a set of mutually-recursive procedures (or a non-recursive equivalent) where each such procedure usually implements one of the production rules of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.

A predictive parser is a recursive descent parser that does not require backtracking. Predictive parsing is possible only for the class of 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(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.

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(k) grammars, but is not guaranteed to terminate unless the grammar is LL(k). Even when they terminate, parsers that use recursive descent with backup may require exponential time.

Although predictive parsers are widely used, programmers often prefer to create LR or LALR parsers via parser generators without transforming the grammar into LL(k) form.

Some authors define recursive descent parsers as the predictive parsers. Other authors use the term more broadly, to include backed-up recursive descent.

void expression(void) { if (sym = plus || sym = minus) getsym(); term(); while (sym = plus || sym = minus) { getsym(); term();

void condition(void) { if (accept(oddsym)) { expression(); } else { expression(); if (sym = eql || sym = neq || sym = lss |
sym = leq || sym = gtr || sym = geq) { getsym(); expression(); } else { error("condition: invalid operator"); getsym(); }

void statement(void) { if (accept(ident)) { expect(becomes); expression(); } else if (accept(callsym)) { expect(ident); } else if (accept(beginsym)) { do { statement(); } while (accept(semicolon)); expect(endsym); } else if (accept(ifsym)) { condition(); expect(thensym); statement(); } else if (accept(whilesym)) { condition(); expect(dosym); statement();

void block(void) { if (accept(constsym)) { do { expect(ident); expect(eql); expect(number); } while (accept(comma)); expect(semicolon); } if (accept(varsym)) { do { expect(ident); } while (accept(comma)); expect(semicolon); } while (accept(procsym)) { expect(ident); expect(semicolon); block(); expect(semicolon); } statement();}

void program(void) { getsym(); block(); expect(period);}

Implementation in functional languages

Recursive descent parsers are particularly easy to implement in functional languages such as Haskell or ML.

See [http://www.cs.nott.ac.uk/~gmh/pearl.pdf Functional Pearls: Monadic Parsing in Haskell]

See also

*JavaCC - a recursive descent parser generator
*Coco/R - a recursive descent parser generator
*ANTLR - a recursive descent parser generator
*Parsing expression grammar - another form representing recursive descent grammar
*Spirit Parser Framework - a C++ recursive descent parser generator framework requiring no pre-compile step
*Tail recursive parser - a variant of the recursive descent parser

References

* "", first edition, Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman, in particular Section 4.4.
* "Modern Compiler Implementation in Java, Second Edition", Andrew Appel, 2002, ISBN 0-521-82060-X.
* "Recursive Programming Techniques", W.H. Burge, 1975, ISBN 0-201-14450-6
* "Crafting a Compiler with C", Charles N Fischer and Richard J LeBlanc, Jr, 1991, ISBN 0-8053-2166-7.
* [http://search.cpan.org/~dconway/Parse-RecDescent-1.94/lib/Parse/RecDescent.pod Parse::RecDescent] : A versatile recursive descent Perl module.
* [http://pyparsing.sourceforge.net/ pyparsing] : A versatile recursive descent Python module.
* [http://jparsec.codehaus.org/ Jparsec] a Java port of Haskell's Parsec module.
* "Compiling with C# and Java", Pat Terry, 2005, ISBN 0-321-26360-X, 624
* "Algorithms + Data Structures = Programs", Niklaus Wirth, 1975, ISBN 0-13-022418-9
* "Compiler Construction", Jonatan Rugarn, 1996, ISBN 0-201-40353-6

External links

* [http://www.mollypages.org/page/grammar/index.mp Introduction to Parsing] - an easy to read introduction to parsing, with a comphrensive section on recursive descent parsing
* [http://teaching.idallen.com/cst8152/98w/recursive_decent_parsing.html How to turn a Grammar into C code] - a brief tutorial on implementing recursive descent parser
* [http://www.thinkanddone.com/prog/java/parser.html A parsing module written in Java] - The tool that allows parsing and evaluating mathematical expressions from within Java program


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Recursive Descent Parser — Rekursiver Abstieg (englisch: Recursive descent parser, RDP) ist eine Technik aus dem Compilerbau, die auf direkte Weise einen LL Parser implementiert. Dabei entsprechen die Nichtterminalsymbole der Grammatik Funktionsaufrufen. Siehe auch Parser… …   Deutsch Wikipedia

  • Parser combinator — In functional programming, a parser combinator is a higher order function which accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some… …   Wikipedia

  • Parser Combinator — In mathematics and functional programming, Higher Order functions (HOF) are defined as the functions that can take functions as their input and can also produce functions as their output. The use of a HOF as an infix operator in a function… …   Wikipedia

  • Operator-precedence parser — An operator precedence parser is a bottom up parser that interprets an operator precedence grammar. For example, most calculators use operator precedence parsers to convert from the human readable infix notation with order of operations format… …   Wikipedia

  • Tail recursive parser — Tail recursive parsers are derived from the more common Recursive descent parsers. Tail recursive parsers are commonly used to parse left recursive grammars. They use a smaller amount of stack space than regular recursive descent parsers. They… …   Wikipedia

  • LR parser — In computer science, an LR parser is a parser for context free grammars that reads input from Left to right and produces a Rightmost derivation. The term LR( k ) parser is also used; here the k refers to the number of unconsumed look ahead input… …   Wikipedia

  • LL parser — An LL parser is a top down parser for a subset of the context free grammars. It parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser). The class of grammars which are… …   Wikipedia

  • Spirit Parser Framework — The Spirit Parser Framework is an object oriented recursive descent parser generator framework implemented using template metaprogramming techniques. Expression templates allow users to approximate the syntax of Extended Backus Naur Form (EBNF)… …   Wikipedia

  • Packrat Parser — Ein Packrat Parser ist ein spezieller Parser, der Funktionsweise eines rekursiv absteigenden Parsers (recursive descent parser) ähnlich, der während des Parsing Prozesses die Zwischenergebnisse aller rekursiven Aufrufe behält und damit viele… …   Deutsch Wikipedia

  • Comparison of parser generators — This is a list of notable lexer generators and parser generators for various language classes. Contents 1 Regular languages 2 Deterministic context free languages 3 Parsing expression grammars, deterministic boolean grammars …   Wikipedia