Python conf in Kharkiv, Nov 16 with Intel, Elastic engineering leaders. Prices go up 21.10

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?

  1. Писать интерпретаторы и компиляторы новых языков программирования.
  2. Анализировать логи.
  3. Создавать утилиты для создания картинок из текстовых описаний (именно это мы и сделаем в данной статье).

Этапы разбора текста

Как происходит разбор любого структурированного текста? Почему структурированного? Да потому, что понимание любого текста — задача пока не решенная. Мы предполагаем, что имеем дело с подмножеством, подчиняющимся определенным правилам, которые называются грамматикой. О том, что это такое, я буду говорить в следующих статьях: дам развернутое определение и расскажу все, что нужно для применения его на практике. Но сейчас достаточно знать, что в начале нужно написать (или взять готовую) грамматику языка, который мы будем разрабатывать.

Что же мы будем делать с грамматикой:

  1. Разберем текст на составляющие, которые называются «лексемы». То есть выполним лексический анализ. Обычно лексемы — это слова текста. Заодно проверим, соответствуют ли наши системы описанным правилам.
  2. Сформируем из лексем более крупные структуры, опять же проверив, соответствуют ли они правилам.
  3. Получим дерево разбора грамматики. Это такое дерево, в корне которого главное правило, в узлах — промежуточные правила, в листьях — конкретные лексемы.
  4. Далее (опционально) можно проверить, соответствует ли наш текст правилам, которые с помощью грамматики учесть нельзя. Это называется семантический анализ.
  5. Обрабатываем ошибки, если они есть.
  6. Если ошибок нет или они для нас непринципиальны, обрабатываем дерево разбора.

Как же работает ANTLR

Вы, наверное, уже догадались, что разбор текстов — дело не простое. И это, таки да, правда. Лучшей в этом деле считается книга дракона — наиболее подробное и толковое руководство. Одна проблема — почти 1200 страниц! На изучение могут уйти годы. Но, к счастью, имеется ANTLR. Он по грамматике делает следующее:

  1. Генерирует класс, разбирающий текст на лексемы.
  2. Генерирует синтаксический анализатор.
  3. Говорит о том, что в лексике или синтаксисе текста есть ошибки (если они есть).
  4. Помогает обойти дерево синтаксического разбора, генерируя для этого классы визитора или листенера. В процессе разбора мы переопределяем нужные методы.

Лепота, большая часть работы сделана! По большому счету в 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 означают, что мы переправляем символы в определенный канал. Что это такое, мы поясним позже; сейчас важно просто знать, что пробел, табуляция и перенос строк в данной грамматике игнорируются.

Визитор

Одной грамматики мало. Нужно как-то обработать текст программы. Для этого есть два способа:

  1. Можно обрабатывать правила при входе и при выходе. Этот способ называется listener.
  2. Можно обрабатывать правило при входе в него и возвращать значение, которое будет обрабатываться правилом выше по иерархии. В конце концов, обработчик главного правила вернет искомое значение.

В данном разделе мы опишем реализацию второго способа, в следующем реализуем первый.

Давайте посмотрим на код.

Визитор наследуется от сгенерированного парсер-генератором класса, в данном случае это параметризируемый класс 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 и принципов его работы.

LinkedIn

18 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Можно ещё код Apache Spark посмотреть как пример живого antlr

👍
приклад presto непоганий! використовую antlr на роботі для написання sql grammar для db github.com/...​src/main/antlr/SqlBase.g4. також непоганий приклад :D

Я бы перед описанием грамматики вставил таки 2-3 примера программы на языке — причём два простых, и один с подковыркой :)
тогда сразу станет понятнее, что высматривать в грамматике.

Тоже хотел об этом же спросить, но учитывая что в начале

У резака лазера (или любого другого) есть всего две базовые опции:
передвинуться в точку A в выключенном состоянии;
прорезать в листе отрезок прямой.

в примерах не будет ничего интересного — MoveTo/LineTo в разных комбинациях. Но вот да, пример того как будет выглядеть язык в конце, с полным набором фич, было бы интересно видеть с самого начала...

Оце вже цікаво. Сам про написання і мови, і компілятора до неї, щоб краще розібратися у глибинах програмування. А тут ще й якийсь ANTLR. Дочекаюся вільного слота у графіку і поколупаю. Дякую.

Где в грамматике, скажем так, точка входа? Или все правила верхнего уровня могут встречаться в тексте?

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

import javafx.scene.canvas.GraphicsContext;

Расскажи плиз про участие JavaFX во всем данном стеке.
Интересуют такие вопросы:
1) для чего применяется
2) проблемы/преимущества
3) это часть антлр или твоего проекта
4) какая версия (oracel, openJFX... 8/9/11+...), как запускается приложение?

JavaFX применяется как гуй и канвас для рисования. Ты скачай с гитхаба проектик и посмотри.
Проблемы/преимущества по сравнению с чем? Я взял JavaFX чтобы не создавать иклипс плагин, и не пояснять как он работает. Так -то мне Eclipse RCP нравится больше.
JavaFX не часть ANTLR
Остальное смотри в pom файле

Не упадет, если прийдет элемент с атрибутом bitmap, внутри которого 100кБ картинка? А то все широко известные парсеры не выдерживают. Переполнение стека.

Вот картинки не парсил, как то не приходилось — для них есть специальные парсеры. Если нет, пишем руками. Там не сложно

А то все широко известные парсеры не выдерживают. Переполнение стека.

Тут что-то непонятно, но слишком странно.
Это bitmap атрибут чего? В каком языке?

Атрибуты и элементы — это, очевидно, xml. У нас обрабатываются шаблоны билетов, в которых razor код. Это достаточно легко делается (сейчас используется nearley с достаточно полным описанием грамматики разора) кроме тех случаев, когда попадается элемент со встроенной картинкой. Были протестированы еще несколько парсеров (каждая грамматика — день работы), и все они падают с переполнением на этих элементах. Токенайзеры не помогают. Лексеры — тоже (производительность парсера с лексером, конечно, повыше будет)

Семён Семеныч, я то думал. Напиши мне в личку — я знаю решение

Вова и не про налоги. В мемориз!

А я ещё и на машинке и лобзиком могу

Главное, чтобы не на машинке лобзиком.

Подписаться на комментарии