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

В информатике , метод рекурсивного спуска является своим родом сверху вниз парсера построенный из набора взаимно рекурсивных процедур (или нерекурсивен эквивалента) , где каждая такая процедура реализует один из нетерминалов в грамматике . Таким образом, структура полученной программы точно отражает структуру распознаваемой грамматики. [1]

Предсказание анализатора является методом рекурсивного спуска , который не требует откатов . [2] Прогнозирующий синтаксический анализ возможен только для класса грамматик LL ( k ) , которые представляют собой контекстно-свободные грамматики, для которых существует некоторое положительное целое число k, которое позволяет синтаксическому анализатору рекурсивного спуска решать, какую продукцию использовать, исследуя только следующую k токенов ввода. Таким образом, грамматики LL ( k ) исключают все неоднозначные грамматики , а также все грамматики, содержащие левую рекурсию.. Любая контекстно-свободная грамматика может быть преобразована в эквивалентную грамматику, не имеющую левой рекурсии, но удаление левой рекурсии не всегда приводит к грамматике LL ( k ). Прогнозирующий синтаксический анализатор работает за линейное время .

Рекурсивный спуск с отслеживанием с возвратом - это метод, который определяет, какое производство использовать, пробуя каждое производство по очереди. Рекурсивный спуск с возвратом не ограничивается грамматиками LL ( k ), но не гарантируется его завершение, если грамматика не является LL ( k ). Даже когда они завершаются, синтаксическим анализаторам, использующим рекурсивный спуск с возвратом, может потребоваться экспоненциальное время .

Хотя предиктивные синтаксические анализаторы широко используются и часто выбираются при написании синтаксического анализатора вручную, программисты часто предпочитают использовать синтаксический анализатор на основе таблиц, созданный генератором синтаксического анализатора [ необходима ссылка ] , либо для языка LL ( k ), либо с использованием альтернативы парсер, например LALR или LR . Это особенно верно, если грамматика не в форме LL ( k ) , поскольку требуется преобразование грамматики в LL, чтобы сделать ее пригодной для прогнозирующего синтаксического анализа. Предиктивные синтаксические анализаторы также могут быть созданы автоматически с использованием таких инструментов, как ANTLR .

Предиктивные синтаксические анализаторы могут быть изображены с помощью диаграмм переходов для каждого нетерминального символа, где границы между начальным и конечным состояниями помечены символами (терминалами и нетерминалами) правой части правила продукции. [3]

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

Следующий РБНФ -как грамматика (для Никлауса Wirth «с PL / 0 языка программирования, из структур Алгоритмов + Данные = Программа ) находится в LL (1) форме:

 программа =  блок "."  .  block =  [ "const"  identify "="  num { ","  identify "="  num }  ";" ]  [ "var"  identify { ","  identify }  ";" ]  { "  идентификатор процедуры "; "  блок ";" }  заявление .  оператор =  идент ": ="  выражение  |  "позвонить"  идент  |  "начало"  заявление { ";"  оператор }  "конец"  |  оператор "если"  условие "то"  | выражение «пока» условие «делать» .      условие =  "нечетное"  выражение  |  выражение ( "=" | "#" | "<" | "<=" | ">" | "> =" )  выражение .  выражение =  [ "+" | "-" ]  термин {( "+" | "-" )  термин }  .  термин =  фактор {( "*" | "/" )  фактор }  .  фактор =  идент  |  номер  |  "("  выражение ")"  .

Терминалы заключены в кавычки. Каждый нетерминал определяется правилом в грамматике, за исключением идентификатора и числа , которые, как предполагается, определены неявно.

Реализация C [ править ]

Ниже реализация рекурсивного спуска парсер выше языка C . Анализатор читает исходный код и завершает работу с сообщением об ошибке, если код не удается проанализировать, и завершает работу без уведомления, если код анализируется правильно.

Обратите внимание, насколько точно предиктивный синтаксический анализатор ниже отражает грамматику выше. В грамматике есть процедура для каждого нетерминала. Анализ выполняется сверху вниз, пока не будет обработан последний нетерминал. Фрагмент программы зависит от глобальной переменной sym , которая содержит текущий символ из ввода, и функции nextsym , которая обновляет sym при вызове.

Реализации функций nextsym и error опущены для простоты.

ЬурейеЕ  перечисление  { идент ,  число ,  lparen ,  rparen ,  раз ,  слэш ,  плюс ,  минус ,  EQL ,  NEQ ,  LSS ,  Leq ,  Гтп ,  GEQ ,  callsym ,  beginsym ,  точка с запятой ,  endsym ,  ifsym ,  whilesym ,  становится ,  thensym ,  Досый ,  constsym ,  запятая,  варсым ,  процым ,  период ,  оддсим }  Символ ;Символ  sym ; void  nextsym ( пустота ); недействительная  ошибка ( const  char  msg []);int  accept ( символ  s )  {  если  ( sym  ==  s )  {  nextsym ();  возврат  1 ;  }  return  0 ; }int  ожидать ( символ  s )  {  если  ( принять ( s ))  вернуть  1 ;  error ( "ожидать: неожиданный символ" );  возврат  0 ; } фактор недействительности ( недействителен )  {  если  ( принять ( идентификатор ))  {  ;  }  else  if  ( accept ( число ))  {  ;  }  else  if  ( accept ( lparen ))  {  выражение ();  ожидать ( rparen );  }  else  {  error ( "фактор: синтаксическая ошибка" );  нексцим ();  } }недействительный  срок ( недействителен )  {  фактор ();  в то время как  ( символ  ==  раз  ||  символ  ==  косая черта )  {  nextsym ();  фактор ();  } }недействительное  выражение ( void )  {  if  ( sym  ==  plus  ||  sym  ==  minus )  nextsym ();  срок ();  в то время как  ( сим  ==  плюс  ||  сим  ==  минус )  {  nextsym ();  срок ();  } }недействительное  условие ( недействительно )  {  если  ( принять ( oddsym ))  {  выражение ();  }  else  {  выражение ();  если  ( sym  ==  eql  ||  sym  ==  neq  ||  sym  ==  lss  ||  sym  ==  leq  ||  sym  ==  gtr  ||  sym  ==  geq )  {  nextsym ();  выражение ();  }  еще {  ошибка ( "условие: недопустимый оператор" );  нексцим ();  }  } }недействительный  оператор ( недействительный )  {  если  ( принять ( идентификатор ))  {  ожидать ( становится );  выражение ();  }  иначе,  если  ( принять ( callsym ))  {  ожидать ( идентификатор );  }  иначе,  если  ( принять ( начинаетсясим ))  {  делать  {  оператор ();  }  while  ( accept ( точка с запятой )); ожидать ( энсим );  }  иначе,  если  ( принять ( ifsym ))  {  условие ();  ожидать ( thensym );  заявление ();  }  else  if  ( accept ( whilesym ))  {  условие ();  ожидать ( досым );  заявление ();  }  else  {  error ( "инструкция: синтаксическая ошибка" );  нексцим ();  } }недействительный  блок ( void )  {  если  ( принять ( constsym ))  {  делать  {  ожидать ( идентификатор );  ожидать ( уравнение );  ожидать ( число );  }  пока  ( принять ( запятая ));  ожидать ( точка с запятой );  }  если  ( принять ( варсым ))  {  делать  {  ожидать ( идентификатор );  } пока  ( принять ( запятая ));  ожидать ( точка с запятой );  }  пока  ( принять ( procsym ))  {  ожидать ( идентификатор );  ожидать ( точка с запятой );  блок ();  ожидать ( точка с запятой );  }  оператор (); }недействительная  программа ( void )  {  nextsym ();  блок ();  ожидать ( период ); }

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

Некоторые генераторы парсеров рекурсивного спуска:

  • TMG - ранний компилятор-компилятор, использовавшийся в 1960-х и начале 1970-х годов.
  • JavaCC
  • Коко / Р
  • ANTLR
  • Spirit Parser Framework - структура генератора синтаксического анализатора с рекурсивным спуском C ++, не требующая предварительной компиляции
  • parboiled (Java) - библиотека синтаксического анализа PEG с рекурсивным спуском для Java

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

  • Комбинатор синтаксического анализатора - функция высшего порядка, используемая в комбинаторном синтаксическом анализе, метод факторизации конструкций синтаксического анализатора с рекурсивным спуском
  • Анализ грамматики выражений - еще одна форма, представляющая грамматику рекурсивного спуска
  • Рекурсивный восходящий парсер
  • Хвостовой рекурсивный парсер - вариант парсера рекурсивного спуска

Ссылки [ править ]

  1. ^ Бурже, WH (1975). Методы рекурсивного программирования . ISBN 0-201-14450-6.
  2. ↑ Watson, Des (22 марта 2017 г.). Практический подход к построению компилятора . Springer. ISBN 978-3-319-52789-5.
  3. ^ Ахо, Альфред В .; Сетхи, Рави; Ульман, Джеффри (1986). Составители: принципы, методы и инструменты (первое изд.). Эддисон Уэсли. п. 183 .

Общие ссылки [ править ]

  • Компиляторы: принципы, методы и инструменты , первое издание, Альфред В. Ахо, Рави Сетхи и Джеффри Д. Уллман, в частности, раздел 4.4.
  • Современная реализация компилятора на Java, второе издание , Эндрю Аппель, 2002, ISBN 0-521-82060-X . 
  • Методы рекурсивного программирования , WH Burge, 1975, ISBN 0-201-14450-6 
  • Создание компилятора с C , Чарльз Н. Фишер и Ричард Дж. Леблан-младший, 1991, ISBN 0-8053-2166-7 . 
  • Компиляция с C # и Java , Пэт Терри, 2005, ISBN 0-321-26360-X , 624 
  • Алгоритмы + структуры данных = программы , Никлаус Вирт, 1975, ISBN 0-13-022418-9 
  • Конструкция компилятора , Никлаус Вирт, 1996, ISBN 0-201-40353-6 

Внешние ссылки [ править ]

  • Введение в синтаксический анализ - легко читаемое введение в синтаксический анализ с подробным разделом, посвященным синтаксическому анализу с рекурсивным спуском.
  • Как превратить грамматику в код C - краткое руководство по реализации синтаксического анализатора рекурсивного спуска
  • Парсер простых математических выражений в Ruby
  • Простой анализ сверху вниз в Python
  • Джек В. Креншоу: « Давайте создадим компилятор» (1988–1995) на Паскале с выводом на языке ассемблера , используя подход «будь простым».
  • Функциональные жемчужины: монадический анализ в Haskell