Введение 4
1. Постановка задачи 6
2. Обзор 7
2.1. Подходы к статическому анализу встроенных языков 7
2.2. Существующие методы и инструменты 7
2.3. Проект YaccConstructor 8
2.4. Лес разбора SPPF 10
2.5. Анализ потоков данных и граф потока управления 11
3. Построение графа потока управления по лесу разбора 14
4. Поиск хорошо определённых переменных в динамически формируе
мых программах 21
5. Реализация 28
5.1. Архитектура 28
5.2. Детали реализации поиска хорошо определённых переменных 29
Заключение 31
Список литературы 32
Существует подход к программированию, в котором одна программа динамически формирует другую программу на некотором языке и передаёт её на выполнение в соответствующее окружение. При этом генерируемый код собирается из строк таким образом, чтобы в момент выполнения результирующая строка представляла собой корректную программу. Далее генерируемый код будем называть встроенным кодом, язык, на котором написан встроенный код, - встроенным языком, получающиеся программы - динамически формируемыми программами. В качестве примера можно привести формирование HTML-страниц в PHP-приложениях, SQL-запросы к базам данных в приложениях на C#, C++, Java. Программы, написанные с использованием такого подхода, обладают высокой производительностью, являются гибкими и выразительными. Благодаря этому подход к программированию, связанный с использованием встроенных языков, получил широкое распространение.
В настоящее время при создании ПО активно используются интегрированные среды разработки (Integrated Development Environment, IDE). Их основная цель - повысить продуктивность работы программиста. Эта цель достигается за счёт того, что IDE интегрирует различные утилиты - компилятор, отладчик, текстовый редактор и т. п., - являясь единственной средой, с помощью которой ведётся разработка. Это избавляет разработчика от необходимости каждый раз вручную переключаться между несколькими программами, что положительно сказывается на его производительности. Также IDE может применять утилиты параллельно и комбинированно. Например, совместная работа текстового редактора и компилятора позволяет реализовать функции автодополнения и навигации по коду, а также статический поиск ошибок, возможность осуществления рефакторинга кода и т. п.
Однако при работе с приложениями, которые используют встроенные языки, трудно реализовать функции IDE, которые указаны выше. Это связано с тем, что компилятор воспринимает встроенный код как обычную строку в основном коде, т. е. встроенный код не анализируется статическим образом. Отсутствие статических проверок ведёт к тому, что об ошибках во встроенном коде станет известно только во время выполнения программы. В некоторых приложениях такая ситуация может оказаться критичной, поскольку ошибка может привести к нарушению целостности данных. Помимо этого в случае, когда встроенный код формируется при помощи условных операторов или циклов основного языка, то его (код) сложно понимать и отлаживать.
Инструмент, осуществляющий статический анализ встроенного кода, позволит избежать описанных выше проблем. Разработка такого инструмента ведётся в рамках проекта YaccConstructor [11, 14, 15, 16], одним из направлений исследований которого является статический анализ встроенных языков. Основной идеей проекта является предположение, что если есть программа, содержащая в себе встроенный код, то в большинстве случаев из неё можно извлечь достаточно информации для проведения статического анализа динамически формируемых программ [14]. В рамках проекта уже проведены исследования в области лексического и синтаксического анализа встроенных языков, предложены и апробированы соответствующие алгоритмы [13, 17]. Однако в проекте отсутствуют средства семантического анализа, которые были бы полезны при решении многих классических задач статического анализа.
В ходе данной работы получены следующие результаты.
• Разработан алгоритм построения графа потока управления для динамически формируемого кода, который принимает на вход лес разбора
• Решена задача поиска хорошо определённых переменных при анализе встроенных языков.
• Выполнена реализация получившихся алгоритмов в рамках исследовательского проекта YaccConstructor.
• Результаты работы вошли в статью “On Development of Static Analysis Tools for String-Embedded Languages” (CEE-SECR’15 Proceedings of the 10th Central and Eastern European Software Engineering Conference in Russia).
Проект можно найти на сайте https://github.com/YaccConstructor/YaccConstructor, автор принимал участие под учётной записью IvanovAndrew.
В дальнейшем планируется исследовать другие задачи анализа потоков данных: задача поиска достижимые определения (use-def chains), живых переменных (defuse chains). Решение первой задачи может быть использовано при реализации такой функции IDE, как “перейти к определению” (go to definition), в то время как решение второй может быть полезно при реализации функции “перейти к использованию” (find usages).
