Синтаксический анализатор рекурсивного спуска

редактировать

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

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

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

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

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

Содержание

  • 1 Пример синтаксического анализатора
    • 1.1 Реализация C
  • 2 Примеры
  • 3 См. также
  • 4 Ссылки
  • 5 Внешние links

Пример парсера

Следующая EBNF -подобная грамматика (для Niklaus Wirth PL / 0 язык программирования из Алгоритмы + Структуры данных = Программы ) находится в формате LL (1) :

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

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

Реализация C

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

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

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

typedef enum {идентификатор, число, lparen, rparen, times, косая черта, плюс, минус, eql, neq, lss, leq, gtr, geq, callsym, beginym, точка с запятой, endym, ifsym, whilesym, становится, thensym, dosym, constsym, comma, varsym, procsym, точка, oddsym} Символ; Символ sym; void nextsym (пустота); недействительная ошибка (const char msg); int accept (символ s) {если (sym == s) {nextsym (); возврат 1; } return 0; } int ожидать (символ s) {if (accept (s)) return 1; error ("ожидать: неожиданный символ"); возврат 0; } фактор недействительности (недействителен) {если (принять (идентификатор)) {; } иначе, если (принять (число)) {; } 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)) {условие (); ожидать (сим); заявление(); } else if (accept (whilesym)) {условие (); ожидать (досым); заявление(); } else {error ("инструкция: синтаксическая ошибка"); нексцим (); }} блок void (void) {если (принять (constsym)) {делать {ожидать (идентификатор); ожидать (eql); ожидать (число); } пока (принять (запятая)); ожидать (точка с запятой); } если (принять (варсым)) {делать {ожидать (идентификатор); } пока (принять (запятая)); ожидать (точка с запятой); } пока (принять (procsym)) {ожидать (идентификатор); ожидать (точка с запятой); блок (); ожидать (точка с запятой); } заявление(); } недействительная программа (void) {nextsym (); блок (); ожидать (период); }

Примеры

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

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

См. Также

Ссылки

Внешние ссылки

Последняя правка сделана 2021-06-03 10:34:00
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте