Тема: Поддержка расширенных контекстно-свободных грамматик в алгоритме синтаксического анализа Generalised LL

Общеупотребимый способ описания синтаксиса языков программи­рования — расширенные контекстно-свободные грамматики. Примером могут служить спецификации языков C, C + +, Java и т.д. С одной сто­роны, эта форма проста для понимания людей, с другой, достаточно формальна и допускает автоматизированное создание синтаксических анализаторов.
Существуют различные инструменты, такие как ANTLR [1], Bison [5], позволяющие для грамматики языка создать синтаксический анализатор для текстов, созданных на этом языке. Проблема заключается в том, что эти инструменты сначала преобразуют грамматику к форме Бэкуса-Наура и только затем строят синтаксический анализатор.
Существуют работы, описывающие синтаксический анализ с помощью расширенных контекстно-свободных грамматик (Extended Context-Free Grammar, ECFG) [6], [14], но практические средства, основанные на данных работах, не были созданы. Кроме того, подходы, описанные в данных исследованиях, поддерживают лишь подклассы контекстно-свободных языков.
Алгоритмы обобщённого синтаксического анализа, например Gen­eralised 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”.
Купить