Диссертация (1150733), страница 10
Текст из файла (страница 10)
Мы строим внутреннюю структуру данных (в дальнейшем изложении называемую внутренним графом) посредством копирования графа входногоавтомата и связывания с его вершинами следующих коллекций:491: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:function PUSH(ℎ ) ← copy ℎ.clear ℎ.for all ℎ in dofor all in outgoing edges of ℎ doℎ ← calculate next state by ℎ . and the token on ADD E DGE (ℎ , ., ℎ, )add ℎ in ℎ.function MAKE R EDUCTIONS(ℎ )while ℎ. is not empty do(, , ) ← ℎ..()find the set of vertices reachable from along the path of length ( − 1), or 0 if = 0;add (, , − ) in .,where is an -th vertex of the pathfor all ℎ in do ← calculate new state by ℎ . and nonterminal ADD E DGE (ℎ , , , ( = 0))function APPLY PASSING R EDUCTIONS(ℎ )for all (, ) in ℎ.
dofor all (, , ) ← ..() dofind the set of vertices ,reachable from along the path of length ( − 1)for all ℎ in do ← calculate new state by ℎ . and nonterminal ADD E DGE (ℎ , , , )Листинг 12: Обработка вершины внутреннего графа– processed — содержит вершины GSS, для которых ранее были вычисленывсе операции push; это множество агрегирует все вершины GSS, ассоциированные с вершиной внутреннего графа;– unprocessed — содержит вершины GSS, операции push для которых ещётолько предстоит выполнить; это множество аналогично множеству алгоритма RNGLR;– reductions — это очередь, аналогичная очереди ℛ RNGLR-алгоритма: онасодержит все операции reduce, которые ещё только предстоит выполнить;50– passingReductionsToHandle — содержит пары (,), где — это вершинаGSS, а — это ребро GSS, вдоль которого необходимо осуществлять проходящие свёртки.Будем предполагать, что доступ к данным коллекциям осуществляется какк полям вершины: 1 .
— доступ к коллекции processed, связанной свершиной 1 .1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:function ADD V ERTEX(ℎ, ) ← find a vertex with state = inℎ. ∪ ℎ.if is not then◁ Вершина была найдена в GSSreturn (, )else ← create new vertex for ℎ with state add in ℎ.for all in outgoing edges of ℎ docalculate the set of zero-reductions by and the token on and add them in ℎ.return (, )function ADD E DGE(ℎ , ℎ, , )( , ) ← ADD V ERTEX(ℎ, )if GSS does not contain edge from to ℎ then ← create new edge from to ℎ.(ℎ )if not and ..
> 0 thenadd ( , ) in ℎ. if not thenfor all in outgoing edges of ℎ docalculate the set of reductions by and the token on and add them in ℎ.Листинг 13: Построение GSSПомимо состояния анализатора и уровня (который совпадает с со-стоянием входного автомата) в вершине GSS хранится также коллекция проходящих свёрток, то есть тройки (, , ), соответствующие свёрткам, чей путьсодержит данную вершину GSS.
Аналогичная тройка используется в RNGLRалгоритме для описания свёртки, но в данном случае обозначает длину оставшейся части пути. Проходящие свёртки сохраняются в каждой вершине пути51(кроме первой и последней) во время поиска путей в функции (см. листинг 12).2.3Построение компактного представления лесаразбораВ качестве компактного представления леса разбора всех корректных выражений из множества значений динамически формируемого выражения используется граф SPPF. Построение компактного представления осуществляется одновременно с синтаксическим разбором во время построения графа стеков GSS,так же как и в алгоритме RNGLR.С каждым ребром GSS ассоциируется список лесов разбора фрагмента выражения.
В графе GSS нет кратных рёбер, поэтому если во время работы функцииaddEdge в нем было найдено добавляемое ребро, то с ним ассоциируется новыйлес разбора, при этом в очередь на обработку не добавляется никаких вершинвходного графа.При добавлении в GSS ребра, соответствующего считанной со входа лексеме,создаётся (и ассоциируется с ним) граф из одной терминальной вершины. Таккак входной автомат является детерминированным, с ребром GSS ассоциируетсяне более одного такого графа.При обработке свёртки алгоритм осуществляет поиск всех путей в графеGSS заданной длины, после чего происходит добавление в GSS новых ребер,соответствующих данной свёртке. С каждым таким ребром ассоциируется лес,имеющий в качестве корня вершину, соответствующую нетерминалу, к которомуосуществлялась свёртка.
Ребра каждого из найденных путей, перечисленные вобратном порядке, образуют правую часть некоторого правила грамматики, покоторому осуществляется свёртка. Для каждого пути создаётся вершина, помеченная номером такого правила, и добавляется в лес как непосредственно достижимая из корня. Каждое ребро пути ассоциировано со списком лесов выводасимвола из правой части правила. Непосредственно достижимыми вершинамивершины-правила становятся ссылки на такие списки, за счёт чего осуществляется переиспользование фрагментов леса.52В алгоритме RNGLR наличие нескольких путей, вдоль которых осуществляется свёртка к нетерминалу, означает существование более чем одного вариантавывода нетерминала. В нашем случае данная ситуация соответствует различным фрагментам нескольких выражений из входного регулярного множества,которые сворачиваются к одному нетерминалу.В конце работы алгоритма осуществляется поиск ребер GSS, для каждогоиз которых верно утверждение, что конечная вершина имеет уровень, равныйфинальному состоянию входного автомата, и включает принимающее состояние (accepting state).
Результирующее представление леса разбора получается спомощью удаления недостижимых вершин из графа, созданного объединениемлесов разбора, ассоциированных с найденными рёбрами GSS.Рассмотрим пример представленный в листинге 14: код динамически формирует выражение expr в строке 4.12345string expr = "" ;for(int i = 0; i < len; i++){expr = "()" + expr;}Листинг 14: Кода на C#, динамически формирующий скобочнуюпоследовательностьМножество значений выражения expr аппроксимируется регулярным выражением (LBR RBR)*, где LBR — открывающая скобка, а RBR — закрывающая.Граф конечного автомата, задающего такую аппроксимацию, изображён на рисунке 4.0LBRRBR1EOF2Рисунок 4: Конечный автомат, задающий регулярную аппроксимациювыражения expr53В результате работы предложенного алгоритма будет получено конечноепредставление леса разбора SPPF, изображённое на рисунке 5.n yard_start_ruleprod 2ns!prod 0t LBRnst RBRprod 0t LBRepsnsepst LBRnsepst RBRprod 0t RBRns!prod 0t LBRnst RBRepsРисунок 5: Конечное представление леса разбора для выражения exprИз построенного SPPF можно извлечь бесконечное количество деревьев,каждое из которых является деревом вывода некоторой цепочки из регулярнойаппроксимации.
На рисунках 6, 7, 8 представлены извлечённые деревья разборадля различных значений выражения expr.2.4Доказательство корректности алгоритмаТ ЕОРЕМА 1. Алгоритм завершает работу для любых входных данных.Д ОКАЗАТЕЛЬСТВО . С каждой вершиной внутреннего представления графавходного конечного автомата ассоциировано не более вершин графа GSS, где — это количество состояний синтаксического анализатора. Таким образом,количество вершин в графе GSS ограничено сверху числом × , где — это54n yard_start_rulenst LBRnst RBRepsРисунок 6: Дерево вывода для выражения = ”()”n yard_start_rulenst LBRnst RBRnsepst LBRnst RBRepsРисунок 7: Дерево вывода для выражения = ”()()”количество вершин графа входного автомата.
Так как в GSS нет кратных ребер,количество его ребер не превышает (( ×)2 ). На каждой итерации основногоцикла алгоритм извлекает из очереди и обрабатывает одну вершину внутреннего графа. Вершины добавляются в очередь только тогда, когда происходитдобавление нового ребра в GSS. Так как количество ребер в GSS конечно, алгоритм завершает работу для любых входных данных. 55n yard_start_rulenst LBRnst RBRnsepst LBRnst RBRnsepst LBRnst RBRepsРисунок 8: Дерево вывода для выражения = ”()()()”Для того, чтобы доказать корректность построения конечного представлениялеса разбора нам потребуется следующее определение.О ПРЕДЕЛЕНИЕ 1.
Корректное дерево — это упорядоченное дерево со следующими свойствами.1. Корень дерева соответствует стартовому нетерминалу грамматики .2. Листья соответствуют терминалам грамматики . Упорядоченная последовательность листьев соответствует некоторому пути во входном графе.3. Внутренние узлы соответствуют нетерминалам грамматики . Дети внутреннего узла (для нетерминала ) соответствуют символам правой частинекоторой продукции для в грамматике .Таким образом, корректное дерево — это дерево вывода некоторой цепочки из регулярного множества в эталонной грамматике. Далее нам необходимодоказать, во-первых, что конечное представление леса разбора SPPF содержиттолько корректные деревья, во-вторых, что для каждой корректной относительноэталонной грамматики цепочки существует корректное дерево вывода в SPPF.Л ЕММА . Пусть обрабатывается внутренний граф = (,). Тогда длякаждого ребра GSS ( , ℎ ) такого, что ∈ ., ℎ ∈ ℎ .,56где ∈ и ℎ ∈ , терминалы ассоциированного поддерева соответствуютнекоторому пути из вершины ℎ в в графе .Д ОКАЗАТЕЛЬСТВО .
Будем строить доказательство при помощи индукции повысоте дерева вывода .База индукции: = 1. Возможны два случая.1. Дерево является -деревом. Такое дерево соответствует пути длины 0; начальная и конечная вершины ребра, соответствующего такому дереву, совпадают, поэтому утверждение верно.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
