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

Исторически, основными генераторами являлись lex и позднее flex для лексических анализаторов и yacc и позднее bison для синтаксических анализаторов. И lex/flex, и yacc/bison в основном генерируют код на языке C. lex/flex для лексического анализа используют детерминированные конечные автоматы, yacc/bison генерируют синтаксические анализаторы по методу LALR.

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

Отдельно стоит упомянуть генератор лексических и синтаксических анализаторов ANTLR4. ANTLR4 написан на Java, и позволяет генерировать анализаторы (на момент написания) на следующих языках:

Java
C#
Python (2 и 3)
JavaScript
Go
C++
Swift
PHP

ANTLR4 использует подход LL(*) для синтаксического анализа. Это вариант алгоритма LL, допускающий предпросмотр произвольной длины на основе регулярных выражений, т.е. выбор очередной продукции производится сопоставлением потока токенов с регулярным выражением. LL(*) является мощным подходом, и способен разбирать языки, не являющиеся LR(k)-языками. Однако, LR(k) разбирает некоторые языки, не являющиеся LL(*)-языками, соответственно в общем случае нельзя сказать, что какой-то из этих подходов заведомо более мощный. Вообще, LL(*) не может обрабатывать грамматики с левой рекурсией, но, как мы видели в лекции 9, левую рекурсию можно устранить алгоритмически (хотя это может приводить к быстрому росту размера грамматики). ANTLR4 может обрабатывать многие леворекурсивные грамматики, преобразуя их в нелеворекурсивную форму автоматически.

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

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

Рассмотрим, например, как может выглядеть код для рассмотренной в предыдущей работе грамматики

E -> E + T | E - T | T
T -> T * F | T / F | F
F -> V ^ F | V
V -> ( E ) | id | number | - V

Описание этой грамматики в формате, близком к синтаксису yacc, будет иметь вид

E : E '+' T   { $$ = new BinOp('+', $1, $3); }
  | E '-' T   { $$ = new BinOp('-', $1, $3); }
  | T         { $$ = $1; }
T : T '*' F   { $$ = new BinOp('*', $1, $3); }
  | T '/' F   { $$ = new BinOp('/', $1, $3); }
  | F         { $$ = $1; }
F : V '^' F   { $$ = new BinOp('^', $1, $3); }
  | V         { $$ = $1; }
V : '(' E ')' { $$ = $2; }
  | id        { $$ = new Identifier($1); }
  | number    { $$ = new Number($1); }
  | '-' V     { $$ = new Negate($2); }

Вместо символа -> в такой записи используется символ :. Символы, обозначающие терминалы, берутся в одинарные кавычки. В остальном синтаксис аналогичный определению грамматики. В фигурных скобках записываются семантические действия, которые в данном случае представляют собой код на C++. $$ обозначает заголовок соответствующей продукции, $1, $2 и т.д. – ссылки на соответствующий элемент тела данной продукции. Эти метапеременные при генерации кода анализатора будут заменены на конкретные идентификаторы, в остальном код будет вставлен без изменений.

Так, например, выражение $$ = new BinOp('*', $1, $3); для продукции T : T '*' F означает, что семантическое значение нетерминала T, которому при разборе ставится в соответствие тело T * F, будет иметь семантическое значение указателя на экземпляр класса BinOp, сконструированный с аргументами '*' (символ *), и семантическими значениями входящих в тело продукции T (первый символ в теле продукции, $1) и F (третий символ в теле продукции, $3).

ALPACA

В рамках данной работы, для примера будет использоваться написанный специально для этого курса простой генератор лексических и синтаксических анализаторов (исходные коды и бинарные файлы доступны для загрузки по адресу https://github.com/lierdakil/parser-generator/releases). На момент написания, поддерживаются языки C++ и Python, и генерация синтаксических анализаторов методами рекурсивного спуска, LL(1), LR(0), LR(1), SLR(1) и LALR(1).

Программа-генератор, далее называемая ALPACA, представляет из себя программу командной строки. По ключу -h выводится справка. Различными ключами можно настроить называния класса и файлов синтаксического анализатора, выбрать целевой язык и метод синтаксического анализа. Аргументом программа принимает путь к файлу описания лексики и грамматики.

Описание лексики отделяется от описания грамматики строкой %%. Описание лексики вводится в формате

token_id /regexp/ { token_value } :: type

где token_id – это опциональный идентификатор токена, а token_value – опциональный код, определяющий семантическое значение токена. Если token_id не указан, то символы, соответствующие регулярному выражению, будут пропускаться без создания токена.

type обозначает тип значения в целевом языке; используется только для C++, в прочих случаях :: type можно опустить.

В коде token_value можно использовать переменную text, соответствующую части входного потока, совпавшую с шаблоном лексемы.

Например, следующее описание соответствует лексике целых неотрицательных чисел, для которых создаётся токен с именем int и атрибутом, содержащим совпавший с шаблоном текст:

number /[0-9]+/ text
/ +/

Имена токенов должны начинаться с маленькой буквы. Допустимые символы в названии токена – латинские буквы, цифры и символ подчёркивания.

Описание грамматики следует после строки “%%”. Синтаксис описания грамматики повторяет формальный синтаксис. Названия нетерминалов должны начинаться с заглавной буквы, названия терминалов – с маленькой. Для терминалов должны использоваться те же имена, что и в определении лексики. Список определений альтернатив для нетерминала должен завершаться символом ; (точка с запятой). Альтернативы разделяются символом |, заголовок отделяется от альтернатив любой из последовательностей ->, ::=, :=, =, :. Например, следующее определение определяет язык, включающий одинаковое количество символов a и b (пробелы игнорируются)

a /a/
b /b/
/ +/

%%

S -> a S b
   |
   ;

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

num /[0-9]+/ { std::stof(text) } :: float
plus /\+/
minus /\-/
/ +/

%%

E -> E plus  num { _1 + _3 }
   | E minus num { _1 - _3 }
   | num         { _1 }
   :: { float }
   ;

Тип используется только в C++, в прочих целевых языках его можно опустить. Если он не указан в C++, будет использован std::any.

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

Кроме того, есть директива %inherit, код идущий в фигурных скобках после %top будет вставлен сразу после имени класса парсера в объявлении (это удобно для добавления класса в иерархию наследования).

Например, для C++:

a /a/
b /b/
/ +/

%%

%top {
#include <memory>

struct Node {
  std::shared_ptr<Node> child;
  Node() : child(nullptr) {}
  Node(std::shared_ptr<Node> &&ch) : child(std::move(ch)) {}
  std::size_t count() {
    if(child)
      return 1+child->count();
    else
      return 0;
  }
};
}

S -> a S b { std::make_shared<Node>(std::move(_2)) }
   |       { std::make_shared<Node>() }
   :: { std::shared_ptr<Node> }
   ;

такое определение позволит посчитать число символов a (и соответственно b). Более корректно вынести определение в %top в отдельный файл и подключать его при помощи #include.

Семантические действия являются выражениями целевого языка. Ссылки на семантические значения элементов тела имеют вид _1, _2 и т.д.

Генератор создаст файлы lexer.h, lexer.cpp, parser.h и parser.cpp, в которых определены классы Lexer и Parser.

Cледующее определение соответствует разбору языка, состоящего из цифр, опционально разделённых пробелами, причём семантические действия конструируют список этих цифр:

digit /[0-9]/ { std::stoi(text) } :: int
/ +/

%%

%top {
#include <list>
}

Digits -> digit Digits { _2.push_front(_1), std::move(_2) }
        |              { std::list<int>() }
        :: { std::list<int> }
        ;

В качестве управляющего кода для сгенерированных анализаторов можно использовать, например, такой код:

std::string line;
if (std::getline(std::cin, line)) {
  Lexer lex(line);
  Parser parser(&lex);
  auto result = parser.parse();
  // сделать что-то с result
}

И лексический, и синтаксический анализаторы принимают вторым параметром булевскую переменную, управляющую отладочным выводом (по умолчанию – false, отладочный вывод отключён).

Упражнения

При выполнении упражнений 2-4, если не указывать семантические действия, в качестве ResultType может быть удобно использовать тип std::nullptr_t или void*.

Упражнение 1

Опишите введённую в работе 1 лексику, используя синтаксис ALPACA, ANTLR4, или генератора лексических анализаторов по Вашему выбору.

Упражнение 2

Опишите введённую в работе 2 грамматику, используя синтаксис ALPACA, ANTLR4, или генератора синтаксических анализаторов по Вашему выбору.

Упражнение 3

Добавьте синтаксис определения переменных в грамматику. Измените соответствующем образом описание грамматики.

Упражнение 4

Добавьте синтаксис определения и вызова функций в грамматику. Измените соответствующем образом описание грамматики.

Упражнение 5

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

Генераторы анализаторов