Хвостовой рекурсивный парсер

В информатике анализаторы хвостовой рекурсии являются производными от более распространенных анализаторов рекурсивного спуска . Синтаксические анализаторы хвостовой рекурсии обычно используются для анализа леворекурсивных грамматик. Они используют меньший объем стекового пространства, чем обычные анализаторы рекурсивного спуска. Их также легко писать. Типичные анализаторы рекурсивного спуска делают невозможным анализ леворекурсивных грамматик (из-за проблемы бесконечного цикла). Синтаксические анализаторы хвостовой рекурсии используют технику переподчинения узлов, которая делает это допустимым.

Пример

Учитывая грамматику EBNF, например следующую:

 E: T
 T: T { '+' F } | F
 F: F { '*' I } | I
 I: <identifier>

Простой анализатор хвостовой рекурсии может быть написан так же, как анализатор рекурсивного спуска. Типичный алгоритм анализа подобной грамматики с использованием абстрактного синтаксического дерева :

1. Разберите следующий уровень грамматики и получите выходное дерево, назовите его первым деревом F.
2. Хотя существует завершающий токен T , который можно поместить в качестве родительского узла этого узла:
   1. Выделить новый узел, N
   2. Установить текущий оператор N в качестве текущего входного токена
   3. Продвинуть ввод на один токен
   4. Установите как левое поддерево N F
   5. Снова проанализируйте еще один уровень и сохраните его как следующее дерево, X.
   6. Установить как правое поддерево N X
   7. Установите F на N
3. Вернуть Н

базовый пример такого типа парсера на языке C. Здесь показан Детали реализации опущены для простоты.

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;
}

См. также

• МЕТА II

Дальнейшее чтение

• Статья в журнале Dr. Dobbs Journal за январь 2006 г. «Рекурсивный спуск, хвостовая рекурсия и ужасное двойное деление»