Парсер с рекурсивным спуском - Википедия - Recursive descent parser

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Февраль 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

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

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

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

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

C реализация

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

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

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

typedef перечислить {идентификатор, номер, lparen, rparen, раз, слэш, плюс,    минус, eql, neq, lss, leq, гтп, geq, callsym, начинается, точка с запятой,    Endym, Ifsym, whilesym, становится, thensym, досым, constsym, запятая,    варсым, procsym, период, oddsym} Символ;Символ сим;пустота нексцим(пустота);пустота ошибка(const char сообщение[]);int принимать(Символ s) {    если (сим == s) {        нексцим();        возвращаться 1;    }    возвращаться 0;}int ожидать(Символ s) {    если (принимать(s))        возвращаться 1;    ошибка("ожидать: неожиданный символ");    возвращаться 0;}пустота фактор(пустота) {    если (принимать(идентификатор)) {        ;    } еще если (принимать(номер)) {        ;    } еще если (принимать(lparen)) {        выражение();        ожидать(rparen);    } еще {        ошибка("фактор: синтаксическая ошибка");        нексцим();    }}пустота срок(пустота) {    фактор();    пока (сим == раз || сим == слэш) {        нексцим();        фактор();    }}пустота выражение(пустота) {    если (сим == плюс || сим == минус)        нексцим();    срок();    пока (сим == плюс || сим == минус) {        нексцим();        срок();    }}пустота условие(пустота) {    если (принимать(oddsym)) {        выражение();    } еще {        выражение();        если (сим == eql || сим == neq || сим == lss || сим == leq || сим == гтп || сим == geq) {            нексцим();            выражение();        } еще {            ошибка(«условие: недопустимый оператор»);            нексцим();        }    }}пустота утверждение(пустота) {    если (принимать(идентификатор)) {        ожидать(становится);        выражение();    } еще если (принимать(callsym)) {        ожидать(идентификатор);    } еще если (принимать(начинается)) {        делать {            утверждение();        } пока (принимать(точка с запятой));        ожидать(Endym);    } еще если (принимать(ифсим)) {        условие();        ожидать(thensym);        утверждение();    } еще если (принимать(whilesym)) {        условие();        ожидать(досым);        утверждение();    } еще {        ошибка("инструкция: синтаксическая ошибка");        нексцим();    }}пустота блокировать(пустота) {    если (принимать(constsym)) {        делать {            ожидать(идентификатор);            ожидать(eql);            ожидать(номер);        } пока (принимать(запятая));        ожидать(точка с запятой);    }    если (принимать(варсым)) {        делать {            ожидать(идентификатор);        } пока (принимать(запятая));        ожидать(точка с запятой);    }    пока (принимать(procsym)) {        ожидать(идентификатор);        ожидать(точка с запятой);        блокировать();        ожидать(точка с запятой);    }    утверждение();}пустота программа(пустота) {    нексцим();    блокировать();    ожидать(период);}

Примеры

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

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

Смотрите также

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

Рекомендации

Общие ссылки

• Компиляторы: принципы, методы и инструменты, первое издание, Альфред В. Ахо, Рави Сетхи и Джеффри Д. Ульман, в частности Раздел 4.4.
• Современная реализация компилятора на Java, второе издание, Эндрю Аппель, 2002, ISBN  0-521-82060-X.
• Рекурсивные методы программирования, W.H. Бердж, 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 - краткое руководство по реализации парсера рекурсивного спуска
• Парсер простых математических выражений в Рубин
• Простой синтаксический анализ сверху вниз в Python
• Джек В. Креншоу: Создадим компилятор (1988-1995), в Паскаль, с язык ассемблера вывод, используя подход "будь простым"
• Функциональные жемчужины: монадический анализ в Haskell