Символьна магія: від текстових даних до візуалізації за допомогою ANTLR

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Усім привіт. Мене звати Роман, я Software Engineer в компанії MEV. В одній з попередніх статей мій колега Віктор розповідав про те, як ми на основі ANTLR, генератора синтаксичних аналізаторів, створили кастомну мову запитів.

Ця мова дозволила нам реалізувати точний і швидкий пошук більш ніж за 300 параметрами. Але тільки цим ми не обмежились. У своїй статті я розповім про ще один приклад застосування ANLTR на практиці та про те, як з його допомогою ми перетворюємо текстові дані на плани та візуалізації нерухомості.

Суть завдання

Перед нами стояло завдання на основі текстових даних з державних установ створити візуалізацію планування нерухомості. Щоб наочніше було зрозуміло, чого ми змогли досягнути, почну з кінця, а саме: з результатів:

В лівій колонці маємо вхідні дані: малозрозумілі, на перший погляд, текстові дані, якими в державних установах описується планування нерухомості. Простими словами, ці текстові дані задають напрям руху лінії, яка зрештою і відображає повноцінне планування.

У правій — візуалізацію планування нерухомості на основі цих текстових даних з урахуванням усіх потрібних параметрів.

Тепер, думаю, вам має бути більше зрозуміла початкова та кінцева точки завдання, тож можемо перейти до більш детального опису «подорожі» між ними.

Декодування текстових даних: розподіл на кімнати

Отже, маємо вхідні дані такого типу CU14R2U17R20D17R2D14L24A1CR20X14A2R10D14CR10X4H.

Якщо розбити їх на окремі частини, які можна вважати кімнатами, вони будуть мати такий вигляд:

Кімната A — «CU14R2U17R20D17R2D14L24»

Кімната B — «CR20X14»

Кімната C — «AR10D14CR10X4»

Розпізнавання символьної мови

Для ефективної інтерпретації та перетворення текстових даних надзвичайно важливо розуміти символьну мову, яку ми використовуємо.

1. Символи «U» — вверх, «D» — вниз, «L» — вліво, «R» — праворуч, це напрямок руху лінії, число після неї вказує на її довжину.
2. Символ «С» ідентифікатор початку малювання фігур з початкової точки, які будуть складати якусь частину будинку.
3. Символ «А» вказує на те, що наступні фігури, допоки не зустрінеться символ «С», будуть підводящими до позиції, з якої потрібно почати малювання.
4. Символ «X» — це ідентифікатор прямокутника з розміром двох його протилежних сторін 10 і 4 умовної розмірності.

Структура опису граматики ANTLR

Для перетворення всього цього набору тексту в набір описаних нами об’єктів ми вирішили використати ANTLR4

Лексеми

Правила

Список правил, за яким розпізнаються різні типи фігур з текстових даних:

Розглянемо, яке значення має кожне з правил:

1. В основі всього лежить правило розпізнавання line. Лінія повинна складатись з напрямку та довжини, DIRECTION та LENGTH відповідно, наприклад «U8».
2. Правило rectangle розпізнає прямокутник, який складається з трьох компонентів: line, символа X та довжини одного з його сторін, наприклад «D8X4».
3. Правило shape визначає будь-які типи фігур, до яких описані правила розпізнавання. У нашому випадку це line та rectangle.
4. Правило path очікує у вхідних даних символ C та будь-які фігури після, представлені правилом розпізнавання shape, наприклад CU8D10X14L5R9.
5. Правило invisiblePath розпізнаванням майже нічим не відрізняється від path, тільки індикатор початку для нього є символ «А», а не «C». До того ж, з path уявний олівець відмальовую видимі фігури, а з invisiblePath — невидимі, по яким олівець потрібно просто переставити.
6. Components представлений як список component, якими є path та invisiblePath.

Використання згенерованого коду

Під час генерації граматики ми отримали такий список файлів:

• SketchVisitor
• SketchBaseVisitor
• SketchLexer
• SketchParser
• Sketch.interp
• Sketch.tokens
• SketchLexer.interp
• SketchLexer.tokens

Для обробки правил ми вирішили використати підхід створення відвідувачів (Visitors) перевизначивши методи, відповідні кожному правилу граматики:

• ComponentsVisitor
  — збирає всі path та invisiblePath в один фінальний список.
• ComponentVisitor
  — генерує фігури, які будуть складати path або invisiblePath.
• LineVisitor
  — генерує фігуру лінії, яка складається з напрямку та довжини.
• RectangleVisitor
  — з граматики нам повертається напрямок сторони прямокутника, його довжина та довжина сусідньої сторони. У відвідувачу ми утворюємо всі чотири сторони, знаючи що в прямокутника протилежні сторони рівні.
  Наприклад U10X15 = [UP 10, RIGHT 15, DOWN 10, LEFT 15]
  Або L4X2 = [LEFT 4, UP 2, RIGHT = 4, DOWN 2]

Після опрацювання відвідувачами ми отримаємо таку структуру об’єктів:

public class Components {
    private List<? extends Path> value;
}
public class Path {
    private List<Shape> shapes;
}
public class InvisiblePath extends Path {}
public abstract class Shape {}
public class Line extends Shape {
    private Direction direction;
    private Integer length;
}
public class Rectangle extends Shape {
    private List<Line> lines;
}
public enum Direction {
    UP("U"), DOWN("D"), LEFT("L"), RIGHT("R");
    @Getter
    private String name;
}

Клас парсеру, який перетворить вхідні текстові дані в список об’єктів фігур, які пізніше будуть відмальовані:

public class VisitorOrientedBuildingSketchParserImpl implements VisitorOrientedSketchParser {
    @Override
    public Components parse(String input) {
        CharStream inputStream = CharStreams.fromString(input);
        SketchParserLexer lexer = new SketchParserLexer(inputStream);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        SketchParser parser = new SketchParser(tokens);
        return new ComponentsVisitor()
.visitComponents(parser.components());
    }
}

Приклад застосування

Отже, ми маємо вхідні дані «CU14R2U17R20D17R2D14L24A1CR20X14A2R10D14CR10X4H» та маємо перетворити їх у список об’єктів, які можна надалі візуалізовувати.

Спочатку, щоб усе було зрозуміліше, розіб’ємо їх на окремі кімнати:

• Кімната А: «CU14R2U17R20D17R2D14L24»

«Path», який складається з восьми фігур ліній

• Кімната B: «CR20X14»

«Path», який складається з прямокутника з чотирма сторонами (які, своєю чергою, є лініями)

• Кімната C: «AR10D14CR10X4»

На малюнку ми бачимо два типи ліній: зелена та чорна. Зелена лінія це InvisiblePath, яка складається з двох ліній: RIGHT 10 та DOWN 14. Ця лінія є підводячою і невидимою на вихідному малюнку плануванні нерухомості. Чорна лінія Path починається з кінця зеленої. У граматиці вона описана як прямокутник та складається з чотирьох ліній.

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

Візуалізація обʼєктів

Останній етап:

• отримавши в результаті список ліній з довжинами та напрямками для візуалізації, ми повинні конвертувати кожну з них у [x, y] координати початку та кінця лінії, враховуючи те, що кожна кімната (Path) повинна відмальовуватися з нульової точки;
• після цього потрібно вибрати зручний для вас фреймворк для роботи з графічним інтерфейсом, як-от Java AWT або більш сучасний Java FX;
• використовуючи вибраний вами фреймворк потрібно відмалювати отримані координати, додавши колір заливки кожної кімнати та додатково відобразити довжину кожної зі сторін;
• отриманий канвас можна експортувати в потрібний для вас формат картинки (.png, .jpg та інші).

Альтернативи

Звичайно, що ANTLR — не єдиний інструмент для вирішення нашого завдання. Перед тим, як зупинитись на ньому, ми розглянули декілька альтернатив.

1. Розпізнавання тексту за допомогою регулярних виразів (RegEx) та групи власноруч створених сервісів для обробки кожного знайденого елементу

Недоліки:

1. Схоже на винаходження велосипеда: для чого писати щось своє, коли є готові рішення?
2. Важка підтримка та розширення.
3. Висока ймовірність проблем та нестабільностей в роботі.
4. Потрібна висока щільність покриття тестами.

2. Створення парсеру за допомогою нативного функціонала Java — Java CC (Java Compiler Compiler), який теж дуже широко поширений та лежить в основі багатьох популярних парсерів, наприклад Apache Lucene.

Переваги:

1. У багатьох експериментах переважає в продуктивності будь-які інші парсери. Тож це буде хороше рішення коли продуктивність критична.
2. Менший розмір jar-a, швидше розгортання.

Недоліки:

1. Суттєво більш затратний в плані розробки, підтримки.
2. Важчий в описі правил, їхній обробці та інтеграції.
3. Немає розділення граматики та коду.

Висновок

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

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

А відтак перетворити текстові дані в плани нерухомості та візуалізувати їх, надаючи зрозумілу та зручну форму для сприйняття.