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: неформальное введение
