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

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

Пример

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

 E: Т Т: Т { '+' F } | F F: F { '*' я } | я я: <идентификатор>

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

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

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

typedef структура _exptree Exptree;структура _exptree {	char жетон;	Exptree *оставили;	Exptree *верно;};Exptree *parse_e(пустота){	возвращаться parse_t();}Exptree *parse_t(пустота){	Exptree *first_f = parse_f();		пока (cur_token() == '+') {		Exptree *replace_tree = alloc_tree();		replace_tree->жетон = cur_token();		replace_tree->оставили = first_f;		next_token();		replace_tree->верно = parse_f();		first_f = replace_tree;	}	возвращаться first_f;}Exptree *parse_f(пустота){	Exptree *сначала я = parse_i();		пока (cur_token() == '*') {		Exptree *replace_tree = alloc_tree();		replace_tree->жетон = cur_token();		replace_tree->оставили = сначала я;		next_token();		replace_tree->верно = parse_i();		сначала я = replace_tree;	}		возвращаться сначала я;}Exptree *parse_i(пустота){	Exptree *я = alloc_tree();	я->оставили = я->верно = НОЛЬ;	я->жетон = cur_token();	next_token();	возвращаться я;}

Смотрите также

• МЕТА II

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

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