Особенности синтаксического анализа открытых интерфейсных контекстно-свободных языков тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Лапшин, Владимир Анатольевич

• Лапшин, Владимир Анатольевич
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Лапшин, Владимир Анатольевич

ВВЕДЕНИЕ.

Мотивация.

Обзор алгоритмов синтаксического анализа, применимых к любой контекстносвободной грамматике.

Свойства контекстно-свободной грамматики, важные для алгоритмов синтаксического анализа.

Цели диссертационной работы.

Результаты и апробация работы.

Научная новизна.

Структура работы.

ГЛАВА 1. АДАПТИРОВАННЫЙ ДЛЯ ПОСТРОЕНИЯ ДЕРЕВЬЕВ ВЫВОДА АЛГОРИТМ ЭРЛИ.

1.1 Введение.

1.2 Адаптированный для построения деревьев вывода алгоритм Эрли.

1.3 Алгоритм построения множества деревьев вывода входной строки по результатам работы адаптированного алгоритма Эрли.

ГЛАВА 2. ВЫБОР АЛГОРИТМА СИНТАКСИЧЕСКОГО АНАЛИЗА.

2.1 Введение.

2.1 Оценка вычислительной сложности адаптированного для построения деревьев вывода алгоритма Эрли.

2.2 Оценка вычислительной сложности алгоритма обхода деревьев, построенных в результате исполнения адаптированного алгоритма Эрли.

2.3 Оценка вычислительной сложности семейства алгоритмов Кока-Янгера-Касами.

ГЛАВА 3. РЕАЛИЗАЦИЯ РАЗБОРЩИКА.

3.1 Введение.

3.2 Реализация синтаксического анализатора.

3.2.1 Интерфейс модуля синтаксического анализатора.

3.2.2 Организация взаимодействия между модулями синтаксического анализатора.

3.3 Реализация лексического анализатора

3.3.1 Интерфейс модуля лексического анализатора.

3.3.2 Лексический тип как регулярный язык.

3.3.3 Лексический тип как детерминированный конечный автомат.

3.3.4 Алгоритм лексического анализа на основе лексических типов.

3.4 Особенности реализации семантических действий.

Введение диссертации (часть автореферата) на тему «Особенности синтаксического анализа открытых интерфейсных контекстно-свободных языков»

ГЛАВА 1. АДАПТИРОВАННЫЙ ДЛЯ ПОСТРОЕНИЯ ДЕРЕВЬЕВ ВЫВОДА АЛГОРИТМ ЭРЛИ.22

ГЛАВА 2. ВЫБОР АЛГОРИТМА СИНТАКСИЧЕСКОГО АНАЛИЗА.60

ГЛАВА 3. РЕАЛИЗАЦИЯ РАЗБОРЩИКА.97

Рис. 3-1. Типичная схема реализации разборщика.97

Рис. 3-2. Интерфейс модуля синтаксического анализатора.103

Рис. 3-3. Интерфейс объекта Grammar.105

Рис. 3-4. Интерфейс лексического анализатора.107

Рис. 3-5. Алгоритм преобразования регулярного выражения в минимизированный

ДКА.120

Рис. 3-6. Определение объекта минимизированного ДКА.121

ЗАКЛЮЧЕНИЕ.133

ЛИТЕРАТУРА.136

Введение Мотивация

В последнее время большое значение приобрела задача построения синтаксических анализаторов для, так называемых, открытых контекстно-свободных языков, т.е. языков, задаваемых контекстно-свободной грамматикой, которая может быть расширена путем добавления новых сущностей, таких как нетерминальные и терминальные символы, а также правила грамматики. И расширение это может быть произведено произвольно между исполнениями алгоритма синтаксического анализа. Подобная ситуация часто встречается в языках интерфейса к системам представления знаний (см., например [5-7]). В этом случае, алгоритм синтаксического анализа помогает системе «понять» команды пользователя. Таким образом, имеет смысл говорить об открытых интерфейсных языках, или об интерфейсных языках открытого типа. Такие языки и, следовательно, определяющие их контекстно-свободные грамматики, имеют следующие особенности:

1. В силу того, что язык является интерфейсным, входная терминальная строка для алгоритма синтаксического анализа имеет сравнительно небольшую длину.

2. В силу открытости языка и алгоритмической неразрешимости задачи распознавания является ли данная КС-грамматика однозначной или нет, никакие ограничения на входную КС-грамматику наложить невозможно.

3. В силу возможности расширения интерфейсного языка новыми сущностями, входная, для алгоритма синтаксического анализа, КС-грамматика часто имеет очень большое число сущностей по сравнению с длиной входной строки.

Синтаксический анализатор можно представить как вычислимую функцию Parse двух аргументов:

• КС-грамматики G = {N,T,P,S}, где N - нетерминальные символы языка, Т - терминалы, Р - правила языка и S - стартовый нетерминальный символ грамматики. ,

• Входной строки со = av.an длины \со\ - п, где at е Т \ < i < п.

Функция Parse производит построение и выдает в качестве результата множество деревьев вывода TrGa (или единственное дерево, если грамматика G однозначная) входной строки со в грамматике G, если она принадлежит языку L(G), заданному грамматикой G, или false - в противном случае.

В традиционной задаче построения синтаксического анализатора, см. например [2] (в дальнейшем мы будем следовать терминологии, введенной в данной книге), при вызовах функции Parse меняется только один параметр -входная строка со. Функция Parse в этом случае имеет вид ParseG(co). Поэтому анализ производительности естественно было представлять как оценку функции EvG(n), где п - длина входной цепочки со, т.е. как зависимость производительности алгоритма от длины входной строки. Так как для данной контекстно-свободной грамматики G = {N,T,P,S} может существовать много различных строк длины п, то мы разбиваем множество терминальных строк Т+ на классы «у" равных по длине строк. Каждый такой класс со" терминальных строк длины |й>| = и и представляется числом п .

Функция EvG{ri), определенная на множестве натуральных чисел N+, берет п в качестве параметра и выдает максимальное время анализа, выраженное в элементарных операциях, которые алгоритм анализа производит над сущностями грамматики G.

Главной целью данной работы является выяснение особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков. Эти особенности, очевидно, определяются свойствами языков, для которых производится синтаксический анализ. Эти свойства, в свою очередь, должны проявляться в особенностях грамматик, задающих данные языки. Выше мы перечислили основные особые свойства открытых интерфейсных языков и задающих их контекстно-свободных грамматик. Но этого недостаточно, необходимо строго определить параметры грамматики, определяющей открытый интерфейсный язык, и имеющие влияние на производительность алгоритма синтаксического анализа. Такие параметры мы определим немного позже, это объем грамматики, ее ветвистость и протяженность. Сейчас же нас интересует вопрос, каким образом можно выразить степень влияния этих параметров на алгоритм синтаксического анализа? Наиболее естественным представляется выразить степень влияния в параметрах вычислительной сложности алгоритма синтаксического анализа, что мы и сделаем. Итак, для выяснения степени влияния особенностей открытого интерфейсного языка на алгоритм синтаксического анализа, мы произведем исследование вычислительной сложности алгоритма определенной выше вычислимой функции Parse. Для того, чтобы не отвлекаться на несущественные детали, мы зафиксируем второй параметр функции Parse - входную строку т = ах.ап. Поэтому функция Parse [G, со), от двух параметров, примет вид Parseот единственного параметра входной контекстно-свободной грамматики G .

Таким образом, оказывается, что для выяснения особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков, нам необходимо произвести оценку вычислительной сложности каждого алгоритма синтаксического анализа, который мы собираемся использовать для анализа открытых интерфейсных языков. Для этого, сначала мы попытаемся выяснить, какие из известных в настоящее время алгоритмов синтаксического анализа подходят для анализа открытых интерфейсных языков, затем выберем из них наиболее подходящий и попытаемся адаптировать его так, чтобы новый полученный алгоритм являлся, по возможности, наиболее оптимальным для синтаксического анализа открытых интерфейсных языков. На основании проведенной в данной работе оценки было выбрано два алгоритма: алгоритм Эрли [44, 45] и алгоритм Кока-Янгера-Касами [47, 56]. Для использования алгоритма Кока-Янгера-Касами необходимо привлечь еще несколько алгоритмов, поэтому в данной работе мы привели пять алгоритмов семейства алгоритма Кока-Янгера-Касами и провели оценку их вычислительной сложности в терминах описанных выше параметров входной грамматики.

Особая ситуация возникла с алгоритмом Эрли. Данный алгоритм не строит деревьев вывода входной строки, но дает ответ лишь на вопрос выводится или нет данная входная строка в данной грамматике. Нам же необходимо произвести построение всех деревьев вывода данной строки. Для этого мы строим модификацию алгоритма Эрли таким образом, чтобы он производил построение всех деревьев вывода входной строки во время своего исполнения. Заметим сразу, что эта задача достаточно трудна, и особенно, для неоднозначных грамматик. Достаточно отметить, что в разные годы ее пытались решить разные исследователи. Например, в начале 80-х годов Масари Томита пытался решить проблему построения всех деревьев вывода входной строки для неоднозначных грамматик, задающих естественные языки. Это ему не удалось, поэтому Томита произвел модификацию известного алгоритма Li? (А:)-анализа [48]. Данная модификация теперь известна как алгоритм Томиты или алгоритм GLR [54, 55]. Известные в данное время реализации алгоритма Эрли [44, 45] производят построения дерева вывода входной строки только для однозначных грамматик. В данной работе представлена модификация алгоритма Эрли, позволяющая строить все деревья вывода входной строки. Данная модификация названа адаптированным для построения деревьев вывода алгоритмом Эрли. В работе также произведена оценка вычислительной сложности функции Parseа (G), реализованной посредством адаптированного алгоритма Эрли, в терминах упоминавшихся выше параметров входной грамматики.

Обзор алгоритмов синтаксического анализа, применимых к любой контекстно-свободной грамматике

Как уже говорилось выше, особенности грамматики открытых языков не позволяют применять к ним алгоритмы синтаксического анализа, требующие ограничений на структуру входной для функции Parse грамматики G. Следовательно, мы рассмотрим только алгоритмы, применимые для анализа языков, задаваемых любой КС-грамматикой без каких-либо ограничений.

Так как исходная КС-грамматика может меняться от одного исполнения алгоритма синтаксического анализа к другому, необходимо минимизировать расходы на дополнительные действия, которые часто производятся в синтаксических анализаторах еще до исполнения самого алгоритма синтаксического анализа. При анализе языков, задаваемых фиксированной КС-грамматикой, часто бывает удобно, еще до исполнения алгоритма синтаксического анализа, выделить из исходной грамматики некоторую информацию, с тем, чтобы не генерировать ее заново каждый раз при очередном исполнении алгоритма синтаксического анализа. Такую модель синтаксического анализа можно назвать статической моделью (СМ). При анализе нерасширяемых языков время, затрачиваемое на выделение подобной информации из входной КС-грамматики, не учитывается, ввиду того, что такая информация выделяется только один раз. В нашем случае, ввиду того, что входная КС-грамматика может меняться от одного запуска синтаксического анализатора к другому, это время учитывать необходимо. Если это время велико по отношению со временем работы синтаксического анализатора, то такой метод для наших целей неприемлем. Будем называть модель синтаксического анализа, в которой никакой информации о языке до исполнения алгоритма синтаксического анализа не выделяется, динамической моделью (ДМ). Далее мы проанализируем известные алгоритмы синтаксического анализа и оценим их сложность, используя описанные выше критерии. Целью данной работы является построение наиболее эффективного алгоритма синтаксического анализа с переменной входной грамматикой.

Среди известных методов синтаксического анализа, применимых для анализа произвольной контекстно-свободной грамматики, можно выделить следующие алгоритмы:

• Нисходящий синтаксический анализатор с возвратами [2, с. 325]. В процессе построения разбора обычно заменяется крайний левый нетерминал, что ведет к построению левого разбора. Но в этом случае анализатор может работать некорректно для леворекурсивных грамматик. Если же наложить ограничения на длину магазина, в котором записывается текущий разбор, и, таким образом, приспособить данный метод для работы с КС-грамматиками без ограничений, то данное затруднение можно преодолеть. Однако существуют грамматики, для которых данный модифицированный анализатор будет работать слишком неэффективно. Известно, кроме того, что производительность данного метода невысока по сравнению с табличными алгоритмами синтаксического анализа, поэтому его мы оценивать не будем.

• Восходящий синтаксический анализатор с возвратами [2, с. 338]. Почти все, что говорилось выше о предыдущем методе, можно сказать и о данном. Так же как и предыдущий алгоритм, он может работать некорректно для некоторых типов грамматик, и попытки адаптации алгоритма к работе с КС-грамматиками без ограничений ведут к замедлению работы алгоритма. Кроме того, производительность работы алгоритма невысока по сравнению с табличными методами. Таким образом, мы не будем оценивать данный алгоритм на основании приведенных выше аргументов.

• Алгоритм Кока-Янгера-Касами [47, 56]. Данный алгоритм работает только с КС-грамматиками специального вида, то есть находящимися в так называемой нормальной форме Хомского. Но данное ограничение не является фундаментальным, так как известно (см. например [2, с. 176]), что любая КС-грамматика может быть преобразована в данную форму. Конечно, такое преобразование имеет свои неудобства, так как преобразованная грамматика, хотя и эквивалентна исходной, все же имеет другой набор правил и, таким образом, не всегда понятна пользователю. Мы приведем оценку вычислительной сложности данного алгоритма как функции от объема входной грамматики во второй главе.

• Алгоритм Томиты [54, 55]. Данный алгоритм является развитием LR(k) анализатора [2, с. 423], в котором, в случае возникновения конфликтов в детерминированном конечном автомате (ДКА), построенным в соответствии с данным методом синтаксического анализа, применяются параллельно несколько магазинов. Чтобы оптимизировать хранение состояний и символов грамматики в магазинах, в алгоритме Томиты используется так называемый Магазин, структурированный с помощью графа (МСГ). В [55] Томита представил несколько алгоритмов построения МСГ в процессе синтаксического анализа. Но ни один из них не работал корректно для всех типов КС-грамматик без ограничений. Однако, в [52] был предложен метод модификации исходного ДКА таким образом, чтобы один из алгоритмов Томиты производил корректный разбор входной терминальной строки. Но, необходимость построения ДКА для LR(k) анализатора перед исполнением алгоритма делает сомнительным использование данного алгоритма в наших целях. Можно сказать, что модель синтаксического анализатора для данного метода является статической и время, необходимое для выделения статической информации из данной КС-грамматики, довольно велико. Поэтому, оценивать данный метод мы не будем.

• Алгоритм Эрли, описанный в [44, 45], а также его модификация, представленная в [46]. Данный алгоритм представляется наиболее подходящим для наших целей. Он не требует ни предварительного преобразования входной грамматики в специальную форму, как в случае алгоритма Кока-Янгера-Касами, ни построения ДКА, как в случае алгоритма Томиты. Алгоритм Эрли отвечает на вопрос принадлежит или нет входная терминальная цепочка о языку L(G), но не строит вывода данной цепочки в грамматике G = [N, Т, P,S). Поэтому мы построим модифицированный алгоритм Эрли, который назовем адаптированным для построения деревьев вывода алгоритмом Эрли. Этот алгоритм строит множество деревьев вывода непосредственно во время своей работы и работает корректно также и для неоднозначных грамматик. В первой главе данной работы мы определим адаптированный для построения деревьев вывода алгоритм Эрли, докажем его корректность, а также определим алгоритм обхода всех построенных во время исполнения адаптированного алгоритма Эрли деревьев вывода сверху вниз и слева направо. Также, докажем корректность этого алгоритма. Во второй главе мы проведем оценку вычислительной сложности адаптированного для построения деревьев вывода алгоритма Эрли как функции от таких свойств входной грамматики как объем, ветвистость и протяженность. Содержание этих свойств будет определено ниже. По результатам проведенной оценки данный алгоритм будет выбран для реализации как наиболее подходящий из рассмотренных выше алгоритмов синтаксического анализа открытых интерфейсных языков. Критериями выбора данного алгоритма являются как широта его применимости (данный алгоритм работает для любой контекстно-свободной грамматики без ограничений), так и отсутствие необходимости производить какие-либо дополнительные манипуляции с входной грамматикой до исполнения алгоритма синтаксического анализа и возможность построения всех деревьев вывода входной строки даже и для неоднозначных грамматик. В третьей главе мы опишем проблемы, возникшие при реализации динамической системы компиляции на основе адаптированного для построения деревьев вывода алгоритма Эрли, а также пути их решения.

Свойства контекстно-свободной грамматики, важные для алгоритмов синтаксического анализа

В процессе изучения различных алгоритмов синтаксического анализа было выделено три свойства контекстно-свободной грамматики, которые имеют влияние на вычислительную сложность алгоритмов синтаксического анализа. Эти свойства есть объем грамматики, ее ветвистость и протяженность.

Определение 1. Пусть дана КС-грамматика G = {N,T,P,S}, где N нетерминальные символы грамматики, Т - терминалы грамматики, Р -правила грамматики и 5 - начальный символ грамматики. Положим |С| = |ЛГ|+|Р|, где \N\ - количество нетерминалов и |р| - количество правил грамматики. Величину |G| будем называть объемом грамматики G .

Определение 2. Пусть G = [N,T,P,S] КС-грамматика и FA - множество правил грамматики G с нетерминальным символом А в левой части.

Обозначим через Fp максимум из |Fj для всех AeN, где [Fj - мощность множества FA. Назовем величину Fp ветвистостью грамматики G.

Нетрудно видеть, что ветвистость Fp, число нетерминальных символов \N\ и число правил грамматики \Р\ связаны соотношениями: \N\ < \P\<\N\-Fp.

Определение 3. Пусть G = {N,T,P,S} КС-грамматика и Мр = Мях{|«|:Л—>аеР] - максимальная из длин правых частей правил грамматики. Назовем величину Мр протяженностью грамматики G.

Во второй главе мы произведем оценку вычислительной сложности адаптированного для построения деревьев вывода алгоритма Эрли и найдем, что сложность данного алгоритма есть О\fp х |р|2 х М2р j для однозначных грамматик. Отсюда, и из того, что |pj<iV xFf , следует, что вычислительная сложность алгоритма адаптированного для построения деревьев вывода алгоритма Эрли есть также O^Fp x|N|2 у.М2р j. Из приведенной оценки видно, что ветвистость грамматики менее влияет на производительность алгоритма синтаксического анализа, чем длина правил грамматики и количество ее правил. С другой стороны, естественно считать, что максимальная длина правила (протяженность грамматики) МР не превышает максимальную длину входного слова |су| = «. Оценка вычислительной сложности для неоднозначной грамматики есть o\fp х|р|2 xM^j или О {fp х |7V|2 х М2р^ j.

Поэтому, при анализе неоднозначных языков, для лучшей производительности алгоритма синтаксического анализа предпочтительнее преобразовать исходную грамматику таким образом, чтобы длины правил были как можно меньше.

Цели диссертационной работы

Основная цель работы состоит в исследовании особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков и в построении эффективных алгоритмов синтаксического анализа для таких языков. В процессе исследования были определены те свойства открытых интерфейсных КС-языков, которые влияют на производительность алгоритмов синтаксического анализа. На основании этих свойств, из множества известных алгоритмов синтаксического анализа, был выделен и, на его основе, построен наиболее подходящий для анализа открытых интерфейсных КС-языков алгоритм.

Кроме того, необходимо было определить те параметры контекстно-свободной грамматики, которые влияют на вычислительную сложность алгоритмов синтаксического анализа. Таким образом, были выделены следующие параметры КС-грамматики, влияющие на вычислительную сложность алгоритмов синтаксического анализа: объем грамматики, ее ветвистость и протяженность.

Основным критерием выбора алгоритмов синтаксического анализа является, наряду с описанными выше критериями, их вычислительная сложность как функция от таких свойств КС-грамматики как ветвистость, протяженность и объем. Поэтому, целью работы является также разработка метода оценивания и оценка вычислительной сложности выбранных алгоритмов синтаксического анализа как функции от объема грамматики, ее ветвистости и протяженности.

Если при выборе наиболее подходящего для синтаксического анализа открытых интерфейсных контекстно-свободных языков алгоритма, не будет найден подходящий, то попытаться создать новый алгоритм либо путем модификации какого-либо из известных алгоритмов синтаксического анализа, либо новый, приспособленный специально для анализа этого типа языков.

На основании проведенного анализа существующих алгоритмов синтаксического анализа необходимо выбрать наиболее эффективный и модифицировать его с учетом особенностей открытых языков.

Одной из целей работы является доказательство корректности работы построенного алгоритма.

После построения наиболее подходящего для наших целей алгоритма синтаксического анализа необходимо реализовать его в виде системы динамической компиляции, которая позволит производить синтаксический анализа языков, задаваемых пополняющимися КС-грамматиками.

Результаты и апробация работы

Основными результатами данной работы являются следующие результаты:

В качестве наиболее подходящего для синтаксического анализа открытых интерфейсных контекстно-свободных языков алгоритма выбран алгоритм Эрли [45, 46]. Данный алгоритм модифицирован таким образом, чтобы производить построение деревьев разбора входной строки во время своей работы, и определен в данной работе как алгоритм 1. Если входная грамматика неоднозначная и для входной терминальной строки существует несколько деревьев разбора, то все они строятся в процессе исполнения алгоритма.

Доказана корректность построенного автором модифицированного для построения деревьев вывода входной строки алгоритма Эрли (доказательство приводится в главе 1 в виде теоремы 1).

Теорема 1. Алгоритм 1 успешно заканчивает свою работу только, и только, если для входной строки со существует хотя бы один вывод S =>+ со.

Основная трудность в доказательстве теоремы заключалась в доказательстве того, что алгоритм всегда заканчивает свою работу. Для этого необходимо было показать, что количество основных строительных элементов алгоритма Эрли - ситуаций Эрли ограничено сверху. Оказалось, что мощности максимально возможных множеств таких ситуаций образуют треугольники Паскаля. Таким образом, было показано, что максимальное число ситуаций Эрли ограничено сверху. Необходимо было также показать, что адаптированный алгоритм Эрли, во время своего исполнения, строит всевозможные деревья вывода входной строки (каждое такое дерево, очевидно, не должно иметь циклов, т.е. одинаковых поддеревьев и значит, соответствовать только кратчайшим выводам). Это доказывается в теореме 2.

Для обхода сверху вниз и слева направо каждого из построенных во время работы модифицированного алгоритма Эрли деревьев вывода входной строки, определен специальный алгоритм. Данный алгоритм берет на вход множество списков ситуаций Эрли, построенных во время исполнения адаптированного алгоритма Эрли и производит обход и построение в явном виде всех деревьев, содержащихся в данном множестве списков ситуаций. Этот алгоритм представлен в главе 1 как алгоритм 2. Корректность работы данного алгоритма доказывается в теореме 2 первой главы.

Теорема 2. Алгоритм 2 по результатам работы алгоритма 1, примененного к терминальной строке со = ах.ап и КС-грамматике G = {N,T,P,S], строит множество всех деревьев вывода данной терминальной строки со = ах.ап.

Теоремы 1 и 2 являются наиболее важными в настоящей работе, так как дают основание для применения адаптированного алгоритма Эрли для синтаксического анализа открытых неоднозначных языков. Построенный в работе алгоритм, позволяющий производить анализ таких языков, является новым.

На основе определенных выше параметров КС-грамматики произведена оценка вычислительной сложности алгоритмов 1 и 2. Результаты данной оценки представлены в формулировках теорем 3 и 4. Замечательным фактом, вытекающим из этих теорем, является то, что неоднозначность входной грамматики отражается только на таком параметре грамматики как ее протяженность и не влияет на остальные параметры алгоритмов 1 и 2.

Теорема 3. Максимальное время выполнения алгоритма 1 есть функция порядка o[fp x|/f хМ^, если входная грамматика однозначная, и

O^Fp х|-Р|2 хМ^+2 j, если входная грамматика неоднозначная.

Теорема 4. Максимальное время выполнения алгоритма 2 есть функции 0(\^Р\у.Мр} для однозначных грамматик и ОхFp х) для неоднозначных.

Проведена оценка вычислительной сложности, как функции от объема входной грамматики алгоритма преобразования этой грамматики в нормальную бинарную форму Хомского [2, с. 176]. Алгоритм Кока-Янгера-Касами требует, чтобы входная грамматика удовлетворяла условиям нормальной бинарной формы Хомского. Поэтому, необходимо провести преобразование исходной грамматики в нормальную бинарную форму перед запуском алгоритма синтаксического анализа Кока-Янгера-Касами. Для этого используются три алгоритма:

• Алгоритм определения порождающих пустую строку нетерминалов, представленный в работе как алгоритм 3, оценка вычислительной сложности которого представлена в теореме 5:

Теорема 5. Алгоритм 3 выполняется за максимальное время О

• Алгоритм исключения из грамматики правил с пустой правой частью, представленный в работе как алгоритм 4, оценка вычислительной сложности данного алгоритма как функции от объема грамматики представлена в теореме 6:

Теорема 6. Алгоритм 4 выполняется за максимальное время C>(|G|) и объем грамматики G', полученной в результате исполнения алгоритма 4, также равен 0(|С?|) .

• Алгоритм преобразования контекстно-свободной грамматики без правил с пустой правой частью в нормальную бинарную форму Хомского, представленный в данной работе как алгоритм 5, оценка вычислительной сложности данного алгоритма приведена в теореме 7:

Теорема 7. Алгоритм 5 выполняется за максимальное время 0(|G|). Объем выходной грамматики G' есть также величина

Проведена оценка вычислительной сложности алгоритма Кока-Янгера-Касами [47, 56] как функции от объема входной грамматики. Данный алгоритм представлен в работе как алгоритм 6, а оценка его вычислительной сложности представлена в теореме 8:

Теорема 8. Алгоритм 6 выполняется за максимальное время O^Gf

Проведена также оценка вычислительной сложности алгоритма построения деревьев разбора входной строки на основе таблицы нетерминалов входной грамматики, построенной в результате исполнения алгоритма Кока-Янгера-Касами. Данный алгоритм представлен в работе как алгоритм 7, а оценка его вычислительной сложности приведена в теореме 9:

Теорема 9. Максимальное время исполнения алгоритма 7 есть 0|jG| j.

Проведено построение динамической системы компиляции на основе адаптированного для построения деревьев вывода алгоритма Эрли. Построение проведено в соответствии с традиционной системой разбиения процесса синтаксического анализа на два этапа: лексический анализ и синтаксический анализ. Произведено построение лексического анализатора на основе динамически задаваемого множества лексических типов.

Основные результаты данной работы опубликованы в работах [17-20]. Результаты работы были доложены: на семинаре отдела систем математического обеспечения Вычислительного Центра РАН под руководством д. ф.-м. н. Серебрякова В. А. на семинаре отделения научных исследований по проблемам информатики Всероссийского института научной и технической информации под руководством д. ф. н. Гиляревского Р. С.

Научная новизна

Все результаты диссертации являются новыми. Новым также является подход к задаче оценки вычислительной сложности алгоритмов синтаксического анализа. В качестве параметров оценки вычислительной сложности алгоритмов в данной работе выступает не длина входной строки, как это обычно производится при представлении новых алгоритмов синтаксического анализа, а параметры, выражающие характеристики входной грамматики. Определение таких характеристик также являлось целью данной работы и, в качестве результата, были выделены три характеристики: объем грамматики, ее ветвистость и протяженность.

В результате исследования был выделен наиболее подходящий для синтаксического анализа открытых интерфейсных языков алгоритм синтаксического анализа. Это алгоритм Эрли для распознавания выводимости входной терминальной строки во входной грамматике. Но, так как данный алгоритм не строит деревья вывода входной строки, а только отвечает, выводится или нет данная строка в данной грамматике, то была произведена модификация данного алгоритма и, таким образом, был получен новый алгоритм, названный адаптированным для построения деревьев вывода алгоритмом Эрли. Данный алгоритм применим к анализу неоднозначных контекстно-свободных языков. В работе впервые доказана корректность работы алгоритма, построенного автором.

Структура работы

Данная работа состоит из трех глав.

В первой главе представлены два алгоритма: адаптированный для построения деревьев вывода алгоритм Эрли и алгоритм обхода сверху вниз и слева направо деревьев вывода, построенных в результате работы адаптированного для построения деревьев вывода алгоритма Эрли. Алгоритмы представлены как алгоритм 1 и алгоритм 2 соответственно. Доказательство корректности работы алгоритма 1 произведено в теореме 1. Доказательство корректности работы алгоритма 2 произведено в теореме 2.

Во второй главе производится оценка вычислительной сложности алгоритма 1 и алгоритма 2 как функции от объема, ветвистости и протяженности входной грамматики. Результаты данной оценки приведены в формулировках теорем 2 и 3. Также в главе 2 представлены: алгоритм нахождения нетерминалов грамматики, выводящихся в пустую строку, представленный в работе как алгоритм 3, алгоритм исключения из исходной грамматики правил с пустой правой частью, представленный в работе как алгоритм 4, и алгоритм преобразования контекстно-свободной грамматики без правил с пустой правой частью в нормальную бинарную форму Хомского, представленный в данной работе как алгоритм 5. Также проведена оценка вычислительной сложности данных алгоритмов как функции от объема входной грамматики, результаты данной оценки представлены, соответственно, в теоремах 5, 6 и 7. Также, в главе 2 представлен алгоритм Кока-Янгера-Касами как алгоритм 6 и алгоритм построения дерева разбора на основе алгоритма Кока-Янгера-Касами как алгоритм 7. Проведена оценка вычислительной сложности алгоритмов 6 и 7 как функции от объема входной грамматики. Результаты данной оценки представлены в формулировках теорем 8 и 9 соответственно.

Третья глава представляет собой описание реализации динамической системы компиляции, реализованной на основе адаптированного для построения деревьев разбора алгоритма Эрли. В данной главе также обсуждаются вопросы, связанные с организацией взаимодействия с модулем трансляции, осуществляемого на основе алгоритма синтаксического анализа. Большая часть главы посвящена вопросам реализации лексического анализатора на основе динамически добавляемых лексических типов. Каждый лексический тип представляет собой регулярный язык, представленный минимизированным детерминированным конечным автоматом. В алгоритме 8 представлен процесс лексического анализа на основе динамически пополняемого множества лексических типов.

Заключение диссертации по теме «Теоретические основы информатики», Лапшин, Владимир Анатольевич

Выход:

1. Слово-токен token, принадлежащее некоторому лексическому типу, содержащее в качестве параметра свой текст или сообщение об ошибке.

Метод:

Производит распознавание длиннейшей подстроки, которая допускается хотя бы одним из минимизированных ДКА, переданных в качестве параметра {Ltt},l<i<k. Каждый из переданных ДКА запускается параллельно для символов входной строки ш = ах.ап. Таким образом, находится лексический тип, минимизированный ДКА которого допускает строку наибольшей длины. Если таких лексических типов несколько, то из них, в результате вызова функции Priority , выбирается единственный с наивысшим приоритетом. Если не существует лексических типов, чьи минимизированные ДКА допускают текущий входной текст, то возвращается сообщение об ошибке.

Алгоритм использует два дополнительных списка минимизированных

ДКА:

1. Current, в котором хранятся минимизированные ДКА, для которых был произведен переход по текущему символу.

2. Accepted , в котором хранятся минимизированные ДКА, которые перешли в допустимое состояние по текущему или по одному из предыдущих символов. Последнее происходит только в том случае, если ни один из автоматов, которые были в списке Current, не перешел в заключительное состояние.

Приведем описание алгоритма в псевдокоде.

Шаг 1. Удаляем элементы из списков Current и Accepted, если таковые в них были. Current.ResetQ Accepted.Reset О

Шаг 2. Инициализируем список Current минимизированными ДКА из множества {Ltt}, 1 <i<k. foreach( MinDFA in Lt) {

MinDFAJieset Current .Insert [MinDFA)

Шаг 3. Повторяем шаги 4-7 пока в Current есть хотя бы один элемент. 1 счетчик символов в строке j := 0 номер последнего символа длиннейшей допустимой строки while ( Current.Size > 0 and i< n) {

Шаг 4. Инициализируем временные списки Current и Accepted TmpCurrent.Reset TmpAccepted.Reset

Шаг 5. Производим переход по символу аг Добавляем ДКА, для которых переход произошел успешно, в TmpCurrent для дальнейшей работы. Если ДКА достиг заключительного состояния, то добавляем его в TmpAccepted. foreach ( MinDFA in Current) { if ( MinDFA.Move[ a, ) = True) {

TmpCurrent.Insert (MinDFA) if ( MinDFA.IsAccepted() = True) TmpAcceptedInsert (MinDFA} }

Шаг 6. Если в текущем множестве TmpAccepted есть хотя бы один ДКА, копируем это множество в Accepted. Также, запоминаем текущий номер символа входной строки, которая является, на данный момент, длиннейшей допустимой строкой. if ( TmpA cceptedSize > 0) {

Accepted := TmpAccepted

Шаг 7. Копируем ДКА, находящиеся в TmpCurrent в список Current для следующего перехода и увеличиваем номер символа входной строки.

Current := TmpCurrent +1 }

Шаг 8. Если в Accepted есть ДКА и был прочитан хотя бы один символ строки, значит какой-то из ДКА допустил данную подстроку. Возвращаем эту подстроку и соответствующий лексический тип. В противном случае возвращаем ошибку. if ( Accepted.Size > 0 ) {

MinDFAPriority ( Accepted)

Token := ConstructToken ( MinDFA.GetLexTypelD, ax.aj j return Token else return False

Таким образом, очевидно, что если какой-либо из минимизированных детерминированных конечных автоматов, принадлежащих коллекции лексических типов, допускает какую-либо подстроку входного текста, то данный минимизированный ДКА обязательно будет присутствовать хотя бы в одном из списков TmpAccepted, строящихся во время исполнения алгоритма 8. Очевидно, также, что если никакая подстрока входного текста не распознается никаким минимизированным ДКА из коллекции лексических типов, то список TmpAccepted6yjiQTnycT при любой итерации шага 3 алгоритма 8, а значит, результирующее множество Accepted также будет пусто, поэтому, в этом случае, алгоритм 8 возвратит ошибку. Очевидно, также, что алгоритм лексического анализа на основе лексических типов будет возвращать длиннейшую из подстрок, допускаемых каким-либо из минимизированных ДКА из коллекции лексических типов.

3.4 Особенности реализации семантических действий

Для реализации семантических действий мы выбрали подход, основанный на понятии атрибутной грамматики. Атрибутная грамматика представляет собой контекстно-свободную грамматику, каждый символ которой может иметь несколько, так называемых, атрибутов - величин, с которыми связаны семантические действия, исполняемый семантическим анализатором, если правило входной КС-грамматики, в соответствии с которым производится разбор входной строки, было использовано в данном разборе. Поэтому, каждое правило входной грамматики обычно также расширяется посредством привязки каждого правила исходной грамматики к некоторому семантическому действию. При распознавании входной строки, в соответствии с некоторым правилом исходной КС-грамматики, происходит исполнение данного, привязанного к этому правилу, семантического действия. Обычно, такое действие состоит в обработке, некоторым образом, зависящим от реализации семантики, атрибутов, присоединенных к символам грамматики, входящим в уже распознанные правила. В этом случае, атрибуты называются синтезируемыми. Использование таких атрибутов бывает особенно удобно, когда дерево вывода входной строки строится снизу вверх, т.е. сначала строятся нижние уровни дерева разбора, а только потом, верхние. При построении дерева сверху-вниз удобнее использовать атрибуты, приходящие вместе с распознанными символами грамматики, которые представляют собой узлы верхнего уровне дерева. Приходящие с верхних узлов дерева разбора атрибуты называются наследуемыми. В качестве примера атрибутной грамматики рассмотрим реализацию семантических действий для следующей КС-грамматики: l.S->S+S 2. S-^n

Нетерминальный символ S, также как и терминальный символ п, имеют атрибут Number, значением которого является целое число. Для нетерминала п значение возвращается лексическим анализатором как атрибут данного нетерминального символа. Значения атрибута Number для нетерминала S вычисляется в соответствии с семантическими правилами:

1. Number[S) = Number(S) + Number{S) для правила S -> S:'+ S.

2. Number(5) = Number(w) для правила S —» я. 1

Очевидно, что в соответствии со способом вычисления атрибутов, атрибут Number, как для нетерминального символа S, так и для терминального символа п, является синтезируемым, т.е. его вычисление производится на основе уже вычисленных атрибутов символов, представляющих узлы нижнего уровня дерева разбора.

В соответствии с данной реализацией семантических действий при разборе входной строки будет вычислено значение выражения, поданного на вход разборщику. Подобным образом организовано взаимодействие между семантическим и синтаксическим анализатором в генераторе разборщиков на основе алгоритма синтаксического анализа LALR(l) [3], известного под именем YACC [51] или, его GNU реализации Bison [51]; LALR(l)анализатор является разновидностью ZJ?(l)-анализа [2, с. 443], известного как метод разбора входной строки снизу-вверх методом перенос-сверка. LALR(l) -анализатор строит правый вывод входной строки. При этом, учитывая ограничения, налагаемые на L/?(l)-грамматику, вывод входной строки является детерминированным, т.е. каждая распознанная продукция должна принадлежать выводу входной строки, если он существует. Так как построение дерева разбора производится снизу-вверх, все атрибуты, использующиеся в семантических действиях, являются синтезируемыми. Доступ к атрибуту производится с помощью специальной комбинации символов $п, где п - номер символа в правой части правила. Символ $$ представляет собой атрибут нетерминального символа КС-грамматики, представляющего левую часть данного правила грамматики. Атрибутная грамматика, дополненная семантическими действиями и определениями терминальных символов, задается в специальном файле - программе для генератора разборщиков. Определенная выше атрибутная грамматика, как программа для Bison, имела бы вид: token Number %%

S: 5"+' S {$$ = $1+ $3} | Number {$$ = GetTokenQ} ; %%

Здесь ключевое слово %token позволяет задать терминальный символ Number. Семантические действия, которые присоединены к правилам КС-грамматики, позволяют производить вычисления атрибутов грамматики в соответствии с распознанными правилами в выводе входной строки.

Возможна также реализация взаимодействия между синтаксическим и семантическим анализаторами в несколько ином виде. Именно, возможно сначала проводить синтаксический анализ с целью построения деревьев вывода входной строки, единственными атрибутами которого будут являться значения терминальных узлов, возвращаемые лексическим анализатором. Таким образом построенные деревья разбора передаются семантическому анализатору для последующего анализа. Данный подход выгоден, когда необходимо организовать действительно конвейерную работу различных модулей разборщика. При таком подходе возможно организовать интерфейс модулей таким образом, чтобы модули ничего не знали друг о друге, т.е. провести полную ортогонализацию модулей.

Ввиду того, что архитектура нашей реализации разборщика построена на конвейерной модели, мы остановим свой выбор на последнем способе, т.е. когда синтаксический анализатор производит построение деревьев разбора, в которых только узлы, помеченные терминальными символами входной КС-грамматики, имеют атрибуты. Единственный атрибут, который имеет каждый узел, помеченный терминальным символом, это подстрока входного, представляющая собой цепочку регулярного языка лексического типа, который представлен во входной КС-грамматике данным терминальным символом. Таким образом, модулю синтаксического анализатора нет никакой необходимости знать семантические действия, которые будет производить семантический анализатор при обходе дерева разбора входной строки. Единственный атрибут, который присоединяется к узлам, помеченным терминальными символами входной КС-грамматики, вычисляется автоматически каждый раз, когда вызывается функция GetToken лексического анализатора.

Основной проблемой, возникающей при исполнении семантических действий над построенными деревьями разбора входной строки, является выбор правильного, с точки зрения данной семантики, дерева разбора входной строки, в том случае, если входная КС-грамматика не является однозначной и входная строка может быть выведена в данной грамматике несколькими различными способами. Выбор того или иного дерева разбора, из нескольких деревьев разбора входной строки, есть прерогатива семантического анализатора и не может быть сделан на этапе синтаксического анализа. В нашей модели, когда обработка семантических действий производится после того, как завершено исполнение алгоритма синтаксического анализа, но не во время его исполнения, как это, например, сделано в YACC или Bison [51], семантический анализатор никак не может повлиять на процесс построения дерева разбора. Поэтому, синтаксический анализатор будет производить построение всех деревьев разбора входной строки, а выбор соответствующего дерева разбора будет производиться семантическим анализатором после того, как процесс построения всех деревьев вывода входной строки будет закончен.

Заключение

В данной диссертационной работе было проведено исследование особенностей построения синтаксических анализаторов для открытых интерфейсных контекстно-свободных языков. Основной проблемой построения такого синтаксического анализатора является определение наиболее подходящего алгоритма для синтаксического анализа открытых интерфейсных контекстно-свободных языков. В работе был проведен обзор существующих алгоритмов синтаксического анализа, применимых к открытым интерфейсным контекстно-свободным языкам. В качестве основных кандидатов для были выбраны два алгоритма: алгоритм Эрли и алгоритм Кока-Янгера-Касами. Алгоритм Эрли не производит построения деревьев ввода входной строки, а только отвечает на вопрос, выводима ли входная строка в данной грамматике или нет. Поэтому, была произведена модификация оригинального алгоритма Эрли для того, чтобы иметь возможность строить все деревья вывода входной строки, если таковые существуют. Таким образом модифицированный алгоритм Эрли назван адаптрированным для построения деревьев вывода алгоритмом Эрли. В данной работе также проведено доказательство корректности данного алгоритма. Для обхода построенных во время исполнения адаптированного для построения деревьев ввода алгоритма Эрли сверху вниз и слева направо был представлен специализированный алгоритм. В данной работе также была доказана его корректность.

В процессе исследования были определены те параметры контекстно-свободной грамматики, которые влияют на вычислительную сложность алгоритмов синтаксического анализа. Это определенные в данной работе объем, ветвистость и протяженность контекстно-свободной грамматики. Была произведена оценка вычислительной сложности адаптированного для построения деревьев вывода алгоритма Эрли и алгоритма обхода сверху вниз и слева направо деревьев, построенных в результате исполнения адаптированного для построения деревьев вывода алгоритма Эрли как функции от объема, ветвистости и протяженности входной грамматики.

Алгоритм Кока-Янгера-Касами позволяет производить анализ языков, заданных контекстно-свободной грамматикой в специальной форме -нормальной бинарной форме Хомского. Для преобразования в нормальную бинарную форму необходимы три алгоритма: алгоритм нахождения нетерминалов, порождающих пустую строку, алгоритм исключения из грамматики правил с пустой правой частью и, собственно, алгоритм преобразования грамматики, не имеющей правил с пустой правой частью, в нормальную бинарную форму Хомского. Все три алгоритма приведены в данной работе. Также в работе приведены алгоритм Кока-Янгера-Касами и алгоритм построения деревьев вывода входной строки по таблице нетерминалов, построенной в результате исполнения алгоритма Кока-Янгера-Касами. Вычислительная сложность, как функция от объема входной грамматики, всех алгоритмов, связанных с алгоритмом Кока-Янгера-Касами, также оценена в данной работе.

На основании вышеприведенной оценки вычислительной сложности как функции от определенных параметров грамматики, для реализации был выбран адаптированный для построения деревьев вывода алгоритм Эрли.

На основе адаптированного для построения деревьев вывода алгоритма Эрли была реализована система динамической компиляции. Данная система реализована с использованием традиционного подхода, состоящего в разбиении синтаксического анализатора на два модуля: модуль лексического анализа и модуль синтаксического анализа. При реализации модуля лексического анализа основная трудность состояла в построении алгоитма лексического анализа на основе динамически пополняемого множества лексических типов. Данная проблема также была решена успешно.

Таким образом, поставленная задача выяснения особенностей синтаксического анализа открытых интерфейсных языков была решена полностью.

Список литературы диссертационного исследования кандидат физико-математических наук Лапшин, Владимир Анатольевич, 2005 год

1. Агафонов В.Н. Синтаксический анализ языков программирования: Уч. пособие. - Новосибирск: НГУ, 1981. - 91 с.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, Том 1. Москва: Мир, 1978. - 612 с.

3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, Том 2. Москва: Мир, 1978. - 322 с.

4. Ахо А., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструменты. Москва: Вильяме, 2001. - 768 с.

5. Вениаминов Е. М., Болдина Д. М. Система представления и обработки знаний ЭЗОП//Материалы конференции Диалог-2001: Прикладные проблемы. 2001. - С. 41-43.

6. Вениаминов Е. М., Вайнтроб А. Ю. Основные принципы диалогового языка для представления знаний средствами категорного подходам/Материалы конференции ДИАЛОГ-87. Тбилиси, 1988. - С. 174-177.

7. Вениаминов Е. М., Манушина М. Ю. Принципы построения открытого языка шаблонных выражений в системе представления знаний//НТИ Сер. 2.-2000.-№7.

8. Братчиков И. JI. Синтаксис языков программирования. Москва: Мир, 1975.-232 с.

9. Вайнгартен Ф. Трансляция языков программирования.,- Москва: Мир, 1977.

10. Ю.Волкова И. А. Руденко Т.В. Формальные грамматики и языки. Элементы теории трансляции. Москва: МГУ, 1999.

11. Н.Гинзбург С. Математическая теория контекстно-свободных языков. -Москва: Мир, 1970.

12. Гладкий А. В. Формальные грамматики и языки. Москва: Наука, 1973.

13. Гладкий А. В., Мельчук И. А. Элементы математической лингвистики. -Москва: Наука, 1969.

14. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. Москва: Мир, 1975.

15. Гросс М., Лантен А. Теория формальных грамматик. Москва: Мир, 1971.

16. Касьянов В.Н., Потгосин И. Методы построения трансляторов. -Новосибирск: Наука, 1986.

17. Лапшин В. А. Оценка производительности алгоритма Кока-Янгера-Касами как функции от объема грамматики//НТИ Сер. 2. 2004. - № 9.

18. Лапшин В. А. Особенности синтаксического анализа открытых интерфейсных контекстно-свободных языков//НТИ Сер. 2. 2004. - № 12.

19. Лапшин В. А. Оценка вычислительной сложности адаптированного для построения деревьев вывода алгоритма Эрли//НТИ Сер. 2. 2005. - № 4.

20. Лапшин В. А. Адаптированный для построения деревьев вывода алгоритм Эрли//НТИ Сер. 2. 2005. - № 5.

21. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. Москва: Мир, 1979.

22. Мартыненко Б.К. Языки и трансляции. Санкт-Петербург: СПГУ, 2003.

23. Попов Э. В. Общение с ЭВМ на естественном языке. Москва, 1982.

24. Попов Э. В. Экспертные системы. Москва, 1987;

25. Пратг Т. Языки программирования: разработка и реализация. Москва: Мир, 1979.

26. Рейуорд-Смит В. Дж. Теория формальных языков. Вводный курс. -Москва: Радио и связь, 1988. 128 с.

27. Саломаа А. Жемчужины теории формальных языков. Москва: Мир, 1986.

28. Серебряков В.А. Лекции по конструированию компиляторов. Москва, 1993.

29. Соколов В. А., Кушниренко О. Б., Бадин Н. М. Формальные языки и грамматики. Задачи и упражнения. Ярославль: Ярославский государственный университет, 1993. - 55 с.

30. Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез). Москва: Наука, 1970. - 400 с.

31. Успенский В. А. Треугольник Паскаля. Москва: Наука, 1979.

32. Фитиалов С.Я. Формальные грамматики. Ленинград: ЛГУ, 1984.

33. Фостер Дж. Автоматический синтаксический анализ. Москва: Мир, 1975.

34. Фридл Дж. Регулярные выражения. изд-во Питер, 2001.

35. Хантер Р. Проектирование и конструирование компиляторов. -Москва: Финансы и статистика, 1984.-232 с.

36. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-е изд.: Пер. с англ. Москва: Издательский дом «Вильяме», 2002. - 528 с.

37. ANTLR/http://www.antlr.org.

38. Bouckert M., Pirotte A., Snelling M. Efficient parsing algorithms for general context-free parsers//Inform. Sci. 1975: vol. 8. - № 1. - p. 1-26.

39. Davis,M.D., Sigal,R., Weyuker,E.J. Gomputability, complexity, and languages, second edition. Boston, Massachusetts: Academic Press, 1994.

40. Chomsky N. Three models for the description of language//IEEE Trans. Inform. Theory. 2: 3. - p. 113-124;

41. Earley J. An efficient context-free parsing algorithm//ACM. 13. - 2. - p. 94-102.

42. Earley J. An efficient context-free parsing algorithm: Ph. D. Dissertation. -Pittsburg: Carnegie Mellon University, 1968.

43. Graham S., Harrison M., Russo W. An improved Context-Free Recognizer//ACM TOPLAS. -1980: vol. 2. -№ 3. p. 415-462.

44. Kasami Т., Torii K. A syntax-analysis procedure for unambiguous context-free grammars//ACM 16. 1969. - № 3. - p. 423-431.

45. Knuth D. E. On the translation of languages from left to right//Inform. Control 8. 1965. - p. 607-639.

46. Lewis H. R., Papadimitriou С. H. Elements of the Theory of Computation. 2nd ed. Prentice Hall, 1998. - 361 p.

47. John C.M. Introduction to Languages and the Theory of Computation.

48. McGraw-Hill, 1991. 51. Johnson S C. Yacc: Yet Another Compiler

49. Compiler/http://dinosaur.compilertools.net/vacc/index.html. 52.Scott E., Johnstone A., Hussain S. S. Tomita-Style Generalized LR

50. Tomita M. Efficient parsing for natural language. Boston: Kluwer Academic Publishers, 1986. - p. 201.

51. Younger D. H. Recognition of context-free languages in time nV/Inform. Control 10. 1967. № 2. - p. 189-208.