НАЧАЛО РАБОТЫ С ANTLR IN C

Давайте посмотрим на некоторые AST

Возьмем простой файл:

def sum(a, b):
вернуть а + б

print(«Сумма %i и %i равна %i» % (5, 3, sum(5, 3)))

А теперь возьмем АСТ. Мы можем распечатать его, используя этот код:

Если мы разберем простой пример и распечатаем его с помощью AstPrinter, мы получим очень сложное AST. Первые строки выглядят так:

Для построения парсера существует множество аннулированных правил. Это имеет смысл при анализе, но в результате получается очень загрязненный AST. Я думаю, что существует два разных ASTS: AST для анализа, который легко создать, и AST для логики, о котором легко рассуждать. К счастью, мы можем без особых усилий превратить первое во второе.

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

Таким образом, мы переходим от 164 узлов к 28. Итоговая логика AST:

file_input
функцияdef
параметры
типдаргслист
tfpdef
tfpdef
люкс
простой_стмт
return_stmt
arith_expr
атом
атом
простой_стмт
власть
атом
трейлер
срок
нить
атом
testlist_comp
целое число
целое число
власть
атом
трейлер
список аргументов
целое число
целое число

В этом дереве все должно быть сопоставлено с концепцией, которую мы понимаем, без каких-либо искусственных узлов, узлов, просто созданных для анализа.

Как вызвать синтаксический анализатор

Теперь давайте посмотрим, как мы можем вызвать синтаксический анализатор.

Наш ParserFacade имеет только один общедоступный метод с именем parse. Он получает файл и возвращает AST. Вряд ли это может быть проще.

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

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

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

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

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

ошибка (56): D:projectsgradle-antlr4srcmainantlrorgexampleSQL.g4:8:6: ссылка на неопределенное правило: simpleSlect

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

Как использовать ANTLR в C++

Теперь мы увидим, как использовать сгенерированный синтаксический анализатор в программе на C++.

Это основной файл нашей программы, в котором показано, как настроить ANTLR для использования в C++. Заголовки, включенные в первые строки (3–5), по сути, являются стандартными, которые вы всегда будете включать. Первый из них необходим для использования среды выполнения, два других предназначены для сгенерированных лексера и парсера. Очевидно, их название изменится в зависимости от названия грамматики, но концепция останется той же.

Строки 15-20 показывают стандартный способ использования парсера ANTLR:

Затем строка 20 использует метод синтаксического анализатора, соответствующий одному из правил грамматики, для получения первого узла, соответствующего правилу. В этом случае существует только один файл узла, поскольку мы определили наше правило. Однако в принципе их может быть много: каждый раз, когда вы вызываете соответствующий метод, вы получаете новый.

Это все очень понятно, если знать терминологию синтаксического анализа. Если вы этого не сделаете, у вас есть два варианта: вы можете получить короткую версию или полную версию. Вкратце, лексер анализирует входные данные (то есть символы) и создает токены, затем синтаксический анализатор анализирует токены для создания дерева синтаксического анализа — структуры, содержащей входные данные, организованные в логическую структуру, определенную грамматикой. Если вместо этого вам нужна длинная версия, вы можете прочитать ее в нашем «Руководстве по синтаксическому анализу: алгоритмы и терминология».

Метод SceneParser::file() возвращает объект FileContext, это тип, определенный сгенерированным анализатором, который содержит метод для доступа к тексту, захваченному правилом, и его различным элементам. Например, наш файл правил содержит ссылку на имя правила, поэтому объект FileContext будет содержать метод name() для доступа к части файла, соответствующей имени. Если компонент содержит более одного элемента, как, например, наши элементы метки, метод вернет вектор.

Формат

Теперь, когда все настроено и работает, мы можем приступить к рассмотрению грамматики нашего формата.

Разумеется, описание написано не вольным текстом, а в формате, близком к нему.

Любое из этих двух действий должно указывать размер элемента, цвет и положение. В дополнение к этому, для каждой команды существуют определенные допустимые значения. Чтобы упростить использование формата, вы не можете выбирать произвольную позицию (например, 100 пикселей слева), а только заранее определенные позиции (например, слева). То же самое касается и размера элементов.

И это почти наш формат. Прежде чем перейти к грамматике, давайте посмотрим на пример файла.

состав:
нарисуйте маленький квадрат красного цвета в центре вверху
напиши среднее «посмотри на меня!» синим слева внизу

Для разработки MySQL-парсера был выбран генератор парсеров ANTLR. Основные преимущества данного генератора:

ANTLR включает двухэтапный алгоритм генерации распознающего кода. Сначала описывается лексическая структура языка, то есть определено, что является токенами. Далее, описывая синтаксическую структуру языка, есть распознаваемые токены, сгруппированные в предложениях. Лексическая и синтаксическая структура в ANTLR о результате с помощью правил. Лексическая структура Определяется типом (описателем лексемы) и значениями. Для описания значений используется язык с элементами регулярных выражений, но с поддержкой рекурсии. Синтаксическая структура правила состоит из лексем описателей на основе правил построения предложений в ANTLR 4, позволяющих определить структуру расположения лексем в предложении или фразе внутри предложения.

При построении правил следует учитывать базовый принцип лексического анализа, реализованный в том числе и в ANTLR. Лексер в первую очередь попытается распознать наиболее длинную последовательность символов из входного потока, подходящую под какое-либо лексическое правило. Если же таких правил несколько, то за ним стоит первое место в порядке определения.

Без использования семантических предикатов в ANTLR можно построить только контекстно-свободную грамматику. Плюсом является то, что в этом случае полученная грамматика будет независимо от завершения выполнения. Предлагаемая в статье грамматика для диалекта MySQL построена без использования семантических предикатов.

Резюме

Это все, что вам нужно знать, чтобы начать анализ с помощью ANTLR на C++. Мы увидели, как разработать грамматику формата данных, а также некоторые основные шаблоны, используемые при написании грамматики. Мы научились использовать посетителя и перемещаться по дереву синтаксического анализа, созданному парсером. И мы удачно использовали все это в программе на C++ для создания простых изображений.

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

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

ANTLR упрощает синтаксический анализ даже на C++.

Оригинал написан в апреле 2018 г. – Последняя редакция и обновление в июле 2023 г.

Мега-учебник ANTLR в формате PDF

Получите Mega Tutorial на свою электронную почту и читайте его, когда захотите, на любом устройстве

Парсер

Для описания синтаксической структуры языка необходимо определить порядок записи:

Структура текста в MySQL

Для MySQL есть отличное описание грамматики, хоть и распределенное по всему справочному плану. Структура расположения предложений в тексте находится в разделе описания протокола обмена сообщениями между сервером и клиентом MySQL. Можно представить, что все предложения, кроме, возможно, последнего использования разделителя ;. Кроме того, есть нюанс, касающийся строковых комментариев: последнее предложение в тексте может закончиться таким комментарием. В итоге получается, что любая корректная последовательность предложений на языке MySQL должна быть представлена в виде:

Мощности контекстно-свободной грамматики не хватает для полной поддержки этих правил, так как MySQL-клиент может использовать команду DELIMITER, с помощью которой можно устанавливать текущий разделитель. В этом случае требуется запомнить и использовать разделитель в других правилах. Таким образом, если использовать эту директиву, корректно написанные SQL-предложения при помощи рассматриваемой грамматики распознаны не будут.

Типы предложений в MySQL

Предложения в MySQL бывают следующих типов:

После перевода документации в грамматику ANTLR 4 корневое правило предложения будет выглядеть следующим образом:

Также существует пустое предложение, состоящее из одной точки с запятой:

empty_statement
: SEMI
;

SEMI: ‘;’;

Последующие пункты официальной документации трансформируются в правила ANTLR аналогичным образом.

SELECT

Пожалуй, самым интересным и обширным предложением в SQL вообще и в MySQL в частности является предложение SELECT. При написании грамматики основное внимание было уделено следующим его частям:

Начнем с определения таблиц. В языке MySQL довольно серьезное описание того, что можно использовать в поле FROM запроса типа SELECT (далее будем называть это «табличными ссылками»). После внимательного изучения и тестирования на действующих версиях становится ясно, что «табличные ссылки» представляют собой конструкцию вида:

в которой «Табличный объект» представляет собой одну из четырех конструкций:

Если начать с менее общего, то получаем, что табличный объект индуктивно определяется как таблица или как конструкция на основе таблиц. Последняя может представлять собой:

Далее получаем, что в поле FROM просто определяется последовательность табличных объектов, состоящая как минимум из одного табличного объекта. Конечно, в грамматике определяются дополнительные конструкции типа «условий соединения», ссылок на партиции (PARTITION) и т. п., но общая структура выглядит следующим образом:

Выражения

Выражения (expressions) в языке MySQL используются повсеместно — везде, где возникает потребность в вычислении значения (вектора значений). Индуктивно выражение можно определить следующим образом:

К числу преобразований относятся операции, операторы (в том числе теоретико-множественные, операторы сравнения), функции, запросы, скобки.

UNION

В отличие от других диалектов, в MySQL есть только две теоретико-множественные операции над таблицами. Первая — JOIN — уже была рассмотрена. Экспериментальным путем было выяснено, что описание UNION в официальной документации несколько неполное. Нами оно было дополнено следующим образом:

При использовании UNION отдельные запросы могут быть заключены в круглые скобки. Требование на их использование не является обязательным, кроме случаев, когда в запросах используются ORDER BY и LIMIT. Тем не менее, если первый запрос в UNION заключен в круглые скобки, в них должны быть заключены и все последующие запросы.

(select 1) union select 2;
(select 1) union (select 2) union select 3;

(((select 1))) union (select 2);
(select 1) union ((select 2)) union (select 3);

Использование грамматики

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

Приложение, использующее парсер, скорее всего будет задействовать один из двух паттернов проектирования — Visitor или Observer. Каждый из них предполагает анализ определенного подмножества узлов дерева разбора. Узлы дерева разбора, не являющиеся листьями, соответствуют каким-либо синтаксическим правилам грамматики. При анализе узлов дерева разбора нужно обращаться к дочерним узлам, соответствующим фрагментам исходного правила. Причем обращаться можно как к отдельным узлам, так и к группам узлов.

Поэтому важным условием создания хорошей грамматики является возможность получения «простого» доступа к любой части правила. Интуитивно «простой» доступ можно описать как возможность получения этой части в виде объекта, не используя поиск и перебор. Для этого в ANTLR есть такие сущности как альтернативные и элементные метки. Альтернативные метки позволяют разбить сложное правило на альтернативные фразы и, в случае использования паттерна проектирования Visitor, обрабатывать каждую такую фразу в отдельном методе. Например, табличный объект в MySQL может быть задан правилом:

Можно заметить, что табличный объект определяется как один из трех возможных вариантов:

Поэтому вместо обработки конструкции целиком определяются альтернативные метки и предоставляется возможность обработки каждого варианта независимо от остальных:

Элементными метками помечаются отдельные нетерминалы или последовательности терминалов. Они предоставляют доступ к содержимому контекста правила в виде поля с заданным именем. Таким образом, вместо вычисления (извлечения) отдельного элемента содержимого некоторого контекста достаточно просто обратиться к такой элементной метке. Вычисление же производится в зависимости от конструкции правила. Чем сложнее написано правило, тем сложнее производить вычисление.

Например, для правила:

возникает необходимость вычисления имени тега, которым идентифицируются строки, загружаемые оператором LOAD XML. Также возникает необходимость определять условия, по которым будет определен конкретный вид оператора LOAD XML:

Для того чтобы не производить вычисления, а сразу получать в коде требуемые значения, можно использовать элементные метки:

Вместе с упрощением кода целевого приложения упрощается и грамматика, так как имена альтернативных меток улучшают читаемость.

От теории к практике

Для парсеров PHP, T-SQL были разработаны и выложены в опенсорс грамматики php, tsql, plsql, которые являются наглядными применениями вышеизложенной теории. Для парсинга Java использовались и сравнивались уже готовые грамматики java и java8. Также для сравнения парсеров на основе Roslyn и ANTLR мы доработали грамматику C# для поддержки версий 5 и 6 языка. Интересные моменты разработки и использования этих грамматик мы описали ниже. Хотя языки на базе SQL являются больше декларативными, нежели императивными, в их диалектах T-SQL, PL/SQL есть поддержка императивных конструкций (Control flow), для которых по большей части и разрабатывается наш анализатор.

Java- и Java8-грамматики

Для большинства случаев парсер на основе грамматики Java 7 быстрее парсит код, по сравнению с Java 8, за исключением случаев с глубокой рекурсией, например в файле ManyStringConcatenation.java, когда парсинг занимает на порядок больше времени и памяти. Хочу заметить, что это не просто синтетический пример — нам реально попадались файлы с подобным «кодом-спагетти». Как оказалось, вся проблема как раз из-за леворекурсивных правил в expression. Грамматика Java 8 содержит правила только с примитивной рекурсией. Правила с примитивной рекурсией отличаются от правил с обычной тем, что они ссылаются на себя же только в левой или правой части какой-либо альтернативы, но не одновременно в обеих. Пример обычного рекурсивного выражения:

А следующие правила получаются после преобразования правила выше в примитивные леворекурсивные:

Или же вовсе в нерекурсивные (однако в этом случае выражения после парсинга будет не очень удобно обрабатывать, потому что они перестанут быть бинарными):

Если же операция обладает правой ассоциативностью (например, возведение в степень), то используются примитивные праворекурсивные правила:

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

PHP-грамматика

Для парсинга PHP на платформе . NET существует проект Phalanger. Однако нас не устроило то, что этот проект практически не развивается, а также не предоставляет интерфейса Visitor для обхода узлов AST (только Walker). Таким образом, было решено разрабатывать грамматику PHP под ANTLR собственными силами.

Регистро-независимые ключевые слова.

Как известно, в PHP все лексемы, за исключением названий переменных (которые начинаются с ‘

В разработанной грамматике PHP использовался первый подход, поскольку лексический анализ обычно проводится за меньшее время, чем синтаксический. И несмотря на то, что грамматика получилось все равно зависимой от рантайма, данный подход потенциально упрощает задачу портирования грамматики на другие рантаймы. Более того, нами был создан Pull Request RFC Case Insensitivity Proof of Concept — для облегчения описания нечувствительный к регистру лексем. Но, к сожалению, он не получил большого одобрения со стороны ANTLR сообщества.

Лексические режимы для PHP, HTML, CSS, JavaScript.

Как известно, вставки PHP-кода могут находится внутри HTML кода практически в любом месте. В этом же HTML могут находится вставки CSS- и JavaScript- кода (эти вставки еще называют «островками»). Например, следующий код (с использованием Alternative Syntax) является валидным:

К счастью, в ANTLR есть механизм так называемых режимов (mode), которые позволяют переключаться между различными наборами токенов при определенном условии. Например, режимы SCRIPT и STYLE предназначены для генерации потока токенов для JavaScript и CSS соответственно (однако в этой грамматике они фактически просто игнорируются). В режиме по умолчанию DEFAULT_MODE генерируются HTML-токены. Стоит отметить, что реализовать поддержку Alternative Syntax в ANTLR можно без единой вставки целевого кода в лексер. А именно так: nonEmptyStatement включает в себе правило inlineHtml, которое, в свою очередь, включает в себя токены, полученные в режиме DEFAULT_MODE:

Сложные контекстно-зависимые конструкции.

Стоит отметить, что хотя ANTLR поддерживает только КС-грамматики, в нем существует так называемые экшены, т. е. вставки произвольного кода, которые расширяют допустимое множество языков как минимум до контекстно-зависимых. С помощью таких вставок была реализована обработка конструкций, типа Heredoc и других:

Грамматика T-SQL

Несмотря на общий корень «SQL», грамматики T-SQL (MSSQL) и PL/SQL достаточно сильно отличаются друг от друга.

Мы были бы рады не разрабатывать собственный парсер для этого непростого языка. Однако существующие парсеры не удовлетворяли критериям полноты охвата, актуальности (грамматика под заброшенный GOLD-parser) и открытым исходникам на C# (General SQL Parser). Было принято решение восстанавливать грамматику TSQL из документации MSDN. Результат получился достойным: грамматика уже охватывает много распространенных синтаксических конструкций, опрятно выглядит, независима от рантайма и покрыта тестами (примеры SQL-запросов из той же MSDN). Неприятным моментом разработки было то, что некоторые токены в грамматике являются опциональными. Например, точка с запятой. Побочным эффектом является то, что восстановление после ошибок при парсинге из-за этого проходит не очень гладко.

Грамматика PL/SQL

Доработка грамматики PL/SQL заняла еще меньше времени, поскольку сама грамматика уже существовала под ANTLR3. Основной сложностью являлось то, что она была разработана под java-runtime. Большая часть java вставок была удалена, так как построить AST можно и без них (как уже говорилось ранее, семантику можно проверять на другом этапе). А такие вставки, как

были заменены на фрагментные лексемы:
decimal_key: D E C I M A L, о которых также говорилось ранее.

C#-грамматика

Как это ни странно, но доработка грамматики, поддерживающей версии 5 и 6 языка, оказалась достаточно непростым занятием. Главной сложностью была поддержка интерполяции строк и корректная обработка препроцессорных директив. В силу того что эти вещи являются сильно контекстно-зависимыми, лексер и парсер для обработки директив получились зависимыми от runtime.

Директивы препроцессора

В C# возможна корректная компиляция следующего кода (код после первой директивы не компилирующийся, но и не учитывающийся в компиляции, т. к. false никогда не выполняется):

#if DEBUG && false
Sample not compilied wrong code
var 42 = a + ;
#else
// Compilied code
var x = a + b;
#endif

Для корректной обработки таких случаев код сначала разбивается на массив токенов, находящихся в каналах по-умолчанию, COMMENTS_CHANNEL и DIRECTIVE. Также создается список codeTokens, куда попадают правильные токены для синтаксического разбора. После этого препроцессорный парсер вычисляет значение директивы для препроцессных токенов. Стоит обратить внимание на то, что ANTLR также позволяет писать код для вычисления значения сложного логического выражения прямо в грамматике. Как это реализовано — можно посмотреть в CSharpPreprocessorParser.g4. Значение true или false вычисляется только для директив #if, #elif, else, для всех же остальных директив всегда возвращается true, поскольку они не влияют на то, будет ли последующий код компилироваться. Также в этом парсере можно определить дефолтные Conditional Symbols (по умолчанию определен «DEBUG»).

После того как значение директивы вычислено и принимает значение true, последующие токены добавляются в список codeTokens, в противном случае — нет. Такой подход позволяет игнорировать неправильные токены (как var 42 = a + ; в этом примере) уже на этапе парсинга. Весь этап парсинга также расписан здесь: CSharpAntlrParser.cs.

Интерполяция строк

Данную фичу было очень непросто разрабатывать, потому что, например, закрывающаяся фигурная скобка может означать как часть интерполируемого выражения (interpolation-expression), так и выход из самого режима выражения. А двоеточие может также быть частью выражения, а может означать конец выражения и описание формата вывода (например, #0.##). Кроме того, такие строки могут быть как обычными (regular), так и без экранирующих символов (verbatium), а также могут быть вложенными друг в друга. Подробнее синтаксис описан в MSDN.

Описанные выше вещи продемонстрированы в следующем коде, валидном с точки зрения синтаксиса:

Интерполяция строк была реализован с использованием стека для подсчета уровня текущей интерполируемой строки, а также фигурных скобок. Все это реализовано в CSharpLexer.g4.

Тестирование

Парсер Roslyn, очевидно, не нуждается в тестировании корректности парсинга. А тестированию парсеров ANTLR мы уделили большое внимание:

Производительность парсеров ANTLR и Roslyn

Тестирование проводилось в однопоточном режиме и Release конфигурации без отладчика. Тестировались версии ANTLR 4 4.5.0-alpha003 и Roslyn (Microsoft. CodeAnalysis) 1.1.1.

WebGoat. P HP

Обработанных файлов — 885. Общее количество строк — 137 248, символов — 4 461 768.
Приблизительное время работы — 00:00:31 сек (лексер 55%, парсер 45%).

PL/SQL Samples

Обработанных файлов — 175. Общее количество строк — 1 909, символов — 55 741.
Приблизительное время работы < 1 сек. (лексер 5%, парсер 95%).

CoreFX-1. 0-rc2

Обработанных файлов — 7329. Общее количество строк — 2 286 274, символов — 91 132 116.
Приблизительное время работы:

Roslyn-1

Обработанных файлов — 6527. Общее количество строк — 1 967 672, символов — 74 319 082.
Приблизительное время работы:

Из результатов тестирования проектов CoreFX и Roslyn можно сделать вывод, что разработанный парсер C# на ANTLR не более чем в 5 раз медленнее парсера Roslyn, что говорит о хорошем качестве последнего. Понятно, что написанный «на коленке» за неделю парсер вряд ли сможет конкурировать с такими гигантами, как Roslyn, однако его все же можно использовать для парсинга C#-кода на Java, Python или JavaScript (и других будущих языках), поскольку скорость парсинга все равно быстрая.

На основании всех остальных тестов можно сделать вывод, что лексирование является в основном более быстрой операцией, чем непосредственно разбор. Исключением является лексер PHP, где лексирование заняло даже больше времени, чем разбор. Вероятно это связано со сложной логикой лексера и сложными правилами, но не с регистронезависимыми ключевыми словами, поскольку лексеры T-SQL и PL/SQL (в которых тоже регистронезависимые ключевые слова) работают гораздо быстрее парсеров (раз в 20). Например, если в грамматике C# использовать лексическое правило SHARP: NEW_LINE Whitespace* ‘#’; вместо SHARP: ‘#’;, то лексер будет не в 7 раз быстрее, а в 10 раз медленнее ! Это объясняется тем, что в любом файле очень много пробелов, а лексер на каждой строчке будет пытаться найти символ #, что значительно замедлит его производительность (мы сталкивались с такой проблемой, поэтому нахождение директивы на новой строчке нужно проверять на этапе семантического анализа).

Механизмы обработки ошибок в ANTLR и Roslyn

Был написан простой C#-файл, содержащий все возможные типы ошибок ANTLR:

Как видно, Roslyn обнаружил столько же ошибок, сколько и ANTLR. А первая и последние ошибки вообще различаются только названием. Также парсеры были протестированы и на более сложных файлах. Понятное дело, что Roslyn детектирует меньшее количество ошибок, и они более релевантны. Однако для простых случаев, таких как пропущенные и лишние токены (точка с запятой, скобки), ANTLR также отображает релевантную позицию и описание ошибки. Хуже ANTLR справляется с ошибками, в которых часть кода лексера написана вручную (директивы компиляции, интерполируемые строки). Например, сейчас если написать директиву #if без условия, то дальнейшая часть кода вообще не распарсится. Однако в этих случае код для восстановления процесса парсинга также нужно писать вручную (поскольку это контекстно-зависимая конструкция).

Потребление памяти

Как было отмечено выше, ANTLR 4 использует внутренний кэш, полученный в процессе парсинга файлов, для увеличения производительности парсинга последующих файлов. Если обрабатывать слишком много файлов (мы тестировали примерно на 70000 PHP файлах) или повторно парсить файлы в одном и том же процессе, то потребление памяти может значительно увеличится вплоть до нескольких гигабайт. Для очистки кэша необходимо использовать методы интерпретатора lexer. Interpreter. ClearDFA() для лексера и parser. Interpreter. ClearDFA() для парсера после обработки определенного количества файлов или превышения определенного порогового значения потребления памяти.

Решив проблему с очисткой кэша, мы столкнулись с проблемой многопоточной работы парсеров. Опытным путем выяснилось, что использование методов GetAllTokens() и очистки кэша ClearDFA() в лексере (аналогично для парсера) из разных потоков в редких случаях может приводить к исключению «Object reference not set to an instance of an object». Несмотря на то, что такое поведение связано с ошибкой в рантайме ANTLR C#, его можно исправить с помощью блокировки с несколькими читателями (парсерами кода) и одним писателем (чистильщиком кэша) ReadWriterLockSlim.

По вполне очевидным причинам парсер Roslyn при работе не потребляет гигабайты памяти. При парсинге 5 крупных C# проектов aspnet-mvc-6.0.0-rc1, roslyn-1.1.1, corefx, Newtonsoft. Json-8.0.2 и ImageProcessor-2.3.0 пиковое потребление памяти не превысило 200 Мб.

Parsing Actions

The actions themselves are simple: they are a series of fixed tokens mixed with a set of possible tokens, everything in a precise order. The fixed tokens are right in the rule action, while the set of possible tokens are inside other parser rule like size, shape, etc. For example if you are drawing a shape the keyword DRAW is required, while you can choose different values for size.

The format of the language is nice and simple:

That’s because a format like this is meant to be used to describe and generate a simple image. You would not want to fiddle with pixels and precise dimensions to create such images. This is not an image format to be used in an image editor.

We use labels in the position rule (line 10), to capture the position on the horizontal and vertical axes. This is probably the most common use for labels. This way we just have to check the value of x or y, instead of checking for the presence of LEFT or TOP.

Drawing Stuff

In the file Scene.h and most of Scene.cpp, we do very simple and obvious things like setting default values and defining methods to convert from the text input to the proper value. Like in this portion of the header file, in which we define the enums that we need.

We have to define two different center values, to avoid confusion, but there is nothing complex here.

These are all things that you can see for yourself looking at the complete files in the repository.

Things get a bit more interesting when we see functions like getSize and getX. There we set the real meaning of the terms used in data format like the sizes small or medium. We define them in relation to the image size, for example small actually means 20% of the image.

In the other function we deal with an issue of the library that we use to draw the images: CImg. It is a good library, but in our testing the font it uses has some issues, so we mess with the real dimensions of the text, as seen by the rest of our program.

Basically, instead of calculating the correct length of the string drawn (the font is monospaced) we multiply the actual size of each character with 0.82. The result is that we say to the rest of the program that the text occupies less space than what it actually does. So that the text is generally more aligned with the shapes. The process is far from perfect, but it generally looks better this way. The size of the text, of course depends both on the size of the font and the length of the text.

There are three cases:

The equivalent getPosition method for the vertical axis is fundamentally the same, only the name changes, so it is not shown here.

Let’s look at the main function of Scene: draw().

Even this method is quite simple: all we do is drawing each individual element in sequence, then we display and save the whole image as a bitmap file.

The image (line 2) has a fixed size of 512x512x1 (the first three arguments), it is a normal RGB image with 3 channels

and it has a white background (255).

Notice that we use two different methods to get the top left corner of the shape or the text. That is not just because CImg has some issues with text, but because the length of the text is not fixed in relation to the size of the image. It varies depending on the length of the text itself. We have already seen the getX function, that it calls the getPosition function.

The name font (line 12) is a bit of a misnomer: you can only set the size (element.getSize()) and the variability (false, which means fixed-width) of the font. Мы не можем выбрать собственный шрифт. После того, как мы установили шрифт, нам просто нужно вызвать функцию для рисования текста (строка 15). Аргументы 0 и 1 задают цвет фона (прозрачный) и непрозрачность текста (полный).

Очевидно, мы установили разные позиции для каждой из наших фигур (строки 23 и 26), но это просто потому, что функции работают по-разному. Чтобы нарисовать квадрат, вам нужно указать левый верхний угол и длину стороны, вместо того, чтобы нарисовать круг, вам нужно указать центр и его радиус.

Знакомство с грамматикой

Прежде всего: давайте разберемся с грамматикой.

Просто зайдите https://github.com/antlr/grammars-v4 и возьмите нужную вам грамматику. Большинство грамматик имеют очень либеральную лицензию.

Существуют десятки грамматик для таких языков, как R, Scala, Python, Swift, PHP и многих других. Существует также один для Java, но для Java вы предпочитаете использовать JavaParser, я прав?

Просто скопируйте грамматику в свой новый проект в src/main/antlr

) нечувствительны к регистрации. В нечувствительности ANTLR к регистру можно реализовать два способа:

В разработанной грамматике PHP использован первый подход, поскольку лексический анализ обычно выполняется за меньшее время, чем синтаксический. Несмотря на то, что грамматика оказалась все равно зависимой от рантайма, данный подход обеспечивает контрольную задачу по переносу грамматики на другие рантаймы. Более того, мы были созданы в запросе на включение RFC, нечувствительность к регистру. Доказательство концепции — для упрощения описания, нечувствительного к лексеме регистра. Но, к сожалению, он не получил большого одобрения со стороны сообщества ANTLR.

Лексические режимы для PHP, HTML, CSS, JavaScript.

Как известно, вставки PHP-кода могут находиться внутри HTML-кода практически в любом месте. В этом же HTML могут находиться вставки CSS- и JavaScript-кода (эти вставки еще называют «островками»). Например, следующий код (с использованием альтернативного синтаксиса) является допустимым:

К счастью, в ANTLR есть механизм так называемых режимов (mode), которые позволяют переключаться между различными наборами токенов при медленной фазе. Например, режимы SCRIPT и STYLE формируют поток токенов для JavaScript и CSS соответственно (однако в этой грамматике они постепенно просто отключаются). В режиме по умолчанию DEFAULT_MODE генерируются HTML-токены. Стоит отметить, что реализовать поддержку альтернативного синтаксиса в ANTLR можно без единой вставки целевого кода в лексер. А именно так: NonEmptyStatement включает в себя правило inlineHtml, которое, в свою очередь, включает в себя токены, полученные в режиме DEFAULT_MODE:

Сложные контекстно-зависимые конструкции.

Стоит отметить, что ANTLR поддерживает только КС-грамматики, в нем существуют так называемые экшены, т.е. е. вставки дополнительного кода, расширение которых допускается на многих языках, как минимум до контекстно-зависимых. С помощью таких вставок была реализована обработка конструкций, типа Heredoc и других:

Грамматика T-SQL

Несмотря на общий корень «SQL», грамматики T-SQL (MSSQL) и PL/SQL достаточно сильно отличаются друг от друга.

Мы были бы рады не разрабатывать собственный анализатор для этого принципа языка. Однако возникновение парсеров не соответствует критериям полноты охвата, актуальности (грамматика под заброшенным GOLD-парсером) и открытым исходникам на C# (General SQL Parser). Было принято решение о сохранении грамматики TSQL из документации MSDN. получился достойным: грамматика уже соответствует многим результатам встречающихся синтаксических конструкций, опрятно выглядит, независима от рантайма и покрыта тестами (примеры SQL-запросов из того же MSDN). Неприятным моментом разработки было то, что некоторые токены в грамматике являются опциональными. Например, точка с запятой. Побочным эффектом является то, что восстановление после ошибок при разборе из-за этого проходит не очень гладко.

Грамматика PL/SQL

Доработка грамматики PL/SQL заняла еще меньше времени, поскольку сама грамматика уже под ANTLR3. Основная сложность заключалась в том, что она была разработана под java-runtime. Большая часть java-вставок была удалена, так как построить AST можно и без них (как уже говорилось ранее, семантику можно проверить на другом этапе). А такие вставки, как

были заменены фрагментные лексемы:
decimal_key: D E C I M A L, о котором также говорилось ранее.

C#-грамматика

Как это ни странно, но доработка грамматики, поддерживающей версии 5 и 6 языка, оказалась достаточно непростым занятием. Главной сложностью была поддержка интерполяции строк и корректная обработка препроцессорных директив. В силу того что эти вещи являются сильно контекстно-зависимыми, лексер и парсер для обработки директив получились зависимыми от runtime.

Директивы препроцессора

В C# возможна корректная компиляция следующего кода (код после первой директивы не компилирующийся, но и не учитывающийся в компиляции, т. к. false никогда не выполняется):

#if DEBUG && false
Sample not compilied wrong code
var 42 = a + ;
#else
// Compilied code
var x = a + b;
#endif

Для корректной обработки таких случаев код сначала разбивается на массив токенов, находящихся в каналах по-умолчанию, COMMENTS_CHANNEL и DIRECTIVE. Также создается список codeTokens, куда попадают правильные токены для синтаксического разбора. После этого препроцессорный парсер вычисляет значение директивы для препроцессных токенов. Стоит обратить внимание на то, что ANTLR также позволяет писать код для вычисления значения сложного логического выражения прямо в грамматике. Как это реализовано — можно посмотреть в CSharpPreprocessorParser.g4. Значение true или false вычисляется только для директив #if, #elif, else, для всех же остальных директив всегда возвращается true, поскольку они не влияют на то, будет ли последующий код компилироваться. Также в этом парсере можно определить дефолтные Conditional Symbols (по умолчанию определен «DEBUG»).

После того как значение директивы вычислено и принимает значение true, последующие токены добавляются в список codeTokens, в противном случае — нет. Такой подход позволяет игнорировать неправильные токены (как var 42 = a + ; в этом примере) уже на этапе парсинга. Весь этап парсинга также расписан здесь: CSharpAntlrParser.cs.

Интерполяция строк

Данную фичу было очень непросто разрабатывать, потому что, например, закрывающаяся фигурная скобка может означать как часть интерполируемого выражения (interpolation-expression), так и выход из самого режима выражения. А двоеточие может также быть частью выражения, а может означать конец выражения и описание формата вывода (например, #0.##). Кроме того, такие строки могут быть как обычными (regular), так и без экранирующих символов (verbatium), а также могут быть вложенными друг в друга. Подробнее синтаксис описан в MSDN.

Описанные выше вещи продемонстрированы в следующем коде, валидном с точки зрения синтаксиса:

Интерполяция строк была реализован с использованием стека для подсчета уровня текущей интерполируемой строки, а также фигурных скобок. Все это реализовано в CSharpLexer.g4.

Тестирование

Парсер Roslyn, очевидно, не нуждается в тестировании корректности парсинга. А тестированию парсеров ANTLR мы уделили большое внимание:

Производительность парсеров ANTLR и Roslyn

Тестирование проводилось в однопоточном режиме и Release конфигурации без отладчика. Тестировались версии ANTLR 4 4.5.0-alpha003 и Roslyn (Microsoft. CodeAnalysis) 1.1.1.

WebGoat. P HP

Обработанных файлов — 885. Общее количество строк — 137 248, символов — 4 461 768.
Приблизительное время работы — 00:00:31 сек (лексер 55%, парсер 45%).

PL/SQL Samples

Обработанных файлов — 175. Общее количество строк — 1 909, символов — 55 741.
Приблизительное время работы < 1 сек. (лексер 5%, парсер 95%).

CoreFX-1. 0-rc2

Обработанных файлов — 7329. Общее количество строк — 2 286 274, символов — 91 132 116.
Приблизительное время работы:

Roslyn-1

Обработанных файлов — 6527. Общее количество строк — 1 967 672, символов — 74 319 082.
Приблизительное время работы:

Из результатов тестирования проектов CoreFX и Roslyn можно сделать вывод, что разработанный парсер C# на ANTLR не более чем в 5 раз медленнее парсера Roslyn, что говорит о хорошем качестве последнего. Понятно, что написанный «на коленке» за неделю парсер вряд ли сможет конкурировать с такими гигантами, как Roslyn, однако его все же можно использовать для парсинга C#-кода на Java, Python или JavaScript (и других будущих языках), поскольку скорость парсинга все равно быстрая.

На основании всех остальных тестов можно сделать вывод, что лексирование является в основном более быстрой операцией, чем непосредственно разбор. Исключением является лексер PHP, где лексирование заняло даже больше времени, чем разбор. Вероятно это связано со сложной логикой лексера и сложными правилами, но не с регистронезависимыми ключевыми словами, поскольку лексеры T-SQL и PL/SQL (в которых тоже регистронезависимые ключевые слова) работают гораздо быстрее парсеров (раз в 20). Например, если в грамматике C# использовать лексическое правило SHARP: NEW_LINE Whitespace* ‘#’; вместо SHARP: ‘#’;, то лексер будет не в 7 раз быстрее, а в 10 раз медленнее ! Это объясняется тем, что в любом файле очень много пробелов, а лексер на каждой строчке будет пытаться найти символ #, что значительно замедлит его производительность (мы сталкивались с такой проблемой, поэтому нахождение директивы на новой строчке нужно проверять на этапе семантического анализа).

Механизмы обработки ошибок в ANTLR и Roslyn

Был написан простой C#-файл, содержащий все возможные типы ошибок ANTLR:

Как видно, Roslyn обнаружил столько же ошибок, сколько и ANTLR. А первая и последние ошибки вообще различаются только названием. Также парсеры были протестированы и на более сложных файлах. Понятное дело, что Roslyn детектирует меньшее количество ошибок, и они более релевантны. Однако для простых случаев, таких как пропущенные и лишние токены (точка с запятой, скобки), ANTLR также отображает релевантную позицию и описание ошибки. Хуже ANTLR справляется с ошибками, в которых часть кода лексера написана вручную (директивы компиляции, интерполируемые строки). Например, сейчас если написать директиву #if без условия, то дальнейшая часть кода вообще не распарсится. Однако в этих случае код для восстановления процесса парсинга также нужно писать вручную (поскольку это контекстно-зависимая конструкция).

Потребление памяти

Как было отмечено выше, ANTLR 4 использует внутренний кэш, полученный в процессе парсинга файлов, для увеличения производительности парсинга последующих файлов. Если обрабатывать слишком много файлов (мы тестировали примерно на 70000 PHP файлах) или повторно парсить файлы в одном и том же процессе, то потребление памяти может значительно увеличится вплоть до нескольких гигабайт. Для очистки кэша необходимо использовать методы интерпретатора lexer. Interpreter. ClearDFA() для лексера и parser. Interpreter. ClearDFA() для парсера после обработки определенного количества файлов или превышения определенного порогового значения потребления памяти.

Решив проблему с очисткой кэша, мы столкнулись с проблемой многопоточной работы парсеров. Опытным путем выяснилось, что использование методов GetAllTokens() и очистки кэша ClearDFA() в лексере (аналогично для парсера) из разных потоков в редких случаях может приводить к исключению «Object reference not set to an instance of an object». Несмотря на то, что такое поведение связано с ошибкой в рантайме ANTLR C#, его можно исправить с помощью блокировки с несколькими читателями (парсерами кода) и одним писателем (чистильщиком кэша) ReadWriterLockSlim.

По вполне очевидным причинам парсер Roslyn при работе не потребляет гигабайты памяти. При парсинге 5 крупных C# проектов aspnet-mvc-6.0.0-rc1, roslyn-1.1.1, corefx, Newtonsoft. Json-8.0.2 и ImageProcessor-2.3.0 пиковое потребление памяти не превысило 200 Мб.

Parsing Actions

The actions themselves are simple: they are a series of fixed tokens mixed with a set of possible tokens, everything in a precise order. The fixed tokens are right in the rule action, while the set of possible tokens are inside other parser rule like size, shape, etc. For example if you are drawing a shape the keyword DRAW is required, while you can choose different values for size.

The format of the language is nice and simple:

That’s because a format like this is meant to be used to describe and generate a simple image. You would not want to fiddle with pixels and precise dimensions to create such images. This is not an image format to be used in an image editor.

We use labels in the position rule (line 10), to capture the position on the horizontal and vertical axes. This is probably the most common use for labels. This way we just have to check the value of x or y, instead of checking for the presence of LEFT or TOP.

Drawing Stuff

In the file Scene.h and most of Scene.cpp, we do very simple and obvious things like setting default values and defining methods to convert from the text input to the proper value. Like in this portion of the header file, in which we define the enums that we need.

We have to define two different center values, to avoid confusion, but there is nothing complex here.

These are all things that you can see for yourself looking at the complete files in the repository.

Things get a bit more interesting when we see functions like getSize and getX. There we set the real meaning of the terms used in data format like the sizes small or medium. We define them in relation to the image size, for example small actually means 20% of the image.

In the other function we deal with an issue of the library that we use to draw the images: CImg. Это хорошая библиотека, но в ходе нашего тестирования используемый ею шрифт имел некоторые проблемы, поэтому мы путаемся с реальными размерами текста, которые видны остальной части нашей программы.

По сути, вместо вычисления правильной длины нарисованной строки (шрифт моноширинный) мы умножаем фактический размер каждого символа на 0,82. В результате мы говорим остальной части программы, что текст занимает меньше места, чем он занимает на самом деле. Чтобы текст в целом более соответствовал фигурам. Процесс далек от совершенства, но в целом так выглядит лучше. Размер текста, конечно, зависит как от размера шрифта, так и от длины текста.

Есть три случая:

Эквивалентный метод getPosition для вертикальной оси по сути тот же, меняется только имя, поэтому он здесь не показан.

Давайте посмотрим на основную функцию Scene: draw().

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

Изображение (строка 2) имеет фиксированный размер 512x512x1 (первые три аргумента), это обычное изображение RGB с 3 каналами (3) и белым фоном (255).

Обратите внимание, что мы используем два разных метода, чтобы получить верхний левый угол фигуры или текста. Это происходит не только потому, что у CImg есть некоторые проблемы с текстом, но и потому, что длина текста не фиксирована по отношению к размеру изображения. Она варьируется в зависимости от длины самого текста. Мы уже видели функцию getX, которая вызывает функцию getPosition.

Название шрифта (строка 12) немного неправильное: вы можете установить только размер (element.getSize()) и изменчивость (false, что означает фиксированную ширину) шрифта. Мы не можем выбрать собственный шрифт. После того, как мы установили шрифт, нам просто нужно вызвать функцию для рисования текста (строка 15). Аргументы 0 и 1 задают цвет фона (прозрачный) и непрозрачность текста (полный).

Очевидно, мы установили разные позиции для каждой из наших фигур (строки 23 и 26), но это просто потому, что функции работают по-разному. Чтобы нарисовать квадрат, вам нужно указать левый верхний угол и длину стороны, вместо того, чтобы нарисовать круг, вам нужно указать центр и его радиус.

Изучаем грамматику

Перво-наперво: разберемся с грамматикой.

Просто зайдите https://github.com/antlr/grammars-v4 и возьмите нужную вам грамматику. Большинство грамматик имеют очень либеральную лицензию.

Существуют десятки грамматик для таких языков, как R, Scala, Python, Swift, PHP и многих других. Существует также один для Java, но для Java вы предпочитаете использовать JavaParser, я прав?

Просто скопируйте грамматику в свой новый проект в src/main/antlr