ANTLR: неформальное введение
В этой статье я дам введение в мощный фреймворк ANTLR. С его помощью мы напишем небольшой язык, помогающий раскраивать лист металла (или любой другой лист). В начале язык будет простым, по мере написания следующих статей станет обрастать подробностями и в конце концов выльется во вполне работоспособный и полноценный. Статья может быть полезна всем, кто хочет быстро разобраться в том, как работает ANTLR.
Что такое ANTLR и зачем он нужен
ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading,
processing, executing, or translating structured text or binary files.
It’s widely used to build languages, tools, and frameworks.
From a grammar, ANTLR generates a parser that can build and walk parse trees.
Terence Parr
Как следует из эпиграфа, ANTLR — это штуковина для генерации парсеров текста. С помощью их можно разобрать текст на составляющие и сказать, соответствует ли он заданным правилам; если да, произвести вычисления или выполнить другую работу.
Изначально ANTLR был создан для языка Java и написан на нем же, но на сегодняшний день для версии 4.7.2 доступна генерация парсеров для С#, Python 2 и 3, JavaScript, Go, C++ и Swift. Это значит, что парсер можно создать и для этих языков. Мы будем использовать Java, но все ниже сказанное без проблем можно перенести и на другие языки.
Что же можно делать с помощью ANTLR?
- Писать интерпретаторы и компиляторы новых языков программирования.
- Анализировать логи.
- Создавать утилиты для создания картинок из текстовых описаний (именно это мы и сделаем в данной статье).
Этапы разбора текста
Как происходит разбор любого структурированного текста? Почему структурированного? Да потому, что понимание любого текста — задача пока не решенная. Мы предполагаем, что имеем дело с подмножеством, подчиняющимся определенным правилам, которые называются грамматикой. О том, что это такое, я буду говорить в следующих статьях: дам развернутое определение и расскажу все, что нужно для применения его на практике. Но сейчас достаточно знать, что в начале нужно написать (или взять готовую) грамматику языка, который мы будем разрабатывать.
Что же мы будем делать с грамматикой:
- Разберем текст на составляющие, которые называются «лексемы». То есть выполним лексический анализ. Обычно лексемы — это слова текста. Заодно проверим, соответствуют ли наши системы описанным правилам.
- Сформируем из лексем более крупные структуры, опять же проверив, соответствуют ли они правилам.
- Получим дерево разбора грамматики. Это такое дерево, в корне которого главное правило, в узлах — промежуточные правила, в листьях — конкретные лексемы.
- Далее (опционально) можно проверить, соответствует ли наш текст правилам, которые с помощью грамматики учесть нельзя. Это называется семантический анализ.
- Обрабатываем ошибки, если они есть.
- Если ошибок нет или они для нас непринципиальны, обрабатываем дерево разбора.
Как же работает ANTLR
Вы, наверное, уже догадались, что разбор текстов — дело не простое. И это, таки да, правда. Лучшей в этом деле считается книга дракона — наиболее подробное и толковое руководство. Одна проблема — почти 1200 страниц! На изучение могут уйти годы. Но, к счастью, имеется ANTLR. Он по грамматике делает следующее:
- Генерирует класс, разбирающий текст на лексемы.
- Генерирует синтаксический анализатор.
- Говорит о том, что в лексике или синтаксисе текста есть ошибки (если они есть).
- Помогает обойти дерево синтаксического разбора, генерируя для этого классы визитора или листенера. В процессе разбора мы переопределяем нужные методы.
Лепота, большая часть работы сделана! По большому счету в ANTLR самое сложное — это создать грамматику для нужного языка, потом все — дальше работает фреймворк. Но поскольку у ANTLR есть обширное сообщество...
Создадим грамматику
В начале язык будет очень простым. У резака лазера (или любого другого) есть всего две базовые опции:
- передвинуться в точку A в выключенном состоянии;
- прорезать в листе отрезок прямой.
С помощью этих двух нехитрых операций можно вырезать в листе металла самую сложную фигуру, поскольку контур любой кривой можно сколько угодно точно приблизить маленькими отрезками прямых.
Таким образом, нам нужны всего две функции, MoveTo(x, y) и LineTo(x, y), где x и y — координаты соответствующей точки. Ниже представлен код нашей грамматики, давайте рассмотрим его.
grammar CuttingLanguage;
actions:action+;
action:moveTo|lineTo;
moveTo: moveToName='MoveTo' '(' x=INT ',' y=INT ')';
lineTo: lineToName='LineTo' '(' x=INT ',' y=INT ')';
INT :'-'? DIGIT+ ;
fragment DIGIT : [0-9];
WS : [ \n\r\t] -> skip ;
Код всегда начинается с имени грамматики. Дальше идут правила. Грамматика без правил не имеет смысла, поэтому невозможна.
Правила могут состоять из других правил и символов, соединяющих их. Например, символ «+» в правиле «actions: action+;» означает, что в правиле actions правило action повторяется 1 или более раз. Если бы вместо «+» стояло «*», это означало бы, что правило повторяется 0 или более. Но в данном случае это не имеет смысла.
Теперь рассмотрим правило action. Вертикальная черта означает «или». Другими словами, правило action — это или moveTo, или lineTo.
Правило moveTo состоит из ключевого слова MoveTo, его метки скобок и переменных x и y типа INT. Правило INT начинается с большой буквы и отличается от вышеуказанных правил, это лексема. Мы отметим это и вернемся к разбору отличия лексем от других правил позже. INT состоит из опционального знака «-», на это указывает знак вопроса после него и одного или нескольких правил DIGIT.
В случае с DIGIT имеем сразу два интересных приема. Во-первых, перечисление в квадратных скобках. Это означает, что может быть любой знак, от 0 до 9. Во-вторых, DIGIT — это фрагмент. Он может быть только частью правила, но сам правилом не является.
И последнее правило — WS; стрелка и слово skip означают, что мы переправляем символы в определенный канал. Что это такое, мы поясним позже; сейчас важно просто знать, что пробел, табуляция и перенос строк в данной грамматике игнорируются.
Визитор
Одной грамматики мало. Нужно как-то обработать текст программы. Для этого есть два способа:
- Можно обрабатывать правила при входе и при выходе. Этот способ называется listener.
- Можно обрабатывать правило при входе в него и возвращать значение, которое будет обрабатываться правилом выше по иерархии. В конце концов, обработчик главного правила вернет искомое значение.
В данном разделе мы опишем реализацию второго способа, в следующем реализуем первый.
Давайте посмотрим на код.
Визитор наследуется от сгенерированного парсер-генератором класса, в данном случае это параметризируемый класс CuttingLanguageBaseVisitor. Конструктор принимает начальное положение точки и GraphicsContext, с помощью которого будем осуществлять рисование; для этого я использовал JavaFX. На GitHub проекта есть код, но следует отметить, что данная статья JavaFX не посвящена. «Просьба в пианиста не стрелять. Он играет, как умеет» ©. Именно поэтому...
В данном классе только два метода: visitMoveTo и visitLineTo. Первый принимает MoveToContext, это тоже сгенерированный парсером класс. У него имеются поля x и у. Помните, в грамматике мы написали x = INT; y = INT. x и y — это метки соответствующих типов. Они же соответствующие лексемы, их текст возвращается с помощью самоочевидного метода getText(), и этот код обрабатывается методом Integer.parseInt.
Далее, мы передвигаем перо в точку (X, Y) и сохраняем текущее положение с помощью gs.save(). Возвращаем точку — положение резака с обновленными координатами.
Метод lineTo работает аналогично, но перед сохранением рисует прямую в точку (X, Y).
package org.newlanguageservice.antlrtutorial;
import org.newlanguageservice.ch1.CuttingLanguageBaseVisitor;
import org.newlanguageservice.ch1.CuttingLanguageParser.LineToContext;
import org.newlanguageservice.ch1.CuttingLanguageParser.MoveToContext;
import javafx.scene.canvas.GraphicsContext;
public class CuttingLanguageVisitor extends CuttingLanguageBaseVisitor<Point> {
private Point point;
private GraphicsContext gc;
public CuttingLanguageVisitor(Point point, GraphicsContext gc) {
this.point = point;
this.gc=gc;
}
@Override
public Point visitMoveTo(MoveToContext ctx) {
int x = Integer.parseInt(ctx.x.getText());
int y = Integer.parseInt(ctx.y.getText());
gc.moveTo(x, y);
gc.save();
return point.setX(x).setY(y);
}
@Override
public Point visitLineTo(LineToContext ctx) {
int x = Integer.parseInt(ctx.x.getText());
int y = Integer.parseInt(ctx.y.getText());
gc.strokeLine(point.getX(), point.getY(), x, y);
gc.save();
return point.setX(x).setY(y);
}
}
Теперь посмотрим, как это запустить. Вот код, передаваемый в слушатель кнопки запуска резака:
CuttingLanguageLexer lexer = new CuttingLanguageLexer(new ANTLRInputStream(textArea.getText())); lexer.removeErrorListeners(); CuttingLanguageParser parser = new CuttingLanguageParser(new CommonTokenStream(lexer)); parser.removeErrorListeners(); lexer.addErrorListener(new CuttingErrorListener()); visitor = new CuttingLanguageVisitor(new Point(0, 0), gc); ParseTree tree = parser.actions(); Point point = visitor.visit(tree); System.out.println(point);
Вначале мы создаем лексер. Это класс, который разбивает текст программы на лексемы (я писал о них выше), во второй строке создаем парсер из лексем. Потом создаем визитор.
Далее получаем корень дерева синтаксического разбора, это входная точка в дерево решений — правило actions. Можно было выбрать любое другое правило из грамматики (но не лексему), и разбор начинался бы с этого правила. С помощью визитора ходим по дереву и в конце получаем точку, в которую перейдет резак в завершение работы. Как видите, все просто.
Листенер
Не всегда в процессе обработки дерева синтаксического разбора нужно делать вычисления. Например, чтобы подкрасить ключевые слова, достаточно лишь получить их координаты. Для этого воспользуемся листенером. Работа этого класса несколько напоминает обход XML с помощью SAX: соответствующий метод класса срабатывает при входе и при выходе из правила.
Код класса представлен ниже:
package org.newlanguageservice.antlrtutorial;
import java.util.ArrayList;
import java.util.List;
import org.newlanguageservice.ch1.CuttingLanguageBaseListener;
import org.newlanguageservice.ch1.CuttingLanguageParser.LineToContext;
import org.newlanguageservice.ch1.CuttingLanguageParser.MoveToContext;
public class CuttingLanguageListener extends CuttingLanguageBaseListener {
List<LexemeWithCoords> lexemes=new ArrayList<>();
@Override
public void enterLineTo(LineToContext ctx) {
lexemes.add(new LexemeWithCoords(
new Point(ctx.lineToName.getStartIndex(),
ctx.lineToName.getStopIndex()+1),
"LineTo"));
}
@Override
public void enterMoveTo(MoveToContext ctx) {
lexemes.add(
new LexemeWithCoords(
new Point(ctx.moveToName.getStartIndex(),
ctx.moveToName.getStopIndex()+1), "MoveTo"));
}
public List<LexemeWithCoords> getLexemes() {
return lexemes;
}
}
Как и в предыдущем случае, мы наследуемся от сгенерированного ANTLR базового класса и переопределяем два метода: enterLineTo и enterMoveTo, в которых получаем координаты ключевых слов в тексте.
После этого мы подкрашиваем текст в редакторе, вот так:
List<LexemeWithCoords> lexemes = listener.getLexemes(); lexemes.forEach(lexeme->textArea.setStyleClass(lexeme.getCoords().getX(), lexeme.getCoords().getY(), "keywords"));
Обработка ошибок
Иногда ошибки бывают в коде, и некоторые из них можно обнаружить с помощью ANTLR, а именно лексические и синтаксические. Ошибки смысловые, когда код написан в соответствии с грамматикой, но не делает нужного, обнаружить нельзя: фреймворк же не знает, чего вы хотите.
Лексер и парсер, которые мы сгенерировали, выбрасывают сообщение о ошибке. Нам надо всего лишь прикрепить к ним слушатель, в простейшем случае он просто выводит сообщение в консоль.
Листенер реализует интерфейс ANTLRErrorListener. В нем четыре метода, но в данный момент нас интересует лишь один — syntaxError.
Выглядит это так:
public class CuttingErrorListener implements ANTLRErrorListener {
@Override
public void syntaxError(Recognizer<?, ?> recognizer, Object offendingSymbol, int line, int charPositionInLine,
String msg, RecognitionException e) {
System.out.println(msg);
}
Полный текст программы доступен по ссылке: github.com/...imirkozhaev/antlrtutorial
В следующих статьях я покажу развёрнутое описание теории, необходимой для понимания ANTLR и принципов его работы.
