Tail recursive parser

Tail Recursive Parser

A Tail Recursive Parser is on that uses a tail recursive parsing technique, it is an alternative to complex bottom-up parsers. Tail Recursive Parsing is a method of parsing a Context Free Grammar, it is usually used in a Compiler for semantic analysis of a source program. Tail Recursive parsers are typically used because they can be easily written (given their closeness to Recursive Descent parsers), and use little stack space. Given a EBNF Grammar such as the following:

E: T
T: T ('+' F)* | F
F: I ('*' I)* | I
I: <identifier>

A simple tail recursive parser can be written much like a Recursive Descent parser. The typical algorithm for parsing a grammar like this using an Abstract Syntax Tree is:

1. Parse the next level of the grammar and get its output tree, designate it the first tree, F
2. While there is terminating token, T, that can be put as the parent of this node:
   1. Allocate a new node, N
   2. Set N's current operator as the current input token
   3. Advance the input one token
   4. Set N's left subtree as F
   5. Parse another level down again and store this as the next tree, X
   6. Set N's right subtree as X
   7. Set F to N
3. Return N