Парсер рекурсивного спуска
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( февраль 2009 г. ) |
В информатике парсер рекурсивного спуска — это своего рода парсер сверху вниз, набора взаимно рекурсивных процедур (или нерекурсивного эквивалента), где каждая такая процедура реализует один из нетерминалов грамматики построенный из . Таким образом, структура полученной программы точно отражает структуру распознаваемой ею грамматики. [1] [2]
— Прогнозирующий анализатор это анализатор с рекурсивным спуском, который не требует обратного отслеживания . [3] Прогнозирующий синтаксический анализ возможен только для класса LL( k ) грамматик, которые являются контекстно-свободными грамматиками , для которых существует некоторое положительное целое число k , которое позволяет анализатору рекурсивного спуска решить, какую продукцию использовать, проверяя только следующие k токенов вход. Поэтому грамматики LL( k ) исключают все неоднозначные грамматики , а также все грамматики, содержащие левую рекурсию . Любая контекстно-свободная грамматика может быть преобразована в эквивалентную грамматику, не имеющую левой рекурсии, но удаление левой рекурсии не всегда дает LL( k ) грамматику. Прогнозирующий анализатор работает в линейном времени .
Рекурсивный спуск с обратным отслеживанием — это метод, который определяет, какую продукцию использовать, путем последовательной проверки каждой продукции. Рекурсивный спуск с обратным отслеживанием не ограничивается грамматиками LL( k ), но не гарантируется его завершение, если только грамматика не является LL( k ). Даже после завершения работы синтаксическим анализаторам, использующим рекурсивный спуск с возвратом, может потребоваться экспоненциальное время .
Хотя прогнозные парсеры широко используются и часто выбираются при написании парсера вручную, программисты часто предпочитают использовать парсер на основе таблиц, создаваемый генератором синтаксического анализатора . [ нужна ссылка ] либо для языка LL( k ), либо с использованием альтернативного синтаксического анализатора, такого как LALR или LR . Это особенно актуально, если грамматика не находится в форме LL( k ) , поскольку требуется преобразование грамматики в LL, чтобы сделать ее пригодной для прогнозного анализа. Прогнозирующие парсеры также можно создавать автоматически с помощью таких инструментов, как ANTLR .
Прогнозирующие анализаторы можно изобразить с помощью диаграмм переходов для каждого нетерминального символа, где границы между начальным и конечным состояниями помечены символами (терминалами и нетерминалами) правой части производственного правила. [4]
Пример парсера
[ редактировать ]Следующая EBNF -подобная грамматика (для Никлауса Вирта из книги PL/0 языка программирования «Алгоритмы + структуры данных = программы ») представлена в LL(1) форме :
program = block "." .
block =
["const" ident "=" number {"," ident "=" number} ";"]
["var" ident {"," ident} ";"]
{"procedure" ident ";" block ";"} statement .
statement =
ident ":=" expression
| "call" ident
| "begin" statement {";" statement } "end"
| "if" condition "then" statement
| "while" condition "do" statement .
condition =
"odd" expression
| expression ("="|"#"|"<"|"<="|">"|">=") expression .
expression = ["+"|"-"] term {("+"|"-") term} .
term = factor {("*"|"/") factor} .
factor =
ident
| number
| "(" expression ")" .
Терминалы выражаются в кавычках. Каждый нетерминал определяется правилом грамматики, за исключением ident и Number , которые считаются определенными неявно.
C-реализация
[ редактировать ]Далее следует реализация парсера рекурсивного спуска для вышеуказанного языка C. на Анализатор считывает исходный код и завершает работу с сообщением об ошибке, если код не удается проанализировать, и завершает работу автоматически, если код анализируется правильно.
Обратите внимание, насколько точно предиктивный парсер ниже отражает грамматику выше. Для каждого нетерминала в грамматике существует процедура. Анализ осуществляется сверху вниз до тех пор, пока не будет обработан последний нетерминал. Фрагмент программы зависит от глобальной переменной sym , которая содержит текущий входной символ, и функции nextsym , которая обновляет sym при вызове.
Реализации функций nextsym и error для простоты опущены.
typedef enum {ident, number, lparen, rparen, times, slash, plus,
minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
varsym, procsym, period, oddsym} Symbol;
Symbol sym;
void nextsym(void);
void error(const char msg[]);
int accept(Symbol s) {
if (sym == s) {
nextsym();
return 1;
}
return 0;
}
int expect(Symbol s) {
if (accept(s))
return 1;
error("expect: unexpected symbol");
return 0;
}
void factor(void) {
if (accept(ident)) {
;
} else if (accept(number)) {
;
} else if (accept(lparen)) {
expression();
expect(rparen);
} else {
error("factor: syntax error");
nextsym();
}
}
void term(void) {
factor();
while (sym == times || sym == slash) {
nextsym();
factor();
}
}
void expression(void) {
if (sym == plus || sym == minus)
nextsym();
term();
while (sym == plus || sym == minus) {
nextsym();
term();
}
}
void condition(void) {
if (accept(oddsym)) {
expression();
} else {
expression();
if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {
nextsym();
expression();
} else {
error("condition: invalid operator");
nextsym();
}
}
}
void statement(void) {
if (accept(ident)) {
expect(becomes);
expression();
} else if (accept(callsym)) {
expect(ident);
} else if (accept(beginsym)) {
do {
statement();
} while (accept(semicolon));
expect(endsym);
} else if (accept(ifsym)) {
condition();
expect(thensym);
statement();
} else if (accept(whilesym)) {
condition();
expect(dosym);
statement();
} else {
error("statement: syntax error");
nextsym();
}
}
void block(void) {
if (accept(constsym)) {
do {
expect(ident);
expect(eql);
expect(number);
} while (accept(comma));
expect(semicolon);
}
if (accept(varsym)) {
do {
expect(ident);
} while (accept(comma));
expect(semicolon);
}
while (accept(procsym)) {
expect(ident);
expect(semicolon);
block();
expect(semicolon);
}
statement();
}
void program(void) {
nextsym();
block();
expect(period);
}
Примеры
[ редактировать ]Некоторые генераторы парсеров рекурсивного спуска:
- TMG - ранний компилятор-компилятор, использовавшийся в 1960-х и начале 1970-х годов.
- JavaCC
- Коко/Р
- АНТЛР
- Spirit Parser Framework - платформа генератора синтаксического анализатора рекурсивного спуска C ++, не требующая этапа предварительной компиляции.
- пропаренный (Java) рекурсивного спуска - библиотека синтаксического анализа PEG для Java
См. также
[ редактировать ]- Комбинатор синтаксического анализа - функция более высокого порядка, используемая при комбинаторном анализе, метод факторизации конструкций синтаксического анализатора рекурсивного спуска.
- Грамматика синтаксического анализа - еще одна форма, представляющая грамматику рекурсивного спуска.
- Рекурсивный парсер восхождения
- Синтаксический анализатор хвостовой рекурсии - вариант парсера рекурсивного спуска.
Ссылки
[ редактировать ]- ^ Эта статья основана на материалах, взятых из Recursive+descent+parser в Бесплатном онлайн-словаре вычислительной техники до 1 ноября 2008 г. и включенных в соответствии с условиями «повторного лицензирования» GFDL версии 1.3 или более поздней.
- ^ Бердж, штат Вашингтон (1975). Методы рекурсивного программирования . ISBN 0-201-14450-6 .
- ^ Уотсон, Дес (22 марта 2017 г.). Практический подход к построению компилятора . Спрингер. ISBN 978-3-319-52789-5 .
- ^ Ахо, Альфред В .; Сетхи, Рави; Ульман, Джеффри (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
Внешние ссылки
[ редактировать ]- Джек В. Креншоу: Давайте построим компилятор (1988–1995) на языке Паскаль с выводом на ассемблере , используя подход «сохранять простоту».