Диссертация (1150733), страница 11
Текст из файла (страница 11)
Дерево, состоящее из единственной вершины-терминала. Такое дерево соответствует терминалу, считанному с некоторого ребра (ℎ , ) внутреннего графа, поэтому утверждение верно.Индукционный переход. Пусть корнем дерева высоты является нетерминал . В силу третьего пункта определения корректного дерева существует правилоэталонной грамматики → 0 , 1 , . . . , , где 0 , 1 , . . . , являются детьмикорневого узла. Поддерево связано с ребром ( , ℎ ) графа GSS, и так как еговысота не больше − 1, то по индукционному предположению существует путьво внутреннем графе из вершины ℎ в вершину . Вершина = ℎ+1 , таккак = ℎ+1 , поэтому во внутреннем графе существует путь из вершины ℎ0 ввершину , соответствующий рассматриваемому корректному дереву.
Так как SPPF является сжатым представлением леса разбора, то для получения конкретного дерева последнее необходимо извлечь из SPPF.Т ЕОРЕМА 2. Любое дерево, извлечённое из SPPF, является корректным.Д ОКАЗАТЕЛЬСТВО . Рассмотрим произвольное дерево, извлечённое из SPPF,и докажем, что оно удовлетворяет определению 1. Первый и третий пункт определения корректного дерева следует из определения SPPF. Второй пункт определения следует из ЛЕММЫ, если применить её к рёбрам из GSS, начальныевершины которых лежит на последнем уровне стека и помечены принимающимсостоянием, а конечные вершины — в вершинах на уровне 0. Т ЕОРЕМА 3.
Для каждой строки, соответствующей пути во входном графе и выводимой в эталонной грамматике , из SPPF может быть извлеченокорректное дерево . То есть будет являться деревом вывода цепочки, соответствующей пути , в грамматике .57Д ОКАЗАТЕЛЬСТВО . Рассмотрим произвольное корректное дерево и докажем, что оно может быть извлечено из SPPF. Доказательство повторяет доказательство корректности для RNGLR-алгоритма [21], за исключением следующей ситуации. RNGLR-алгоритм строит граф GSS по слоям: гарантируется, что∀ ∈ [0.. − 1]−ый уровень GSS будет зафиксирован на момент построения−ого уровня. В нашем случае это свойство не верно, так как во входном графе могут быть циклы и нет возможности упорядочить обработку его вершин.Это, в свою очередь, может приводить к появлению новых путей для свёрток,которые уже были обработаны ранее.
Единственный возможный способ образования такого нового пути — это добавление ребра ( , ℎ ) в стек, где вершина ранее присутствовала в GSS и имела входящие ребра. Так как алгоритм сохраняет информацию о том, какие свёртки проходили через вершины GSS, тодостаточно продолжить свёртки, проходящие через вершину . Таким образомгарантируется выполнение всех возможных свёрток и построение корректногодерева вывода. З АМЕЧАНИЕ . Построение леса разбора осуществляется одновременно с построением GSS, при этом дерево вывода нетерминала связывается с ребром GSSкаждый раз при обработке соответствующей свёртки вне зависимости от того, было ли ребро в графе до этого или оно добавлено на данном шаге. Этообстоятельство позволяет утверждать, что если все возможные редукции быливыполнены, то и лес разбора содержит все деревья для всех корректных цепочекиз аппроксимации.58Глава 3Инструментальный пакетВ данной главе описан разработанный в диссертации инструментальныйпакет (Software Development Kit, SDK) YC.SEL.SDK, предназначенный дляразработки решений по статическому анализу динамически формируемых выражений.
Представлена архитектура разработанного SDK, а также архитектура надстройки YC.SEL.SDK.ReSharper, позволяющая создавать расширения для ReSharper с целью поддержки встроенных языков. Изложенный выше алгоритм синтаксического анализа реализован в рамках одной из компонентSDK.YC.SEL.SDK и YC.SEL.SDK.ReSharper являются платформами для разработки инструментов статического анализа динамически формируемого кода.3.1АрхитектураПрактически любой язык программирования может использоваться каквстроенный.
При этом нет необходимости рассматривать различные языки, достаточно ограничиться диалектами одного языка. Например, существует множество различных диалектов SQL, каждый из которых имеет свои особенности иможет оказаться встроенным языком. Внешним языком также может быть любойязык программирования. Трудность заключается в том, что любое из сочетанийвнешнего и встроенного языка может встретиться на практике, и задачи, которые необходимо решать в этой ситуации, могут быть различными (поиск ошибок, подсчёт метрик, автоматизация трансформаций и т.д.). Реализовать универсальный инструмент, решающий все задачи для всех языков, не представляется59возможным. Более целесообразно создать набор инструментов, упрощающий создание конечных решений для конкретных языков и задач.
В качестве примераможно рассмотреть инструменты для разработки компиляторов [12, 13], которые включают в себя генераторы лексических, синтаксических анализаторов инабор библиотек с вспомогательными функциями и тем самым упрощают создание конкретного компилятора для выбранного языка и целевой платформы.Требуемый набор инструментов для работы со встроенными языками долженподдерживать весь процесс обработки кода (см. рисунок 9. Можно выделитьследующие основные шаги этого процесса.– Анализ основного кода, который выполняется сторонним инструментом.Результат этого шага — дерево разбора с информацией, достаточной длявыполнения дальнейших шагов.– Построение аппроксимации множества возможных значений динамическиформируемых выражений.– Лексический анализ аппроксимации, построенной на предыдущем шаге.– Синтаксический анализ аппроксимации множества значений динамическиформируемого кода, результатом которого является лес разбора, пригодныйдля дальнейшей обработки.– Обработка леса разбора, полученного на предыдущем шаге, вычислениесемантики.На каждом шаге может быть получена информация, значимая для пользователя ( например, список ошибок), и её необходимо отобразить для него соответствующим образом.Для того чтобы упростить процесс создания конечных инструментов, однойиз компонент сщданного SDK является генератор синтаксических анализаторовна основе предложенного в данной работе алгоритма.
Также в SDK входит генератор лексических анализаторов, библиотека построения регулярной аппроксимации, набор вспомогательных функций. Подробное описание компонент приведено далее.60Рисунок 9: Диаграмма последовательности обработки встроенных языковТак как анализ внешнего языка является сложной самостоятельной задачей,то он не включён в разработанный SDK. На вход созданному на основе SDKинструменту должно подаваться дерево разбора внешнего языка с информацией,достаточной для решения поставленных в данной работе задач.3.1.1Архитектура YS.SEL.SDKРазработанный SDK включает компоненты, необходимые для реализациишагов, представленных на рисунке 9 и описанных ранее, за исключением анализа внешнего языка.
Архитектура SDK изображена на рисунке 10 и включает всебя генераторы анализаторов и различные библиотеки времени исполнения.Рисунок 10: Архитектура SDK61Так как анализ внешнего языка не входит в задачи разработанного SDK, топервый шаг, выполнение которого необходимо обеспечить, — это построениеаппроксимации. В нашем случае строится регулярное приближение множествазначений динамически формируемого выражения.Построение регулярной аппроксимации основано на алгоритме, изложенномв работе [55], который позволяет строить приближение сверху для множествазначений выражений. То есть , задаваемый регулярным приближением, неменьше, чем 1 , задаваемый программой (выполняется включение ∈ 1 ).Это позволяет говорить о надёжности дальнейших анализов в том смысле, чтоони не теряют информации о 1 .
Например, это важно при поиске ошибок. Еслив не обнаружено ошибок (то есть ∈ 2 , где 2 — эталонный), значит и в1 ошибок нет. При этом могут быть найдены ошибки в , которых нет в 1 ,то есть будут ложные срабатывания. Однако наличие ложных срабатываний лучше, чем пропущенные ошибки, и их количество может быть уменьшено путёмповышения точности аппроксимации.Для того чтобы сделать построение приближения независимым от внешнего языка, реализовано обобщённое представление графа потока управления(Control Flow Graph, CFG) [11], которое содержит всю необходимую для дальнейшей работы информацию.
Таким образом, разработчику необходимо реализовать построение обобщённого представления CFG для конкретного внешнегоязыка. В результате компонента строит конечный автомат, являющийся приближением множества значений динамически формируемых выражений.Архитектура компоненты, отвечающей за лексический анализ, представлена на рисунке 11. Основой является лексический анализатор, который состоит из двух частей: генератора лексических анализаторов, который по описаниюлексики обрабатываемого языка, задаваемой в виде файла с расширением fsl(Lexer.fsl), строит соответствующий конечный преобразователь, и интерпретатора, который производит анализ входной структуры данных на основе построенного генератором преобразователя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
