Хвостовой рекурсивный синтаксический анализатор

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

Для EBNF Грамматика, например:

E: T T: T {'+' F} | F F: F {'*' I} | I I: 

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

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

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

typedef struct _exptree exptree; struct _exptree {символ символа; exptree * left; exptree * right; }; exptree * parse_e (недействительно) {return parse_t (); } exptree * parse_t (недействительно) {exptree * first_f = parse_f (); в то время как (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 (недействительно) {exptree * first_i = parse_i (); в то время как (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; я->токен = cur_token (); next_token (); вернуть я; }

• META II

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