Диссертация (1150733), страница 6
Текст из файла (страница 6)
Как правило, эти инструменты реализуютодин из основных подходов, описанных в разделе 1.4.Java String Analyzer (JSA) [30,68] — инструмент для анализа строк и строковых операций в программах на Java. Основан на проверке включения регулярнойаппроксимации встроенного языка в контекстно-свободное описание эталонно-28го. Для каждого строкового выражения строится конечный автомат, представляющий приближенное значение всех значений этого выражения, которые могутбыть получены во время выполнения программы.
Для того, чтобы получить этотконечный автомат, необходимо из графа потока данных анализируемой программы построить контекстно-свободную грамматику, которая получается в результате замены каждой строковой переменной нетерминалом, а каждой строковойоперации — правилом продукции. После этого полученная грамматика аппроксимируется регулярным языком. В качестве результата работы данный инструменттакже возвращает строки, которые не входят в описанный пользователем язык,но могут сформироваться во время исполнения программы.PHP String Analyzer (PHPSA) [29, 69] — инструмент для статического анализа строк в программах на PHP.
Расширяет подход инструмента JSA [30].Использует контекстно-свободную аппроксимацию, что достигается благодаряотсутствию этапа преобразования контекстно-свободной грамматики в регулярную, и это повышает точность проводимого анализа. Для того чтобы обрабатывать строковые операций и учитывать их при построении контекстно-свободнойграмматики, используется конечный преобразователь. Дальнейший анализ строковых выражений полностью заимствован из инструмента JSA.Alvor [31, 32, 64] — плагин к среде разработки Eclipse [70], предназначенныйдля статической проверки корректности SQL-выражений, встроенных в Java1 .Для компактного представления множества динамически формируемого строкового выражения используется понятие абстрактной строки: данная строка, фактически, является регулярным выражением над используемыми в строке символами.
В инструменте Alvor отдельным этапом выделен лексический анализ.Поскольку абстрактную строку можно преобразовать в конечный автомат, толексический анализ заключается в преобразовании этого конечного автомата вконечный автомат над терминалами при использовании конечного преобразователя, полученного генератором лексических анализаторов JFlex [71]. Несмотряна то, что абстрактная строка позволяет конструировать строковые выраженияпри участии циклов, плагин в процессе работы выводит сообщение о том, что неможет поддержать эти конструкции.
Также инструмент Alvor не поддерживаетобработку строковых операций, за исключением конкатенации.1Во время написания данного текста велась работа над поддержкой встроенных языков в PHP.29IntelliLang [72] — плагин к средам разработки PHPStorm [73] и IntelliJ IDEA2 ,предоставляющий поддержку встроенных строковых языков, таких как HTML,SQL, XML, JavaScript. Плагин обеспечивает подсветку синтаксиса, автодополнение, статический поиск ошибок. Для среды разработки IntelliJ IDEA расширениеIntelliLang также предоставляет отдельный текстовый редактор для работы совстроенным языком. Для использования данного плагина требуется ручная разметка переменных, содержащих выражения на том или ином встроенном языке.PHPStorm [73] — интегрированная среда разработки для PHP, котораяосуществляет подсветку и автодополнение встроенного кода на HTML, CSS,JavaScript, SQL.
Однако такая поддержка осуществляется только в случаях, когда строка получена без использования каких-либо строковых операций. ТакжеPHPStorm для каждого встроенного языка предоставляет отдельный текстовыйредактор.Varis [75] — плагин для Eclipse, представленный в 2015 году и предоставляющий поддержку кода на HTML, CSS и JavaScript, встроенного в PHP.
В плагинереализованы функции подсветки встроенного кода, автодополнения, переходак объявлению (jump to declaration), построения графа вызовов (call graph) длявстроенного JavaScript.Абстрактный синтаксический анализ. Kyung-Goo Doh, Hyunha Kim, DavidA. Schmidt (Hanyang University, South Korea) в серии работ [26–28] описалиалгоритм статического анализа динамически формируемых строковых выражений на примере статической проверки корректности динамически генерируемого HTML в PHP-программах. Хотя для данного примера отсутствует этап проведения лексического анализа, в общем случае можно использовать композициюлексического анализа и синтаксического разбора. Для этого достаточно хранитьсостояние конечного преобразователя, который используется для лексическогоанализа, внутри состояния синтаксического разбора.
Данный алгоритм такжепредусматривает обработку строковой операции string-replacement с использованием конечного преобразователя, который по аналогии с лексическимконечным преобразователем хранит своё состояние как часть состояния синтаксического разбора. На вход абстрактный синтаксический анализатор принимает data-flow уравнения, полученные при анализе исходного кода, и LALR(1)2IntelliJ IDEA — среда разработки для JVM-языков [74].30таблицу.
Далее производится решение этих уравнений в домене LR-стеков. Проблема возможного бесконечного роста стеков, возникающая в общем случае,разрешается с помощью абстрактной интерпретации (abstract interpretation [76]).В работе [28] данный подход был расширен вычислением семантики с помощью атрибутных грамматик, что позволило анализировать более широкий, чемLALR(1), класс грамматик.
В качестве результата алгоритм возвращает наборабстрактных синтаксических деревьев. На текущий момент реализацию данногоалгоритма в открытом доступе найти не удалось, хотя в работах авторов приводятся результаты апробации. Таким образом, на данный момент не существуетдоступного инструмента, основанного на данном алгоритме.1.6Алгоритмы и структуры данных для обобщённого синтаксического анализаВ этом разделе будет описан алгоритм обобщённого восходящего синтаксического анализа RNGLR [21], используемый в данной работе.
Кроме этого, будутописаны основные структуры данных, специфичные для обобщённого синтаксического анализа.Анализ динамически формируемых выражений подразумевает работу сомножеством значений. При синтаксическом анализе множества появится множество стеков и множество деревьев разбора. Среди существующих алгоритмовесть класс алгоритмов обобщённого синтаксического анализа [77], в рамках которого разработаны эффективные методы работы с множеством стеков и деревьев разбора. По этой причине рассмотрим некоторые алгоритмы обобщённогосинтаксического анализа и применяемые в них структуры данных более подробно.1.6.1Алгоритм обобщённого LR-анализаОдним из распространённых подходов к синтаксическому анализу являетсятабличный LR-анализ, при котором производится правосторонний вывод и дерево вывода строится снизу вверх.
Механизм анализа основан на примененииавтомата с магазинной памятью, управляющие таблицы для которого строятся31на основе грамматики обрабатываемого языка [78]. Идея состоит в том, что символы входной цепочки переносятся в стек до тех пор, пока на вершине стека ненакопится цепочка, совпадающая с правой частью какого-либо из правил (операция перенос или shift). Далее все символы этой цепочки извлекаются из стека,и на их место помещается нетерминал, соответствующий этому правилу (операция свёртка или reduce).
Входная цепочка допускается автоматом, если послепереноса в автомат последнего символа входной цепочки и выполнении необходимого числа свёрток в стеке окажется только стартовый нетерминал грамматики.Как уже было сказано ранее, при выполнении табличного синтаксическогоанализа для данной грамматики строится таблица действий и таблица переходов.Таблица переходов — это вспомогательная таблица, использующаяся при одномиз действий; в её ячейках может содержатся либо состояние анализатора, либосимвол ошибки.Таблица действий определяет дальнейшее действие в текущем состоянии ис текущим символом на входе.
Каждая ячейка данной таблицы может содержатьодно из следующих значений:– accept (“успех”) — разбор входной цепочки завершился успешно;– shift (“перенос”) — на вершину стека переносится состояние, которое соответствует входному символу, читается следующий символ;– reduce (“свёртка”) — в стеке набрались состояния, которые можно заменитьодним, исходя из правил грамматики; значение нового состояния берётсяиз таблицы переходов;– error (“ошибка”) — анализатор обнаружил ошибку во входной цепочке.При работе с неоднозначными грамматиками могут возникнуть ситуации, когда в одну ячейку таблицы необходимо записать несколько действий.
Это означает, что в процессе обработки некоторой цепочки при цепочки анализатор не может однозначно решить, какое действие совершить в текущем состоянии. Такимобразом возникают конфликты shift/reduce, когда можно либо прочитать очередной символ, либо произвести свёртку, и reduce/reduce, когда можно произвестисвёртку по нескольким правилам грамматики.32Для решения данной проблемы Масару Томитой (Carnegie-Mellon University,Pittsburgh) был предложен алгоритм Generalized LR (GLR) [20], изначально предназначенный для анализа естественных языков.
GLR-алгоритм был предназначен для работы с неоднозначными контекстно-свободными грамматиками, а значит позволял обрабатывать shift/reduce и reduce/reduce конфликты. Используемые в данном алгоритме управляющие таблицы схожи с управляющими таблицами LR-алгоритма, но отличаются тем, что ячейки могут содержать несколькодействий. Основная идея GLR-алгоритма состоит в проведении всех возможных действий во время синтаксического анализа. При этом для эффективногопредставления множества стеков и деревьев вывода используются специальныеструктуры данных, основанные на графах.1.6.2Структурированный в виде графа стекСтруктурированный в виде графа стек (Graph Structured Stack или GSS) [20]является ориентированным графом, чьи вершины соответствуют элементам отдельных стеков, а ребра связывают последовательные элементы. Вершина можетиметь несколько входящих рёбер, что соответствует слиянию нескольких стековили несколько исходящих, что соответствует конфликту — ситуации, в которойдальнейший разбор может осуществляться несколькими способами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
