Recursive descent parser: Difference between revisions

Revision as of 15:37, 10 August 2002

Revision as of 11:40, 13 August 2002

Line 1:

A '''recursive descent parser''' is a top-down [[parser]] built from a set of [[Mutual recursion|mutually-recursive]] procedures or a non-recursive equivalent where each such [[procedure]] usually implements one of the productionsproduction rules of the [[formal grammar|grammar]]. Thus the structure of the resulting program closely mirrors that of the grammar it recognises.

=== Example ===

Consider the following [[formal grammar|grammar]] in [[BNF]]:

: <E> ::= NOT <E> | ( <E> <F> ) | TRUE | FALSE

: <F> ::= AND <E> | OR <E>

We define a procedure <tt>parse_''A''()</tt> 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 <tt>read_ch(''a'')</tt> and <tt>parse_''A''()</tt> 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 <tt>read_ch(''a'')</tt> 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]].

=== References ===