zabika.ru   1 ... 6 7 8 9

Генераторы спецификаций трансляции

Задача генератора спецификации трансляции заключается в текстовом выводе внутреннего представления в формат некоторого инструмента. Для этого подаваемое на вход генератора внутреннее представление должно удовлетворять ограничениям конкретного формата, например, не должно быть метаправил и возможно конструкций РБНФ. Общая для всех генераторов проблема форматирования печати решается с помощью соответствующей библиотеки Microsoft.FSharp.Text.StructuredFormat, входящей в FSharp.PowerPack. Она обладает достаточными для задачи возможностями по выводу списков, управлению отступами, заданию максимальной длины строки и другими, что существенно облегчает работу.

FsYaccPrinter


Генератор спецификации трансляции из внутреннего представления в формат FsYacc.

Так как формат FsYacc поддерживает минимум конструкций, перед использованием данного генератора необходимо применить к внутреннему представлению ряд преобразований.

Применение

Благодаря гибкой модульной архитектуре и универсальности внутреннего представления можно найти различные способы применения инструмента.

  • Реинжиниринг спецификации трансляции, то есть однократное ее кардинальное улучшение в рамках текущей задачи. Это может быть ее трансляция в формат более подходящего инструмента или исследование и автоматизированная модификация спецификации в том же формате. Применение инструмента позволяет решить проблему неожиданно большого числа конфликтов в грамматике для LALR(1)-анализатора путем перевода ее на GLR-анализатор, позволяющий работать с неоднозначными грамматиками. Таким же образом могут быть решены и другие непредвиденные проблемы, связанные с выбранным генератором анализаторов.

  • Использование грамматики из открытого источника вместо написания собственной. Инструмент облегчает ее интеграцию в проект, предоставляя возможность транслировать ее в требуемый формат, более удобно исследовать и поддерживать в дальнейшем.
  • Использование собственного генератора синтаксических анализаторов как модуля системы вместе с одним из фронтендов.


  • Использование выбранного генератора анализаторов, но разработка спецификации трансляции на другом, более богатом языке с постоянной автоматической трансляцией кода в его формат.

Реальные проекты, в которых инструмент был применен, описаны ниже.

SqlMigration


В пилотном проекте по автоматической трансляции кода из T-SQL в PL/SQL YaccConstuctor был выбран в качестве приложения для разработки парсера T-SQL. Грамматика разрабатывается на языке YARD и автоматически транслируется инструментом в формат FsYacc, которым и строится транслятор. При таком подходе благодаря применению конструкций YARD, которые не поддерживаются FsYacc, в особенности конструкций РБНФ и внутренних альтернатив, удается в несколько раз сократить грамматику и этим упростить разработку. На текущий момент исходный файл содержит 200 строк, а сгенерированный — 800.

Приложение использовалось в демонстрационных целях, трансляция производилась небольшого подмножества конструкций T-SQL, и поэтому не возникло неудобств с использованием дерева разбора, строящимся атрибутами, генерируемыми преобразованием BuildAST. Это освободило разработчика от необходимости писать их вручную.

Также для структурирования кода применялась возможность описывать грамматику в нескольких модулях.

При дальнейшем развитии проекта планируется использовать грамматику, написанную на YARD для демонстрационного проекта. Дополнительный плюс к выбору YARD-а в качестве языка, на котором будет разрабатываться парсер — минимизация последствий срабатывания риска. То есть, если в процессе разработки грамматики становится сложно вручную разрешать конфликты в классе LALR(1), или даже окажется, что язык SQL шире, чем LALR(1), то можно будет использовать более мощный генератор, например, GLR или основанный на парсер-комбинаторах, нужно будет лишь реализовать генератор спецификации трансляции в требуемый формат.

Claret

Claret [6] — система статического анализа языка C. Планируется применение YaccConstructor для разработки парсера на основе грамматики, взятой из открытого источника и автоматизированной ее модификации. К сожалению, на данный момент инструмент полностью применить не получилось, так как он требует некоторых доработок, в частности, привязку к токену его типа и автоматический поиск правил, которые могут быть объединены конструкциями РБНФ.

Заключение


В ходе выполнения данной дипломной работы были получены следующие результаты.

  1. Обоснован выбор базовой технологии для построения инструмента реинжиниринга спецификаций трансляций.

  2. Реализована возможность чтения грамматики в формате инструмента ANTLR, FsYacc печать в форматы YARD, FsYacc. Реализованы необходимые для этого трансформации: раскрытие внутренних подправил, добавление токена конца файла к стартовому правилу, замена литералов токенами, раскрытие конструкций РБНФ.

  3. Для удобства разработки грамматики реализована простая поддержка возможности задания спецификации трансляции в нескольких файлах, выбор, объединять в альтернативу или оставлять последнее из правил с одинаковыми именами. Также, реализовано преобразование, генерирующее семантические действия для построения AST.

  4. Инструмент успешно применен в проекте SqlMigration.

Дальнейшее развитие проекта может включать в себя поддержку форматов других генераторов синтаксических анализаторов и исследование способов совместить их. Другим направлением развития может быть развитие собственного языка спецификации трансляций, а именно конструкции расширенных регулярных выражений, перестановок, развитие поддержки модульной структуры грамматики, например, на основе работы [5]. Будет продолжаться работа над GLR-генератором [7]. Также, на основе проекта представляет интерес разработать дополнение к среде разработки Visual Studio, позволяющее более удобно разрабатывать транслятор и интегрировать его в основное приложение.

Исходные коды проекта, описание и документацию можно найти на сайте [8].

Примеры использования преобразования BuildAST




Дерево вывода для грамматики

+s: e;

e: NUMBER | NUMBER PLUS e ;





Дерево вывода для грамматики

+s: NUMBER (PLUS NUMBER)* ;

Эта грамматика задает тот же язык, но записана короче и дерево вывода содержит меньше вспомогательных узлов. Такое дерево, отображающее конструкции РБНФ, возможно получить и генератором, их не поддерживающим. Это задается порядком применения преобразований.


Список использованных источников


1. Чемоданов, И.С. и Дубчук, Н.П. Обзор современных средств автоматизации создания синтаксических анализаторов. Системное программирование. СПб.: Изд-во С.-Петерб. ун-та. 2006 г., стр. 286-316.

2. Чемоданов, Илья. Генератор синтаксических анализаторов для решения задач автоматизированного реинжиниринга программ. 2007.

3. Улитин, К.А. Разработка архитектуры для генератора синтаксических анализаторов. 2010.

4. Бреслав, А.А. Применение принципов MDD и аспектно-ориентированного программирования к разработке ПО, связанного с формальными грамматиками.

5. —. Средства повторного использования формальных грамматик и их применение для создания диалектов.

6. Claret home page. [В Интернете] http://code.google.com/p/claret/.

7. Григорьев, С.В. Генератор синтаксических анализаторов для неоднозначных контекстно-свободных грамматик. 2010.

8. YaccConstructor home page. [В Интернете] http://code.google.com/p/recursive-ascent/.

9. Ахо, А., и др., и др. Компиляторы: принципы, технологии и инструментарий. 2008.

10. Богданов, В.Л. и Гордеев, В.С. Практический опыт написания синтаксического анализатора языка программирования Кобол. [авт. книги] Под ред. проф. А.Н. Терехова и А.А. Терехова. Автоматизированный реинжиниринг программ. 2000, стр. 64-75.


11. Syme, Don. Expert F#. 2007.

12. Clint, Paul, Lammel, Ralf и Verhoef, Chris. Toward an engineering discipline for GRAMMARWARE.

13. Мартыненко, Б.К. Языки и трансляции. 2004.

14. Репизиторий, документация, примеры грамматик ANTLR. [В Интернете] http://antlr.org.

15. Спецификация FsYacc. [В Интернете] http://fsharppowerpack.codeplex.com/wikipage?title=FsYacc.

16. Current Parsing Techniques in Software Renovation Considered Harmful. Brand, Mark van den, Sellink, Alex и Verhoef, Chris. IWPC '98.

17. TXL Home Page. [В Интернете] http://www.txl.ca/.

18. Stratego Program Transformation Language. [В Интернете] http://strategoxt.org/.

19. DMS Software Reengineering Toolkit. [В Интернете] http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html.


1 Например, страница http://en.wikipedia.org/wiki/Comparison_of_parser_generators приводит около 150.



<< предыдущая страница