Санкт-Петербургский государственный университет
Математическое обеспечение и администрирование
информационных систем
Системное Программирование
Азимов Рустам Шухратуллович
Диагностика синтаксических ошибок в
динамически формируемом коде
Бакалаврская работа
Научный руководитель:
ст. преп., магистр информационных технологий Григорьев C. В.
Рецензент:
программист ООО ”ИнтеллиДжей Лабс” Авдюхин Д. А.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Software and Administration of Information Systems
Software Engineering
Rustam Azimov
Syntax errors detection in dynamically
generated code
Bachelor’s Thesis
Scientific supervisor:
Senior Lecturer Semen Grigorev
Reviewer:
Software Developer at IntelliJ Labs OOO Dmitry Avdyukhin
Saint-Petersburg
2016
Оглавление
Введение
4
1. Постановка задачи
5
2. Обзор
2.1. Регулярная аппроксимация динамически формируемого выражения . .
2.2. Алгоритм ослабленного синтаксического анализа регулярной аппроксимации динамически формируемого выражения . . . . . . . . . . . . . . .
2.3. Понятие синтаксической ошибки в алгоритмах LR-семейства . . . . . . .
2.4. Проект YaccConstructor . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
6
6
11
12
3. Понятие синтаксической ошибки
14
4. Механизм диагностики ошибок
16
4.1. Компактное представление префиксов внутреннего графа . . . . . . . . 16
4.2. Алгоритм построения префиксов . . . . . . . . . . . . . . . . . . . . . . . 17
4.3. Алгоритм диагностики ошибок . . . . . . . . . . . . . . . . . . . . . . . . 19
5. Корректность механизма диагностики ошибок
23
5.1. Корректность алгоритма построения префиксов . . . . . . . . . . . . . . 23
5.2. Корректность алгоритма диагностики ошибок . . . . . . . . . . . . . . . 30
6. Экспериментальное исследование
34
7. Заключение
37
Список литературы
38
3
Введение
При разработке сложных программных систем существует проблема недостатка выразительности и гибкости языков программирования общего назначения. Часто для решения данной проблемы помимо основного языка используют один или
несколько других (встроенных) языков. В данном подходе программа, написанная
на основном языке, динамически формирует строковое представление кода на встроенном языке, и далее сформированная строка анализируется и выполняется специальными компонентами (базы данных, веб-браузер) во время исполнения основной
программы.
Как правило, динамически формируемые выражения, описывающие код программ
на встроенных языках, конструируются с использованием конкатенаций строковых
литералов в ветках условных операторов, циклах и рекурсивных процедурах. Это приводит к множеству возможных значений встроенного кода, что не позволяет в общем
виде использовать статический анализ для проверки корректности формируемого выражения. В результате этого становятся недоступными такие типы функциональности, как информирование о синтаксических ошибках, автодополнение и подсветка
синтаксиса. Отсутствие этих возможностей повышает вероятность ошибок, которые
обнаруживаются лишь во время выполнения программы, а также усложняет процесс
разработки и тестирования.
Существует ряд инструментов, позволяющих проводить анализ динамически формируемых строковых выражений: Java String Analyzer [5, 9], PHP String Analyzer [12],
Alvor [8, 2, 1], IntelliLang [7], PHPStorm [14], Varis [13] (анализ этих технологий приведен в работе [21]). Большинство реализаций проводят диагностику синтаксических
ошибок, но плохо расширяемы: как в смысле поддержки других языков, так и в
смысле решения новых задач. Существует алгоритм, описанный в статье [19] и реализованный как часть проекта YaccConstructor [11], который позволяет провести
синтаксический анализ динамически формируемых выражений. В отличие от других
инструментов, реализация данного алгоритма хорошо расширяема и строит конечное
представление леса разбора относительно входной грамматики, которое может быть
использовано в дальнейшем семантическом анализе. Недостаток данного алгоритма
заключается в отсутствии механизма диагностики синтаксических ошибок. Устранению этого недостатка и посвящена данная работа.
4
1. Постановка задачи
Целью данной работы является разработка механизма диагностики ошибок в алгоритме ослабленного синтаксического анализа регулярной аппроксимации динамически формируемого выражения, реализованного в проекте YaccConstructor [11].
Для достижения этой цели были сформулированы следующие задачи.
• Определить понятие синтаксической ошибки в терминах регулярной аппроксимации динамически формируемого выражения.
• Разработать механизм диагностики ошибок в синтаксическом анализе регулярной аппроксимации динамически формируемого выражения.
• Доказать корректность механизма.
• Реализовать
предложенный
YaccConstructor.
механизм
• Провести экспериментальное исследование.
5
в
рамках
проекта
2. Обзор
Алгоритм, доработке которого посвящена данная работа, основан на алгоритме
RNGLR [16] (Right-Nulled Generalized LR). В свою очередь, RNGLR является модификацией алгоритма Generalized LR (GLR) [18], предназначенного для анализа естественных языков. GLR-алгоритм использует управляющие таблицы семейства LR
(Left-to-right Rightmost) алгоритмов [6] с возможностью содержать несколько действий в одной ячейке. Таким образом, при описании работы алгоритма ослабленного
синтаксического анализа регулярной аппроксимации динамически формируемого выражения необходимо рассмотреть все вышеперечисленные алгоритмы.
В данном разделе дано краткое описание работы алгоритма ослабленного синтаксического анализа регулярной аппроксимации динамически формируемого выражения. Также рассмотрено понятие синтаксической ошибки в алгоритмах LR-семейства
и описан проект, в рамках которого велась разработка предложенного алгоритма.
2.1. Регулярная аппроксимация динамически формируемого
выражения
Под регулярной аппроксимацией подразумевается аппроксимирование сверху множества значений динамически формируемого выражения некоторым регулярным выражением. В терминах привычных для задач распознавания, проверка корректности
выражений из аппроксимирующего множества формулируется как задача проверки
включения регулярного языка в другой (как правило, контекстно-свободный язык),
которая разрешима во многих важных на практике случаях [3]. Метод построения
рассматриваемой аппроксимации, представленный в работе [4], реализован [10] в проекте YaccConstructor.
2.2. Алгоритм ослабленного синтаксического анализа регулярной аппроксимации динамически формируемого выражения
Чтобы понять принцип работы данного алгоритма, сначала рассмотрим алгоритмы LR-семейства, такие как LR(1), SLR(1), LALR(1). Все эти алгоритмы принимают
на вход строку и контекстно-свободную грамматику. Если удалось построить детерминированную управляющую таблицу по данной грамматике, то перечисленные алгоритмы позволяют ответить на вопрос о принадлежности произвольной строки языку,
порождаемому данной грамматикой. Входная строка читается слева направо и в процессе чтения программа, выполняющая синтаксический анализ, (парсер) меняет свои
состояния по правилам, установленным в управляющей таблице. Нужная ячейка таб-
6
лицы определяется текущим состоянием и правым контекстом (одним или несколькими следующими терминалами) входной строки. История состояний программы хранится в виде стека. Кроме перехода из состояния в состояние ячейка управляющей
таблицы содержит действия, которые бывают двух видов: сдвиг (push, shift) — чтение
следующей части входной строки и свертка (reduce) — применение одного из правил входной грамматики. Строка принимается алгоритмом лишь в том случае, если
она была полностью обработана, и конечное состояние парсера — одно из заранее
определенных принимающих состояний.
Иногда построить детерминированную таблицу не удается, и в одной ячейке управляющей таблицы могут быть конфликты следующих видов: сдвиг/свертка (shift/
reduce) и свертка/свертка (reduce/reduce). Существует два подхода, применяемых к
обработке таких неоднозначностей. Первый из них подразумевает разрешение конфликтов, а второй — анализ всех возможных последовательностей действий, предпринимаемых парсером. Алгоритмы семейства GLR, разработанные для анализа произвольных неоднозначных контекстно-свободных грамматик, используют второй подход. При работе этих алгоритмов порождается множество стеков состояний и деревьев разбора, для эффективного хранения которых используются специализированные структуры данных: структурированный в виде графа стек GSS (Graph Structured
Stack) и компактное представление леса разбора SPPF [15] (Shared Packed Parse Forest).
Следует отметить, что оригинальный GLR-алгоритм не способен анализировать
все контекстно-свободные грамматики, поэтому в работе [16] был предложен RNGLRалгоритм, который является его расширением. RNGLR специальным способом обрабатывает обнуляемые справа правила входной грамматики (имеющие вид A → αβ, где
β выводит пустую строку ϵ). RNGLR, как и GLR, строит GSS ”слоями”, т.е. сначала
выполняются все возможные операции свертки для текущего терминала, после чего
осуществляется операция сдвига к следующему терминалу входной строки. Вершина GSS представляется в виде пары (s, l), где s — состояние парсера, а l — уровень
(позиция текущего терминала во входном потоке).
Алгоритм, доработке которого посвящена данная работа, является расширением алгоритма RNGLR, способным производить синтаксический анализ регулярного
множества входных строк. При анализе рассматриваемым алгоритмом регулярного множества, состоящего из единственной строки конечной длины, результат будет
аналогичен результату анализа алгоритма RNGLR. В расширении вместо строки на
вход подается конечный недетерминированный автомат с единственными начальным
и конечным состояниями, который порождает регулярную аппроксимацию значений
динамически формируемого выражения. Данный автомат представляется в виде ориентированного графа (далее входного графа) с вершинами — состояниями автомата
и ребрами — переходами автомата. Строится внутренний граф, который получается
из входного — ассоциацией вершин GSS и некоторых коллекций с вершинами гра7
фа. Основная идея расширения заключается в перемещении по внутреннему графу
и последовательном построении GSS. В качестве ”слоев” выступают вершины внутреннего графа, таким образом каждая вершина GSS хранит состояние парсера state
и уровень level (который отождествляется с вершиной внутреннего графа). Теперь
операция сдвига выполняется не по одному токену, а по множеству токенов, нагруженных на дуги, исходящие из текущей вершины графа.
Для организации порядка обработки вершин внутреннего графа используется глобальная очередь Q. При добавлении новой вершины GSS сначала все свертки длины
0 (zero-reductions) добавляются в очередь операций reduce, после этого выполняется
операция сдвига следующих токенов со входа, а соответствующие вершины графа
добавляются в очередь Q. Так как добавление нового ребра GSS может порождать
новые свeртки, то в очередь на обработку Q необходимо добавить вершину внутреннего графа, которой соответствует начальная вершина добавленного ребра (процесс
построения GSS описан в алгоритме 3). Операции свертки проводятся вдоль путей в
GSS, таким образом, если начальная вершина нового ребра ранее присутствовала в
GSS, то необходимо заново вычислить свертки путей, проходящих через эту вершину
(функция applyPassingReductions в алгоритме 2).
Кроме состояния анализатора state и уровня level, в вершине GSS хранится коллекция проходящих сверток. Проходящая свертка — это тройка (startV, N, l), соответствующая свертке, чей путь содержит данную вершину GSS, а длина оставшейся
части пути равна l. Проходящие свeртки сохраняются в каждой вершине пути (кроме
первой и последней) во время поиска путей в функции makeReductions (алгоритм 2).
В вершинах внутреннего графа хранятся следующие коллекции:
• processed — вершины GSS, для которых ранее были вычислены все операции
push;
• unprocessed — вершины GSS, операции push для которых ещё только предстоит
выполнить;
• reductions — очередь операций reduce, которые ещё только предстоит выполнить;
• passingReductionsToHandle — пары из вершины GSS и ребра GSS, вдоль которых
необходимо обновить проходящие свeртки.
8
Algorithm 1 Алгоритм ослабленного синтаксического анализа регулярной аппроксимации динамически формируемого выражения
1: function PARSE(grammar, automaton)
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
inputGraph ← construct inner graph representation of automaton
parserSource ← generate RNGLR parse tables for grammar
if inputGraph contains no edges then
if parserSource accepts empty input then report success
else report failure
else
ADDVERTEX(inputGraph.startV ertex, startState)
Q.Enqueue(inputGraph.startV ertex)
while Q is not empty do
v ← Q.Dequeue()
MAKEREDUCTIONS(v)
PUSH(v)
APPLYPASSINGREDUCTIONS(v)
if ∃vf : vf .level = qf and vf .state is accepting then report success
else report failure
9
Algorithm 2 Обработка вершины внутреннего графа
1: function PUSH(innerGraphV )
2:
3:
4:
5:
6:
7:
8:
U ← copy innerGraphV.unprocessed
clear innerGraphV.unprocessed
for all vh in U do
for all e in outgoing edges of innerGraphV do
push ← calculate next state by vh .state and the token on e
ADDEDGE(vh , e.Head, push, f alse)
add vh in innerGraphV.processed
9: function MAKEREDUCTIONS(innerGraphV )
10:
11:
12:
13:
14:
15:
16:
17:
18:
while innerGraphV.reductions is not empty do
(startV, N, l) ← innerGraphV.reductions.Dequeue()
find the set of vertices X reachable from startV
along the path of length (l − 1), or 0 if l = 0;
add (startV, N, l − i) in v.passingReductions,
where v is an i-th vertex of the path
for all vh in X do
statet ← calculate new state by vh .state and nonterminal N
ADDEDGE(vh , startV, statet , (l = 0))
19: function APPLYPASSINGREDUCTIONS(innerGraphV )
20:
21:
22:
23:
24:
25:
26:
for all (v, edge) in innerGraphV.passingReductionsT oHandle do
for all (startV, N, l) ← v.passingReductions.Dequeue() do
find the set of vertices X ,
reachable from edge along the path of length (l − 1)
for all vh in X do
statet ← calculate new state by vh .state and nonterminal N
ADDEDGE(vh , startV, statet , f alse)
10
Algorithm 3 Построение GSS
1: function ADDVERTEX(innerGraphV, state)
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
v ← find a vertex with state = state in
innerGraphV.processed ∪ innerGraphV.unprocessed
if v is not null then
▷ Вершина была найдена в GSS
return (v, f alse)
else
v ← create new vertex for innerGraphV with state state
add v in innerGraphV.unprocessed
for all e in outgoing edges of innerGraphV do
calculate the set of zero-reductions by v
and the token on e and add them in innerGraphV.reductions
return (v, true)
13: function ADDEDGE(vh , innerGraphV, statet , isZeroReduction)
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
(vt , isN ew) ← ADDVERTEX(innerGraphV, statet )
if GSS does not contain edge from vt to vh then
edge ← create new edge from vt to vh
Q.Enqueue(innerGraphV )
if not isN ew and vt .passingReductions.Count > 0 then
add (vt , edge) in innerGraphV.passingReductionsT oHandle
if not isZeroReduction then
for all e in outgoing edges of innerGraphV do
calculate the set of reductions by v
and the token on e and add them in innerGraphV.reductions
2.3. Понятие синтаксической ошибки в алгоритмах LR-семейства
Конкретная формальная грамматика делит множество всевозможных строк на
принимаемые (принадлежащие языку, порожденному данной грамматикой) и непринимаемые. Несоответствие синтаксическим правилам, определенным грамматикой
называется синтаксической ошибкой. Таким образом, в строке присутствует синтаксическая ошибка (может быть не одна) тогда и только тогда, когда она не является
принимаемой для соответствующей грамматики.
Алгоритмы из LR-семейства обладают свойством корректного префикса (correctprefix property) [6], то есть если данные алгоритмы корректно определяют принимаемая ли строка для рассматриваемой грамматики, то они обнаруживают ошибку на
первом терминале, который образует из прочтенной части входной строки некорректный префикс (ни одна принимаемая строка не начинается на данный префикс).
11
Если алгоритмы из LR-семейства обнаружили синтаксическую ошибку, то возможен один из двух вариантов:
• парсер обработал всю входную строку, но итоговое состояние не принадлежит
множеству принимающих состояний;
• парсер выполнил все операции свертки для текущего терминала, но не имеется
ни одной операции сдвига к следующему терминалу входной строки.
Таким образом, данные алгоритмы продолжают свою работу до тех пор, пока
обработанная часть строки является корректным префиксом.
2.4. Проект YaccConstructor
В рамках исследовательского проекта YaccConstructor [11] лаборатории языковых
инструментов JetBrains на математико-механическом факультете СПбГУ проводятся
исследования в области лексического, синтаксического анализа, а также статического
анализа встроенных языков. Проект YaccConstructor является модульным инструментом, имеющим собственный язык спецификации грамматик. Также в нем объединены различные алгоритмы лексического и синтаксического анализа. В рамках проекта
была создана платформа для статического анализа встроенного кода. На рис. 1 представлена диаграмма последовательности, иллюстрирующая взаимодействие модулей
платформы. Выделена компонента, осуществляющая синтаксический анализ множества значений динамически формируемого выражения.
Предыдущая реализация платформы игнорировала синтаксические ошибки, что
усложняло процесс разработки и тестирования программных систем, использующих
данную платформу. Однако это повлекло необходимость разработки механизма диагностики ошибок в рамках алгоритма синтаксического анализа, чему и посвящена
данная работа.
12
Рис. 1: Диаграмма последовательности: взаимодействие компонентов инструмента
YaccConstructor (рисунок взят из работы [20])
13
3. Понятие синтаксической ошибки
Прежде чем описывать алгоритм диагностики ошибок, необходимо определить понятие синтаксической ошибки для алгоритма ослабленного синтаксического анализа
регулярной аппроксимации динамически формируемого выражения. На вход данного
алгоритма подается не одна строка, а множество строк, поэтому необходимо обнаруживать ошибки во всех строках из данного множества. Для этого необходимо определить понятие синтаксической ошибки для алгоритма RNGLR. Определим сначала
понятие синтаксической ошибки для GLR-алгоритма.
GLR-алгоритм, получивший на вход строку, не принимаемую соответствующей
грамматикой, останавливает свою работу в двух случаях:
• синтаксический анализатор обработал всю входную строку, но среди множества
итоговых состояний ни одно состояние не принадлежит множеству принимающих состояний;
• синтаксический анализатор выполнил все операции свертки для текущего терминала, но среди множества состояний текущего уровня не имеется ни одного
состояния, по которому в управляющей таблице существует операция сдвига к
следующему терминалу входной строки.
Таким образом, пока обработанная часть входной строки является корректным
префиксом данной грамматики, хотя бы один стек из множества стеков состояний текущего уровня может быть продолжен с использованием операции сдвига к следующему терминалу входной строки. Другими словами, GLR-алгоритм, как и алгоритмы
LR-семейства, обладает свойством корректного префикса. Ошибочным терминалом
входной строки GLR-алгоритма, будем называть первый терминал из необработанной
части входной строки, на момент обнаружения синтаксической ошибки (если обработана вся строка, то это специальный терминал, обозначающий конец строки).
Алгоритм RNGLR также обладает свойством корректного префикса, т.к. является
расширением GLR-алгоритма со специальной обработкой некоторых правил входной
грамматики. Определение ошибочного терминала входной строки RNGLR-алгоритма
аналогично определению ошибочного терминала GLR алгоритма.
Ввиду того, что алгоритм ослабленного синтаксического анализа регулярной аппроксимации динамически формируемого выражения, в отличие от RNGLR-алгоритма,
принимает на вход не строку, а множество строк, то необходимо искать синтаксические ошибки во всем входном множестве строк. Для каждой отдельной строки понятие синтаксической ошибки совпадает с понятием синтаксической ошибки в RNGLRалгоритме. Множество входных строк выражено конечным недетерминированным
автоматом с единственными начальным и конечным состояниями. Данный автомат
представляется в виде ориентированного графа (внутреннего графа) с терминалами
14
на ребрах. В таком случае, обработанная часть входных данных –– не префикс строки, а терминалы, ассоциированные с ребрами (то есть нагруженные на ребрах) в пути
во внутреннем графе из начальной вершины в вершину, соответствующую текущему
уровню. Рассматриваемый путь будем называть префиксом внутреннего графа. Если строка p, образованная терминалами на ребрах рассматриваемого пути префикса
внутреннего графа P , является корректным префиксом эталонной грамматики, то
префикс внутреннего графа P назовем корректным, иначе — некорректным.
Пусть непустая строка p является корректным префиксом для рассматриваемой
грамматики, тогда при обработке данной строки RNGLR-алгоритмом будут прочитаны все её терминалы и на последнем уровне GSS будет хотя бы одна вершина. Пусть
(s1 , .., sn ) — все состояния вершин рассматриваемого последнего уровня GSS. Тогда в
последней вершине V пути префикса внутреннего графа P ∃(v1 , .., vn ) — GSS-вершины,
где vi .state = si , ∀i ∈ [1, .., n]. Префикс внутреннего графа P назовем корректным для
GSS-вершины v, если v ∈ (v1 , .., vn ). Если строка p пустая и она является корректным префиксом для рассматриваемой грамматики, то префикс внутреннего графа P
состоит из единственной начальной вершины внутреннего графа и назовем его корректным для GSS-вершин (u1 , .., un ), где ∀i, ui — либо начальная GSS-вершина, либо
существует последовательность сверток длины 0, приводящая парсер из начального
состояния в состояние ui .state.
Назовем ошибочным ребром ребро внутреннего графа e, которое не нагружено
специальным терминалом конца строки EOF , такое, что существует хотя бы один
корректный префикс внутреннего графа P , заканчивающийся в вершине, из которой исходит данное ребро, но при добавлении ребра e в конец префикса P образуется некорректный префикс внутреннего графа. Если ребро e нагружено терминалом
конца строки EOF , то ребро e является ошибочным, если существует хотя бы один
корректный префикс внутреннего графа P , заканчивающийся в вершине, из которой исходит данное ребро, но строка, образованная последовательностью терминалов
на ребрах пути P не является принимаемой эталонной грамматикой. Аналогом ошибочного терминала во входной строке RNGLR-алгоритма, является ошибочное ребро
внутреннего графа.
Таким образом, цель диагностики ошибок в рамках синтаксического анализа регулярной аппроксимации множества значений динамически формируемого выражения
заключается в обнаружении ошибочных ребер внутреннего графа и выводе корректных префиксов внутреннего графа, заканчивающихся в вершине, из которой исходит
рассматриваемое ошибочное ребро, и становящихся некорректными при добавлении
в конец этого ребра.
15
4. Механизм диагностики ошибок
Предлагаемый механизм диагностики ошибок состоит из двух частей:
• алгоритм синтаксического анализа регулярной аппроксимации динамически формируемых выражений (далее основной анализ) модифицируется, позволяя для
каждой GSS вершины строить все корректные для нее префиксы внутреннего
графа;
• после основного анализа с помощью построенных префиксов обнаруживаются
ошибочные ребра внутреннего графа.
Далее в этой главе будут рассмотрены: компактное представление префиксов внутреннего графа, алгоритм построения корректных префиксов внутреннего графа для
GSS-вершин и алгоритм диагностики ошибок, проводящий анализ построенных префиксов.
4.1. Компактное представление префиксов внутреннего графа
Так как внутренний граф может иметь циклы, то множество различных префиксов внутреннего графа может быть бесконечным. В качестве компактного представления всех корректных префиксов внутреннего графа для вершины GSS используется
ориентированный граф с выделенным множеством начальных вершин (далее граф
префиксов). Из-за особенностей операций, используемых при построении графов префиксов, начальные вершины представляют не начало, а конец хранимых префиксов
внутреннего графа в рассматриваемом графе префиксов. Каждая вершина в графе
префиксов ассоциируется с ребром GSS или является специальной вершиной EOP
(End Of Prefix). Ребра GSS, в свою очередь, будем делить на три вида:
• терминальное ребро — ребро, порожденное операцией сдвига по какому-то терминалу t;
• нетерминальное — ребро, порожденное операцией свертки длины l, где l > 0;
• обнуляемое — ребро, порожденное операцией свертки длины l, где l = 0.
Будем говорить, что начальная вершина V графа префиксов GP1 соединена с графом
префиксов GP2 , если для любой начальной вершины U графа префиксов GP2 , существует ребро из вершины V в вершину U . Каждая, кроме EOP , начальная вершина
графа префиксов соединена с одним графом префиксов. Вершина EOP не имеет исходящих дуг.
С каждым нетерминальным ребром ассоциируется множество путей в GSS, по
которым произведена операция свертки для данного нетерминального ребра. Будем
16
говорить что данное нетерминальное ребро порождает каждый путь из рассмотренного множества путей GSS.
Рассмотрим путь (V1 , .., Vn ) в графе префиксов GP как последовательность вершин
графов префиксов. Удалим вершину EOP , если она присутствует, а также заменим
все вершины в данном пути на ребра GSS, с которыми они ассоциируются. Получим
последовательность (e1 , .., en ) ребер GSS. Раскрытием данной последовательности будем называть последовательность, получающуюся в результате применения следующих действий:
• все нетерминальные ребра GSS e, заменяются на последовательность ребер, соответствующую одному из порожденных ребром e пути;
• все обнуляемые ребра GSS удаляются из последовательности.
Если после конечного числа раскрытий в последовательности останутся только терминальные ребра GSS, то будем говорить, что изначальный путь в графе префиксов
сводится к строке, получающейся инвертированием этой последовательности терминальных ребер и их замены на терминалы, с которыми они ассоциированы. Если
полученная строка получается заменой ребер в пути префикса внутреннего графа P ,
на терминалы, которыми нагружены эти ребра, то путь в графе префиксов сводится
к префиксу внутреннего графа P . Будем говорить, что граф префиксов GP порождает префикс внутреннего графа P , если ∃(V1 , .., Vn , EOP ) — путь в графе префиксов
GP , где V1 — одна из начальных вершин графа префиксов GP , который сводится к
префиксу внутреннего графа P . В графе префиксов также могут быть циклы, что
позволяет сводиться к бесконечному множеству префиксов внутреннего графа.
4.2. Алгоритм построения префиксов
Данный алгоритм является модификацией алгоритма ослабленного синтаксического анализа регулярной аппроксимации динамически формируемого выражения.
Добавляется ассоциация вершин GSS с коллекцией pref ixes — граф префиксов, порождающий все корректные префиксы внутреннего графа для данной GSS вершины.
После создания начальной GSS-вершины в ее графе префиксов создается начальная
вершина EOP . Добавляется ассоциация нетерминальных ребер GSS с коллекцией
paths — множество путей в GSS, порождаемых рассматриваемым нетерминальным
ребром. Функция addEdge модифицируется, добавляется дополнительный параметр
pathsT oAdd — множество путей в GSS, которое необходимо добавить к множеству путей в GSS, порождаемых ребром edge из вершины vt в вершину vh . Также создается
начальная вершина графа префиксов vt .pref ixes, ассоциированная с ребром edge и
соединенная с графом префиксов vh .pref ixes. Функция addV ertex не изменилась.
17
Algorithm 4 Модификация построения GSS
1: function ADDEDGE(vh , innerGraphV, statet , isZeroReduction, pathsT oAdd)
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
(vt , isN ew) ← ADDVERTEX(innerGraphV, statet )
if GSS does not contain edge from vt to vh then
edge ← create new edge from vt to vh
Q.Enqueue(innerGraphV )
if not isN ew and vt .passingReductions.Count > 0 then
add (vt , edge) in innerGraphV.passingReductionsT oHandle
if not isZeroReduction then
for all e in outgoing edges of innerGraphV do
calculate the set of reductions by v and the token on e
and add them in innerGraphV.reductions
V ← vertex of the prefix graph,
associated with edge and connected to vh .pref ixes
add V to initial vertexes of vt .pref ixes
if pathsToAdd is not empty then
edge ← edge from vt to vh
add all paths in pathsT oAdd to edge.paths
Параметр pathsT oAdd при вызове функции addEdge для терминальных или обнуляемых ребер GSS является пустым множеством.
Algorithm 5 Модификация операции сдвига
1: function PUSH(innerGraphV )
2:
3:
4:
5:
6:
7:
8:
9:
U ← copy innerGraphV.unprocessed
clear innerGraphV.unprocessed
for all vh in U do
for all e in outgoing edges of innerGraphV do
push ← calculate next state by vh .state and the token on e
pathsT oAdd ← empty set
ADDEDGE(vh , e.Head, push, f alse, pathsT oAdd)
add vh in innerGraphV.processed
18
Algorithm 6 Модификация операции свертки
1: function MAKEREDUCTIONS(innerGraphV )
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
while innerGraphV.reductions is not empty do
(startV, N, l) ← innerGraphV.reductions.Dequeue()
find the set of vertices X reachable from startV
along the path of length (l − 1), or 0 if l = 0;
add (startV, N, l − i) in v.passingReductions,
where v is an i-th vertex of the path
for all vh in X do
statet ← calculate new state by vh .state and nonterminal N
if l > 0 then
pathsT oAdd ← all paths, by which vh is reachable
from startV
else
pathsT oAdd ← empty set
ADDEDGE(vh , startV, statet , (l = 0), pathsT oAdd)
16: function APPLYPASSINGREDUCTIONS(innerGraphV )
17:
18:
19:
20:
21:
22:
23:
24:
25:
for all (v, edge) in innerGraphV.passingReductionsT oHandle do
for all (startV, N, l) ← v.passingReductions.Dequeue() do
find the set of vertices X ,
reachable from edge along the path of length (l − 1)
for all vh in X do
statet ← calculate new state by vh .state and nonterminal N
pathsT oAdd ← all paths, by which vh is reachable
from startV
ADDEDGE(vh , startV, statet , f alse, pathsT oAdd)
После описанных модификаций алгоритм синтаксического анализа регулярной аппроксимации динамически формируемого выражения для каждой вершины GSS дополнительно конструирует все корректные для нее префиксы внутреннего графа.
4.3. Алгоритм диагностики ошибок
Данный алгоритм получает на вход внутренний граф с построенными в ходе основного синтаксического анализа структурами (в том числе и префиксами внутреннего
графа GSS вершин), а также сгенерированные RNGLR-таблицы. Алгоритм делает
обход внутреннего графа и для каждого исходящего из вершины внутреннего графа
ребра анализирует множества графов префиксов соседних вершин.
Для обхода внутреннего графа используется глобальная очередь Q. Все ребра
19
внутреннего графа, ведущие не в конечную вершину, обрабатываются в функции
processV ertex. Для ребер, ведущих в конечную вершину внутреннего графа, используется глобальная очередь F , с последующей обработкой в функции processEOF .
В результате работы алгоритма все ребра из множества errors являются ошибочными, а ребра из множества probErrors — возможно ошибочными. То есть множество всех ошибочных ребер принадлежит объединению двух данных множеств.
Кроме того, с элементами этих множеств ассоциируются множества графов префиксов (элемент e множества errors или множества probErrors ассоциируется со множеством errors[e] или probErrors[e] соответственно), которые порождают корректные
префиксы, заканчивающиеся в вершине, из которой исходит рассматриваемое ребро.
Данные множества могут быть использованы при создании сообщения пользователю
о возможных ошибках динамически формируемого выражения. Все префиксы, порождаемые графами префиксов из множества errors[e], становятся некорректными
при добавлении в конец ребра e. Все префиксы, порождаемые графами префиксов
из множества probErrors[e], возможно становятся некорректными при добавлении в
конец ребра e. Но множество всех корректных префиксов внутреннего графа, заканчивающихся в вершине, из которой исходит ребро e, и становящихся некорректными
при добавлении ребра e в конец, порождается хотя бы одним графом префиксов из
объединения множеств errors[e] и probErrors[e], где множество errors[e] пусто, если
e∈
/ errors, и множество probErrors[e] пусто, если e ∈
/ probErrors.
Algorithm 7 Алгоритм диагностики ошибок
1: function FINDERRORS(inputGraph, parserSource)
2:
3:
4:
5:
6:
7:
8:
Q.Enqueue(inputGraph.startV ertex)
while Q is not empty do
v ← Q.Dequeue()
PROCESSVERTEX(v)
while F is not empty do
e ← F.Dequeue()
PROCESSEOF(e)
20
Algorithm 8 Анализ неконечных ребер внутреннего графа
1: function PROCESSVERTEX(innerGraphV )
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:
28:
29:
30:
31:
32:
for all e in outgoing edges of innerGraphV do
if token on e is EOF then
F.Enqueue(e)
else
if e.Head was not processed then
Q.Enqueue(e.Head)
headP ref ixes ← all prefixes graphs
from all GSS vertexes of e.Head;
pushedP ref ixes ← all prefixes graphs, to which connected
some initial vertex of prefixes graph in headP ref ixes,
associated with terminal edge;
withCycle ← all cyclical prefixes graphs in pushedP ref ixes
withoutCycle ← all non-cyclical graphs in pushedP ref ixes
notP ushedP ref ixes ← all prefixes graphs
from all GSS vertexes of innerGraphV ,
without prefixes graphs from pushedP ref ixes;
for all p in notP ushedP ref ixes do
if prefixes graph p has a cycle then
add e to probErrors
add p to probErrors[e]
else
for all pref ixP ath in paths of prefixes graph p do
pathG ← prefixes graph generated by pref ixP ath
if withoutCycle does not have any prefixes graph with
equivalent to pref ixP ath path then
if withCycle is not empty then
add e to probErrors
add pathG to probErrors[e]
else
add e to errors
add pathG to errors[e]
21
Algorithm 9 Анализ конечных ребер внутреннего графа
1: function PROCESSEOF(edge)
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
acceptedP ref ixes ← all prefixes graphs
from all GSS vertexes of edge.T ail with accepted state;
withCycle ← all cyclical prefixes graphs in acceptedP ref ixes
withoutCycle ← all non-cyclical graphs in acceptedP ref ixes
notAcceptedP ref ixes ← all prefixes graphs
from all GSS vertexes of edge.T ail with not accepted state;
for all p in notAcceptedP ref ixes do
if prefixes graph p has a cycle then
add edge to probErrors
add p to probErrors[edge]
else
for all pref ixP ath in paths of prefixes graph p do
pathG ← prefixes graph generated by pref ixP ath
if withoutCycle does not have any prefixes graph
with equivalent to pref ixP ath path then
if withCycle is not empty then
add edge to probErrors
add pathG to probErrors[edge]
else
add edge to errors
add pathG to errors[edge]
22
5. Корректность механизма диагностики ошибок
5.1. Корректность алгоритма построения префиксов
В данном разделе приведено доказательство того, что построенные графы префиксов порождают только корректные для соответствующей вершины стека префиксы
внутреннего графа.
ТЕОРЕМА 1. Каждый корректный для GSS-вершины v префикс внутреннего графа,
соответствующий пути P = (V1 , .., Vl ) во внутреннем графе, порождается графом
префиксов v.pref ixes, построенным алгоритмом построения префиксов.
ДОКАЗАТЕЛЬСТВО. Обозначим входную эталонную грамматику за G. Пусть p —
строка, образованная терминалами на ребрах пути P . Докажем теорему методом математической индукции по l — количеству вершин в пути P .
База l = 1. Тогда p — пустая строка. Так как рассматриваемый префикс внутреннего графа корректен для GSS-вершины v, то либо v — начальная вершина GSS v0 ,
либо существует последовательность сверток длины 0, приводящая парсер из начального состояния v0 .state в состояние v.state. В первом случае v = v0 , а, значит, среди
начальных вершин графа префиксов v.pref ixes имеется вершина EOP . Так как путь
в графе префиксов v.pref ixes состоящий из единственной начальной вершины EOP
сводится к пустой строке, то граф префиксов v.pref ixes порождает префикс внутреннего графа, соответствующий пути P . Во втором случае в GSS существует путь из
вершины v в вершину v0 , состоящий из обнуляемых ребер (e1 , .., ea ). Значит в графе
префиксов v.pref ixes существует путь S = (E1 , .., Ea , EOP ), где E1 — начальная вершина графа префиксов v.pref ixes и ∀i ∈ [1, .., a], Ei — ассоциируется с обнуляемым
ребром ei . Путь S также сводится к пустой строке, следовательно граф префиксов
v.pref ixes порождает префикс внутреннего графа, соответствующий пути P . База
доказана.
Индукционный переход. Пусть теорема доказана для всех префиксов внутреннего графа, соответствующих путям с количеством вершин не большим k, где
k > 0. Докажем теорему для префикса внутреннего графа, соответствующего пути
P = (V1 , .., Vk+1 ).
Так как рассматриваемый префикс внутреннего графа корректен для GSS-вершины
v, то непустая строка p — корректный префикс для грамматики G. Значит, получив
на вход строку p, алгоритм RNGLR обработает все терминалы этой строки и построит
GSS, имеющий вершины (v1 , .., vn ) на последнем уровне. Причем, ∃i : vi .state = v.state.
По построению GSS существует хотя бы один путь из вершины vi в начальную GSSвершину v0 . Пусть Q = (w1 , .., wm ) — один из таких путей, где w1 = vi , а wm = v0 .
Рассмотрим ребро e = (w1 , w2 ). Ребро e может быть терминальным, нетерминальным
или обнуляемым.
23
Если e — терминальное ребро, то пусть оно ассоциировано с терминалом t, нагруженным на ребро (Vk , Vk+1 ) внутреннего графа. Префикс внутреннего графа, соответствующий пути P ′ = (V1 , .., Vk ), корректен в силу корректности префикса, соответсвующего пути P . То есть в вершине внутреннего графа Vk+1 существуют вершины
GSS (u1 , .., ub ), для которых префикс внутреннего графа, соответствующий P ′ , корректен. Тогда ∃j ∈ [1, .., b] : uj .state = w2 .state. По индукционному предположению
префикс внутреннего графа, соответствующий пути P ′ , порождается графом префиксов uj .pref ixes. Следовательно существует путь R = (R1 , .., Rc , EOP ) графа префиксов uj .pref ixes, где R1 — начальная вершина графа префиксов, такой, что путь R
сводится к строке p′ , где p′ — строка p без последнего терминала t. Так как в построенном RNGLR-алгоритмом GSS присутствует ребро e = (w1 , w2 ), то в управляющих
таблицах, соответствующих грамматике G, существует операция сдвига по терминалу t из состояния w2 .state в состояние w1 .state. Значит при обработке основным
анализом GSS-вершины uj будет добавлено ребро e′ = (v, uj ), т.к. uj .state = w2 .state
и v.state = w1 .state. Значит в граф префиксов v.pref ixes будет добавлена начальная вершина E ′ , соответствующая терминальному ребру e′ = (v, uj ) и соединенная
с графом префиксов uj .pref ixes. Поэтому в графе префиксов v.pref ixes существует
путь R′ = (E ′ , R1 , .., Rc, EOP ), который сводится к строке p. Таким образом, граф
префиксов v.pref ixes порождает префикс внутреннего графа, соответствующий пути
P.
Если e — нетерминальное ребро, то пусть оно ассоциировано с нетерминалом N
и путями GSS (P1 , .., Pd ). Пусть в GSS, сконструированным RNGLR-алгоритмом, вершина w2 была создана после обработки первых s < k терминалов строки p. Обозначим
p1 — строка, составленная из первых s терминалов строки p, а p2 — строка, составленная из последних (k − s) терминалов строки p. Так как префикс, соответствующий
пути Ps = (V1 , .., Vs+1 ) — корректен, то в вершине Vs+1 существует GSS-вершина h такая, что этот префикс корректен для GSS-вершины h и h.state = w2 .state. Количество
вершин пути Ps равно (s+1), что не превышает k, поэтому по индукционному предположению префикс внутреннего графа, соответствующий пути Ps порождается графом
префиксов h.pref ixes. Значит существует путь R = (R1 , .., Rc , EOP ) в графе префиксов h.pref ixes, где R1 – начальная вершина графа префиксов, такой, что путь R сводится к строке p1 . В GSS, построенном RNGLR-алгоритмом, имеется нетерминальное
ребро e, значит в GSS, построенным основным анализом, имеется нетерминальное
ребро e′ = (v, h), ассоциированное с нетерминалом N , так как h.state = w2 .state и
v.state = w1 .state. Значит в граф префиксов v.pref ixes будет добавлена вершина E ′ ,
ассоциированная с нетерминальным ребром e′ . Среди путей GSS, ассоциированных с
ребром e′ будут также присутствовать пути, аналогичные путям (P1 , .., Pd ) (последовательности состояний вершин GSS в таких путях совпадают, соответствующие ребра
будут иметь одинаковый вид, соответствующие терминальные ребра будут ассоции24
рованы с одинаковыми терминалами, а соответствующие нетерминальные ребра — с
одинаковыми нетерминалами). Так как в GSS, построенном RNGLR-алгоритмом, нет
циклов (кроме циклов, состоящих только из обнуляемых ребер), а количество ребер
конечно, тo из нетерминального ребра e с помощью конечного числа раскрытий можно получить последовательность терминальных ребер, соответствующих строке p2 .
Значит и в GSS, построенном основным анализом, можно с помощью аналогичного
конечного числа раскрытий из ребра e′ , получить последовательность терминальных
ребер, соответствующих строке p2 . Таким образом, в графе префиксов v.pref ixes существует путь (E ′ , R1 , .., Rc , EOP ), который сводится к строке p. Следовательно граф
префиксов v.pref ixes порождает префикс внутреннего графа, соответствующий пути
P.
Если e — обнуляемое ребро, обозначим ef = (wf , wf +1 ) — первое не обнуляемое ребро в пути Q. Префикс внутреннего графа, соответствующий пути P , является корректным для GSS-вершины wf . Граф префиксов wf .pref ixes порождает
префикс внутреннего графа, соответствующий пути P , так как в GSS, построенном
RNGLR-алгоритмом, существует путь из вершины wf , который начинается с терминального или нетерминального ребра, а такие случаи уже рассмотрены. Пусть
(F1 , .., Fg , EOP ) — путь графа префиксов wf .pref ixes, который сводится к строке
p. Тогда ∃(Z1 , .., Zf −1 , F1 , .., Fg , EOP ) — путь графа префиксов w1 .pref ixes, где ∀j ∈
[1, .., (f − 1)], Zj ассоциируется с обнуляемым ребром (wj , wj+1 ). Значит этот путь также сводится к строке p. А так как w1 .state = v.state, то w1 = v. Следовательно граф
префиксов v.pref ixes порождает префикс внутреннего графа, соотвествующий пути
P. □
Для доказательства того, что каждый префикс внутреннего графа, порождаемый
графом префиксов v.pref ixes, является корректным для GSS-вершины v нам понадобится следующая лемма.
ЛЕММА. Пусть GSS-вершина vm корректна для префикса внутреннего графа, соответствующего пути P1 = (V1 , .., Vl ), терминалы на ребрах которого образуют
строку p1 = (t1 , .., tl−1 ) (p1 = ϵ, если l = 1). Пусть ∃Q = (v1 , .., vm ) — путь в GSS,
в котором E = (e1 , .., em−1 ) — последовательность ребер, сводящаяся за конечное
число раскрытий к строке p2 = (tl , .., tl+r−1 ) (p2 = ϵ, если r = 0). Тогда префикс
внутреннего графа, соответствующий пути P = (V1 , .., Vl , Vl+1 , .., Vl+r ) корректен
для GSS-вершины v1 , и терминалы на ребрах пути P образуют строку p = p1 · p2 .
ДОКАЗАТЕЛЬСТВО. Докажем лемму методом математической индукции по длине
строки p2 равной r.
База r = 0 или r = 1. Так как GSS-вершина vm корректна для префикса внутреннего графа, соответствующего пути P , то RNGLR-алгоритм, получив на вход строку
p1 , обработает все терминалы этой строки и на последнем уровне построенного GSS,
создаст вершину wm такую, что wm .state = vm .state.
25
Если r = 0, то строка p2 = ϵ, следовательно ∀i, ei — обнуляемо. Следовательно
∀i, vi ассоциировано с Vl . Таким образом, существует последовательность операций
сверток длины 0, приводящих анализатор из состояния vm .state в состояние v1 .state.
Следовательно в GSS, построенном RNGLR-алгоритмом, в результате применения
аналогичной последовательности операций сверток длины 0, на последнем уровне
будет существовать путь из обнуляемых ребер, начинающийся в GSS-вершине w1 и
заканчивающийся в вершине wm , где w1 .state = v1 .state. Из существования на последнем уровне GSS, построенного RNGLR-алгоритмом, вершины w1 следует, что префикс
внутреннего графа, соответствующий пути P1 также является корректным и для GSSвершины v1 . А так как в данном случае путь P1 равен пути P , то утверждение леммы
при r = 0 доказано.
Если r = 1, то строка p2 — не пустая, а значит среди ребер в последовательности E существует ровно одно не обнуляемое ребро. Пусть j такое, что ej = (vj , vj+1 )
— не обнуляемое ребро последовательности E. Если j = (m − 1), то префикс внутреннего графа, соответствующий пути P1 , корректен для GSS-вершины vj+1 , так как
vj+1 = vm . Если j < (m − 1), то существует путь в GSS из обнуляемых ребер, начинающийся в вершине vj+1 и заканчивающийся в вершине vm . Последовательность
ребер в данном пути сводится к пустой строке. Так как утверждение леммы при r = 0
было доказано, то префикс внутреннего графа, соответствующий пути P1 , является
корректным для GSS-вершины vj+1 . Теперь рассмотрим не обнуляемое ребро ej . Если
ej — терминальное ребро, то оно ассоциировано с терминалом tl . Тогда в управляющих таблицах существует операция сдвига по терминалу tl из состояния vj+1 .state в
состояние vj .state. Значит, RNGLR-алгоритм, обработав строку p1 , может выполнить
операцию сдвига из GSS-вершины с состоянием vj+1 .state в вершину с состоянием
vj .state. Значит префикс внутреннего графа, соответствующий пути (V1 , .., Vl , Vl+1 ),
является корректным для GSS-вершины vj . Если j = 1, то vj = v1 и утверждение
леммы доказано. Пусть j > 1. Последовательность ребер (e1 , .., ej−1 ) за конечное число раскрытий сводится к пустой строке. Так как случай при r = 0 был рассмотрен,
то доказано, что префикс внутреннего графа, соответствующий пути P , корректен
для GSS-вершины v1 . Теперь пусть ej — нетерминальное ребро. Покажем, что префикс внутреннего графа, соответствующий пути P , также является корректным и
для GSS-вершины vj .
Рассмотрим ту конечную последовательность раскрытий, примененную к последовательности ребер E, после которой останется единственное терминальное ребро,
ассоциированное с терминалом tl . Существует два варианта: либо после первого применения операции раскрытия в последовательности останется единственное терминальное ребро eterm = (uterm , vj+1 ), ассоциированное с терминалом tl , либо при применении первых i > 0 операций раскрытия последовательность ребер GSS будет состоять из единственного нетерминального ребра, причем ∀d ∈ [1, .., i], после применения
26
первых d операций раскрытия последовательность состоит из единственного ребра
Sd = (hd , gd ). Первый вариант означает, что префикс внутреннего графа, соответствующий пути P = (V1 , .., Vl , Vl+1 ), является корректным для GSS-вершины uterm . А
так как в GSS, построенным основным анализом, существует ребро ej = (vj , vj+1 ),
ассоциированное с нетерминалом N и с GSS путем, в котором присутствует единственное ребро eterm , то префикс внутреннего графа, соответствующий пути P , также является корректным и для GSS-вершины vj . Рассмотрим второй вариант. Пусть
ej = S0 = (h0 , g0 ), тогда ∀d ∈ [1, .., i], при применении d-ой операции раскрытия нетерминальное ребро Sd−1 заменяется на последовательность ребер, соответствующих одному из порожденных ребром Sd−1 пути, начинающегося в вершине wd и закачивающегося в вершине gd−1 , причем wd , как и vj принадлежит вершине внутреннего графа Vl+1 . Пусть w0 = vj . Так как в данных путях ребро Sd является единственным
не обнуляемым ребром, то ∀d ∈ [1, .., i], существует путь из вершины wd в вершину
hd и существует путь из вершины gd в вершину gd−1 , оба из которых имеют только
обнуляемые ребра. При применении (i + 1)-ой операции раскрытия нетерминальное
ребро Si заменятся на последовательность ребер, соответствующую пути в GSS из
вершины wterm в вершину gi , причем в этом пути единственное не обнуляемое ребро — это терминальное ребро Sterm = (hterm , gterm ), ассоциированное с терминалом
tl . Так как ∀d ∈ [1, .., i], существует путь из вершины gd в вершину gd−1 , состоящий
только из обнуляемых ребер, и существует путь из вершины gterm в вершину gi , состоящий только из обнуляемых ребер, то также существует путь из вершины gterm в
вершину g0 = vj+1 и существует путь из вершины gd в вершину g0 = vj+1 , состоящие
только из обнуляемых ребер. А так как префикс внутреннего графа, соответствующий пути P1 , является корректным для GSS-вершины vj+1 , то префикс внутреннего
графа, соответствующий пути P1 , также является корректным и для GSS-вершин из
множества {g1 , .., gi , gterm }. Так как в GSS, построенным основным анализом, существует терминальное ребро Sterm = (hterm , gterm ), ассоциированное с терминалом tl ,
то префикс внутреннего графа, соответствующий пути P = (V1 , .., Vl , Vl+1 ), является
корректным для GSS-вершины hterm . А так как существует путь из вершины wterm в
вершину hterm , то префикс внутреннего графа, соответствующий пути P , также является корректным и для GSS-вершины wterm . Аналогичным образом доказывается, что
∀d ∈ [0, ..i], префикс внутреннего графа, соответствующий пути P , является корректным для GSS-вершины wd . А так как w0 = vj , то, в частности, префикс внутреннего
графа, соответствующий пути P , является корректным для GSS-вершины vj .
Таким образом показали, что префикс внутреннего графа, соответствующий пути
P , является корректным для GSS-вершины vj . А так как существует путь из вершины
v1 в вершину vj , состоящий из обнуляемых ребер, то из доказательства утверждения
леммы при r = 0 следует, что префикс внутреннего графа, соответствующий пути P ,
также является корректным и для GSS-вершины v1 , что и доказывает утверждение
27
леммы при r = 1. База индукции доказана.
Индукционный переход. Пусть утверждение леммы доказано для всех строк
p2 длины меньшей r. Докажем утверждение леммы для строки p2 длины r > 1.
Так как строка p2 не пустая, то среди ребер в последовательности E существует хотя бы одно не обнуляемое ребро. Пусть j такое, что ej = (vj , vj+1 ) — последнее
не обнуляемое ребро последовательности E. Если j = (m − 1), то префикс внутреннего графа, соответствующий пути P1 , корректен для GSS-вершины vj+1 , так как
vj+1 = vm . Если j < (m − 1), то существует путь в GSS из обнуляемых ребер, начинающийся в вершине vj+1 и заканчивающийся в вершине vm . Последовательность
ребер в данном пути сводится к пустой строке. Значит, по индукционному предположению префикс внутреннего графа, соответствующий пути P1 , является корректным
для GSS-вершины vj+1 . Теперь рассмотрим не обнуляемое ребро ej .
Если ej — терминальное ребро, то оно ассоциировано с терминалом tl . Тогда в
управляющих таблицах существует операция сдвига по терминалу tl из состояния
vj+1 .state в состояние vj .state. Значит, RNGLR-алгоритм, обработав строку p1 , может выполнить операцию сдвига из GSS-вершины с состоянием vj+1 .state в вершину с состоянием vj .state. Значит префикс внутреннего графа, соответствующий пути
(V1 , .., Vl , Vl+1 ), является корректным для GSS-вершины vj . Так как строка p2 имеет
длину r > 1, то j > 1. Последовательность ребер (e1 , .., ej−1 ) за конечное число раскрытий сводится к строке pj = (tl+1 , .., tl+r−1 ). Так как длина строки pj равна (r − 1),
то по индукционному предположению префикс внутреннего графа, соответствующий
пути P , корректен для GSS-вершины v1 . И утверждение леммы доказано.
Если ej — нетерминальное ребро. Тогда рассмотрим два случая.
Первый случай: ∃i ∈ [1, .., (j − 1)], ei — не обнуляемое ребро. Тогда ребро ej в последовательности E после рассматриваемого конечного числа раскрытий сводится
к непустой строке (tl , .., tl+h−1 ), длины h < r. А так как префикс внутреннего графа, соответствующий пути P1 , является корректным для GSS-вершины vj+1 , то, по
индукционному предположению, префикс внутреннего графа, соответствующий пути (V1 , .., Vl , Vl+1 , .., Vl+h ), является корректным для GSS-вершины vj . А так как последовательность ребер (ej−1 , .., e1 ) за конечное число раскрытий сводится к строке
(tl+h , .., tl+r−1 ) длины (r−h) < r, то, по индукционному предположению, префикс внутреннего графа, соответствующий пути P , является корректным для GSS-вершины v1 ,
что и доказывает утверждение леммы.
Второй случай: ∀i ∈ [1, .., (j − 1)], ei — обнуляемое ребро. Покажем, что префикс
внутреннего графа, соответствующий пути P , также является корректным и для GSSвершины vj .
В данном случае ej — единственное не обнуляемое ребро в последовательности
E. Рассмотрим ту конечную последовательность раскрытий, примененную к последовательности ребер E, после которой остаются только терминальные ребра, причем
28
строка, образованная инвертированием этой последовательности терминальных ребер и заменой их на терминалы, с которыми они ассоциированы, является строкой
p2 = (tl , .., tl+r−1 ). Существует два варианта: либо после первого применения операции
раскрытия в последовательности будет более одного не обнуляемого ребра, либо при
применении первых i > 0 операций раскрытия последовательность ребер GSS будет
состоять из единственного нетерминального ребра, причем ∀d ∈ [1, .., i], после применения первых d операций раскрытия последовательность состоит из единственного
ребра Sd = (hd , gd ). Первый вариант означает, что нетерминальное ребро ej ассоциировано с путем F = (x1 , .., xn ), где GSS-вершина x1 , как и вершина vj , принадлежит
вершине внутреннего графа Vl+r , а GSS-вершина xn = vj+1 . Причем в пути F имеется более одного не обнуляемого ребра. Найдем минимальное y такое, что ребро
ef irst = (xy , xy+1 ) является не обнуляемым. Так как в пути F имеется более одного
не обнуляемого ребра, то последовательность ребер F1 = ((x1 , x2 ), .., (xy , xy+1 )), как и
последовательность ребер F2 = ((xy+1 , xy+2 ), .., (xn−1 , xn )) после применения конечного числа раскрытий сводится к строке длины меньшей r. Пусть последовательности
ребер F1 и F2 сводятся за рассматриваемое конечное число раскрытий к строкам
f1 = (tl+c , .., tl+r−1 ) и f2 = (tl , .., tl+c−1 ), где 0 < c < r. Так как xn = vj+1 , то по
индукционному предположению префикс внутреннего графа, соответствующий пути
(V1 , .., Vl+c ), является корректным для GSS-вершины xy+1 . Это, в свою очередь, означает, что префикс внутреннего графа, соответствующий пути P = (V1 , .., Vl+r ), является
корректным для GSS-вершины x1 . А так как в GSS, построенным основным анализом,
существует ребро ej = (vj , vj+1 ), ассоциированное с GSS путем F , то префикс внутреннего графа, соответствующий пути P = (V1 , .., Vl+r ), является также корректным и для
GSS-вершины vj . Рассмотрим второй вариант. Аналогично рассуждениям в базе индукции при r = 1, конструируем множества {S0 , .., Si }, {w0 , .., wi }, {h0 , .., hi }, {g0 , .., gi }.
При применении (i+1)-ой операции раскрытия нетерминальное ребро Si заменятся на
последовательность ребер, соответствующую пути R в GSS из вершины r1 в вершину gi , причем в пути R существует более одного не обнуляемого ребра. GSS-вершина
r1 , как и вершина vj , принадлежит вершине внутреннего графа Vl+r . Применив к
пути R, рассуждения, аналогичные рассуждениям при рассмотрении пути F , получим, что префикс внутреннего графа, соответствующий пути P , является корректным
для любой GSS-вершины из множества {w0 , .., wi , r1 }, а так как w0 = vj , то, в частности, префикс внутреннего графа, соответствующий пути P , является корректным
для GSS-вершины vj .
Таким образом показали, что префикс внутреннего графа, соответствующий пути
P , является корректным для GSS-вершины vj . А так как существует путь из вершины v1 в вершину vj , состоящий из обнуляемых ребер, то по индукционному предположению префикс внутреннего графа, соответствующий пути P , также является
корректным и для GSS-вершины v1 , что и доказывает утверждение леммы. □
29
ТЕОРЕМА 2. Каждый префикс внутреннего графа, соответствующий пути P =
(V1 , .., Vl ) внутреннего графа и порождаемый графом префиксов v.pref ixes, является
корректным для GSS-вершины v.
ДОКАЗАТЕЛЬСТВО. Пусть p — строка, образованная из терминалов на ребрах пути
P . Длина строки p равна (l − 1). Так как префикс внутреннего графа, соответствующий пути P , порождается графом префиксов v.pref ixes, то в этом графе префиксов
существует путь X из одной из начальных вершин графа префиксов v.pref ixes в
вершину EOP , который сводится к строке p.
Если путь X состоит из единственной вершины EOP , то она является начальной вершиной графа префиксов v.pref ixes, а значит v — начальная вершина GSS. А
так как путь X в графе префиксов v.pref ixes сводится к пустой строке, то строка
p — пустая, и путь P состоит из единственной начальной вершины внутреннего графа V1 . Значит префикс внутреннего графа, соответствующий пути P , корректен для
начальной вершины GSS, которой является вершина v.
Пусть путь X = (E1 , .., Em , EOP ), где m > 0 и E1 — одна из начальных вершин графа префиксов v.pref ixes. Из построения графов префиксов следует, что существует
путь из GSS-вершины v в начальную GSS-вершину v0 . Причем последовательность
ребер в данном пути после конечного числа раскрытий сводится к строке p. А так
как префикс внутреннего графа, соответствующий пути F = (V1 ), корректен для начальной GSS-вершины v0 и существует путь из GSS-вершины v в GSS-вершину v0 , в
котором последовательность ребер сводится за конечное число раскрытий к строке
p, то, по ЛЕММЕ, префикс внутреннего графа, соответствующий пути P = (V1 , .., Vl )
является корректным для GSS-вершины v. □
5.2. Корректность алгоритма диагностики ошибок
В данном разделе приведено доказательство того, что любое ребро e внутреннего
графа из множества errors является ошибочными, а все ошибочные ребра принадлежат множеству errors ∪ probErrors. Также будет доказано, что любой префикс
внутреннего графа, порождаемый графом префиксов из множества errors[e], является корректным, но при добавлении к данному префиксу в конец ребра e образуется
некорректный префикс внутреннего графа, а все такие префиксы порождаются хотя
бы одним графом префиксов из множества errors[e] ∪ probErrors[e].
ТЕОРЕМА 3. После работы алгоритма диагностики ошибок любое ребро e внутреннего графа из множества errors является ошибочными. А любой префикс внутреннего графа, порождаемый графом префиксов из множества errors[e], является
корректным, но при добавлении к данному префиксу в конец ребра e образуется
некорректный префикс внутреннего графа.
ДОКАЗАТЕЛЬСТВО. Докажем, что ребро e является ошибочным, методом от про-
30
тивного. Пусть ребро внутреннего графа e ∈ errors не является ошибочным. Пусть
ребро e нагружено терминалом t, исходит из вершины внутреннего графа Vl и входит
в вершину Vl+1 . Обозначим входную эталонную грамматику за G. Рассмотрим два
случая.
Если Vl+1 — не конечная вершина внутреннего графа. Пусть (e1 , .., en ) — терминальные ребра GSS, ассоциированные с терминалом t, причем ∀i ∈ [1, .., n], ei = (xi , yi ),
где xi принадлежит вершине Vl+1 , а yi принадлежит вершине Vl . Пусть GSS-вершина
v, принадлежащая вершине внутреннего графа Vl , принадлежит множеству Z, если ∀i ∈ [1, .., n], v ̸= yi . Так как e ∈ errors, то ∃v ∈ Z — GSS-вершина, такая, что
v.pref ixes порождает некоторый префикс внутреннего графа, который не порождается графом префиксов yi .pref ixes, ∀i ∈ [1, .., n]. Множество всех таких префиксов
внутреннего графа обозначим K. Пусть один из префиксов внутреннего графа множества K соответствует пути P = (V1 , .., Vl ). Пусть p — строка, образованная последовательностью терминалов на пути P . Так как v.pref ixes порождает префикс
внутреннего графа, соответствующий пути P , то, по ТЕОРЕМЕ 2, получаем, что этот
префикс является корректным для GSS-вершины v. Значит строка p является корректным префиксом для грамматики G. Пусть Q — множество GSS-вершин, для которых префикс внутреннего графа, соответствующий пути P , является корректным. Так
как рассматриваемый префикс внутреннего графа не порождается графом префиксов
yi .pref ixes, ∀i ∈ [1, .., n], то, по ТЕОРЕМЕ 1, данный префикс не является корректным
для GSS-вершины yi , ∀i ∈ [1, .., n]. Значит, ∀i ∈ [1, .., n], yi ∈
/ Q. Поэтому ∀q ∈ Q, в
управляющих таблицах не существует операции сдвига из состояния q.state по терминалу t. Значит, RNGLR-алгоритм, обработав все терминалы строки p и получив
следующим терминалом входной строки — терминал t, не сможет сделать ни одной
операции сдвига по данному терминалу. Таким образом, префикс внутреннего графа,
соответствующий пути P = (V1 , .., Vl , Vl+1 ), не является корректным. Значит, ребро e
является ошибочным. Получили противоречие.
Если Vl+1 — конечная вершина внутреннего графа, тогда t является специальным
терминалом EOF конца строки. Пусть A1 — множество GSS-вершин, принадлежащих
вершине Vl , и имеющих принимающее состояние, а A2 — множество GSS-вершин, принадлежащих вершине Vl , и имеющих непринимающее состояние. Так как e ∈ errors,
то существует GSS-вершина v ∈ A2 такая, что граф префиксов v.pref ixes порождает некоторый корректный префикс внутреннего графа, который не порождается ни
одним графом префиксов GSS-вершин из множества A1 . Множество всех таких префиксов внутреннего графа обозначим L. Пусть один из префиксов внутреннего графа
множества L соответствует пути F = (V1 , .., Vl ). Пусть f — строка, образованная последовательностью терминалов на пути F . По ТЕОРЕМЕ 2, данный префикс внутреннего
графа является корректным для GSS-вершины v, так как он порождается графом
префиксов v.pref ixes. Значит, префикс внутреннего графа, соответствующий пути
31
F , является корректным. А так как графы префиксов GSS-вершин из множества A1
не порождают префикс внутреннего графа, соответствующий пути F , то, по ТЕОРЕМЕ 1, рассматриваемый префикс внутреннего графа не является корректным ни
для одной GSS-вершины из множества A1 . Значит, RNGLR-алгоритм, обработав все
терминалы строки f , на последнем уровне GSS не будет иметь ни одной вершины с
принимающим состоянием. Значит, строка f не является принимаемой грамматикой
G. Таким образом, ребро e является ошибочным. Получили противоречие.
В случае, когда Vl+1 не является конечной вершиной внутреннего графа, префикс
внутреннего графа, соответствующий пути P = (V1 , .., Vl ), взят из множества K произвольным образом. Для этого префикса показано, что он является корректным, но при
добавлении к данному префиксу в конец ребра e образуется некорректный префикс
внутреннего графа. Из построения множества графов префиксов errors[e] следует,
что данные графы префиксов порождают префиксы внутреннего графа из множества K и только их. Таким образом, любой префикс внутреннего графа, порождаемый одним из графов префиксов errors[e], является корректным, но при добавлении
к нему в конец ребра e образуется некорректный префикс внутреннего графа. Аналогично, данное утверждение доказывается в случае, если Vl+1 — конечная вершина
внутреннего графа с множеством префиксов внутреннего графа равным L. □
ТЕОРЕМА 4. После работы алгоритма диагностики ошибок любое ошибочное ребро
e внутреннего графа, исходящее из вершины Vl и входящее в вершину Vl+1 , принадлежит объединению множеств errors и probErrors. А любой префикс внутреннего
графа, заканчивающийся в вершине Vl и становящийся некорректным при добавлении в конец ребра e, порождается хотя бы одним графом префиксов из объединения
множеств errors[e] и probErrors[e].
ДОКАЗАТЕЛЬСТВО. Пусть ребро e нагружено терминалом t. Пусть L — множество
всех префиксов внутреннего графа, заканчивающихся в вершине Vl и становящихся
некорректным при добавлении в конец ребра e. Так как ребро e является ошибочным,
то множество L не пусто. Рассмотрим префикс внутреннего графа из множества L.
Пусть этому префиксу соответствует путь внутреннего графа P = (V1 , .., Vl ). Пусть p
— строка, получающаяся заменой в последовательности ребер в пути P на терминалы,
которыми нагружены соответствующие ребра. Так как данный префикс внутреннего
графа является корректным, то существует GSS-вершина v, принадлежащая вершине
внутреннего графа Vl , такая, что рассматриваемый префикс является корректным для
вершины v. По ТЕОРЕМЕ 1, данный префикс внутреннего графа порождается графом
префиксов v.pref ixes. Обозначим G — входная эталонная грамматика. Рассмотрим
два случая.
Если Vl+1 — не конечная вершина внутреннего графа. Пусть (e1 , .., en ) — терминальные ребра GSS, ассоциированные с терминалом t, причем ∀i ∈ [1, .., n], ei = (xi , yi ),
где xi принадлежит вершине Vl+1 , а yi принадлежит вершине Vl . Пусть GSS-вершина
32
u, принадлежащая вершине внутреннего графа Vl , принадлежит множеству Z, если
∀i ∈ [1, .., n], u ̸= yi . Так как один из префиксов, порождаемых графом префиксов
v.pref ixes, становится некорректным при добавлении в конец ребра e, то v ∈ Z. Если
граф префиксов v.pref ixes имеет цикл, то ребро e ∈ probErrors, а префикс внутреннего графа, соответствующий пути P , порождается одним из графов префиксов
множества probErrors[e]. Пусть граф префиксов v.pref ixes не имеет циклов. В виду того, что рассматриваемый префикс внутреннего графа становится некорректным
при добавлении в конец ребра e, то ∀i ∈ [1, .., n], yi .pref ixes не порождает данный
префикс. Если ∃i ∈ [1, .., n] такое, что граф префиксов yi .pref ixes имеет цикл, то
e ∈ probErrors, а префикс внутреннего графа, соответствующий пути P , порождается одним из графов префиксов множества probErrors[e]. Если такого i не существует,
то e ∈ errors, а префикс внутреннего графа, соответствующий пути P , порождается
одним из графов префиксов множества errors[e]. Таким образом, в данном случае,
e ∈ errors ∪ probErrors, а префикс внутреннего графа, соответствующий пути P ,
порождается одним из графов префиксов множества errors[e] ∪ probErrors[e].
Если Vl+1 — конечная вершина внутреннего графа, тогда t является специальным
терминалом EOF конца строки. Пусть A1 — множество GSS-вершин, принадлежащих вершине Vl , и имеющих принимающее состояние, а A2 — множество GSS-вершин,
принадлежащих вершине Vl , и имеющих непринимающее состояние. Так как один из
префиксов, порождаемых графом префиксов v.pref ixes, становится некорректным
при добавлении в конец ребра e, то v ∈ A2 . Если граф префиксов v.pref ixes имеет цикл, то ребро e ∈ probErrors, а префикс внутреннего графа, соответствующий
пути P , порождается одним из графов префиксов множества probErrors[e]. Пусть
граф префиксов v.pref ixes не имеет циклов. Ввиду того, что рассматриваемый префикс внутреннего графа становится некорректным при добавлении в конец ребра e,
то ∀z ∈ A1 , z.pref ixes не порождает данный префикс. Если ∃z ∈ A1 такое, что граф
префиксов z.pref ixes имеет цикл, то e ∈ probErrors, а префикс внутреннего графа, соответствующий пути P , порождается одним из графов префиксов множества
probErrors[e]. Если такого z не существует, то e ∈ errors, а префикс внутреннего графа, соответствующий пути P , порождается одним из графов префиксов множества
errors[e].
Таким образом, во всех случаях, e ∈ errors ∪ probErrors, а префикс внутреннего
графа, соответствующий пути P , порождается одним из графов префиксов множества errors[e] ∪ probErrors[e]. Так как префикс внутреннего графа, соответствующий
пути P , выбирался из множества L произвольным образом, то утверждение теоремы
доказано. □
33
6. Экспериментальное исследование
Предложенный механизм диагностики ошибок был реализован на платформе .NET
как часть проекта YaccConstructor; основным языком разработки являлся F# [17].
Данная реализация является модификацией ранее реализованного в рамках проекта
алгоритма ослабленного синтаксического анализа регулярной аппроксимации динамически формируемого выражения.
Модифицированный алгоритм был протестирован на серии тестов с целью проверки работоспособности. Данные тесты проверяли, что алгоритм строит корректные
множества errors и probErros ребер входного графа. Для каждого теста специфицировалась грамматика на языке YARD и в явном виде задавался граф конечного автомата, ребра которого были промаркированы лексемами входной грамматики.
Входные графы для данных тестов содержали как ветвления, так и циклы. На всех
тестах модифицированный алгоритм корректно строил множества errors и probErros.
Кроме того, на всех тестах, входные графы которых не содержали циклов, модифицированный алгоритм точно определял все ошибочные ребра входного графа, то есть
probErros, в данном случае, являлось пустым множеством.
Также на нескольких сериях синтетических тестов была протестирована производительность модифицированного алгоритма. Анализ промышленного проекта по
миграции базы данных с MS-SQL Server 2005 на Oracle 11gR2 показал, что запросы
часто формируются конкатенацией фрагментов, каждый из которых формируется с
помощью ветвлений или циклов. Ниже приведена входная грамматика, использованная в данных тестах.
start_rule ::= s
s ::= s PLUS n
n ::= ONE | TWO | THREE | FOUR | FIVE | SIX | SEVEN
Входные графы представляли собой конкатенацию базовых блоков без циклов. Каждая серия тестов характеризовалась тремя параметрами:
• height — количество ветвлений в базовом блоке;
• length — максимальное количество повторений базовых блоков;
• errorBranches — количество веток в базовом блоке, содержащих ошибочное ребро (на рис. 2 изображен базовый блок без ошибочных ребер, а на рис. 3 — базовый
блок с двумя выделенными ошибочными ребрами).
Замеры времени работы алгоритмов проводились на машине со следующими техническими характеристиками: Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz, RAM:
8.0 GB, процессор x64.
34
ONE
0
FIVE
1
PLUS
2
TWO
THREE
3
4
PLUS
PLUS
PLUS
6
SEVEN
7
PLUS
8
5
Рис. 2: Базовый блок при height = 3, errorBranches = 0
ONE
0
FIVE
1
PLUS
2
TWO
THREE
3
4
ONE
TWO
PLUS
6
SEVEN
7
PLUS
8
5
Рис. 3: Базовый блок при height = 3, errorBranches = 2
Каждая серия объединяет набор из 50 тестов, каждый из которых содержит одинаковое количество ветвлений в базовом блоке, при этом количество повторений блока совпадает с порядковым номером теста (length = i, для теста с номером i). Для
каждого теста измерялось время, затраченное на синтаксический анализ. Измерения
проводились 10 раз, после чего усреднялись. График, представленный на рис. 4, иллюстрирует сравнение времени работы алгоритма синтаксического анализа до и после
модификаций. Можно заметить, что выполненная модификация существенно увеличивает продолжительность анализа. Причина этого в том, что выполненная модификация является прототипом, а в будущем планируется улучшить производительность
путем улучшения реализации. График на рис. 5 демонстрирует зависимость времени работы модифицированного алгоритма от количества повторений базового блока
и количества веток, содержащих ошибочное ребро, в каждом из них. Наблюдается
уменьшение времени работы модифицированного алгоритма при увеличении количества ошибочных ребер. Одной из причин этого является уменьшение количества
корректных префиксов внутреннего графа при увеличении количества ошибочных
ребер.
35
Рис. 4: Сравнение времени работы алгоритма синтаксического анализа до и после
модификаций, при height = 4, errors = 0
Рис. 5: Зависимость времени работы модифицированного алгоритма от размера входного графа и количества ошибочных ребер при height = 6
36
7. Заключение
В ходе данной работы получены следующие результаты.
• Определено понятие синтаксической ошибки в терминах регулярной аппроксимации динамически формируемого выражения.
• Разработан механизм диагностики ошибок в синтаксическом анализе регулярной
аппроксимации динамически формируемого выражения.
• Доказана корректность предложенного механизма.
• Предложенный механизм реализован на языке программирования F# в рамках
проекта YaccConstructor.
• Проведено экспериментальное исследование: тестирование работоспособности и
тестирование производительности.
• Исходный код проекта YaccConstructor можно найти на сайте https://github.
com/YaccConstructor/YaccConstructor, автор принимал участие под учётной
записью rustam-azimov.
В дальнейшем планируется использовать результат работы модифицированного
алгоритма синтаксического анализа для формирования сообщений об обнаруженных
ошибках, удобных для пользователя. Кроме того, необходимо произвести теоретическую оценку сложности модифицированного алгоритма.
37
Список литературы
[1] Alvor [Электронный ресурс]. –– URL: https://bitbucket.org/plas/alvor (дата
обращения: 18.05.2016).
[2] Annamaa A., Breslav A., Vene V. Using Abstract Lexical Analysis and Parsing to
Detect Errors in String-Embedded DSL Statements // Proceedings of the 22nd Nordic
Workshop on Programming Theory. –– 2010. –– P. 20–22.
[3] Asveld P. R. J., Nijholt A. The Inclusion Problem for Some Subclasses of Contextfree Languages. –– Vol. 230. –– Essex, UK : Elsevier Science Publishers Ltd., 1999. ––
December. –– P. 247–256.
[4] Automata-based Symbolic String Analysis for Vulnerability Detection / F. Yu,
M. Alkhalaf, T. Bultan, O. H. Ibarra // Form. Methods Syst. Des. –– 2014. –– Vol. 44,
no. 1. –– P. 44–70.
[5] Christensen A. S., Møller A., Schwartzbach M. I. Precise Analysis of String
Expressions // Proc. 10th International Static Analysis Symposium (SAS). ––
Vol. 2694 of LNCS. –– Springer-Verlag, 2003. –– P. 1–18.
[6] Dick G., Ceriel H. Parsing Techniques: A Practical Guide. –– Upper Saddle River, NJ,
USA : Ellis Horwood, 1990. –– ISBN: 0-13-651431-6.
[7] IntelliLang [Электронный ресурс]. –– URL: https://www.jetbrains.com/idea/
help/intellilang.html (дата обращения: 18.05.2016).
[8] An Interactive Tool for Analyzing Embedded SQL Queries / A. Annamaa, A. Breslav,
J. Kabanov, V. Vene // Proceedings of the 8th Asian Conference on Programming
Languages and Systems. –– APLAS’10. –– Berlin, Heidelberg : Springer-Verlag, 2010. ––
P. 131–138.
[9] Java String Analyzer [Электронный ресурс]. –– URL: http://www.brics.dk/JSA/
(дата обращения: 18.05.2016).
[10] Khabibullin M., Ivanov A., Grigorev S. On Development of Static Analysis
Tools for String-Embedded Languages. –– 2015. –– URL: https://github.com/
YaccConstructor/articles/blob/master/2015/SECR/paper/Main.pdf
(online;
accessed: 18.05.2016).
[11] Kirilenko I., Grigorev S., Avdiukhin D. Syntax Analyzers Development in Automated
Reengineering of Informational System // St. Petersburg State Polytechnical
University Journal. Computer Science. Telecommunications and Control Systems. ––
2013. –– Vol. 174, no. 3. –– P. 94–98.
38
[12] Minamide Y. Static Approximation of Dynamically Generated Web Pages //
Proceedings of the 14th International Conference on World Wide Web. –– WWW
’05. –– New York, NY, USA : ACM, 2005. –– P. 432–441.
[13] Nguyen H. V., Kästner C., Nguyen T. N. Varis: IDE Support for Embedded Client
Code in PHP Web Applications // Proceedings of the 37th International Conference
on Software Engineering (ICSE). –– New York, NY : ACM Press, 2015. –– Formal
Demonstration paper.
[14] PHPStorm IDE [Электронный ресурс]. –– URL: https://www.jetbrains.com/
phpstorm/ (дата обращения: 18.05.2016).
[15] Rekers J. Parser Generation for Interactive Environments. –– 1992.
[16] Scott E., Johnstone A. Right Nulled GLR Parsers // ACM Trans. Program. Lang.
Syst. –– 2006. –– Vol. 28, no. 4. –– P. 577–618.
[17] Syme Don, Granicz Adam, Cisternino Antonio. Expert F# (Expert’s Voice in .Net). ––
ISBN: 1590598504, 9781590598504.
[18] Tomita M. An Efficient Context-free Parsing Algorithm for Natural Languages //
Proceedings of the 9th International Joint Conference on Artificial Intelligence Volume 2. –– IJCAI’85. –– San Francisco, CA, USA : Morgan Kaufmann Publishers
Inc., 1985. –– P. 756–764.
[19] Verbitskaia E., Grigorev S., Avdyukhin D. Relaxed Parsing of Regular Approximations
of String-Embedded Languages // Preliminary Proceedings of the PSI 2015: 10th
International Andrei Ershov Memorial Conference. –– PSI’15. –– 2015. –– P. 1–12.
[20] Вербицкая Е. А. Синтаксический анализ регулярных множеств : Квалификационная работа магистра / Е. А. Вербицкая ; Санкт-Петербургский государственный университет. –– 2015.
[21] Григорьев C. В. Синтаксический анализ динамически формируемых программ :
Дисс… кандидата наук / C. В. Григорьев ; Санкт-Петербургский государственный университет. –– 2015.
39
Отзывы:
Авторизуйтесь, чтобы оставить отзыв