Диссертация (1150733), страница 7
Текст из файла (страница 7)
Объединение стеков происходит в процессе анализа, когда на вершинах различных веток,соответствующих одинаковой позиции во входном потоке, оказывается одинаковое состояние анализатора. Засчёт такой организации GSS обеспечивается переиспользование общих участков отдельных стеков. Пример организации GSSприведён на рисунке 1: “наивное” решение копировать стеки при возникновении конфликтов приводит к дублированию информации, чего можно избежатьпри использовании GSS.33Рисунок 1: Пример GSS1.6.3Сжатое представление леса разбораДля повторного использования общих поддеревьев вывода Ян Рекерс (JanRekers, University of Amsterdam) предложил сжатое представление леса разбора(Shared Packed Parse Forest, SPPF) [23], которое позволяет компактно представлять множество деревьев вывода. Важным свойством SPPF является то, что изнего можно извлечь только те и только те деревья, которые могли быть получены в результате построения вывода конкретного входа в заданной грамматике.Для обеспечения этого свойства в SPPF, кроме терминальных и нетерминальныхузлов, добавляются дополнительные узлы различных типов.
Конкретный набортипов дополнительные узлов может отличаться в зависимости от алгоритма анализа.Пример SPPF для грамматики 1 (листинг 6) и входа ABC приведён на рисунке 2. Представлены два различных дерева вывода (2a и 2b) и результат ихобъединения в SPPF (2c). Узлы с именами вида “n <name>” — это нетерминальные узлы, “е <name>” — терминальные, “prod <num>” — дополнительные узлы,показывающие, согласно какой продукции из грамматики производился выводнетерминала, являющегося предком данного узла.34123456sspmln::=::=::=::=::=::=mpA nA lnB CЛистинг 6: Грамматика 1nsnsprod 1prod 2prod 1nmnpnmprod 3prod 4nsprod 2prod 4nptAprod 3tAnnnnprod 6prod 6prod 6tC(a) Первое дерево выводаtBtBnlprod 5prod 5nntBtAnltCtC(b) Второе дерево вывода(c) Объединение деревьеввывода в SPPFРисунок 2: Пример SPPF для грамматики 1 и входа ABC351.6.4Алгоритм RNGLRRNGLR-алгоритм (Right-Nulled Generalized LR) [21] является модификацией GLR-алгоритма, который не был способен обрабатывать все контекстносвободные грамматики.
Алгоритм предложен Элизабет Скотт (Elizabeth Scott)и Адриан Джонстон (Adrian Johnstone) из университета Royal Holloway (Великобритания). RNGLR расширяет GLR-алгоритм специальным способом обработки обнуляемых справа правил (right-nullable rules, правила, имеющие видA → , где выводит пустую строку ), позволяя обрабатывать произвольныеконтекстно-свободные грамматики.Для эффективного представления множества стеков во время синтаксического анализа в алгоритме RNGLR, как и в классическом GLR, используетсяструктурированный в виде графа стек (GSS).
Вершина GSS — это пара (, ), где — состояние синтаксического анализатора, а — уровень (позиция во входномпотоке).RNGLR-алгоритм последовательно считывает символы входного потока слева направо, по одному за раз, и строит GSS по “слоям”: сначала осуществляютсявсе возможные свёртки для данного символа, после чего сдвигается следующийсимвол со входа. Свёртка или сдвиг модифицируют GSS следующим образом.Предположим, что в GSS необходимо добавить ребро ( , ℎ ). По построению,конечная вершина добавляемой дуги к такому моменту уже обязательно находится в GSS.
Если начальная вершина также содержится в GSS, то в граф добавляется новое ребро (если оно ранее не было добавлено), иначе создаются идобавляются в граф и начальная вершина, и ребро. Каждый раз, когда создаётсяновая вершина = (, ), алгоритм вычисляет новое состояние синтаксическогоанализатора ′ по и следующему символу входного потока. Пара (, ′ ), называемая push, добавляется в глобальную коллекцию . Также при добавленииновой вершины в GSS вычисляется множество -свёрток, после чего элементыэтого множества добавляются в глобальную очередь ℛ. Свёртки длины > 0вычисляются и добавляются в ℛ каждый раз, когда создаётся новое (не-) ребро.
Подробное описание работы со структурированным в виде графа стеком GSSпредставлено в листинге 8.В силу неоднозначности грамматики входная строка может иметь несколькодеревьев вывода, как правило, содержащих множество идентичных поддеревьев.361:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:24:25:26:27:function PARSE(, )ℛ←∅◁ Очередь троек: вершина GSS, нетерминал, длина свёртки←∅◁ Коллекция пар: вершина GSS, состояние синтаксическогоанализатораif = thenif accepts empty input then report successelse report failureelseADD V ERTEX (0, 0, )for all in 0...ℎ − 1 doREDUCE ()PUSH ()if = .ℎ − 1 and there is a vertex in the last level of GSSwhich state is accepting thenreport successelse report failurefunction REDUCE()while ℛ is not empty do(, , ) ← ℛ.()find the set of vertices reachable from along the path of length ( − 1)or length 0 if = 0for all ℎ = (ℎ , ℎ ) in do ← calculate new state by ℎ and nonterminal ADD E DGE (, ℎ , ., , ( = 0))function PUSH()′ ← copy ′while is not empty do(, ) ← .()ADD E DGE (, , .
+ 1, , )Листинг 7: RNGLR-алгоритмДля того, чтобы компактно хранить множество деревьев вывода, используетсяSPPF, являющийся ориентированным графом и в данном случае обладающийследующей структурой.1. Корень соответствует стартовому нетерминалу грамматики.2. Терминальные вершины, не имеющие исходящих дуг, соответствуют либотерминалам грамматики, либо деревьям вывода пустой строки .371:2:3:4:5:6:7:8:9:10:11:12:13:14:function ADD V ERTEX(, , )if GSS does not contain vertex = (, ) thenadd new vertex = (, ) to GSScalculate the set of shifts by and the [ + 1] and add them to calculate the set of zero-reductions by and the [ + 1] andadd them to ℛreturn function ADD E DGE(, ℎ , , , ) ← ADD V ERTEX(, , )if GSS does not contain edge from to ℎ thenadd new edge from to ℎ to GSSif not thencalculate the set of reductions by and the [ + 1] andadd them to ℛЛистинг 8: Построение GSS3.
Нетерминальные вершины являются корнем дерева вывода некоторогонетерминала грамматики; только вершины-продукции могут быть непосредственно достижимы из таких вершин.4. Вершины-продукции представляют правую часть правила грамматики длясоответствующего нетерминала. Вершины, непосредственно достижимыеиз них, упорядочены и могут являться либо терминальными, либо нетерминальными вершинами. Количество таких вершин находится в промежутке [ − . . .
], где — это длина правой части продукции, а — количество финальных символов, выводящих . При этом такие символыигнорируются для уменьшения потребления памяти.SPPF создаётся параллельно с построением GSS. С каждым ребром GSS ас-социирован либо терминальный, либо нетерминальный узел. Когда добавлениеребра в GSS происходит во время операции push, новая терминальная вершинасоздаётся и ассоциируется с ребром. Нетерминальные вершины ассоциируются с рёбрами, добавленными во время операции reduce. Если ребро уже естьв GSS, к ассоциированной с ним нетерминальной вершине добавляется новаявершина-продукция. Подграфы, ассоциированные с рёбрами пути, вдоль которого осуществлялась свёртка, добавляются как дети к вершине-продукции.
Послетого, как входной поток прочитан до конца, производится поиск всех вершин,38имеющих принимающее состояние анализатора, после чего подграфы, ассоциированные с исходящими из таких вершин рёбрами, объединяются в один граф.Из полученного графа удаляются все недостижимые из корня вершины, в результате чего остаются только корректные деревья разбора для входной строки.Листинг 7 представляет более детальное описание алгоритма.1.7Используемые инструментыВ этом разделе описываются основные инструменты, использованные в работе: YaccConstructor [45, 79], выбранный в качестве основы для реализацииалгоритма синтаксического анализа динамически формируемых выражений, иReSharper SDK [80], использованный для разработки расширений для MicrosoftVisual Studio IDE.1.7.1YaccConstructorОдной из задач данной работы является создание инструментария, упрощающего разработку целевых инструментов статического анализа строковых выражений, который включает такие этапы, как лексический и синтаксический анализ.
Широко распространённой практикой является использование генераторов,которые по описанию языка строят соответствующий анализатор. Данный подход может быть использован и для создания инструментов анализа встроенныхязыков. При этом работа с описаниями языков — грамматикой и лексическийспецификацией — в рамках решаемой задачи аналогична работе с ними в стандартных генераторах.
По этой причине необходимо выбрать соответствующуюплатформу.В качестве такой платформы был выбран YaccConstructor (YC) [45, 79] — исследовательский проект лаборатории языковых инструментов JetBrains, которыйявляется модульным, имеет открытый исходный код и предназначен для исследований в области лексического и синтаксического анализа. YC реализован наплатформе Microsoft .NET3 , основной язык разработки — F#4 [83].34Microsoft .NET — платформа для разработки программных продуктов компании Microsoft [81].F# — функциональный язык программирования для платформы .NET [82].39Рисунок 3: Архитектура платформы YaccConstructorАрхитектура YC представлена на рисунке 3.
YC позволяет собирать требуемый инструмент из существующих модулей: можно выбрать фронтенд, соответствующий используемому языку спецификации грамматики, задать необходимые преобразования грамматики, указать необходимый генератор. Генераторы (backend) представляют различные инструменты, которые по внутреннемупредставлению грамматики получают результат, полезный для конечного пользователя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
