В информатике , хвостовые рекурсивные парсеры являются выводом из наиболее распространенных рекурсивных спускаемых анализаторов . Хвостовые рекурсивные парсеры обычно используются для анализа леворекурсивных грамматик. Они используют меньший объем стека, чем обычные парсеры с рекурсивным спуском. Их также легко писать. Типичные парсеры рекурсивного спуска делают невозможным анализ леворекурсивных грамматик (из-за проблемы с бесконечным циклом). Хвостовые рекурсивные синтаксические анализаторы используют технику репартинга узлов, которая делает это допустимым.
Пример [ править ]
Учитывая Грамматику EBNF, такую как:
E : T T : T { '+' F } | F F : F { '*' I } | I I : < идентификатор >
Простой хвостовой рекурсивный синтаксический анализатор можно написать так же, как и синтаксический анализатор с рекурсивным спуском. Типичный алгоритм анализа такой грамматики с использованием абстрактного синтаксического дерева :
- Проанализируйте следующий уровень грамматики и получите его выходное дерево, обозначьте его первым деревом, F
- Пока есть завершающий токен T , который можно использовать как родительский для этого узла:
- Выделите новый узел, N
- Установить текущий оператор N как текущий токен ввода
- Переместить ввод на один токен
- Установите левое поддерево N как F
- Снова проанализируйте другой уровень и сохраните его как следующее дерево, X
- Установить правое поддерево N как X
- Установите F на N
- Возврат N
Здесь показан базовый пример синтаксического анализатора этого типа на языке C. Детали реализации опущены для простоты.
typedef struct _exptree exptree ; структура _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 -> токен = 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 -> токен = 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 * я = alloc_tree (); i -> left = i -> right = NULL ; я -> токен = cur_token (); next_token (); вернуть я ; }