Диссертация (Синтаксический анализ динамически формируемых программ)

Правительство Российской ФедерацииФедеральное государственное бюджетное образовательное учреждениевысшего профессионального образования«Санкт-Петербургский государственный университет»На правах рукописиГригорьев Семён ВячеславовичCинтаксический анализ динамически формируемых программСпециальность 05.13.11«Математическое и программное обеспечение вычислительных машин,комплексов и компьютерных сетей»Диссертация на соискание учёной степеникандидата физико-математических наукНаучный руководитель:кандидат физико-математических наук, доцентКознов Дмитрий ВладимировичСанкт-Петербург — 20152СодержаниеВведение . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 Обзор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.1 Языки и грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.2 Конечные автоматы и преобразователи . . . . . . . . . . . . . . . . 191.3 О применимости статического анализа строковых выражений . . . 221.4 Подходы к анализу встроенных языков . .

. . . . . . . . . . . . . . 241.5 Обзор инструментов для работы со встроенными языками . . . . . 271.6 Алгоритмы и структуры данных для обобщённого синтаксического анализа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301.6.1Алгоритм обобщённого LR-анализа . . . . . . . . . . . . . . 301.6.2Структурированный в виде графа стек . .

. . . . . . . . . . 321.6.3Сжатое представление леса разбора . . . . . . . . . . . . . . 331.6.4Алгоритм RNGLR . . . . . . . . . . . . . . . . . . . . . . . . 351.7 Используемые инструменты . . . . . . . . . . . . . . . . . . . . . . 381.7.1YaccConstructor . . . . . . . . . . . .

. . . . . . . . . . . . . . 381.7.2ReSharper SDK . . . . . . . . . . . . . . . . . . . . . . . . . . 411.8 Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422 Алгоритм синтаксического анализа регулярной аппроксимации . . 442.1 Постановка задачи . . . . . . . . . . . . . . . . . . .

. . . . . . . . . 442.2 Описание алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.3 Построение компактного представления леса разбора . . . . . . . . 512.4 Доказательство корректности алгоритма . . . . . . . . . . . . . . . . 533 Инструментальный пакет . . . . . . . . . . . . . . . . .

. . . . . . . . . 583.1 Архитектура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5833.1.1Архитектура YS.SEL.SDK . . . . . . . . . . . . . . . . . . . . 603.1.2Архитектура YC.SEL.SDK.ReSharper . . . . . . . . . . . . . 643.2 Применение YC.SEL.SDK . . . .

. . . . . . . . . . . . . . . . . . . . 683.3 Особенности реализации . . . . . . . . . . . . . . . . . . . . . . . . 734 Метод реинжиниринга встроенного программного кода . . . . . . . . 744.1 Особенности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744.2 Метод . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765 Эксперименты, ограничения, обсуждение . . . . . . . . . . . . . . . . 895.1 Апробация в промышленном проекте по реинжинирингу . . . . . . 905.2 Экспериментальная оценка производительности алгоритма . . . . .

935.3 Сравнение с инструментом Alvor . . . . . . . . . . . . . . . . . . . . 965.4 Разработка расширений для поддержки встроенных языков . . . . . 995.5 Ограничения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1036 Сравнение и соотнесение . . . . . . . . . . . . . . .

. . . . . . . . . . . 105Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112Список рисунков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123Список таблиц .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1254ВведениеАктуальность работыСтатический анализ исходного кода является известной техникой получениязнаний о программе без её исполнения [1–3]. Статический анализ являетсянеотъемлемой частью многих процессов, связанных с разработкой программного обеспечения (ПО), и может использоваться, например, для упрощения работы с кодом с помощью подсветки синтаксиса языка в программах, навигациипо коду, реализации контекстных подсказок. Более того, статический анализ используется для обнаружения ошибок на ранних стадиях разработки, до запускапрограммы, а также для поиска различных семантических ошибок, которые немогут быть определены с помощью обычного синтаксического анализа.

Также,статический анализ используется при решении задач трансформации исходногокода и реинжиниринге [4].На практике широко используются динамические встроенные языки — приложение, созданное на одном языке, генерирует программу на другом языке ипередаёт её на выполнение в соответствующее окружение. Примерами могутслужить динамические SQL-запросы к базам данных из приложений на Java,С++, С#, формирование HTML-страниц в PHP-приложениях [5–7]. Генерируемый код собирается из строк таким образом, чтобы в момент выполнения результирующая строка представляла собой корректную программу. Примеры использования встроенных языков представлены в листингах 1, 2 и 3.

Следует отметить, что одна программа может генерировать код на нескольких языках (см.листинг 3). При этом возможно получение частей кода из разных источников(например, учитывать текстовый ввод пользователя, что часто используется длязадания фильтров при конструировании SQL-запросов). Использование динамически формируемых программ позволяет избежать дополнительных накладных5расходов, присущих таким технологиям, как ORM1 , и достичь высокой производительности.

Благодаря этому использование динамически генерируемых программ получило широкое распространение и применяется до сих пор. Вместе сэтим, несмотря на появление новых технологий, динамическая генерация SQLзапросов активно используется и в настоящее время [9].123456CREATE PROCEDURE [dbo].[MyProc] @TABLEResVarChar(30)ASEXECUTE (’INSERT INTO ’ + @TABLERes + ’ (sText1)’ +’ SELECT ’’Additional condition: ’’ + sName’ +’ from #tt where sAction = ’’1000000’’’)GOЛистинг 1: Код с использованием динамического SQL12345678910111213141516171819import javax.script.*;public class InvokeScriptFunction {public static void main(String[] args) throws Exception {ScriptEngineManager manager = new ScriptEngineManager();ScriptEngine engine = manager.getEngineByName("JavaScript");// JavaScript code in a StringString script ="function hello(name) { print(’Hello, ’ + name); }";// evaluate scriptengine.eval(script);// javax.script.Invocable is an optional interface.// Check whether your script engine implements or not!// Note that the JavaScript engine implements// Invocable interface.Invocable inv = (Invocable) engine;// invoke the global function named "hello"inv.invokeFunction("hello", "Scripting!!" );}}Листинг 2: Вызов JavaScript из JavaДинамически формируемые выражения часто конструируются с помощьютаких операций, как конкатенация в циклах или условных предложениях, а также в рекурсивных процедурах.

Это затрудняет статический анализ и приводитк получению множества возможных значений для каждого выражения в момент1ORM или Object-Relational Mapping — технология программирования, которая связывает базы данных собъектно-ориентированными приложениями [8].61234<?php// Embedded SQL$query = ’SELECT * FROM ’ .

$my_table;$result = mysql_query($query);5// HTML markup generationecho "<table>\n";while ($line = mysql_fetch_array($result, MYSQL_ASSOC)) {echo "\t<tr>\n";foreach ($line as $col_value) {echo "\t\t<td>$col_value</td>\n";}echo "\t</tr>\n";}echo "</table>\n";678910111213141516?>Листинг 3: Использование нескольких встроенных в PHP языков (MySQL,HTML)выполнения. Вследствие этого фрагменты динамически формируемого кода воспринимаются компилятором исходного языка как простые строки, не подлежащие дополнительному анализу, а это, в свою очередь, приводит к высокой вероятности возникновения ошибок во время выполнения программы.

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

Например, при наличии в коде приложения динамически формируемых SQL-запросов нельзя точно ответить на вопрос о том, с какими элементамибазы данных не взаимодействует система, и удалить их. При переносе такой системы на другую СУБД необходимо гарантировать, что для всех динамическиформируемых выражений их значения в момент выполнения будут корректными для новой СУБД [10]. Следует отметить, что отсутствие статических анализаторов динамически формируемых программ не позволяет реализовывать дляпоследних стандартную функциональность интегрированных сред разработки(Integrated Development Environment, IDE) — подсветку синтаксиса и автодопол-7нение, рефакторинг кода и т.д.