Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Пример [ править ]

Учитывая Грамматику 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 ; структура  _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 (); вернуть  я ; }

См. Также [ править ]

Дальнейшее чтение [ править ]