Автореферат (1150732), страница 2
Текст из файла (страница 2)
Доказательство завершаемости и корректности предложенногоалгоритма проводится с применением теории формальных языков, теории графов и теории сложности алгоритмов. Приближение множества значений динамически формируемого выражения строилось в виде регулярного множества,описываемого с помощью конечного автомата.Положения, выносимые на защиту1. Разработан алгоритм синтаксического анализа динамически формируемыхвыражений, позволяющий обрабатывать произвольную регулярную аппроксимацию множества значений выражения в точке выполнения, реализующий эффективное управление стеком и гарантирующий конечность представления леса вывода.
Доказана завершаемость и корректность предложенного алгоритма при анализе регулярной аппроксимации, представимойв виде произвольного конечного автомата без -переходов.2. Создана архитектура инструментария для разработки программных средствстатического анализа динамически формируемых строковых выражений.3. Разработан метод анализа и обработки встроенного программного кода впроектах по реинжинирингу информационных систем.Научная новизнаНаучная новизна полученных в ходе исследования результатов заключается в следующем.1. Алгоритм, предложенный в диссертации, отличается от аналогов (работыАндрея Бреслава, Кюнг-Гу Дох, Ясухико Минамиде) возможностью построения компактной структуры данных, содержащей деревья вывода длявсех корректных генерируемых цепочек. Это позволяет как проверять корректность анализируемых выражений, так и проводить более сложные видыанализа.
Ряд существующих алгоритмов (JSA, PHPSA) предназначен только для проверки корректности выражений, основанной на решении задачио включении одного языка в другой. Выполнение более сложных видованализа, трансформаций или построения леса разбора не предполагается.62. Новизна представленной архитектуры заключается в том, что она позволяетсоздать платформу для разработки инструментов, решающих широкий кругзадач анализа динамически формируемого кода. Архитектуры существующих инструментов (JSA, PHPSA, Alvor, Varis) ориентированы на решениеконкретных задач для определённых языков программирования. Решениеновых задач или поддержка других языков с помощью этих инструментовзатруднены ввиду ограничений, накладываемых архитектурой и возможностями используемых алгоритмов.3. Метод анализа и обработки встроенного программного кода в проектах пореинжинирингу информационных систем предложен впервые.
Как отмечают К. В. Ахтырченко и Т. П. Сорокваша в работе “Методы и технологии реинжиниринга ИС”, имеются проблемы в методологической основе реинжиниринга: существующие работы в области реинжиниринга программногообеспечения либо содержат высокоуровневые решения, не касающиеся деталей, важных при решении прикладных задач (например, работы К. Вагнера, Х. Миллера), либо являются набором подходов к решению конкретныхзадач (например, сборник “Автоматизированный реинжиниринг программ”под редакцией А.
Н. Терехова и А. А. Терехова или “Software Reengineering(IEEE Computer Society Press Tutorial)” Р. С. Арнольда). При этом, встроенный программный код часто не учитывается. С другой стороны, работы,например, М. Д. Шапот, Э. В. Попова, С. Л. Трошина, А. Клеви, посвящены решению конкретных задач обработки встроенного программного кодав контексте реинжиниринга ИС, но не предлагают общего формального метода для их решения.Теоретическая и практическая значимость работыТеоретическая значимость диссертационного исследования заключается в разработке формального алгоритма синтаксического анализа динамическиформируемого кода, решающего задачу построения конечного представления леса вывода, не решаемую ранее, а также в формальном доказательстве завершаемости и корректности разработанного алгоритма.На основе полученных в работе научных результатов был разработан инструментарий (Software Development Kit, SDK), предназначенный для созданиясредств статического анализа динамически формируемых выражений.
Данныйинструментарий позволяет автоматизировать создание лексических и синтаксических анализаторов при решении задач реинжиниринга — изучения и инвентаризации систем, автоматизации трансформации выражений на встроенных языках. Предложенный инструмент также может использоваться при реализацииподдержки встроенных языков в интегрированных средах разработки.С использованием разработанного инструментария было реализованорасширение к инструменту ReSharper (ООО “ИнтеллиДжей Лабс”, Россия),7предоставляющее поддержку встроенного T-SQL в проектах на языке программирования C# в среде разработки Microsoft Visual Studio.
Так же было выполнено внедрение результатов работы в промышленный проект по переносу хранимого SQL-кода с MS-SQL Server 2005 на Oraclе 11gR2 (ЗАО “Ланит-Терком”,Россия).Степень достоверности и апробация результатовДостоверность и обоснованность результатов исследования опираетсяна использование формальных методов исследуемой области, выполнение формальных доказательств и инженерные эксперименты.Основные результаты работы были доложены на ряде международных научных конференций: SECR-2012, SECR-2013, SECR-2014, TMPA-2014,Parsing@SLE-2013, рабочем семинаре “Наукоемкое программное обеспечение”при конференции PSI-2014. Доклад на конференции SECR-2014 был награждёнпремией Бертрана Мейера за лучшую исследовательскую работу в области программной инженерии.
Дополнительной апробацией является то, что разработкаинструментальных средств на основе предложенного алгоритма была поддержана Фондом содействия развитию малых форм предприятий в технической сфере(программа УМНИК, проекты № 162ГУ1/2013 и № 5609ГУ1/2014).Публикации по теме диссертацииВсе результаты диссертации изложены в 7 научных работах, из которых3 [1–3] содержат основные результаты работы и опубликованы в журналах из“Перечня российских рецензируемых научных журналов, в которых должныбыть опубликованы основные научные результаты диссертаций на соисканиеученых степеней доктора и кандидата наук”, рекомендовано ВАК.
1 работа [4]индексируются Scopus. Работы [1–7] написаны в соавторстве. В [1] С. Григорьеву принадлежит реализация ядра платформы YaccConstructor. В [2, 3] и [5]С. Григорьеву принадлежит постановка задачи, формулирование требований кразрабатываемым инструментальным средствам, работа над текстом.
В [4] автору принадлежит идея исследования, реализация и описание алгоритма анализавстроенных языков на основе RNGLR-алгоритма. В [6] С. Григорьеву принадлежит реализация инструментальных средств, проведение экспериментов, работанад текстом. В работе [7] автору принадлежит разработка алгоритма синтаксического анализа динамически формируемого кода.Объем и структура работыДиссертация состоит из введения, шести глав, заключения и списка литературы. Полный объем диссертации 125 страниц текста с 26 рисунками и 8 таблицами. Список литературы содержит 106 наименований.8Содержание работыВо введении обосновывается актуальность исследований, выполненныхв рамках данной диссертационной работы, приводится обзор научной литературы по изучаемой проблеме, формулируется цель и задачи, описывается научнаяновизна и практическая значимость представляемой работы.В первой главе проводится обзор области исследования.
Рассматриваются подходы к анализу динамически формируемых строковых выражений и соответствующие инструменты. Описывается алгоритм обобщённого восходящегосинтаксического анализа RNGLR, использованный в работе. Также описываютсяпроекты YaccConstructor и ReSharper SDK, использованные в качестве технологий реализации результатов диссертации. На основе проведённого обзора можносделать следующие выводы.∙ Проблема анализа строковых выражений актуальна в нескольких областях:поддержка встроенных языков в интегрированных средах разработки; оценка качества кода, содержащего динамически формируемые строковые выражения; реинжиниринг программного обеспечения.∙ Большинство существующих технологических средств поддерживают конкретный внешний и встроенный языки и, как правило, решают только однузадачу (например, поиск ошибок). При этом они плохо расширяемы, как всмысле поддержки других языков, так и в смысле решения новых задач.Полноценные средства разработки инструментов статического анализа динамически формируемых выражений, упрощающие создание решений дляновых языков, отсутствуют.∙ Для эффективного решения задач анализа строковых выражений необходимо структурное представление динамически формируемого кода, однако натекущий момент отсутствует законченное решение, позволяющего строитьдеревья вывода для динамически формируемых выражений.Во второй главе задача синтаксического анализа динамически формируемых выражений формализуется следующим образом: для данной однозначнойконтекстно-свободной грамматики = ⟨, , , ⟩ и детерминированного конечного автомата без -переходов = (, Σ, , 0 , ) такого, что Σ ⊆ ,необходимо построить конечную структуру данных , содержащую деревьявывода в всех цепочек ∈ ( ), корректных относительно грамматики, и не содержащую других деревьев.
Иными словами, необходимо построитьалгоритм P такой, что(∀ ∈ ( ))( ∈ () ⇒ (∃ ∈ P(( ), )) (, , ))∧(∀ ∈ P(( ), ))(∃ ∈ ( )) (, , ).9Здесь (, , ) — это предикат, который истинен, если является деревомвывода в грамматике .Так как P игнорирует ошибки, то будем называть его алгоритмом ослабленного (relaxed) синтаксического анализа регулярной аппроксимации динамически формируемого выражения.Далее описывается алгоритм, решающий поставленную задачу: алгоритмсинтаксического анализа регулярного множества на основе RNGLR, строящийконечную структуру данных, содержащую деревья вывода для всех цепочек анализируемого множества. Далее доказывается ряд вспомогательных утверждений,необходимых для доказательства основных утверждений о корректности предложенного алгоритма.О ПРЕДЕЛЕНИЕ 1. Корректное дерево — это упорядоченное дерево со следующими свойствами.1.
Корень дерева соответствует стартовому нетерминалу грамматики .2. Листья соответствуют терминалам грамматики . Упорядоченная последовательность листьев соответствует некоторому пути во входном графе.3. Внутренние узлы соответствуют нетерминалам грамматики . Дети внутреннего узла (для нетерминала ) соответствуют символам правой частинекоторой продукции для в грамматике .Л ЕММА . Пусть задан внутренний граф = (, ). Тогда для каждогоребра GSS ( , ℎ ) такого, что ∈ ., ℎ ∈ ℎ ., где ∈ и ℎ ∈ , терминалы ассоциированного поддерева соответствуют некоторомупути из вершины ℎ в в графе .Сформулированы и доказаны три теоремы о завершаемости и корректности предложенного алгоритма.Т ЕОРЕМА 1. Алгоритм завершает работу для любых входных данных.Т ЕОРЕМА 2. Любое дерево, извлечённое из SPPF, является корректным.Т ЕОРЕМА 3.
Для каждой строки, соответствующей пути во входномграфе и выводимой в эталонной грамматике , из SPPF может быть извлечено корректное дерево . То есть будет являться деревом вывода цепочки,соответствующей пути , в грамматике .В третьей главе описывается инструментальный пакет YC.SEL.SDK,разработанный автором работы на основе предложенного выше алгоритма.YC.SEL.SDK предназначен для разработки инструментов анализа динамически формируемых выражений, поддерживающих процесс, схема которого представлена на рисунке 1. Описывается архитектура и особенности реализациикомпонентов, отвечающих за выделение точек интереса, построение регулярной аппроксимации множества значений динамически формируемого выраже10Рис. 1: Пороцесс обработки динамически формируемых выраженийния, проведение лексического и синтаксического анализа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
