Recursive descent parser

Recursive descent (English: recursive descent ) is a technique from the Compiler, (i.e., without table) a LL parser implemented in a direct manner.

Requirement is an LL (k ) grammar for the language to be parsed. The following is the frequent case is assumed.

Code for the grammar rules of a non-terminal symbol

For each non-terminal symbol of the grammar, a procedure is defined. if

With all the rules on the left side, see the procedure in pseudo-code as follows:

Proc ( )     if lookahead in then           else if lookahead in then           ...     else if lookahead in then           else       error The following applies:

• Lookahead is the current input character (or token ).
• Is the set of terminal symbols (or tokens), which may be at the beginning of a word that has been generated from one of the words in the set.
• Is the set of terminal symbols that can be generated from the start symbol in a word immediately to the right of.
• Is the code for parsing.

The amounts need to be involved here, because the empty word can contain; see LL (k ) grammar.

Code for a sequence of grammar symbols

( May be the terminals and / or nonterminals ) For consists of the code sections for in the same order.

The code for a single symbol looks like this:

• If the terminal is:

If lookahead = then     lookahead: = GetSymbol ()   else     error If nonterminal is:

() This GetSymbol is a function that returns the next input character (or token ).