PackCC - PackCC

PackCC
Разработчики) Арихиро Ёсида
Написано в C
Операционная система Кроссплатформенность
Тип Генератор парсеров
Лицензия Лицензия MIT
Интернет сайт github .com / arithy / packcc

PackCC является генератор синтаксических анализаторов для C . Его основные особенности заключаются в следующем:

Грамматика выходного синтаксического анализатора может быть описана в PEG (Parsing Expression Grammar). PEG - это язык синтаксического анализа сверху вниз , который похож на грамматику регулярных выражений . По сравнению с языком анализа снизу вверх, таким как язык Yacc , PEG гораздо более интуитивно понятен и не может быть двусмысленным. PEG не требует, чтобы токенизация была отдельным шагом, и правила токенизации могут быть записаны так же, как и любые другие правила грамматики.

Сгенерированный синтаксический анализатор может очень эффективно анализировать входные данные с помощью анализа пакетов. Парсинг packrat - это алгоритм рекурсивного спуска , который ускоряется с помощью мемоизации . Используя синтаксический анализ packrat, любой ввод можно анализировать за линейное время. Однако без него результирующий синтаксический анализатор мог бы демонстрировать экспоненциальную временную производительность в худшем случае из-за неограниченной возможности упреждающего просмотра.

В отличие от обычных парсеров Packrat, PackCC может поддерживать прямые и косвенные левые рекурсии правила грамматики. Это делает правила грамматики более интуитивно понятными.

Сгенерированный код украшен и максимально прост для понимания. Фактически, он использует много операторов goto, но потоки управления гораздо более отслеживаемы, чем штормы goto спагетти, генерируемые некоторыми другими генераторами парсеров.

Сам PackCC находится под лицензией MIT, но сгенерированный код может распространяться по любой лицензии или использоваться в проприетарном программном обеспечении.

Пример входного файла

Калькулятор настольный. Обратите внимание, что включены леворекурсивные грамматические правила. 

%prefix "calc"

statement <- _ e:expression _ EOL { printf("answer=%d\n", e); }
           / ( !EOL . )* EOL      { printf("error\n"); }

expression <- e:term { $$ = e; }

term <- l:term _ '+' _ r:factor { $$ = l + r; }
      / l:term _ '-' _ r:factor { $$ = l - r; }
      / e:factor                { $$ = e; }

factor <- l:factor _ '*' _ r:unary { $$ = l * r; }
        / l:factor _ '/' _ r:unary { $$ = l / r; }
        / e:unary                  { $$ = e; }

unary <- '+' _ e:unary { $$ = +e; }
       / '-' _ e:unary { $$ = -e; }
       / e:primary     { $$ = e; }

primary <- < [0-9]+ >               { $$ = atoi($1); }
         / '(' _ e:expression _ ')' { $$ = e; }

_      <- [ \t]*
EOL    <- '\n' / '\r\n' / '\r' / ';'

%%
int main() {
    calc_context_t *ctx = calc_create(NULL);
    while (calc_parse(ctx, NULL));
    calc_destroy(ctx);
    return 0;
}

Ноты

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