Пока индексируется github (благодаря лимиту в 5000 запросов в час), который нужен для получения данных для статьи, поговорим о тестировании лексеров и парсеров.
Обсудим пожелания к процессу разработки грамматик, их тестированию и контролю качества, чтобы не превратиться в существо с картинки.
Типичный разработчик парсера Основная проблема при разработке парсеров — высокая вариативность входных данных; комбинации языковых элементов могут свести с ума, особенно если это какой-нибудь C++.
Конечно, вы можете взять большие объемы исходного кода и ждать несколько дней, пока все будет проанализировано и вы получите отчет об ошибках.
Но проблема в том, что нужен TDD, причем такой, чтобы максимум за 15 секунд можно было получить хотя бы 100% охват всех вариантов грамматики (включая комбинации).
Отдельно стоит упомянуть лексер, так как даже с токенами часто возникают проблемы.
Пример, когда даже жетоны стреляют тебе в ногу При участии в разработке анализатора C++ стояла задача разработать препроцессор, особенность заключалась в том, что файлы для ускорения отладки кэшировались в виде конвертированных файлов, которые можно было бы проанализировать обычным парсером C++, но если бы не было кэш, затем парсер перешел к вводу токенов из препроцессора.
Как оказалось, несмотря на то, что вклеивание токенов в текст давало правильный результат, сами токены были неправильными и парсер вылетал с ошибкой.
Чтобы охватить такое большое количество вариантов грамматики за столь короткое время, вам придется опираться лишь на небольшие примеры, демонстрирующие конкретную работу парсера, например:
Конечно, читатель может подумать, а какой смысл в таких тестах, если они такие простые? Так же и сам парсер прост, но после него он становится настолько сложным, что без гарантии, что парсер работает именно так, как надо, его может быть очень сложно отлаживать, потому что вы будете тратить время на ненужные случаи, которые нужно будет отладить.class Example { boolean flag; }
проверил.
В результате время тратится на мелочи.
Очевидным преимуществом небольших, правильных с точки зрения парсера примеров (или синтаксически правильных, семантику трогать не надо) является возможность указать тысячи таких вариантов, гарантируя, что все они отработаются в кратчайшие сроки.
чрезвычайно короткие сроки, позволяющие разработчику в любой момент скомпилировать проект и запустить тесты, на которых захочется проверить работу.
Разработка парсера превращается в TDD, когда сначала пишешь пример для парсинга, а потом пишешь правила.
Еще одним преимуществом является тот факт, что если что-то сломается, человеку будет проще искать нужную информацию в десятке файлов, чем в огромном файле на десяток разделов, не говоря уже о том, что найти дельты больших файлов все равно сложно.
проблема.
Однако есть недостаток: нужно уметь видеть, какие варианты грамматик являются уникальными наборами.
Вы же не скажете, что изменив имя переменной в примере вы добавили новый регистр? Вы можете протестировать идентификаторы в отдельной папке, не вдаваясь в подробности этой функции где-либо еще.
Предлагаю рассмотреть следующий вариант: у нас есть язык C# и тернарный оператор, вопрос в том, сколько уникальных вариантов использования мы можем выбрать? (Можно написать в комментариях) А пока вот вам несколько важных опций:
- ИДЕНТИФИКАТОР? Я СДЕЛАЛ
- ИДЕНТИФИКАТОР? БУКВАЛЬНЫЙ: БУКВАЛЬНЫЙ
- ИДЕНТИФИКАТОР? ? ЛЮБОЙ: ЛЮБОЙ
Антлру просто не хватило глубины поиска в правилах и он не смог поймать вертушку.
В то же время это второстепенная проблема, которую совершенно недопустимо решать путем анализа больших объемов информации.
В то же время, даже если вы обнаружите такую ошибку в большом коде, не помешает вытащить из него достаточно небольшой участок, чтобы воспроизвести ошибку и отладить ее, не заморачиваясь вокруг ненужными данными.
Что лучше, отлаживать проект размером 100 МБ один раз в час или запускать тест хотя бы 1000 раз по 0,001 секунды?
Тестирование лексера
Чтобы быть абсолютно уверенным в неизменяемости вывода лексера и дать гарантию на следующие этапы обработки, следует обеспечить вывод токенов.Шаг токенизации берет на себя лексер; Также на этом этапе полезно добавить предварительную обработку, чтобы на выходе можно было сразу получить готовый поток токенов.
Для таких языков, как C++, лексер просто нужно запускать отдельно от парсера, чтобы получить правильный вывод — иначе вы не сможете открыть все макросы.
Соответственно для этого нужно сначала прогнать все файлы через лексер, а уже потом парсер.
Один из вариантов - сохранить поток результата работы лексера - токенов - в файл как есть, но люди еще не научились читать бинарные файлы, поэтому предлагаю использовать json, это не только поможет увидеть изменения через дельты с минимальным шумом, но и автоматизирует поиск разницы.
{
"tokens" : [ {
"tokenType" : "PACKAGE",
"statement" : "1:0[7]"
}, {
"tokenType" : "Identifier",
"statement" : "1:8[7]",
"text" : "example"
}, {
"tokenType" : "SEMI",
"statement" : "1:15[1]"
}, {
"tokenType" : "CLASS",
"statement" : "3:0[5]"
}, {
"tokenType" : "Identifier",
"statement" : "3:6[7]",
"text" : "Example"
}, {
"tokenType" : "FoldBlock",
"statement" : "3:14[21]",
"children" : {
"tokens" : [ {
"tokenType" : "LBRACE",
"statement" : "3:14[1]"
}, {
"tokenType" : "BOOLEAN",
"statement" : "4:4[7]"
}, {
"tokenType" : "Identifier",
"statement" : "4:12[4]",
"text" : "flag"
}, {
"tokenType" : "SEMI",
"statement" : "4:16[1]"
}, {
"tokenType" : "RBRACE",
"statement" : "5:0[1]"
}, {
"tokenType" : "EOF",
"statement" : "5:1[3]"
} ]
}
}, {
"tokenType" : "EOF",
"statement" : "6:0[5]"
} ]
}
Я уверен, что вам не составит труда обнаружить разницу, если что-то изменится в файле или вы измените обработку токенов.
Следует отметить, что токены характеризуются не только типом, но и текстом, причем для некоторых токенов текст нам не важен, поэтому где-то необходимо хранить список типов токенов, для которых нужно хранить текст. .
В моем примере для этого используется ParserService, но можно и статический, если вам достаточно одного языка, или вообще встраивать эти данные в тест, что отчасти не лучший вариант (причина будет позже) .
Имея на руках такой дамп представления файла, написать модульный тест довольно легко: def testLexer(suite: Suite): Unit = {
implicit val ps: ParserService = ParserService(suite.language)
for (fi <- suite.fileInfos) {
assertFile(fi.file)
val lexerOutput: LexerOutput = readFromFile[LexerOutput](testConfig(LexerSuiteDir, suite, fi.file))
val lexer = ps.newLexer(asVirtualFile(fi))
val stream = new CommonTokenStream(lexer)
stream.fill()
val tokens = CollectionConverters.asScala(stream.getTokens)
assertTokens(lexer, lexerOutput, tokens)
}
}
private def assertTokens(lexer: AbstractRScanLexer, lexerOutput: LexerOutput, tokens: mutable.Buffer[Token]): Unit = {
val queue = new mutable.Queue[LexerOutputToken]()
queue ++= lexerOutput.tokens
for (t <- tokens) {
assertTrue(queue.nonEmpty, "Queue should not be empty")
val lot = queue.dequeue()
val tokenType = lexer.getVocabulary.getSymbolicName(t.getType)
assertEquals(lot.tokenType, tokenType, "Token types are not equal")
assertEquals(lot.statement, tokenStatement(t), "Token types are not equal")
if (lot.text != null) {
assertEquals(lot.text, t.getText, "Texts are not equal")
}
if (lot.children != null) {
assertTrue(t.isInstanceOf[RScanToken], "Must be RScanToken")
val rt = t.asInstanceOf[RScanToken]
assertTrue(rt.foldedTokens().
nonEmpty, "Must have fold tokens") assertTokens(lexer, lot.children, rt.foldedTokens().
toBuffer) } else { assertFalse(t.isInstanceOf[RScanToken] && t.asInstanceOf[RScanToken].
foldedTokens().
nonEmpty, "No fold tokens allowed")
}
}
if (queue.nonEmpty && queue.head.tokenType.equals("EOF")) queue.dequeue()
assertTrue(queue.isEmpty, "Queue must be empty")
}
Все, что мы делаем, это проверяем совпадение ключа и специального текста в потоке токенов, но если наш токен содержит свертку, то мы просто рекурсивно продолжаем проверку токенов.
Выделив код в библиотеку, вы можете добавить тестирование лексера, просто написав конфигурацию для теста: class JavaParserTest extends AbstractJUnitAntlr4Test {
@ParameterizedTest(name = "[{index}] {0}")
@MethodSource(Array("testFiles"))
override def testLexer(suite: Suite): Unit = {
super.testLexer(suite)
}
@ParameterizedTest(name = "[{index}] {0}")
@MethodSource(Array("testFiles"))
override def testParser(suite: Suite): Unit = {
super.testParser(suite)
}
}
object JavaParserTest {
private val TestDataDirectory = "/test/java/unit"
def testFiles: java.util.stream.Stream[Arguments] = Antlr4TestUtils.filesFromResourceDirectory(JavaLanguage.ref, TestDataDirectory, getClass, Seq("java"))
}
Этот тест создаст коллекцию наборов тестовых данных (набор) из папки ресурсов /test/java/unit, а junit создаст все необходимые тесты и передаст каждый из них в качестве параметра нашему методу testLexer, а затем вызовет родительский метод. и вуаля — наша грамматика проверена, и так для любого языка.
Сгенерируйте дампы и запустите тест! java -Xmx128m -Dfile.encoding=UTF-8 -classpath $CLASSPATH \
org.lastrix.rscan.test.ParserTestSuiteGenerator \
-l Java -d $TEST_PATH -e .
java
.
/gradlew clean test
Тестирование парсера
Тестирование лексера — простая и тривиальная задача.
Но главная проблема при тестировании парсера — это то, как вы работаете с AST. Идеальным вариантом будет работа не с сырым AST, а с обогащенным, уже оснащенным данными, что позволит уменьшить объем выходных данных, например так: {
"languageName" : "Java",
"items" : [ {
"keyText" : "RAW_DECL_PACKAGE at field000.java[1:0-5:1]",
"children" : [ {
"keyText" : "NAME at field000.java[1:8-1:15]",
"children" : [ {
"keyText" : "UNRESOLVED_ID at field000.java[1:8-1:15]",
"specText" : "example"
} ]
}, {
"keyText" : "RAW_DECL_CLASS at field000.java[3:0-5:1]",
"children" : [ {
"keyText" : "NAME at field000.java[3:6-3:13]",
"children" : [ {
"keyText" : "UNRESOLVED_ID at field000.java[3:6-3:13]",
"specText" : "Example"
} ]
}, {
"keyText" : "MEMBERS at field000.java[3:14-5:1]",
"children" : [ {
"keyText" : "RAW_DECL_FIELD at field000.java[4:4-4:16]",
"children" : [ {
"keyText" : "RAW_TYPE at field000.java[4:4-4:11]",
"children" : [ {
"keyText" : "UNRESOLVED_ID at field000.java[4:4-4:11]",
"specText" : "boolean"
} ]
}, {
"keyText" : "RAW_DECL_VARIABLE at field000.java[4:12-4:16]",
"children" : [ {
"keyText" : "NAME at field000.java[4:12-4:16]",
"children" : [ {
"keyText" : "UNRESOLVED_ID at field000.java[4:12-4:16]",
"specText" : "flag"
} ]
} ]
} ]
} ]
} ]
} ]
} ]
}
В этом случае любое изменение представления или изменение исходного кода приведет к изменению структуры выходных данных так, что дельта изменений будет минимальной и затронет только измененные области.
Самое простое сейчас — написать модульный тест, чтобы проверить, что парсер выдает именно то, что от него ожидают: def testParser(suite: Suite): Unit = {
implicit val ps: ParserService = ParserService(suite.language)
for (fi <- suite.fileInfos) {
assertFile(fi.file)
val parserOutput: ParserOutput = readFromFile[ParserOutput](testConfig(ParserSuiteDir, suite, fi.file))
val op = antlr4.parseFile(asVirtualFile(fi))
assertTrue(op.isInstanceOf[RLangOp], "Must be RLangOp")
assertEquals(parserOutput.languageName, op.asInstanceOf[RLangOp].
language.name, "Languages are not equal")
assertOperations(op.key, op.children, parserOutput.items)
}
}
private def assertOperations(ownerKey: ROpKey, children: Seq[ROp], items: Seq[ParserOutputItem]): Unit = {
if (children.isEmpty) {
assertTrue(items == null || items.isEmpty, s"No items in operation: $ownerKey")
return
} else if (items == null) {
Assertions.fail(s"Missing child operations: $ownerKey")
}
val queue = new mutable.Queue[ParserOutputItem]()
queue ++= items
for (child <- children) {
assertTrue(queue.nonEmpty, s"Must not be empty at: ${child.key}")
val poi = queue.dequeue()
assertEquals(poi.keyText, child.key.toString, "Key text is not equal")
assertEquals(poi.specText, child.specText, "SpecText is not equal")
assertOperations(child.key, child.children, poi.children)
}
assertTrue(queue.isEmpty, s"Queue must be empty for: $ownerKey")
}
Теперь парсер будет гарантированно выдавать одно и то же, проверку работы парсера можно включить в CI/CD и гарантировать хотя бы формально, что парсер действительно работает в соответствии со спецификацией языка (конечно, если примеры верны и разработчик не спал на работе).
Имея на руках такую базу коротких примеров, в случае обнаружения ошибки, даже если половина файлов потребует изменений (что маловероятно), вам все равно не придется просматривать все — ведь все возможности на всех языках имеют иерархическую структуру, поэтому называть папки можно не только по имени, но и путем добавления серийного номера.
При таком подходе вам, возможно, вообще не придется смотреть все подряд. Я исправил первые два, а остальные 100 разрешились сами собой.
Правильно выстраивая иерархию тестовых данных, вы можете на порядки сократить время разработки и отладки.
Но самым главным преимуществом такого подхода к тестированию парсеров является то, что он увеличивает скорость разработки парсеров без потери качества, снижает трудозатраты, а ваши разработчики не превратятся в существ на обложке статьи, повторяющих одно и то же «тестирование».
Зачем тратить недели рабочего времени, если то же самое можно сделать за пару секунд? Для генерации тестовых дампов используется специальный класс org.lastrix.rscan.test.ParserTestSuiteGenerator, и по сути система тестирования имеет два режима.
В первом режиме (основном) он проверяет, что всё работает как надо, во втором помогает разработчику наглядно увидеть, как его правки в грамматике влияют на изменение вывода (вы не забыли, что все тестовые дампы добавляются в наш репозиторий?), мы внесли соответствующие правки, запустили генератор дампов и сразу увидели разницу, тем более, что Intellij IDEA позволяет легко работать с тысячами измененных файлов — хуже, если файлы больше 4 кб.
А имея под рукой большую библиотеку ввода-вывода, можно упростить работу с внутренней документацией, частично генерируя ее из тестовых данных.
После парсера еще есть этапы, не так ли? Полный исходный код проекта для тестирования парсера языка Java можно найти здесь .
В пример включен небольшой набор тестовых данных (478 примеров), на моей машине (Intel i7 9700k) обработка занимает всего 1с 45мс, при этом этими тестами покрыто 65% строк кода парсера.
Заключение
В статье предлагается подход к тестированию лексеров и парсеров, который позволяет ускорить разработку и отказаться от старомодного подхода, когда для проверки грамматики приходилось анализировать тысячи огромных проектов, чтобы поймать небольшую ошибку.Написание огромного количества кода вручную для проверки результата работы — все это можно автоматизировать, кроме разве что проверки результата генерации.
Хотя вы не можете полностью исключить возможность тестирования большого кода, вы можете уменьшить необходимость прибегать к этому подходу.
Обнаруженную в большом коде ошибку можно легко воспроизвести в маленьком коде и в будущем мы сможем контролировать эту проблему.
Теги: #программирование #java #scala #компиляторы #antlr4
-
Пространство И Холст
19 Oct, 24 -
Как Перенести Свой Бизнес В Облако
19 Oct, 24 -
Антивирус Как Угроза
19 Oct, 24 -
Черный Рынок Вновь Открылся
19 Oct, 24 -
Онлайн-Встреча По Обеспечению Качества 28/10
19 Oct, 24
