Диссертация (1150733), страница 9
Текст из файла (страница 9)
Такжесформулированы и доказаны утверждения о корректности данного алгоритма.2.1Постановка задачиАнализируемая программа является генератором выражений и таким образом задаёт некоторый язык 1 . Предположим, что взаимодействует с базойданных с помощью динамически формируемых выражений. В этом случае мыговорим, что использует динамический SQL, подразумевая, что программойгенерируются выражения на языке SQL.
Однако это не совсем корректно, так какпрограмма может, например, содержать ошибку и некоторые из построенных ейвыражений не будут корректными SQL-выражениями. Кроме того, программа может генерировать не все возможные выражения на SQL. Таким образом,1 ̸= SQL.С другой стороны, может быть задан эталонный язык 2 , которому должны принадлежать все выражения, генерируемые программой . Как правило 245описывается с помощью контекстно-свободной грамматики.
Например, это может быть грамматика конкретного диалекта SQL.В результате мы имеем описание двух языков, и задача проверки корректности выражений, генерируемых , может быть сформулирована как проверкавложенности языка 1 в язык 2 . Однако в рамках данной работы нас интересует не просто вложенность языков, а построение деревьев вывода. Как ужеговорилось, язык 2 может быть задан с помощью грамматики.
Пусть заданаграмматика такая, что 2 = (). Тогда задача синтаксического анализа динамически формируемых выражений может быть сформулирована следующимобразом: для всех цепочек ∈ 1 , выводимых в грамматике , необходимопостроить соответствующие деревья вывода.Отметим, что решение изложенных выше вопросов в общем виде возможно не всегда. Трудности могут быть связаны прежде всего с классами рассматриваемых языков.
Эталонный язык 2 , скорее всего, является некоторым языком программирования и принадлежит к классу контекстно-свободных языков(хотя могут быть и исключения). Генерируемый язык 1 не обязан быть дажеконтекстно-зависимым. Так как программа-генератор реализована на тьюрингполном языке, то 1 в общем случае может быть рекурсивно-перечислимым.Из практических соображений можно предположить, что 1 является подмножеством некоторого языка программирования и может быть достаточно хорошоприближен некоторым контекстно-свободным языком. Однако проверка включения двух контекстно-свободных языков не разрешима в общем случае [63]. Приэтом разрешимой является проверка включения регулярного языка в однозначный контекстно-свободный [63].
В однозначные контекстно-свободные языкипопадают такие практически значимые классы, как LR(k) и LL(k), что позволяет использовать в качестве 2 практически значимые языки. При этом для 1необходимо строить регулярное приближение .Для того, чтобы обеспечить надёжность анализа строковых выражений, необходима аппроксимация сверху, то есть должно выполняться включение 1 ⊆ .Это необходимо для того, чтобы не потерять информацию об анализируемомязыке. Например, при работе со встроенным SQL безопаснее считать таблицуиспользуемой, чем удалить её как неиспользуемую, если она на самом деле использовалась. При этом необходимо следить за точностью такой аппроксимации,46чтобы избегать слишком большого количества ошибок. В работе [55] показано,как можно строить подходящую регулярную аппроксимацию сверху с учётомстроковых операций и циклов.Таким образом далее мы будем предполагать, что язык 2 является однозначным контекстно-свободным и задан некоторой грамматикой , а для языка 1строится регулярный язык такой, что 1 ⊆ и мы работает далее с .При этом основной нашей задачей является построение деревьев разбора длявсех цепочек из , корректных относительно грамматики .
Однако можетбыть бесконечным языком и, следовательно, содержать бесконечное множествокорректных цепочек. По этой причине явное построение всех деревьев разбора не представляется возможным. Решением может являться структура данных,которая при конечном объёме будет хранить бесконечное количество деревьев.При этом деревья должны однозначно извлекаться из этой структуры. То есть изпостроенной структуры можно получить только те и только те деревья, которыесоответствуют разбору какой-либо корректной цепочки из языка в эталоннойграмматике .Регулярный язык может быть представлен в виде конечного автомата.Заметим, что аппроксимация, построенная непосредственно по исходному коду, будет являться конечным автоматом 1 = (1 ,Σ1 ,1 ,01 ,1 ) над алфавитомсимволов, что не очень удобно для проведения синтаксического анализа, таккак грамматика = ⟨, , , ⟩ задана, скорее всего, над алфавитом токенови Σ1 * .
Чтобы устранить эту проблему, можно воспользоваться конечнымпреобразователем, который предназначен для трансформации языков. Таким образом, можно получить конечный автомат 2 = (2 ,Σ2 ,2 ,02 ,2 ) такой, чтоΣ2 ⊆ . Преобразование конечного автомата над алфавитом символов в конечный автомат над алфавитом токенов называется лексическим анализом регулярной аппроксимации или встроенного языка.Заметим так же, что без потери общности можно считать, что 2 являетсядетерминированным конечным автоматом без -переходов, так как любой конечный автомат можно преобразовать к эквивалентному детерминированному без-переходов.Сформулируем задачу синтаксического анализа динамически формируемыхвыражений образом.
Для заданной однозначной контекстно-свободной грам-47матики = ⟨, , , ⟩ и детерминированного конечного автомата без переходов = (,Σ,,0 , ) такого, что Σ ⊆ , необходимо построить конечную структуру данных , содержащую деревья вывода в всех цепочек ∈ ( ), корректных относительно грамматики и не содержащую другихдеревьев. Иными словами, необходимо построить алгоритм P такой, что(∀ ∈ ( ))( ∈ () ⇒ (∃ ∈ P(( ),)) (, , ))∧(∀ ∈ P(( ),))(∃ ∈ ( )) (,,).Здесь (,,) — это предикат, который истинен, если является деревомвывода в грамматике .Так как P игнорирует ошибки, то будем называть его алгоритмом ослабленного (relaxed) синтаксического анализа регулярной аппроксимации динамическиформируемого выражения.2.2Описание алгоритмаАлгоритм принимает на вход эталонную однозначную контекстно-свободнуюграмматику = ⟨, , , ⟩ над алфавитом терминальных символов и детерминированный конечный автомат (,Σ,,0 , ), имеющий одно стартовое состояние 0 , одно конечное состояние , и не содержит -переходов, где Σ ⊆ —алфавит входных символов, — множество состояний, — отношение перехода.По описанию грамматики генерируются управляющие RNGLR-таблицы и некоторая вспомогательная информация (называемая в псевдокоде, см.листинг 11).Алгоритм производит обход графа входного автомата и последовательностроит стек в виде GSS подобно тому, как это делается RNGLR-алгоритме.
Однако так как мы имеем дело с графом вместо линейного потока, понятие следующего символа трансформируется во множество терминальных символов,лежащих на всех исходящих рёбрах данной вершины, что изменяет операцииshift и reduce (смотри строку 5 в алгоритме 12 и строки 9 и 21 в алгоритме 13).Для того, чтобы управлять порядком обработки вершин входного графа, мы используем глобальную очередь . Каждый раз, когда добавляется новая вершина481:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:function PARSE(, )ℎ ← construct inner graph representation of ← generate RNGLR parse tables for if ℎ contains no edges thenif accepts empty input then report successelse report failureelseADD V ERTEX (ℎ. , ).(ℎ.
)while is not empty do ← .()MAKE R EDUCTIONS ()PUSH ()APPLY PASSING R EDUCTIONS ()if ∃ : . = and . is accepting then report successelse report failureЛистинг 11: Алгоритм ослабленного синтаксического анализа регулярнойаппроксимации динамически формируемого выраженияв GSS, сначала необходимо произвести все свёртки длины 0, и после этого выполнить сдвиг следующих токенов входного потока. Таким образом необходимодобавить соответствующую вершину графа в очередь на обработку. Добавлениенового ребра в GSS может порождать новые свёртки, таким образом в очередьна обработку необходимо добавить вершину входного графа, которой соответствует начальная вершина добавленного ребра. Детальное описание процессапостроения GSS приведено в листинге 11. Свёртки производятся вдоль путей вGSS, и если было добавлено ребро, начальная вершина которого ранее присутствовала в GSS, необходимо заново вычислить проходящие через эту вершинусвертки (смотри функцию applyPassingReductions в листинге 12).Так же как и RNGLR, мы ассоциируем вершины GSS с позициями входного графа, однако в нашем случае уровень вершины — это состояние входногоавтомата.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
