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 recognises.
Recursive descent parsers recognize the class of LL(k) grammars for unbounded k. In less formal terms, they recognize all grammars except those that are left recursive. The running time of a recursive descent parser is 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 or 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 nonterminals. This allows these parsers to match a certain class of non-context-free languages.
| Contents |
Example parser
Consider the following grammar in BNF:
- <E> ::= NOT <E> | ( <E> <F> ) | TRUE | FALSE
- <F> ::= AND <E> | OR <E>
We define a procedure parse_A() for every nonterminal A that parses a string in the language of A. In this procedure it is first determined, with the current symbol in the input stream, which rule for the nonterminal will be used. Then it simply calls the procedures read_ch(a) and parse_A() for every terminal a and nonterminal A in the right-hand side for the rule.
procedure parse_E() {
if ch = 'N' { read_ch('N') read_ch('O') read_ch('T') parse_E() }
else if ch = '(' { read_ch('(') parse_E() parse_F() read_ch(')') }
else if ch = 'T' { read_ch('T') read_ch('R') read_ch('U') read_ch('E') }
else if ch = 'F' { read_ch('F') read_ch('A') read_ch('L') read_ch('S') read_ch('E') }
}
procedure parse_F() {
if ch = 'A' { read_ch('A') read_ch('N') read_ch('D') parse_E() }
else if ch = 'O' { read_ch('O') read_ch('R') parse_E() }
}
These procedures use a global variable ch that contains the current first character in the input stream. The procedure read_ch(a) reports an error if ch is not equal to a and otherwise reads the next character from the input stream into ch.
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.
Formalizing recursive descent parsers
Although context-free grammars are commonly used to 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 grammars, which model the structure and behavior of typical recursive descent parsers directly.
Implementation in functional languages
Recursive descent parsers are particularly easy to implement in functional languages such as Haskell. See Functional Pearls: Monadic Parsing in Haskell (http://www.cs.nott.ac.uk/~gmh/pearl.pdf) (pdf format).
References
- Recursive Programming Techniques, W.H. Burge, 1975, ISBN 0-201-14450-6
- The Dragon book
- Parse::RecDescent (http://search.cpan.org/~dconway/Parse-RecDescent-1.94/lib/Parse/RecDescent.pod): A versatile recursive descent Perl module.
- This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.