Знакомство с antlr
Antlr - генератор парсеров для структурированных текстов. В файле с расширением .g4 описывается грамматика языка, затем antlr генерирует код парсера для одного из доступных target языков (java, c#, python2, python3, js, go, c++, swift). Новые фичи появляются сначала для java, затем для остальных.
На гитхабе есть репозиторий с кучей грамматик. Если повезет, можно найти нужную и не заморачиваться с ее написанием. Но, к сожалению, они там не все рабочие.
Например, когда мне понадобился лексер для скала кода - он не работал. Грамматика была описана, но по ней даже простейший hello world на токены не разбивался. Было несколько issue, но ни кто не хотел этим заниматься. На момент написания статьи я уже оформил pull request и его смержили в мастер.
О своем маленьком опыте с antlr я и хотел написать.
В интернете достаточно статей как написать свой калькулятор на antlr. У меня задача другая. Мне нужно взять существующую грамматику, понять почему она не работает, и пофиксить ее. Приступим. Для начала создадим новый проект… Самый удобный плагин для antlr оказался в gradle.
Нужно:
- добавить antlr плагин
- указать свежую версию antlr для плагина (по умолчанию 2.7.7 - очень старая)
- указать версию antlr-runtime, для использования сгенерированного лексера/парсера
- добавить аргументы и директорию, куда сложить .java классы
plugins {
id 'scala'
id 'antlr'
id 'application'
}
mainClassName = 'ru.d10xa.antlr.Main'
dependencies {
antlr "org.antlr:antlr4:4.7.1"
compile "org.antlr:antlr4-runtime:4.7.1"
compile "org.scala-lang:scala-library:2.12.6"
testCompile "org.scalatest:scalatest_2.12:3.0.5"
}
repositories {
jcenter()
}
generateGrammarSource {
arguments += ['-visitor', '-listener', '-package', 'antlr']
outputDirectory = new File(buildDir, "generated-src/antlr/main/antlr")
}
Скачиваем грамматику для scala
curl -o src/main/antlr/Scala.g4 -L https://github.com/antlr/grammars-v4/raw/master/scala/Scala.g4
Генерируем java классы
gradle generateGrammarSource
src/main/antlr это директория для грамматик по умолчанию для gradle плагина.
Для поиска ошибки нужно узнать на какие токены бьется scala код и какое дерево AST строится. Для этого я беру сгенерированый лексер и печатаю в консоль все токены по очереди, пока не встретится EOF (end of file) Обход дерева производит ParseTreeWalker. Для этого ему нужно указать вершину и передать ParseTreeListener. В Scala и Java вершины называются compilationUnit. Моя имплементация ParseTreeListener будет писать все что видит в println (входы и выходы из правил, а так же терминальные ноды и ошибки).
Код:
import java.nio.charset.Charset
import antlr.ScalaLexer
import antlr.ScalaParser
import org.antlr.v4.runtime.CharStreams
import org.antlr.v4.runtime.CommonTokenStream
import org.antlr.v4.runtime.Lexer
import org.antlr.v4.runtime.ParserRuleContext
import org.antlr.v4.runtime.Token
import org.antlr.v4.runtime.tree.ErrorNode
import org.antlr.v4.runtime.tree.ParseTreeListener
import org.antlr.v4.runtime.tree.ParseTreeWalker
import org.antlr.v4.runtime.tree.TerminalNode
object Main {
def main(args: Array[String]) {
val fileToParse = args(0)
def lexer: ScalaLexer =
new ScalaLexer(CharStreams.fromFileName(fileToParse, Charset.forName("UTF-8")))
def tokens: CommonTokenStream = new CommonTokenStream(lexer)
println("=====")
printTokens(lexer)
println("=====")
val parser: ScalaParser = new ScalaParser(new CommonTokenStream(lexer))
val walker = ParseTreeWalker.DEFAULT
val parseTreeListener = new PrintlnParseTreeListener(parser)
val compilationUnit = parser.compilationUnit
walker.walk(parseTreeListener, compilationUnit)
}
def printTokens(lexer: ScalaLexer): Unit = {
def tokenStream(lexer: Lexer): Stream[Token] =
lexer.nextToken() match {
case t if t.getType == Token.EOF => Stream.empty
case t => t #:: tokenStream(lexer)
}
val tokensForPrint: Seq[String] =
tokenStream(lexer).toList.zipWithIndex.map {
case (token, index) =>
val name = lexer.getVocabulary.getDisplayName(token.getType)
val value = token.getText
s"${index + 1}) $name: $value"
}
tokensForPrint foreach println
}
class PrintlnParseTreeListener(parser: ScalaParser) extends ParseTreeListener {
override def visitTerminal(node: TerminalNode): Unit = {
println(s"visitTerminal, $node")
}
override def visitErrorNode(node: ErrorNode): Unit = {
println(s"visitErrorNode, $node")
}
override def enterEveryRule(ctx: ParserRuleContext): Unit = {
val names: Array[String] = parser.getRuleNames
println(s"enterEveryRule, ${names(ctx.getRuleIndex)} $ctx")
println(ctx.getText)
}
override def exitEveryRule(ctx: ParserRuleContext): Unit = {
println(s"exitEveryRule, $ctx")
}
}
}
Пример выхлопа для Scala.g4
package foo.bar
object HelloWorld {
def main(args: Array[String]): Unit = {
println("Hello, world!")
}
}
=====
1) 'package': package
2) Id: example
3) 'object': object
4) Id: HelloWorld
5) '{': {
6) 'def': def
7) Id: main
8) '(': (
9) Id: args
10) ':': :
11) Id: Array
12) '[': [
13) Id: String
14) ']': ]
15) ')': )
16) ':': :
17) Id: Unit
18) '=': =
19) '{': {
20) Id: println
21) '(': (
22) StringLiteral: "Hello, world!"
23) ')': )
24) '}': }
25) '}': }
=====
enterEveryRule, compilationUnit []
packageexampleobjectHelloWorld
visitTerminal, package
enterEveryRule, qualId [1411]
example
visitTerminal, example
exitEveryRule, [1411]
enterEveryRule, topStatSeq [1420]
objectHelloWorld
enterEveryRule, topStat [1373 1420]
objectHelloWorld
enterEveryRule, tmplDef [1393 1373 1420]
objectHelloWorld
visitTerminal, object
enterEveryRule, objectDef [1237 1393 1373 1420]
HelloWorld
visitTerminal, HelloWorld
enterEveryRule, classTemplateOpt [1265 1237 1393 1373 1420]
exitEveryRule, [1265 1237 1393 1373 1420]
exitEveryRule, [1237 1393 1373 1420]
exitEveryRule, [1393 1373 1420]
exitEveryRule, [1373 1420]
exitEveryRule, [1420]
exitEveryRule, []
Для других грамматик можно использовать этот код, заменив ScalaLexer, ScalaParser на НазваниеГрамматикиLexer, НазваниеГрамматикиParser. Если parseTree в грамматике отличен от compilationUnit, можно указать другой интересующий.
Как запускать main class описывать не буду. Расскажу как я запускал gui. Я пробовал запускать через плагин к Intellij Idea, но у меня он часто вызывал полное зависание IDE. Видел даже специальный редактор для грамматик ANTLRWorks, выглядит круто(на youtube), но поддерживает только antlr3
Простой shell скрипт оказался самым удобным способом запустить gui.
#!/usr/bin/env bash
if [ "$#" -ne 3 ]; then
echo "Illegal number of parameters"
echo "> GrammarName startRuleName input-filename(s)"
exit 1
fi
GRAMMAR_NAME="$1"
START_RULE_NAME="$2"
INPUT_FILENAMES="$3"
WORKDIR="$(pwd)/.antlr-tmp"
ANTLR_JAR="antlr-4.7.1-complete.jar"
ANTLR_JAR_PATH="${WORKDIR}/jar/${ANTLR_JAR}"
rm -r "$WORKDIR/build/"
mkdir -p "$WORKDIR/jar"
mkdir -p "$WORKDIR/build"
if ! [ -s "$ANTLR_JAR_PATH" ]; then
curl -o "$ANTLR_JAR_PATH" "https://www.antlr.org/download/$ANTLR_JAR"
fi
cp "$(pwd)/src/main/antlr/$GRAMMAR_NAME.g4" "$WORKDIR/build/"
cd "$WORKDIR/build/"
java -jar "${ANTLR_JAR_PATH}" "$GRAMMAR_NAME.g4"
export CLASSPATH="${WORKDIR}/build/:${ANTLR_JAR_PATH}"
javac *.java
cd -
java org.antlr.v4.gui.TestRig "$GRAMMAR_NAME" "$START_RULE_NAME" -gui "$INPUT_FILENAMES"
Редактирование файла .g4
Я пробовал idea и visual studio code. В idea кроме подсветки синтаксиса ничего не работает, или работает плохо. Даже самое необходимое “go to definition” не работает. В visual studio code редактировать гораздо удобнее. Go to definition работает, и даже при наведении курсора мыши показывает код правила для лексера или парсера. То есть даже прыгать к объявлению не приходится. Во вкладке OUTLINE можно фильтровать правила по названию.
Поиск и устранение ошибок
Опишу одну из ошибок, с которыми я столкнулся. Алгоритм решения был везде похожий.
Строка def main(args: Array[String]): Unit разбилась на токены неверно.
Это можно было увидеть по набору токенов, которые я вывел в println. Один из токенов был args:, вместо args.
Смотрим название правила, по которому выделился токен. В строке 9) Id: args: правило называется Id.
Само правило выглядит так:
Id : Plainid | '`' (CharNoBackQuoteOrNewline | UnicodeEscape | CharEscapeSeq )+ '`' ;
То есть Id в Scala это либо простой id, либо токен с опциональными особыми символами, но обернутый обратными апострофами.
Тут и так понятно, что args: парсится как Plainid и проблема в нем. Но я объясню суть “дебага” именно на нем.
Выносим Plainid как отдельное правило, чуть выше Id. Например, IdTemp.
IdTemp : Plainid ;
В токенах видим, что args: это IdTemp 9) IdTemp: args:.
Значит нужно повторить операцию с Plainid, разбив его на более простые токены,
и дальше станет понятно, откуда приехало двоеточие.
Иногда, внимательного чтения достаточно, но в некоторых случаях, проще поредактировать файл с грамматикой
и посмотреть как меняется набор токенов.
Заключение:
Antlr очень мощный инструмент для написания сложных парсеров. Там где не справляются регулярки(а именно, вложенные структуры) - antlr спешит на помощь.
Ссылки: