Диссертация (1150733), страница 17
Текст из файла (страница 17)
Проводилось 10 запусков, время анализа усреднялось.– Размер входного конечного автомата: количество состояний #Q и количество переходов #T.– Размер построенного SPPF: количество вершин #V и количество рёбер #E.– Результат анализа: ′ +′ — завершился успешно, ′ −′ — завершился с ошибкой,T — завершён по таймауту.Таблица 4: Распределение динамически формируемыхSQL-запросов по времени обработкиКатегория динамически формируемых запросовКоличествозапросовСодержат корректные выраженияНе содержат ни одного корректноговыраженияОбработка завершена по таймаутуВсего2188240Времяобработки(минуты)14912430427Результаты измерений времени работы представлены в таблице 4. Алгоритмуспешно завершил работу на 2188 входных графах, аппроксимирующих множества значений запросов.
Ручная проверка входных графов, на которых алгоритмзавершался с ошибкой, показала, что они действительно содержали некорректные выражения. Причиной этого стала либо некорректная работа лексического92анализатора, либо наличие в выражениях конструкций, не поддержанных в существующей грамматике. Так как лексический анализатор и грамматика былиполностью заимствованы из оригинального проекта, то наличие этих ошибокне является недоработками алгоритма синтаксического анализа. Общее времясинтаксического анализа составило 27 минут, из них 13 минут было затраченона разбор графов, не содержащих ни одного корректного выражения. Из них 4минуты — обработка одного графа (5747 рёбер и 3897 вершин), прерванная потаймауту.
Дальнейшие значения приводятся только для графов, которые удалосьпроанализировать. 604 из этих графов порождали ровно одно значение и анализировалось не более 1 миллисекунды. На разбор 1790 графов ушло не более10 миллисекунд. На анализ двух графов было затрачено более 2 минут. Первыйграф содержал 2454 вершин и 54335 рёбер, второй — 2212 вершин и 106020 рёбер. Распределение входных графов по промежуткам времени, затраченных наанализ, приведено на графике на рисунке 15.Рисунок 15: Распределение запросов по времени анализаТестирование на реальных данных показало, что предложенный в работе алгоритм синтаксического анализа применим в промышленных проектах. Такжеданная апробация показала, что предложенная архитектура SDK позволяет использовать отдельные компоненты независимо и комбинировать их.93Таблица 5: Пример отчёта по результатам запускасинтаксического анализа в проекте “S2O”№t(мс)Размер#Q7510479817108389792423692839037776411792r16+273+364+4 15982 +53+6 256000 T7 28360 +817+9207+10110+11111+12262+133+143+5.2DFAРазмер SPPF#T#V#E76107410758061878626377750172372395432281 920618 188511210799699557470041408 1315491 279451750646085165224938709573529421475721805967148122190219073333249955116109310929213911391Экспериментальная оценка производительности алгоритмаАлгоритм синтаксического анализа динамически формируемых выраженийбыл протестирован на нескольких наборах синтетических тестов, цель которых заключалась в исследовании производительности алгоритма на практически значимых входных данных.
Анализ проекта “S2O” показал, что запросычасто формируются конкатенацией фрагментов, каждый из которых формируется с помощью ветвлений или циклов. Ниже приведена эталонная грамматика ,использованная в этих тестах._ ::= ::= PLUS n ::= ONE | TWO | THREE | FOUR |FIVE | SIX | SEVENВходные данные представляли собой конечные автоматы над алфавитом терминальных символов грамматики , построенные с помощью конкатенации ба-94зовых блоков.
Предполагается, что такие графы могут быть получены в результате лексического анализа регулярной аппроксимации, построенной по некоторойпрограмме. В данном случае базовый блок — это шаблонный конечный автомат,который используется для построения тестовых конечных автоматов. Каждыйпакет тестов характеризовался тремя параметрами:– ℎℎ — количество ветвлений в базовом блоке;– ℎ — максимальное количество повторений базовых блоков;– — наличие в базовом блоке циклов (если значение равно false, тоиспользуются базовые блоки, изображённые на рисунке 16, если true —то изображённые на рисунке 17).3ONEFIVE01PLUS2TWOTHREE4PLUSPLUSPLUS6SEVEN7PLUS85Рисунок 16: Базовый блок без циклов при ℎℎ = 3ONEFIVE01PLUS2TWOPLUS34PLUSPLUSTHREE6SEVEN7PLUS85Рисунок 17: Базовый блок, содержащий цикл, при ℎℎ = 3Замеры проводились на вычислительной станции со следующими характеристиками.– Операционная система: Microsoft Windows 8.1 Pro.– Тип системы: x64-based PC.– Процессор: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz, 3601 Mhz, 4Core(s), 8 Logical Processor(s).95– Объём оперативной памяти: 16.0 GB.Чтобы выявить зависимость времени работы алгоритма от размера входных данных, были созданы пакеты из 500 тестов.
Все тесты в каждом из пакетов содержали одинаковое количество ветвлений в базовом блоке. При этомколичество повторений блока совпадает с порядковым номером теста, то естьℎ = для -того теста. Для каждого теста измерялось время, затраченное насинтаксический анализ. Измерения проводились 10 раз, после чего вычислялосьсреднее время обработки одного графа. График, представленный на рисунке 18,иллюстрирует зависимость времени, затрачиваемого на синтаксический анализ,от количества повторения базового блока и количества ветвлений в каждом изних. Можно заметить, что время растёт линейно в зависимости от размера входного графа. График на рисунке 19 показывает, что наличие циклов в графе приодинаковом значении параметра ℎℎ увеличивает продолжительность анализа, зависимость времени от размера графа остаётся линейной.Рисунок 18: Зависимость времени работы алгоритма от размера входного графапри = 96Рисунок 19: Зависимость времени работы алгоритма от размера входного графаи наличия в нем циклов при ℎℎ = 45.3Сравнение с инструментом AlvorЕдинственным доступным для сравнения инструментом, производящим синтаксический анализ динамически формируемого кода, является Alvor [31, 32].Другие инструменты либо основаны на других подходах и решают другие задачи(например, [29, 30]), либо отсутствуют в открытом доступе (например, инструмент описываемый в работах [26, 27]).
Alvor реализует близкий к представленному в работе подход: независимые шаги анализа, что позволяет легко выделитьсинтаксический анализ, который основан на GLR-алгоритме. Существенным отличием от разработанного алгоритма является то, что Alvor не строит деревьявывода. Исходный код Alvor опубликован [64], что позволяет модифицироватьего таким образом, чтобы измерять параметры выполнения конкретных методов.Сравнение производилось на синтетических тестах, которые строились попринципу, аналогичному изложенному в разделе 5.2. Так как Alvor на вход принимает регулярное выражение, называемое абстрактной строкой [32], а анализатор, созданный на основе YC.SEL.SDK — конечный автомат, то был реализован генератор, который по входным параметрам создает файл с абстрактнойстрокой и с описанием соответствующего автомата в формате DOT [89].
Синтак-97сис описания абстрактной строки приведён в листинге 18. При этом абстрактнаястрока подвергалась последовательно лексическому и синтаксическому анализуи измерялось время работы последнего, а конечный автомат строился сразу надалфавитом токенов и подвергался синтаксическому анализу.1234absStr =|||"str"’{’absStr(’,’ absStr)+’}’ //alternativesabsStr absStr//concatenationabsStr ’*’//closureЛистинг 18: Синтаксис описания абстрактной строкиПримеры тестовых входов для одинаковых входных параметров (однократного и двукратного повторения базовых блоков и ℎℎ = 2 ) для инструмента наYC.SEL.SDK и Alvor представлены на рисунке 20 и листинге 19 соответственно.12"select "{"X3 + Y4","1"}",d from tbl""select "{"X3 + Y4","1"}","{"X7 + Y8","5"}",d from tbl"Листинг 19: Пример абстрактных строк для ℎℎ = 2 одного и двухповторений базового блокаIDENT0KW_SELECT13PLUS4DEC_NUMBERIDENTIDENT2COMMA57PLUSDEC_NUMBER8IDENT6COMMA9IDENT10KW_FROM11IDENT12Рисунок 20: Входной граф для синтаксического анализатора на базеYC.SEL.SDK при ℎℎ = 2 и двух повторениях базового блокаРезультаты измерений представлены в таблице 6 и на рисунке 21.
В легендеи в заголовке таблицы указан инструмент (YC или Alvor) и значение параметраℎℎ (например, h=2).При более чем шестнадцатикратном повторении блоков с ℎℎ = 2 время работы Alvor превысило 30 минут и измерения были прекращены. Аналогичная ситуация возникает при более чем десятикратном повторении блоков сℎℎ = 3. Таким образом, измерения показывают, что время работы анализатора Alvor растёт экспоненциально относительно количества повторений базовогоблока при ℎℎ > 1. Анализатор, созданный на основе YC.SEL.SDK, в такихслучаях имеет лучшую производительность. При этом на линейном входе Alvorработает быстрее. Однако, асимптотика YC.SEL.SDK на входных данных, имеющих подобную структуру, такая же, как у оригинального алгоритма RNGLR,98что показано в предыдущих экспериментах. При этом существуют возможностидля оптимизации текущей реализации, благодаря чему производительность налинейном входе может быть улучшена.Рисунок 21: Сравнение производительности Alvor и синтаксическогоанализатора на базе YC.SEL.SDKТак как Alvor не предоставляет платформы для простой реализации поддержки новых языков, то для сравнения было выбрано подмножество языка SQL, общее для Alvor и реализованного в рамках апробации инструмента.
Отсутствиевозможности быстро построить новый анализатор на основе Alvor помешалосравнению на реальных данных, так как спецификация грамматики T-SQL является задачей, требующей большого количества времени. По этой причине замеры производились на синтетических тестах. В результате измерений быловыяснено, что производительность реализованного алгоритма синтаксическогоанализа лучше чем производительность аналогичного алгоритма, реализованного в инструменте Alvor на входных данных, содержащих большое количествоветвлений: Alvor показывает экспоненциальный рост времени обработки, а реа-99Таблица 6: Результаты сравнения производительности Alvor исинтаксического анализатора на базе YC.SEL.SDKYC(h=1) Alvor(h=1) YC(h=2) Alvor(h=2) YC(h=3) Alvor(h=3)0.0990.1130.7060.2840.4050.110.1990.2480.7020.6460.8010.6220.20.1930.7070.4471.6011.1290.2010.3020.9010.7481.7015.4030.30.2171.5021.322.2037.890.3010.1751.6354.1142.40218.1870.40.1031.8777.7342.2442.4470.3020.1042.0027.0762.704171.5290.8020.1332.20213.2043.104580.5451.1020.1192.28224.5783.2042521.3181.1020.1182.40446.6623.4031.7660.192.704103.4173.6051.7010.2492.803248.1074.4081.8030.2143.103554.3144.7062.0010.2273.2171125.9764.8431.8030.2353.4032886.2615.006лизованный алгоритм является полиномиальным, что согласуется с результатами, полученными в предыдущем разделе.5.4Разработка расширений для поддержки встроенных языковНа основе YC.SEL.SDK и YC.SEL.SDK.ReSharper, представленых ранее, были реализованы расширения к ReSharper, которые предоставляют поддержку длядвух встроенных языков: подмножества языка T-SQL [94] и языка арифметических выражений Calc.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
