Общеупотребимый способ описания синтаксиса языков программирования — расширенные контекстно-свободные грамматики. Примером могут служить спецификации языков C, C + +, Java и т.д. С одной стороны, эта форма проста для понимания людей, с другой, достаточно формальна и допускает автоматизированное создание синтаксических анализаторов.
Существуют различные инструменты, такие как ANTLR [1], Bison [5], позволяющие для грамматики языка создать синтаксический анализатор для текстов, созданных на этом языке. Проблема заключается в том, что эти инструменты сначала преобразуют грамматику к форме Бэкуса-Наура и только затем строят синтаксический анализатор.
Существуют работы, описывающие синтаксический анализ с помощью расширенных контекстно-свободных грамматик (Extended Context-Free Grammar, ECFG) [6], [14], но практические средства, основанные на данных работах, не были созданы. Кроме того, подходы, описанные в данных исследованиях, поддерживают лишь подклассы контекстно-свободных языков.
Алгоритмы обобщённого синтаксического анализа, например Generalised LL [22], способны использовать контекстно-свободные грамматики, описывающие произвольные контекстно-свободные языки. Но они так же не допускают использования ECFG без предварительного преобразования к форме Бэкуса-Наура.
Одно из возможных применений обобщённого синтаксического анализа — поиск генов и иных последовательностей в биологическом материале. Из материала извлекаются геномы содержащихся в нём организмов — последовательности над алфавитом {A; C; G T}. Но для того чтобы снизить расходы на хранение этих последовательностей, по ним строится конечный автомат. В геноме существуют различные последовательности, позволяющие классифицировать организм, которые имеют некоторые общие свойства, которые можно описать контекстно-свободной грамматикой [18], поэтому для их поиска можно применять синтаксический анализ. Синтаксический анализ конечных автоматов называют синтаксическим анализом регулярных множеств. Одной из целей данной работы является применение полученного GLL алгоритма в синтаксическом анализе регулярных множеств, в частности — метагеномных сборок.
На кафедре Системного Программирования СПбГУ, в рамках исследовательского проекта YaccConstructor [32], разрабатывается подход для поиска структур, заданных с помощью контекстно-свободной грамматики в метагеномных сборках, основанный на алгоритме Generalised LL. Предполагается, что синтаксический анализ для расширенных контекстно-свободных грамматик без преобразований даст значительный прирост производительности существующего подхода.
В рамках данной работы была разработана и реализована модификация алгоритма GLL, работающая с расширенными контекстно-свободными грамматиками. Показано, что полученный алгоритм повышает производительность поиска структур, заданных с помощью контекстно-свободной грамматики в метагеномных сборках. Более детально, были получены следующие результаты.
• В качестве подходящего представления ECFG выбраны рекурсивные конечные автоматы.
• Спроектирована структура данных для представления леса разбора для ECFG на основе сжатого леса разбора (SPPF).
• Разработан алгоритм на основе Generalised LL, строящий лес разбора для ECFG.
• Алгоритм реализован в рамках проекта YaccConstructor. Исходный код доступен в репозитории YaccConstructor [31], автор работал под учётной записью “gorohovart”.
• Проведено экспериментальное сравнение реализованного алгоритма с существующим в проекте YaccConstructor, показавшее двухкратный прирост на использованных данных.
• Результаты работы успешно представлены на международной конференции “Tools and Methods of Program Analysis” (Москва, 2017г.) в докладе “Extended Context-Free Grammars Parsing with Generalized LL”.
