Диссертация (1150733), страница 8
Текст из файла (страница 8)
Например, это могут быть генераторы синтаксических анализаторов,основанные на различных алгоритмах или принтеры, генерирующие текст грамматики в определённом формате или на заданном языке. YC является расширяемой платформой: модуль любого типа может быть реализован, в том числе, спереиспользованием уже существующих, и подключён к платформе.В рамках YC разработан язык спецификации грамматик YARD, поддерживающий атрибутные грамматики, грамматики в EBNF 5 и многое другое.
В листинге 9 представлена грамматика языка арифметических выражений Calc на языкеYARD.5EBNF — расширенная форма Бэкуса-Наура. Грамматики в этой форме позволяют использовать регулярныевыражения в правых частях правил [84].401234[<Start>]expr: factor [MULT expr]powExpr: NUM | LBR expr RBRfactor: powExpr [POW factor]Листинг 9: Пример грамматики языка арифметических выражений на языкеYARDСинтаксис языка YARD удобен для разработчика, однако генераторы, какправило, не поддерживают обработку грамматик в этом формате. Часто требуется, чтобы правая часть правила грамматики не содержала регулярных выражений, а состояла бы из цепочки из терминалов и нетерминалов. Это необходимодля работы алгоритма построения таблиц.
Для решения этой задачи в YC реализован ряд преобразований грамматик. В результате их применения к грамматике, представленной в листинге 9, можно получить грамматику, представленнуюв листинге 10.12345678[<Start>]expr: factorexpr: factor MULT exprpowExpr: NUMpowExpr: LBR expr RBRfactor: powExprfactor: powExpr POW factorstartRule: exprЛистинг 10: Пример преобразованной грамматики языка арифметическихвыраженийТакже в рамках платформы YC в качестве одного из модулей был реализовангенератор синтаксических анализаторов на основе RNGLR-алгоритма. Это позволяет переиспользовать общие функции и структуры данных при разработкеанализатора для встроенных языков. Таким образом, алгоритм анализа встроенных языков и соответствующий генератор может быть реализован в рамкахплатформы YC в качестве одного из модулей. При этом можно использовать готовый язык описания грамматики и преобразования, а также переиспользоватьнеобходимые элементы генератора анализаторов на основе RNGLR-алгоритма.Таким образом, YC был выбран в качестве основы для реализации благодаряудобной архитектуре и большому количеству готовых решений.411.7.2ReSharper SDKДля демонстрации разработанного в рамках данной работы инструментапредставляется целесообразным создать на его основе целевое решение.
Дляэтого требуется окружение, способное обрабатывать внешний язык, посколькутакие операции, как построение дерева разбора, базовый анализ (например, построение графа потока управления или графа потока данных), лежат за пределами нашей задачи. При этом такие инструменты должны предоставлять необходимую для решения основной задачи функциональность. Также необходимоиметь удобный способ взаимодействия с пользователем: необходимо получатькод для анализа и адекватно отображать результаты. Один из самых распространённых способов работы с программным кодом — это работа в интегрированнойсреде разработки.Так как реализация программных средств в данной диссертационной работе выполнялось на платформе Microsoft .NET, то соответствующее окружениетакже должно работать на данной платформе.
Одной из самых известных средразработки для платформы .NET, позволяющей создавать расширения на .NETязыках, является Microsoft Visual Studio IDE [85]. Она и была выбрана в качествеосновы для интеграции инструмента статического анализа строковых выражений. Однако у данной среды разработки достаточно сложный механизм созданиярасширений, что является следствием его универсальности. При решении нашейзадачи универсальность не требовалась, поэтому можно было бы использоватьболее простые механизмы.Такой механизм предоставляется ReSharper SDK [80].
ReSharper [86] — расширение для Microsoft Visual Studio, предоставляющее пользователю широкийнабор дополнительных анализов кода. Для разработчиков предоставляется свободно распространяемый набор библиотек (SDK), реализующий анализаторыдля C#, VB.NET и др. Большая часть функциональности ReSharper выделена вданные библиотеки, что даёт возможность сторонним разработчикам создаватьсобственные расширения к ReSharper. В контексте данной работы это позволяет упростить создание плагинов для поддержки различных встроенных языков.Кроме того, ReSharper SDK предоставляет более удобную “обёртку” для многимих интерфейсаов Microsoft Visual Studio, что упрощает взаимодействие с ней иможет быть использовано при предоставлении результатов пользователю.42Следует также отметить, что ReSharper является многоязыковым инструментом, то есть поддерживает большой набор различных языков и спроектировантак, чтобы максимально упростить поддержку новых языков. Это позволяет создавать инструменты, обрабатывающие не только различные встроенные языки,но также и различные внешние.Может быть выделена следующая функциональность ReSharper SDK, необходимая для реализации поддержки встроенных языков в Microsoft Visual Studio.– Построение дерева разбора внешнего языка (C#, JavaScript и другие, поддерживаемые ReSharper), узлы которого содержат координаты конструкцийв исходном коде, что позволяет точно связывать текстовое и структурноепредставление кода.– Анализ потока данных и анализ потока управления для поддерживаемыхязыков.
На основе существующих анализов можно строить более сложные,необходимые, например, для построения регулярной аппроксимации.– Вывод сообщений об ошибках и графическое выделение некорректныхмест в текстовом редакторе.– Взаимодействие с редактором кода, позволяющее настраивать подсветкусинтаксиса, получать позицию курсора и управлять ею, что нужно длядинамической подсветки парных элементов.Таким образом ReSharper SDK и Microsoft Visual Studio IDE выбраны в качестве основы для разработки целевого инструмента, реализующего представленные в данной работе результаты.1.8ВыводыНа основе проведённого обзора можно сделать следующие выводы, обосновывающие необходимость проведения исследований в области статическогоанализа динамически формируемых строковых выражений.– Проблема анализа строковых выражений актуальна в нескольких областях: поддержка встроенных языков в интегрированных средах разработки,43оценка качества кода, содержащего динамически формируемые строковыевыражения, реинжиниринг программного обеспечения.– Большинство реализаций поддерживают конкретные внешние и встроенние языки и, как правило, решают одну достаточно узкую задачу.
Приэтом они плохо расширяемы, как в смысле поддержки других языков, таки в смысле решения новых задач. Полноценные средства разработки инструментов статического анализа динамически формируемых выражений,упрощающие создание решений для новых языков, отсутствуют.– Для эффективного решения этих задач необходимо структурное представление динамически формируемого программного кода, однако существующие алгоитмы и инструменты этого не обеспечивают.Обзор также позволяет выявить следующие подходы, технологии и средства.– В качестве приближения множества значений целесообразно использоватьрегулярную аппроксимацию [30, 55], так как при работе с ней ряд важныхзадач является разрешимым в общем случае, что не верно для контекстносвободной.
Работа с регулярной аппроксимацией также упрощает решениезадачи лексического анализа встроенных языков.– Лексический и синтаксический анализы должны быть разделены. Этооправдано как с теоретической, так и с практической точек зрения, таккак лексический анализ не привносит потери точности и упрощается переиспользование спецификаций языков и самих анализаторов.– В качестве основы алгоритма синтаксического анализа динамически формируемых выражений можно выбрать алгоритм обобщённого синтаксического анализа [77], так как он реализует эффективное управление множеством стеков и деревьев разбора, что важно при работе с динамическиформируемыми выражениями.44Глава 2Алгоритм синтаксическогоанализа регулярнойаппроксимацииВ данной главе формально описана задача синтаксического анализа динамически формируемых выражений, а так же изложен алгоритм её решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
