🏆 Рейтинг ІТ-работодателей 2019: уже собрано более 5000 анкет. Оцените свою компанию!
×Закрыть

ANTLR: немного теории

С преподаванием теории программирования вечно какая-то путаница. В большинстве вузов её излагают на первых двух курсах, когда студент еще не умеет толком писать программы и не понимает, как использовать полученные знания. Да и курс, как правило, не содержит достаточное количество жизненных, практических примеров. Поэтому к этим знаниям относятся как к нудной схоластике. Они зазубриваются, лишь бы сдать, и напрочь забываются к последнему курсу. В результате, когда теория нужна в работе, программист даже не понимает, что ее нужно применить.

Я пойду другим путём: буду излагать только то, что нужно для работы или понадобится в ближайшее время для объяснения практического примера. К более сложным концепциям вернусь потом, когда будет понимание, зачем это сложное вообще надо.

Напомню, что ANTLR — это фреймворк для генерации парсеров текста. Если пока что совсем с ним не знакомы, прочтите неформальное введение.

Грамматика

Он как-то похвалил мой итальянский язык, и мы с ним подолгу разговаривали по-итальянски. Я сказал, что итальянский язык кажется мне слишком легким для того, чтобы серьезно им заинтересоваться. Все кажется в нем так легко. «О да, — сказал майор. — Но почему же вы не обращаете внимания на грамматику?» И мы обратили внимание на грамматику, и скоро итальянский язык оказался таким трудным, что я боялся слово сказать, пока правила грамматики не улягутся у меня в голове.
Эрнест Хемингуэй «В чужой стране»

Существует очень много определений грамматики, но пока они нам не нужны. В ANTLR используется только небольшое подмножество. Итак, контекстно-независимая порождающая грамматика — это не более, чем набор продукций, выражений вида X → Y, где X и Y — цепочки символов или правил. Начинается грамматика со стартового правила, например S.

Если путём подстановки из главного правила можно получить некоторую строку, она соответствует грамматике. Если нельзя, то нет.

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

S → (S)
S→ ɛ, где ɛ - специальный символ, обозначающий пустоту.

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

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

Спецсимволы, или Расширенное определение грамматик

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

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

Если мы хотим сказать, что правило A порождает цепочку B, это можно записать так:

A → B
A → C

или так:

A → B|C

Перечисления

Чтобы сказать, что цепочка встречается один или более раз, используется символ «+», нуль или более раз - «*», нуль или 1 раз - «?».

Пример. Допустим, мы хотим создать грамматику, описывающую цепочку букв «a».

Если хотя бы одна буква должна присутствовать, записать это можно так:

S→a+

Если мы хотим, чтобы грамматике соответствовала цепочка вообще без букв, запишем это так:

S→a*

В случае, когда буква «а» может встретиться нуль или один раз, так:

S→a?

Теперь вернёмся к грамматике из предыдущей статьи.

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];

Как видно, в ANTLR вместо стрелочек используется двоеточие (возможно, потому, что стрелочка относится к спецсимволам и её просто нет на большинстве клавиатур). В остальном применение спецсимволов совпадает с определением, данным выше. Кое-что из текущей грамматики осталось не до конца описанным. Самое время дать пояснения.

Лексический и синтаксический анализ

В теории автоматов, на которой базируются грамматики, никаких лексических и синтаксических анализов нету. Изучается структура данных под названием «автомат». На вход ей подаются символы из изучаемой строки, в конце этого процесса автомат находится в состоянии, говорящем о том, соответствует ли строка грамматике или нет.

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

Обратите внимание на грамматику из предыдущей статьи. В ней есть правила, начинающиеся с большой буквы, — это лексемы. И с маленькой — это, собственно, правила. Разбиение на правила и лексемы, в общем-то, условно. В самом деле, что считать правилом, а что лексемой? В ANTLR есть одно важное отличие: правила могут состоять из правил, лексем и строк; лексемы — только из строк, других лексем и фрагментов. Что же такое фрагмент? Это часть грамматики, которая может быть только частью лексемы, частью же правила быть не может. То есть вот так написать можно:

INT :'-'? DIGIT+ ; 
fragment DIGIT : [0-9];

А так нет:

int :'-'? DIGIT+ ; 
fragment DIGIT : [0-9];

Леворекурсивные грамматики

Один мудрый человек сказал, что после фразы «один мудрый человек сказал» обычно пишут какую-то дурь. ©

ANTLR, как и любое другое программное обеспечение, не упало нам с неба. Его кто-то написал и в процессе пользовался неким алгоритмом. Он называется LL(1)-парсинг, или леворекурсивный парсинг, или рекурсивный обход слева направо. Приводить его алгоритм целиком мы не будем, желающие могут погуглить. Но важно, что с правилом, содержащим самого себя в правой части, без продвижения по строке этот алгоритм справиться не может. То есть при обработке вот такого правила:

A→Aabc

он зациклится. Пояснить это в двух словах можно так: алгоритм этот разбирает грамматику слева направо, рекурсивно. То есть при разборе предыдущего правила вызовется правило для разбора A рекурсивно. Потом ещё раз A и ещё раз. И так пока не переполнится стек.

Если вернуться от абстрактной теории к конкретному фреймворку, у меня для вас две хороших новости и одна плохая. Новость хорошая: ANTLR, начиная с четвёртой версии, поддерживает леворекурсивные грамматики. Новость плохая: это только для непосредственной левой рекурсии. Косвенную он по-прежнему обработать не может. У косвенной левой рекурсии, конечно же, есть определение, но оно сложное, поэтому его мы приводить не будем. Вместо этого рассмотрим вот такую грамматику:

Value→[0-9]+ ‘/’ '(' Expr ')'
Product → Expr (('*' / '/') Expr)*
Sum     → Expr (('+' / '-') Expr)*
Expr    → Product |Sum | Value

Как видно, при вызове Expr необходимо сразу же, без продвижения по строке, анализировать Product, а при вызове Product — Expr, тоже без продвижения. Правило сразу же вызывает другое правило и происходит зацикливание. И ещё одна хорошая новость: существует алгоритм устранения левой рекурсии из грамматики, как непосредственной, так и косвенной. Его мы приводить тоже не будем, поскольку по словам «устранение левой рекурсии» алгоритм запросто находится в Гугле.

Какой код генерирует ANTLR

Как я уже писал в предыдущей статье, для обработки грамматики можно использовать два принципиально различных способа: visitor и listener.

Листенер

Для листенера ANTLR генерирует интерфейс, наследуемый от ParseTreeListener. В нем для каждого правила или метки (мы вернемся к ним позже).

Он выглядит вот так:

 // Generated from CuttingLanguage.g4 by ANTLR 4.4
package org.newlanguageservice.ch1;
import org.antlr.v4.runtime.misc.NotNull;
import org.antlr.v4.runtime.tree.ParseTreeListener;

/**
 * This interface defines a complete listener for a parse tree produced by
 * {@link CuttingLanguageParser}.
 */
public interface CuttingLanguageListener extends ParseTreeListener {
	/**
	 * Enter a parse tree produced by {@link CuttingLanguageParser#action}.
	 * @param ctx the parse tree
	 */
	void enterAction(@NotNull CuttingLanguageParser.ActionContext ctx);
	/**
	 * Exit a parse tree produced by {@link CuttingLanguageParser#action}.
	 * @param ctx the parse tree
	 */
	void exitAction(@NotNull CuttingLanguageParser.ActionContext ctx);
	/**
	 * Enter a parse tree produced by {@link CuttingLanguageParser#lineTo}.
	 * @param ctx the parse tree
	 */
	void enterLineTo(@NotNull CuttingLanguageParser.LineToContext ctx);
	/**
	 * Exit a parse tree produced by {@link CuttingLanguageParser#lineTo}.
	 * @param ctx the parse tree
	 */
	void exitLineTo(@NotNull CuttingLanguageParser.LineToContext ctx);
	/**
	 * Enter a parse tree produced by {@link CuttingLanguageParser#actions}.
	 * @param ctx the parse tree
	 */
	void enterActions(@NotNull CuttingLanguageParser.ActionsContext ctx);
	/**
	 * Exit a parse tree produced by {@link CuttingLanguageParser#actions}.
	 * @param ctx the parse tree
	 */
	void exitActions(@NotNull CuttingLanguageParser.ActionsContext ctx);
	/**
	 * Enter a parse tree produced by {@link CuttingLanguageParser#moveTo}.
	 * @param ctx the parse tree
	 */
	void enterMoveTo(@NotNull CuttingLanguageParser.MoveToContext ctx);
	/**
	 * Exit a parse tree produced by {@link CuttingLanguageParser#moveTo}.
	 * @param ctx the parse tree
	 */
	void exitMoveTo(@NotNull CuttingLanguageParser.MoveToContext ctx);
}

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

Визитор

С визитором та же история, интерфейс наследуется от ParseTreeVisitor и является параметризируемым. Это говорит о том, что каждый метод визитора должен возвращать некоторое значение. Именно этим отличается визитор от листенера, а ещё тем, что методы, соответствующие правилу, вызываются только один раз.

Метки грамматик

Допустим, имеется вот такая грамматика:

grammar Arithmetic;

expr
:   expr '+' expr #plus
	| expr '-' expr #minus
	| expr '*' expr #mul
	| expr '/' expr #div
	| INT #int
;

INT :[0-9]+;

WS: [ \t\r\n]+ -> skip; 

Она содержит непосредственную левую рекурсию, но, как мы говорили выше, ANTLR умеет с ней справляться. Однако, как сделать, чтобы на каждую арифметическую операцию было одно действие без переписывания самой грамматики — так, как показано в листинге выше. Мы добавляем к правилам метки названия правил с решеткой. И после этого сгенерированные грамматикой листенер и визитор будут содержать методы-обработчики и для меток.

Выглядеть это будет так:

// Generated from Arithmetic.g4 by ANTLR 4.7.2
import org.antlr.v4.runtime.tree.ParseTreeVisitor;

/**
 * This interface defines a complete generic visitor for a parse tree produced
 * by {@link ArithmeticParser}.
 *
 * @param <T> The return type of the visit operation. Use {@link Void} for
 * operations with no return type.
 */
public interface ArithmeticVisitor<T> extends ParseTreeVisitor<T> {
	/**
	 * Visit a parse tree produced by the {@code div}
	 * labeled alternative in {@link ArithmeticParser#expr}.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	T visitDiv(ArithmeticParser.DivContext ctx);
	/**
	 * Visit a parse tree produced by the {@code minus}
	 * labeled alternative in {@link ArithmeticParser#expr}.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	T visitMinus(ArithmeticParser.MinusContext ctx);
	/**
	 * Visit a parse tree produced by the {@code mul}
	 * labeled alternative in {@link ArithmeticParser#expr}.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	T visitMul(ArithmeticParser.MulContext ctx);
	/**
	 * Visit a parse tree produced by the {@code int}
	 * labeled alternative in {@link ArithmeticParser#expr}.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	T visitInt(ArithmeticParser.IntContext ctx);
	/**
	 * Visit a parse tree produced by the {@code plus}
	 * labeled alternative in {@link ArithmeticParser#expr}.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	T visitPlus(ArithmeticParser.PlusContext ctx);
}

Смотрите, появились правила visit..., где ... — имя метки. Хотя в грамматике таких правил нет.

В завершение

Вот вкратце всё, что я хотел рассказать по теории. На первое время хватит. Будут и другие экскурсы, но непосредственно, когда они понадобятся. Следующая статья будет посвящена обзору инструментов для ANTLR-разработки.


Предыдущая часть цикла: ANTLR: неформальное введение

LinkedIn

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

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

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

Вот поэтому статьи Кожаева очень полезны. Одно дело ковырять большую, толстую серьезную книжку и другое познакомится с грамматиками в варианте, что предлагает ТС.
Он на пальцах и упрощенно о сложном рассказывает. Для общего понимания что это, для чего и как его есть — этого часто достаточно.

Ну проблема же не в сложности.
Проблема в том, что оно работает неочевидно для обычной жизни.
Тоесть нет особой проблемы разобраться и что-то вроде как делать, но есть проблема делать что-то более-менее сложное с ипользованием грамматик.
Грамматики шикарная концепция, но, похоже, для оперирования надо абстрактное мышление выше 130 по IQ тестам(на абстрактной части).

Таки надо и IQ тут не причем. Кому эта тема интересна, те обучают себя и на такой тип мышления и делают эти задачи.

Кожаев? И не о мордобое?

А вообще ВовкаМорковка мне твоя статья понравилась. Легко читать. Просто изложено, как применять оное.

З.Ы. Только не хватает ссылок на то, что читать, кто хочет глубоко вникнуть в тему.

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

Она не плохая, но упор я буду делать на то чего в этой книге нет, или изложено плохо

и, кстати, вот ссылочка на курс который чуть более чем на половину про antlr: docs.google.com/...​cjTLr83qGK6mQ_JiwVYGg/pub

А вот первое видео курса по компиляторам от University of Washington: www.youtube.com/watch?v=Kk22pqxy_VI там есть версии всего курса с разбором половины драгон бука. Это не про ANTLR, но там много чего про грамматики и парсеры.

Мне кажется что книжка по ANTLR4 покрывает эту статью с головой, но +1 за тех статью на доу это вообще тут редкость. Хорошая вводная статья!

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

Есть еще курс компиляторов от стенфорда на курсере, но тру, драгон бук осилить это не шутка. В общем +1 за статью!

Вот это несколько олдфажно, но теория там подаётся кошерно:
www.goodreads.com/...​ion-for-digital-computers

не кажется что книжка по ANTLR4 покрывает эту статью с головой,

Да. Но много ты знаешь на ДОУ личностей, что осилят оное?
А вот Кожаев же спустился до идиотов и объясняет им элементарное.
И за это я ему аплодирую.

я его изучал в институте, именно тогда когда не умел еще толком программировать. не скажу что в жизни пригодилось, просто знаю что такая штука есть ;-)

Мы используем для своего DSL запросов, который потом транслируем в mongo filter.

Спасибо, мы его уже допилили до довольно вменяемого состояния.

Возможно вам понадобится IDE, или графическая интерпретация

public interface CuttingLanguageListener extends ParseTreeListener
public interface ArithmeticVisitor extends ParseTreeVisitor

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

Есть же вещи с хорошим и приятным синтаксисом, без листнеров, визиторов и прочей «архитектуры», парсбек, например.
github.com/djspiewak/parseback

ANTLR это стандарт, под него куча книг, форумов, уже готовых грамматик и парсеров в конце-концов. Поэтому, если ты хочешь что либо сделать быстро выбираешь его. Я ведь парсерами и грамматиками зарабатываю деньги — не развлекаюсь. Играть можно с чем угодно вообще

JS и PHP тоже стандарты. Они что, хорошие языки? На них хорошо писать? На них получаются хорошие продукты? Если это стандарт то это уже автоматически хорошо? Если это 300 раз расписано зачем об этом на доу писать? Писать надо о том, о чём информация устарела или её нет.

JS и PHP тоже стандарты. Они что, хорошие языки?

Да, быстро можно заработать денег.

На них хорошо писать? На них получаются хорошие продукты?

Да, весь web это PHP и js

Если это 300 раз расписано зачем об этом на доу писать?

Мой родной язык русский, я пишу статьи на нём потом перевожу на английский. Если я уже всё равно написал почему-бы не опубликовать на dou

исать надо о том, о чём информация устарела или её нет.

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

Да, быстро можно заработать денег.

Работая ассенизатором можно тоже быстро заработать денег. НЕ показатель хорошести языка.

Да, весь web это PHP и js

 Все товары — это Китай. Китайские товары за минимальную цену лучшие?

Работая ассенизатором можно тоже быстро заработать денег.

Кому как

Все товары — это Китай. Китайские товары за минимальную цену лучшие?

Внезапно да, лучшие по соотношению цена/качество.

Работая ассенизатором можно тоже быстро заработать денег. НЕ показатель хорошести языка.

Зато показатель полезности твоей деятельности для других людей.

Люди по молодости думают, что чем экзотичные их инструмент, тем они круче. А потом ходят и думают: почему меня такого умного и красивого на работу не берут? Я же брейнфак знаю, на нем писать очень сложно! И не понимают, дурашки, что работодателю нужны не интеллектуальные игры, а работа в срок и подешевле

Да вы батенька поди тёплое с мягким путаете

брейнфак

сделали просто понтов ради.
скалу сделали из прагматичных целей:
1) убрать бойлерплейт
2) повысить надёжность
3) убрать монополию ООП и необходимость городить огромные огородные костыли
4) позволить расширять язык так как это надо пользователю
Судя по тому что экосистема живенькая и челики активно используют её в проде, у одерского и Co. получилось. То что на каждом углу не хайрят — ну уж извините, язык молодой и не был создан как затычка в пустующую нишу.

Скала это одно, фреймворк без поддержки и сообщества — другое

«Поддержка сообщества» и т.д. это не всегда показатель качества продукта. Вон гугловская(тм) либа для датастора github.com/...​ts/google-cloud-datastore. Но хорошей она не является — надо много потеть чтобы из неё что-то сделать что то годное, и потеть без поддержки сообщества.

Работая ассенизатором можно тоже быстро заработать денег.

Лучше честно и быстро заработать вывозом говна, чем сидеть безработным и жаловаться.

Они что, хорошие языки? На них хорошо писать? На них получаются хорошие продукты?

Можеш будь-ласка пристібнути в профіль лінкедін щоб ми могли бачити с ким маємо справу?

Писать надо

Бери і пиши, тут на ДОУ редакція дуже демократична.

Scala? нет спасибо! закопайте обратно эту стюардессу!

По описанию parseback крут, но похож на какое-то abandonware. Последняя сборка, как я понимаю под Scala 2.11 последний релиз в 2017 году. Для себя потыкать можно, но в комерческий код безопаснее тащить fastparse или scala-parser-combinators.

Угадал автора по заголовку 😎.

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