Encyclopedia > Recursive descent parser

  Article Content

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.

Example

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()
  begin
    if ch = 'N' then read_ch('N'); read_ch('O'); read_ch('T'); parse_E(); end-if;
    if ch = '(' then parse_E(); parse_F(); read_ch(')'); end-if;
    if ch = 'T' then read_ch('T'); read_ch('R'); read_ch('U'); read_ch('E'); end-if;
    if ch = 'F' then read_ch('F'); read_ch('A'); read_ch('L'); read_ch('S'); read_ch('E'); end-if;
  end

  procedure parse_F()
  begin
    if ch = 'A' then read_ch('A'); read_ch('N'); read_ch('D'); parse_E(); end-if;
    if ch = 'O' then read_ch('O'); read_ch('R'); parse_E(); end-if;
  end

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.

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


This article (or an earlier version of it) contains material from FOLDOC, used with permission.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Museums in England

... Museum, Bamburgh Northumberland Fusiliers Museum[?] in Alnwick Castle Oxford Ashmolean Museum Pitt Rivers Museum[?] Staffordshire Brindley Water Museum[?], ...

 
 
 
This page was created in 25.4 ms