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 : [ 

\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);
 }

Повний текст програми доступний за посиланням:

У наступних статтях я покажу розгорнутий опис теорії, необхідної для розуміння ANTLR та принципів його роботи.

Опубліковано: 27/06/19 @ 10:00
Розділ Різне

SEO Блог