Разбираемся с библиотекой лексического анализа ANTLR424.12.2021 11:16

8359d5893aff06c67d31df2978865aa9.png

У нас в SberDevices разрабатывается платформа по управлению рекомендациями, которая взаимодействует с разными ML-движками. Со временем их станет много, и, когда пользователь умных устройств Sber будет запрашивать контент — искать фильмы, музыку, спрашивать о чём-то виртуальных ассистентов Салют, — запрос будет проходить через нашу платформу.

Сначала выбор движка мы хотели завязывать на источник сообщений — пользовательское приложение на устройстве. Сейчас мы решили управлять маршрутизацией на основе содержания сообщений — по различным полям. Для этого используется набор правил, похожих на условие WHERE в SQL, т.е. мы выбираем маршруты, у которых совпадают условия со значениями полей сообщений.

В SQL-запросе пользователь шлёт условие, по которому из существующих строк таблицы выбираются подходящие. В нашей задаче получается наоборот: входящему сообщению нужно сопоставить все условия, которые у нас есть, и вернуть те, которые прошли проверку. Правила маршрутизации — это настройки, и их должны создавать не только программисты, но и менеджеры контента или дейта-сайентисты. С такими задачами справляются такие фреймворки, как, например Drools, но мы написали своё легковесное решение с упрощенным DSL, условия на котором может понять не только разработчик. 

Для обработки правил, написанных на кастомном DSL, лучшая библиотека — ANTLR4. Я находил много статей, в которых описываются разные аспекты работы с ANTLR4, но ни в одной из них я не увидел, то, что изучил на пути создания production-ready кода. Поэтому, разобравшись, я решил собрать туториал. Ниже опишу пример парсинга SQL SELECT-запроса в объектную модель Java. Будем двигаться постепенно, в этот раз рассмотрим простейший случай. На нём мы разберём саму идею этого парсера, сделаем минимальную реализацию.

Немного про ANTLR

Давайте представим, что мы создаём базу данных и должны поддержать язык SQL. Рассмотрим простейший запрос на выборку данных:

SELECT id, name, enabled FROM users;

Задача лексического анализа — получение списка колонок и имени таблицы, на основе которых будет выполнен запрос и извлечение данных. Вспомним, что вместо списка колонок там может быть звёздочка, закроем глаза и представим if/else-блоки, которые потребуются, чтобы навесить логику. 

Чтобы решить эту задачу, скорее всего, вы будете стремиться разделить логику анализа последовательности символов и реагирования на их значения. Другими словами, нужно отделить логику поиска имени таблицы от обработки, валидации этого имени и дальнейшего добавления в модель данных, используемых при запросе.

ANTLR позволяет сгенерировать набор интерфейсов, в которые будут передаваться распознанные блоки: каждая колонка из списка или имя таблицы, очищенное от пробелов и слова FROM. ANTLR — либа уже довольно старая и проверенная временем, которую тем не менее непрерывно улучшают, выпускают новые версии. Список использования этого анализатора очень велик, а наиболее близкое нам, джавистам, известное место использования — Hibernate Query Language.

ANTLR — кроссплатформенная утилита, которая позволяет однажды созданный синтаксис использовать, применять в различных проектах и модулях, на разных языках — проще говоря, везде где есть поддержка этой либы. Например, на бекенде в Java, при парсинге текста и на фронтенде в JavaScript, при создании подсветки синтаксиса или валидации ввода данных. Список языков, поддерживающих ANTLR4, можно найти тут.

Принцип работы ANTLR основан на синтаксическом анализе входного потока данных (ну или простой строки), построения синтаксического дерева, обхода этого дерева и предоставления сгенерированного API для внедрения логики для каждого из событий обхода. API генерируется на основе »грамматики», которая определяет структуру предложения, отдельных фраз/слов и конкретных символов. 

Другими словами, грамматика определяет DSL, который ожидается во входящем потоке данных и включает в себя декларацию токенов. Они разбивают входящий поток на сегменты, создавая тем самым события для API. 

Такой вот regexp на максималках. Ладно, хватит болтать, давайте кодить уже!

Настраиваем проект для работы с ANTLR

Я использую gradle для сборки проекта, описание будет соответствующее.

Добавляем зависимость и регистрируем плагин antlr: 

apply plugin: 'antlr'

...
dependencies {
    antlr "org.antlr:antlr4:4.9.3"
		....
}

Самым главным пунктом настройки является расположение файла грамматики. Плагин смотрит на специальную директорию проекта — src/main/antlr, файл должен быть в ней или поддиректориях. Поддиректории будут восприняты плагином как Java-пакеты, в которых будут расположены сорцы: сгенерированные парсер, лексер и прочие. После генерации классы будут доступны в ваших исходниках.

В моём примере путь к файлу выглядит так:  

src/main/antlr/org/example/SQL.g4

Тут:

  • src/main/antlr — директория, чтобы удовлетворить требования плагина;

  • org/example — основной пакет моего демо-приложения;

  • SQL.g4 — название, отражающее назначение файла — грамматика языка SQL.

Название файла следует выбирать, как если бы это был класс, так как оно будет использоваться как префикс для всего сгенерированного кода.

Основные сущности ANTLR

Стандартный алгоритм работы ANTLR включает в себя следующие сущности:

Файл грамматики — файл, который содержит декларацию правил для парсера и лексера. У ANTLR4 он имеет расширение *.g4

Исходный поток данных — он содержит в себе DSL, который мы собираемся распарсить: не обязательно валидный, если будут какие-либо ошибки, можно накрутить свою логику и решать что с ними делать.

Лексер (Lexer) — сгенерированный код, который занимается лексическим анализом и токенизацией текста. Для SELECT-запроса, который мы обсуждали выше, лексеру следует предоставить слова SELECT и FROM и символ »;». По ним будет токенизирован исходный поток данных и в таком виде он будет передан в парсер. Кроме ключевых слов в лексере следует указать примитивные типы, например, для нашего запроса нужно будет объявить понятие слова — как иначе отделить имя колонки от звёздочки или запятой. Когда перейдем к примерам, будет понятнее.

Парсер — сгенерированный код, который из токенов создает синтаксическое дерево, пригодное для визуализации и обхода. Всё в том же SELECT-запросе видна чёткая структура: между SELECT и FROM всегда список колонок (ну или звёздочка), а сразу после FROM идёт имя таблицы. Каждый из регионов следует обозначить своим именем, и для них будет сгенерирован Java-метод, в который будет передано содержимое этого региона в сгенерированной абстракции.

Обходчик (Walker) — стандартный API, который делает обход дерева и, сталкиваясь с токенами, сообщает о соответствующих им событиях слушателю.

Лисенер (Listener) — сгенерированный код, который предоставляет набор пустых шаблонных методов. Ихмы можем переопределять в своём наследнике и накручивать нашу логику.

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

Теперь, понимая что требуется для парсера и лексера, создадим файл грамматики.

Создание файла грамматики SQL.g4

Файл имеет специальную структуру. Первым в файле декларируются названия грамматики, а также Java-пакет, к которому она принадлежит: 

grammar SQL;

@header {

   package org.example;

}

Далее располагают правила для парсера. Каждое из этих правил будет иметь события входа в него и выхода из блока текста, описанного в правиле, и соответствующие им методы в лисенере. Имена правил станут частью имён методов в Java, поэтому должны соответствовать конвенции: 

sqlQuery
   : simpleSelect EOF;

simpleSelect
   : SELECT (allColumns | specificColumns) FROM table EOQ;

specificColumns
   : column (',' column)
   ;

allColumns
   : ASTERISK
   ;

column
   : VALID_NAME
   ;

table
   : VALID_NAME
   ;

Принято делать входную точку, которая агрегирует в себе все правила и лексику. У нас это будет имя sqlQuery, к нему мы будем обращаться из Java-кода.

Рассмотрим подробнее каждое из правил.

sqlQuery содержит только ссылку на правило simpleSelect — так сделано на случай, если мы будем добавлять новый запрос, он не будет связан с simpleSelect и код обработчиков событий simpleSelect останется без изменений. EOF (end of file), конец потока символов, ключевое слово самого ANTLR.

simpleSelect содержит в себе обитателей лексера: SELECT, FROM и EOQ, а также другие правила — allColumns, specificColumns и table. Причём allColumns и specificColumns — взаимоисключающие. Синтаксис напоминает regexp — обязательно должно быть что-то из этих двоих. А вот что именно? Тут не должно быть неопределённости, и это достигается структурой правил allColumns и specificColumns.

allColumns содержит только ASTERISK, т.е. в этом правиле ожидается только звёздочка и всё. Звездочка не может быть именем колонки. И если после SELECT идёт звёздочка, мы сразу отправляемся в правило allColumns. Можно подумать что это ненужная декларация, ведь правило simpleSelect могло выглядеть так: SELECT ('*'| specificColumns) FROM table EOQ. Тогда мы бы не попали в метод лисенера, соответствующий allColumns, следовательно понять, нужны ли все колонки, пришлось бы по косвенным признакам. В нашем простом примере это легко реализовать, но в сложной лексике это станет нетривиальной задачей.

specificColumns содержит как минимум одно правило column, но через запятую может быть указано сколько угодно column.

column и table содержат некое VALID_NAME, как и SELECT, FROM и прочие — это правило лексера. Давайте задекларируем их и разберёмся с ними.

Правила для лексера: 

ASTERISK: '*';
SELECT: 'SELECT';
FROM: 'FROM';
EOQ: ';';

VALID_NAME
   : [a-zA-Z] [a-zA-Z_0-9]*
   ;

SPACE:          [ \t\r\n]+    -> channel(HIDDEN);
COMMENT_INPUT:  '/*' .*? '*/' -> channel(HIDDEN);
LINE_COMMENT:   ('-- ' | '#')
                ~[\r\n]*
                ('\r'? '\n' | EOF)
                              -> channel(HIDDEN);

Самое простое и понятное тут — это константы: ASTERISK, SELECT, FROM, EOQ. Они соответствуют конкретным значениям. Мы уже поняли, что благодаря им парсер может однозначно идентифицировать нужную ветвь правил.

VALID_NAME — декларация похожа на очередной regexp, но с пробелом между первым символом и последующими. Этот пробел игнорируется, т.е. VALID_NAME — это непрерывное слово, которое начинается с буквы и может содержать цифры, длина может быть любой. Но как только мы натыкаемся на что-то отличное от буквы или цифры (в SQL это, скорее всего, точка, запятая или пробел), мы считаем значение завершённым.

Тут есть особенность: SELECT и FROM соответствуют этому паттерну, поэтому их нужно декларировать выше, чем VALID_NAME — и они первыми будут попадать в обработчик. Если VALID_NAME будет стоять выше, то первое слово запроса SELECT * FROM users; будет воспринято как токен VALID_NAME, а не как токен SELECT.

SPACE, COMMENT_INPUT, LINE_COMMENT — здесь по названию ясно что это. :) Синтаксис, конечно, непонятный, но зная, как работает regexp, и понимая, что пробелы между символами игнорируются, понять, что там написано, можно. Буду честен, я его нашел среди готовых грамматик, коих много на просторах интернета. Все они имеют запись -> channel(HIDDEN);. Это означает, что они будут проигнорированы нашим лисенером.

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

Генерация кода

Gradle-плагин antlr, который мы подключили, приносит с собой 3 таски. Они занимаются генерацией кода и добавляют сгенерированный код в sourceSets, так, благодаря им, код становится доступным в ваших исходниках.

Таски можно кастомизировать до определённой степени, так в своём примере я добавил два аргумента: относиться к ворнингам как к эррорам и отображать детализацию исключений. Полный список аргументов можно найти в документации к ANTLR4.

generateGrammarSource {
    arguments += [
            "-Werror", "-long-messages"
    ]
}

Выполните любую gradle-таску, включающую в себя compileJava, например ./gradlew assemble. В директории build (или что там у вас настроено) появится директория generated-src, в которой будут располагаться исходники сгенерированных файлов, а скомпилированные будут лежать, как положено, в classes. 

Если файлы не сгенерировались или лежат не там где надо, проверьте в какой директории лежит файл .g4 и указаны ли в нём грамматика, пакеты и правила. Если есть ошибки в самом файле .g4, то таска выдаёт вполне адекватные ошибки в лог:

> Task: generateGrammarSource FAILED

error (56): D:\projects\gradle-antlr4\src\main\antlr\org\example\SQL.g4:8:6: reference to undefined rule: simpleSlect

После всех описанных шагов, у меня сгенерировались классы: SQLParser, SQLLexer, SQLListener, SQLBaseListener. Первые два мы уже обсудили в разделе сущностей, третий — это интерфейс лисенера, в котором есть пары методов enter/exit для каждого из правил парсера из g4-файла. SQLBaseListener — пустая реализация интерфейса, сделана для удобства, так как, скорее всего, вам не нужны будут все методы интерфейса. Переопределить нужно только те, что нужны вашей логике, я так и сделал.

Реализация своей логики в Java-коде

Для простоты расширяем класс SQLBaseListener, переопределяя только те методы, что нужны нам: 

public class SQLParserListener extends SQLBaseListener {

   private final List columns = new ArrayList<>();

   private String fromTable;
   private boolean allColumns;

   public SQLQuery getQuery() {
       return new SQLQuery(fromTable, new ArrayList<>(columns), allColumns);
   }

   @Override
   public void enterSqlQuery(SQLParser.SqlQueryContext ctx) {
       fromTable = null;
       columns.clear();
       allColumns = false;
   }

   @Override
   public void exitColumn(SQLParser.ColumnContext ctx) {
       columns.add(ctx.VALID_NAME().getText());
   }

   @Override
   public void exitAllColumns(SQLParser.AllColumnsContext ctx) {
       allColumns = true;
   }

   @Override
   public void exitTable(SQLParser.TableContext ctx) {
       fromTable = ctx.VALID_NAME().getText();
   }
}

В нашем простейшем примере всё, что нужно сделать, это получить доступ к слову, которое было распознано как VALID_NAME, находясь в правильном контексте. Например, когда мы вошли или вышли в правило table, мы имеем доступ к его дочерним правилам, среди которых и VALID_NAME.

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

Например, вместо того, чтобы работать с правилом списка колонок enter/exitAllColumns, лучше создать лексику в g4-файле, которая будет разбивать этот список на элементы, и в Java воспользоваться enter/exitColumn, реализовывать только обработку элементов списка.

Заключение

Для нашего примера использование ANTLR выглядит, как стрельба из пушки по воробьям. Но стоит нам добавить обработку условия WHERE, которое может содержать, например, несколько вложенных AND и/или OR (причём в стандарте SQL ни глубина, ни сложность не ограничена), и на if/else-блоках такой код будет глубоким болотом — всё равно придется делать нечто схожее с ANTLR.

Спасибо, что дочитали (или проскролили : D) до этого момента. В качестве благодарности делюсь ссылкой на код, который был упомянут выше. Версию кода для этой статьи можно найти по тегу simple_select_query. Тесты написаны, так что можно даже продебажить. 

© Habrahabr.ru