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

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

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

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

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

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

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

Следующий РБНФ -как грамматика (для Никлауса Wirth «с PL / 0 языка программирования, из структур Алгоритмов + Данные = Программа ) находится в LL (1) форме: 

 program = block "." .
 
 block =
     ["const" ident "=" num {"," ident "=" num} ";"]
     ["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 ")" .

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

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
  • Коко / Р
  • ANTLR
  • Spirit Parser Framework - структура генератора синтаксического анализатора с рекурсивным спуском C ++, не требующая предварительной компиляции
  • parboiled (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

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