Tail recursive parser

<h2 id="example">Example</h2>
<p>Given an <a href="/facts/EBNF/89KI2QTe">EBNF</a> Grammar such as the following:
</p>
 E: T
 T: T { '+' F } | F
 F: F { '*' I } | I
 I: <identifier>

<p>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 <a href="/facts/Abstract_syntax_tree/73AUK1jI">abstract syntax tree</a> is:
</p>
<ol><li>Parse the next level of the grammar and get its output tree, designate it the first tree, F</li>
<li>While there is terminating token, T, that can be put as the parent of this node:
<ol><li>Allocate a new node, N</li>
<li>Set N's current operator as the current input token</li>
<li>Advance the input one token</li>
<li>Set N's left subtree as F</li>
<li>Parse another level down again and store this as the next tree, X</li>
<li>Set N's right subtree as X</li>
<li>Set F to N</li></ol></li>
<li>Return N</li></ol>
<p>A basic example of this kind of parser in <a href="/facts/C_(programming_language)/Ky2No763">C</a> is shown here. Implementation details have been omitted for simplicity.
</p>
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();
	i->left = i->right = NULL;
	i->token = cur_token();
	next_token();
	return i;
}

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/META_II/eA8GbqrX">META II</a></li></ul>
<h2 id="further-reading">Further reading</h2>
<ul><li><a href="http://www.drdobbs.com/cpp/184406384?pgno=1">Article in the January 2006 edition of Dr. Dobbs Journal, "Recursive Descent, Tail Recursion, & the Dreaded Double Divide"</a></li></ul>

Tail recursive parser open-in-new

Tail recursive parser