Парсер рекурсивного спуска

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

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

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

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

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

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

Следующая 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

См. также

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

Ссылки

Общие ссылки

• Составители: Принципы, методы и инструменты , первое издание, Альфред В. Ахо, Рави Сетхи и Джеффри Д. Ульман, в частности раздел 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) на языке Паскаль с выводом на ассемблере , используя подход «сохранять простоту».