В информатике , метод рекурсивного спуска является своим родом сверху вниз парсера построенный из набора взаимно рекурсивных процедур (или нерекурсивен эквивалента) , где каждая такая процедура реализует один из нетерминалов в грамматике . Таким образом, структура полученной программы точно отражает структуру распознаваемой грамматики. [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 (); выражение (); } else { ошибка ( "условие: недопустимый оператор" ); нексцим (); } } }недействительный оператор ( недействительный ) { если ( принять ( идентификатор )) { ожидать ( становится ); выражение (); } иначе, если ( принять ( 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
Смотрите также
- Комбинатор синтаксического анализатора - функция высшего порядка, используемая в комбинаторном синтаксическом анализе, метод факторизации конструкций синтаксического анализатора с рекурсивным спуском
- Анализ грамматики выражений - еще одна форма, представляющая грамматику рекурсивного спуска
- Рекурсивный восходящий парсер
- Хвостовой рекурсивный парсер - вариант парсера рекурсивного спуска
Рекомендации
- ^ Бурже, WH (1975). Методы рекурсивного программирования . ISBN 0-201-14450-6.
- ^ Уотсон, Дес (22 марта 2017 г.). Практический подход к построению компилятора . Springer. ISBN 978-3-319-52789-5.
- ^ Ахо, Альфред В .; Сетхи, Рави; Ульман, Джеффри (1986). Составители: принципы, методы и инструменты (первое изд.). Эддисон Уэсли. п. 183 . CS1 maint: обескураженный параметр ( ссылка )
Общие ссылки
- Компиляторы: принципы, методы и инструменты , первое издание, Альфред В. Ахо, Рави Сетхи и Джеффри Д. Уллман, в частности, раздел 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