Tail Recursive Parser - AbsoluteAstronomy.com

Tail recursive parsers are derived from the more common Recursive descent parser

Recursive descent parser

A recursive descent parser is a top-down parser built from a set of mutually-recursive procedures where each such procedure usually implements one of the production rules of the grammar...

s. Tail recursive parsers are commonly used to parse left recursive grammars. They use a smaller amount of stack space than regular recursive descent parsers. They are also easy to write. Typical recursive descent parsers make parsing left recursive grammars impossible (because of an infinite loop problem). Tail recursive parsers use a node reparenting technique that makes this allowable. Given an EBNF Grammar such as the following:
E: T
T: T ('+' F)* | F
F: F ('*' I)* | I
I:
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

Abstract syntax tree

In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...

is:

Parse the next level of the grammar and get its output tree, designate it the first tree, F
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
Return N

A C programming language implementation of this parser is shown here:

typedef struct _exptree exptree;
struct _exptree {
char token;
exptree *left;
exptree *right;
};

exptree *parse_e(void)
{
return parse_t;
}

exptree *parse_t(void)
{
exptree *first_f = parse_f;

while(cur_token '+') {
exptree *replace_tree = alloc_tree;
replace_tree->token = cur_token;
replace_tree->left = first_f;
next_token;
replace_tree->right = parse_f;
first_f = replace_tree;
}

return first_f;
}

exptree *parse_f(void)
{
exptree *first_i = parse_i;

while(cur_token '*') {
exptree *replace_tree = alloc_tree;
replace_tree->token = cur_token;
replace_tree->left = first_i;
next_token;
replace_tree->right = parse_i;
first_i = replace_tree;
}

return first_i;
}

exptree *parse_i(void)
{
exptree *i = alloc_tree;
exptree->left = exptree->right = NULL;
exptree->token = cur_token;
next_token;
return i;
}

Further reading