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

На правах рукописи

Лапшин Владимир Анатольевич

Особенности синтаксического анализа открытых интерфейсных контекстно-свободных языков

Специальность - 05.13.17 Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2005

Работа выполнена в Российском Государственном Гуманитарном Университете

Научный руководитель:

доктор физико-математических наук, профессор Вениаминов Евгений Михайлович

Официальные оппоненты:

доктор физико-математических наук Борщев Владимир Борисович

кандидат физико-математических наук Валиев Марс Котдусович

Ведущая организация:

Институт проблем управления РАН

Защита состоится «3О» ИСЛ'Ь^2005 г. в «1&» часов на заседании диссертационного совета Д 002.026.01 при Всероссийском институте научной и технической информации по адресу: 125190, Москва, ул. Усиевича, д. 20.

С диссертацией можно ознакомиться в библиотеке Всероссийского института научной и технической информации.

Автореферат разослан «1€>уугГ?Д"|?2005 г.

Ученый секретарь диссертационного совета Д 002.026.01 доктор биологических наук,

профессор

М. А. Каменская

19019

Общая характеристика работы Актуальность темы работы

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

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

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

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

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

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

• Входной строки ю = а,...а„ длины |а>| = п, где а, е Т 1 £ i < п.

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

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

строк длины п, то мы разбиваем множество тйрчвдалНиЫкИ&ркЛьЛГ* М классы а>" равных

БИБЛИОТЕКА

СП№1 OB

по длине строк. Каждый такой класс а" терминальных строк длины \т\ = п и представляется числом п. Функция Evg (и) , определенная на множестве натуральных чисел N*, берет и в качестве параметра и выдает максимальное время анализа, выраженное в элементарных операциях, которые алгоритм анализа производит над сущностями грамматики G.

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

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

Особая ситуация возникла с алгоритмом Эр ли. Данный алгоритм не строит деревьев вывода входной строки, но дает ответ лишь на вопрос выводится или нет данная входная строка в данной грамматике. Для наших же целей необходимо произвести построение всех деревьев вывода данной строки. Для этого в данной работе строится модификация алгоритма Эрли таким образом, чтобы он производил построение всех деревьев вывода входной строки во время своего исполнения. Заметим сразу, что эта задача достаточно трудна, и особенно, для неоднозначных грамматик. Достаточно отметить, что в разные годы ее пытались решить разные исследователи. Например, в начале 80-х годов Масари Томита пытался решить проблему построения всех деревьев вывода входной строки для неоднозначных грамматик, задающих естественные языки [12]. Это ему не удалось, поэтому Томита произвел модификацию известного алгоритма LR(k)-анализа [9]. Данная модификация теперь известна как алгоритм Томиты или алгоритм GLR [11-12]. Известные в данное время реализации алгоритма Эрли [5-7] не производят построения дерева вывода входной строки вообще или производят такое построение только для однозначных грамматик. В данной

работе представлена модификация алгоритма Эрли, позволяющая строить все деревья вывода входной строки. Данная модификация названа адаптированным для построения деревьев вывода алгоритмом Эрли. В работе также произведена оценка вычислительной сложности функции Parsea{G), реализованной посредством адаптированного алгоритма Эрли, в терминах упоминавшихся выше параметров входной грамматики.

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

Основное содержание работы состоит в исследовании особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков. Цели этого исследования заключаются в следующем:

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

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

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

На основании вышеуказанных целей диссертационной работы были поставлены Следующие Задачи:

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

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

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

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

Методы исследований

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

производительности алгоритма как функции от выделенных на этапе исследования свойств КС-грамматики.

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

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

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

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

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

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

Практическая и теоретическая ценность

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

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

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

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

Апробация работы

Результаты работы были доложены:

на семинаре отдела систем математического обеспечения Вычислительного Центра РАН под руководством д. ф.-м. н. Серебрякова В. А.

на семинаре отделения научных исследований по проблемам информатики Всероссийского института научной и технической информации под руководством д. ф. н. Гиляревского Р. С.

Публикации

Основные результаты данной работы опубликованы в работах [1-4] списка опубликованных работ.

Объем работы

Диссертация содержит 140 страниц и состоит из введения, трех глав и списка литературы, содержащего 56 названий.

Содержание работы Краткое содержание работы

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

Целью данной работы является исследование особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков. Язык, заданный контекстно-свободной грамматикой, называется открытым, если он может бьггь пополнен новыми сущностями: правилами грамматики, нетерминальными и терминальными символами, между двумя исполнениями алгоритма синтаксического анализа. Язык называется интерфейсным, если он используется для осуществления взаимодействия между пользователем некоторой системы и этой системой. Таким образом, алгоритм синтаксического анализа используется системой как один из инструментов, позволяющих «понять» предложения пользователя. Были выделены три основных особенности синтаксического анализа открытых | интерфейсных контекстно-свободных языков.

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

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

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

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

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

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

Определение 2. Пусть в = {М,Т,Р,8} КС -грамматика и РА - множество правил грамматики Б с нетерминальным символом А в левой части. Обозначим через максимум из для всех А е N, где - мощность множества РА. Назовем величину Рг ветвистостью грамматики в.

Нетрудно видеть, что ветвистость Рр, число нетерминальных символов и число правил грамматики |/>| связаны соотношениями: [Л^ < |Р|< х Рр.

Определение 3. Пуст ь <3 = {Л/,Г,/>,5} КС-грамматика и Ме = Мах {|а|: А а е Р} -максимальная из длин правых частей правил грамматики. Назовем величину Ме протяженностью грамматики О.

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

есть о1уР'е х|Р|2 х М^ для однозначных грамматик. Отсюда, и из того, что < // х ^,

следует, что вычислительная сложность алгоритма адаптированного для. построения

деревьев вывода алгоритма Эр ли есть также Из приведенной оценки

видно, что ветвистость грамматики менее влияет на производительность алгоритма синтаксического анализа, чем длина правил грамматики и количество ее правил. С другой стороны, естественно считать, что максимальная длина правила (протяженность грамматики) Мр не превышает максимальную длину входного слова \а>\ = п. Оценка вычислительной

сложности для неоднозначной грамматики есть или о(/£х|ЛГ|2

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

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

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

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

На основании проведенного выбора наиболее подходящего для синтаксического анализа открытых интерфейсных контекстно-свободных языков, была реализована система динамической компиляции. Данная система была реализована традиционным способом разделения процесса синтаксического анализа на лексический и синтаксический анализы. Каждый терминальный символ в синтаксическом анализаторе представляет собой регулярный язык, представленный в лексическом анализаторе специальным лексическим типом. Ввиду того, что множество лексических типов может динамически пополняться, необходимо было разработать как метод оптимального представления лексических типов в лексическом анализаторе, так и алгоритм лексического анализа, основанный на таком представлении. В качестве такого представления был выбран минимизированный детерминированный конечный автомат. Лексический тип изначально задается пользователем с помощью регулярного выражения. Затем, встроенный в лексический анализатор компилятор регулярных выражений производит синтаксический анализ данного регулярного выражения в недетерминированный конечный автомат, а затем, из данного недетерминированного конечного автомата в несколько этапов получается минимизированный детерминированный конечный автомат. Также, необходимо было продумать метод взаимодействия синтаксического анализатора с семантическим анализатором системы, в которой данный язык выступает в качестве интерфейса. В качестве результата синтаксический анализатор выдает множество деревьев разбора (или единственное дерево, если входная грамматика однозначная) входной строки, где узлы, обозначаемые терминальными символами грамматики, имеют единственный атрибут -строку символов, возвращенную лексическим анализатором.

,Глава 1

' -Ш]}йая №тава посвящена обсуждений' вопросов^ связанных' с адаптированным для построения деревьев вывода алгоритмом Эрли. Как известно, оригинальный алгоритм Эрли не производит построения деревьев вывода входной строки, а отвечает только на вопрос, выводится или нет данная входная строка в данной грамматике. Поэтому, необходимо модифицировать данный алгоритм таким образом, чтобы он производил построение всех деревьев разбора в данной грамматике. Модифицированный алгоритм Эрли производит построение деревьев разбора снизу вверх и справа налево. Часто, необходимо произвести обход каждого из деревьев сверху вниз и слева направо. Поэтому, в данной главе представлен также и алгоритм обхода построенных в результате модифицированного алгоритма Эрли деревьев вывода входной строки сверху вниз и слева направо.

Прежде чем начать излагать произведенную модификацию алгоритма Эрли, необходимо напомнить в чем заключается оригинальный алгоритм Эрли. Алгоритм Эрли оперирует списками так называемых ситуаций Эрли. Каждая ситуация Эрли состоит из трех компонентов: помеченного правила грамматики (где помеченное правило это просто правило грамматики с точкой где-нибудь в правой части), номера списка, в котором начался вывод данного правила, и строки предосмотра, состоящей из терминальных символов грамматики. Известно, что использование предосмотров не дает сколько-нибудь заметного улучшения производительности, но влияет на количество ситуаций Эрли в списках ситуаций Поэтому, использовать третий компонент ситуации Эрли мы не будем. Итак, ситуация Эрли это пара, состоящая из правила грамматики с точкой правой части и некоторого числа, большего нуля и меньшего, либо равного длине входной строки. Например, для правила грамматики вида А -> Х1...Хк можно построить к+1 помеченных правил, начиная с А -»•Л',. Хк, А->Х, •Хг..Хк и заканчивая А -*Х{...Хк •. Второй компонент пары - это некоторое число /, 0 < / < |о|, где со =ау.дп - это входная строка, а |й>| - это ее длина. Ситуацию Эрли, состоящую из помеченного правила А^Ху.Х,»Хм..Хк и второго компонента г, будем обозначать как [А-^Х^.Х/'Х^.-Х,,,!]. Алгоритм Эрли состоит в последовательном

построении списков ситуаций Эрли (называемых состояниями Эрли). Список строится для каждого символа входной строки и для нулевой позиции при ее чтении.

Мы произведем модификацию алгоритма Эрли путем изменения определения ситуации Эрли, добавив в нее два дополнительных компонента: ссылку I на ту же ситуацию,Эрни, что и текущая, но с точкой, левее на символ. Второй дополнительный компонент -гэто список ссылок (р) на ситуации, приведшие к передвижению точки на символ правее и добавлении

текущей ситуации в данный список. Мы докажем в дальнейшем, что ссылка, I содержит, указатель на левый узел того же уровня в дереве вывода входной строки, а1СПиеок ссылок (/>} указатели на поддеревья нижнего уровня дерева вывода входной ■. «троки. Т.е., фактически, во время исполнения модифицированного алгоритма Эрли, . производится построение всех деревьев вывода входной строки. Важным моментом здесь является то, что для сравнения ситуаций между собой мы будем использовать только первые три компонента: помеченное правило, номе|р списка и ссылку I, список ссылок (р) в сравнении-не участвует. В противном случае, возмояйш случаи когда в каком-нибудь списке расширенных ситуаций Эрли можегг быть неограниченное число элементов и, следовательно, модифицированный алгоритм Эрли не сможет закончить свое исполнение. . I

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

Лемма 1. Максимальное число ситуаций Эрли вида [Л —► Х{...Хк» ХмЛ.Хт, с

одними и теми же первыми двумя компонентами А -> Х1...Хк *Хку]..Хм и у у отличающихся {щаькр,„ значением ссылки /, иршидлржащих .состоянию^ , У['}, ^ есть: ' (1-]+к~\)\ , "НМК*-!)'.'6™

=1, если к = 0, ¿ = у, $ =0,если к = 0,7* j.

Если входная грамматика однозначная, то 5* = I для всех \<к<т.

Лемма2. Максимальное количество ситуаций Эрли в состоянии Эрли У\}\ есть величина

порядка \Р\х{Мп + + + > гае Мр - максимальная из длин правых частей

' 4 ' ' (/+1)!Л/,!

правил входной грамматики б = {Г, . Если исходная грамматика однозначная, то

максимальное количество ситуаций есть |Р) х (Мр + 1)х((' + 1).

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

ЛеммаЗ. Ситуация Эрли [Л-юг*/7,у',/,(р)] принадлежит состоянию Эрли УЩ тогда и только тогда, когда а)+1... а, и существуют такие строки у и 3, что 5 =>' у АЗ и у а1..м}.

При этом, если строка а равна:

ы

1. а'а, где а - это терминальный символ входной грамматики. Тогда а = а, и а'=>* о,+|...ам и вывод имеет вид £ =>' у АЗ =>'а{...^А8 => ¿¡¡...а^рЗ =>' йу.лр'арЗ ■=> ах...а^ар8. Ситуация [А-** а•/),),/,(/>)] в этом случае есть [А -» а'а, • где.

2. а'В; где В - это нетерминальный символ входной грамматики. Тогда существует число к, такое, что а" =>* X =>' ам...а, и вывод имеет вид 5 уА5 =>' аг..а;АЗ

аг..а^рЗ ах...ала'Вр8 =>* а,...акВрЗ =>* йу.а^З. В этом случае, ситуация [Л->а*р,],1,(р)] есть [А^а'В» р,],1,{р)\ где / = |А->а'»Вр,],Г,{р)' еУ[к) и

список (р) содержит ссылку р = г}*,к,1",(р) ^ е К [<}.

3. Л, где Л - пустая строка, т.е. помеченное Л - -> а*р правило есть А > •/?, то ситуация '[^->а»/?,у,/,(р)] имеет "вид [А-+»р,],пи11,0\, г = / и вывод >. имеет вид ,5 =>*. =>* => а, ...а,.

Таким образом, лемма 3 говорит о том, что каждая ситуация Эрли вида [А -> а • Д/,/,(р)] не просто так попадает в список, соответствующий некоторому символу входной строки а,, а только, и только, если существует вывод 5 =>' и,, .ар.8 =>' а^.м^. Поэтому, если входная строка ю = о,...а„ выводится во входной грамматике С = [Т,Ы,Р,8}, т.е. существует вывод а, ..ап, то в списке, соответствующем терминалу ап должна присутствовать ситуация вида [5 -> Х,...^»,О,/,(;?)]. Верно и обратное, а значит, верна

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

Во второй части первой главы рассматривается алгоритм обхода сверху вниз и слева направо всех деревьев вывода входной строки, построенных в результате исполнения адаптированного для построения деревьев вывода алгоритма Эрли. Такой алгоритм бывает необходим ввиду того, что алгоритм Эрли производит построение деревьев вывода снизу вверх и справа налево, что часто бывает неудобно для семантических анализаторов. Кроме того, алгоритм обхода производит построение всех деревьев вывода в явном виде. В адаптированном алгоритме Эрли узлы деревьев вывода скрыты внутри ситуаций Эрли как дополнительные компоненты I и (р).

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

Лемме 4. Алгоритм обхода деревьев, построенных в результате исполнения адаптированного алгоритма Эрли всегда заканчивает свою работу за конечное число шагов

10

Следующая теорема завершает доказательство корректности работы алгоритма. Теорема 2. Алгоритм обхода деревьев, построенных в результате исполнения адаптированного алгоритма Эр ли, примененного к терминальной строке а^ау.лп и КС-грамматике б = {И,Т,Р,8}, строит множество всех деревьев вывода данной терминальной строки са = а1...а„.

Глава 2

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

Адаптированный для построения деревьев вывода алгоритм Эрли во время своей работы производит манипуляции со списками ситуаций Эрли и сущностями входной грамматики. Входная грамматика, будучи представленной в памяти программы, синтаксического анализатора, имеет естественное упорядочивание: по мере добавления память программы терминальных и нетерминалы»^ символов грамматики, каждому из них дается порядковый номер, а правила грамматики могут быть представлены как векторы, в которых первым элементом выступает помер''' символа левой части Ьравила, а остальные элементы представляют собой номера символов в правой части правила. Сами правила также могут быть естественным образом пронумерованы. Тогда, операции над сущностями входной грамматики сводятся к трем основным операциям: операции на вектором символов грамматики, операции над вектором правил грамматики и операции над вектором, представляющим данное правило грамматики. При оценке вычислительной сложности алгоритмов мы будем полагать элементарным каждое обращение к одном из указанных выше трех векторов. Алгоритмы семейства Эрли работают также с ситуациями Эрли, элементами вида [А-> Х,...Х,»Хм...Хк,/,/,(/>)], где А-+Х1...Х,»Хм...Хк - помеченное правило входной грамматики, / - номер одного из списков ситуаций Эрли, 1 - ссылка на некоторую ситуацию Эрли, а (р) - список таких ссылок. Помеченное правило в памяти программы представимо в виде пары чисел (г,/), где г - номер правила грамматики в представлении программы, а / - номер позиции точки в правиле. Ссыпку на ситуацию легко представить как пару номеров, где первый элемент - это номер списка ситуаций, а второй -порядковый номер ситуации Эрля в этом списке. Таким образом, ссылка / может быть представлена парой чисел, а список ссылок (р) - вектором таких пар. Отсюда видно, что, например, операция передвижения точки в помеченном правиле, принадлежащем некоторой ситуации, на символ правее, сводится просто к увеличению на единицу числа ( в паре (г,/),

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

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

Для оценки вычислительной сложности адаптированного для построения деревьев вывода алгоритмов Эрли нам необходимы сначала следующие леммы: I ■

л

Лемма5. Для любой ситуации Эрли [Л-»а•/?,£,/,(/>)], принадлежащей состоянию У[г],

/ к ^ (ЛЛ+х+1)!

максимальное количество элементов в списке (р) есть грх—г—г-—„ ¡если входная

\1 + 1)\Мг\

грамматика неоднозначная, и 1 если входная грамматика однозначная.

Лемма 6. Операции поиска, добавления и удаления любой ситуации Эрли вида [А -> а* ¡5,к, 1,(р)~\ в любом состоянии Эрли занимают постоянное время.

. Следующая теорема дает оценку вычислительной сложности адаптированного для построения деревьев вывода алгоритма Эрли в терминах объема входной грамматики, ее вехвистостинпротяженности. - ,... ¡,;>. . ..„, , ,

'Теорема'З!! Минимальное время выполнения адаптированного длй, пострбв&яй деревьев ¡вывод; >алгорцима'.-Эрли есть, функция порядка (?(;/> х|£|2 х А/П» .если вхоянаягграмматика

однозначная и СМх|,Р| хМу I если входная грамматика неоднозначная.

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

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

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

функция

дм неоднозначных.

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

Для оценки алгоритма определения порождающих пустую строку нетерминалов грамматики нам необходима следующая

Лемма 7. Пусть нетерминал АеИ порождает пустую строку и минимальная высота дерева вывода этого нетерминала в пустую строку равна Я. Тогда нетерминал А будет добавлен в N€ на Я-ом повторении шага 1 алгоритма определения порождающих пустую строку нетерминалов.

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

Теорема 5. Алгоритм определения порождающих пустую строку! 1 Нетерминалов

выполняется за время о||С|2

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

Теорема 6. Алгоритм преобразования грамматики в эквивалентную ей, грамматику, не

содержащую правил с пустой правой частью выполняется за время 0(]С[) и объем

грамматики С, полученной в результате исполнения алгоритма данного алгоритма, также

равен 0(|С|).

Оценка вычислительной сложности алгоритма преобразования грамматики без правил с пустой правой частью в эквивалентную ей грамматику в нормальной форце. Хомского, а ' т&йз&е оценка'объема полученной в результате исполнения грамматикй, 'дается, в Следующей

Теорема 7. Алгоритм преобразования -грамматики без правил с пустой правой частью в эквивалентную ей грамматику в нормальной форме Хомского выполняется за время <?(|(7|) • Объем выходной грамматики О' есть также величина .

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

Теорема 8. Алгоритм Кока-Янгера-Касами выполняется за максимальное время О^2).

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

Теорема 9. Максимальное время работы алгоритма построения дерева вывода по таблице нетерминальных символов, построенной в результате исполнения алгоритма Кока-Янгера-

Касами есть

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

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

Глава 3

Третья глава посвящена описанию проблем, связанных с построением динамической системы компиляции с использованием адаптированного для построения деревьев вывода алгоритма Эрли. Система динамической компиляции реализована согласно классической модели, при которой процесс синтаксического анализа, с целью упрощения восприятия грамматики языка человеком, разделяется на две фазы: фазу лексического анализа и, собственно, фазу синтаксического анализа. Модуль лексического анализатора обрабатывает входной текст и выдает в результате поток слов-лексем, каждое из которых принадлежит определенному лексическому типу. Каждый лексический тип представлен в модуле синтаксического анализатора как соответствующий терминальный символ входной грамматики. Таким образом осуществляется связь между модулями синтаксического и лексического анализаторов. Также, необходимо рассмотреть вопросы,~ связанные с реализацией взаимодействия между синтаксическим и семантическим анализаторами. Существуют несколько различных способов организации такого взаимодействия, нам необходимо выбрать наиболее приемлемый для анализа открытых интерфейсных языков. . 'Интерфейс модуля синтаксического анализатора совмещает как функции, непосредственно относящиеся к синтаксическому анализатору,' так и функции, позволяющие проводить модификацию входной ' Грамматики.' группа, состоящая--.из • четырех методов: AddTerminalt AddNonterminal, AddRule я SetStartSymbol позволяет проводить модификацию грамматики синтаксического анализатора. Вторая группа методов о i носится, собственно, к реализации синтаксического анализатора. Из них основным является метод Rim, позволяющий производить запуск алгоритма синтаксического анализа на основе добавленных ранее сущностей входной грамматики.

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

списка ситуаций Эрли. Третий элемент - ссылка на некоторую, уже существующую, ситуацию Эрли, представляется парой неотрицательных целых, в которое в качестве первого элемента выступает номер списка ситуаций Эрли, а второго - порядковый номер ситуации в списке. Четвертый элемент - список ссылок на ситуации Эрли, представляется вектором пар неотрицательных целых.

Лексический анализатор реализован в виде отдельного модуля, предоставляющего интерфейс для добавления новых лексических типов и получения из входного текста очередной лексемы., Метод, позволяющий получить очередную лексему от лексического анализатора, традиционно называется GetToken. Обычный сценарий работы с лексическим анализатором строится по следующей схеме: сначала, с помощью метода AddLexType, в лексический анализатор добавляется множество лексических типов. Затем вызывается метод Initialize который инициализирует модуль лексического анализатора входным текстом. Далее, вызывается метод GetToken для взятия очередной лексемы из входного текста.

При реализаций лексического анализатора в виде динамически пополняющейся коллекции лексических типов, необходимо разработать метод представления регулярного языка лексического типа удобный как для человека, так и для представления в памяти программы. Ввиду того, что язык лексического типа является регулярным, удобным для человеческого восприятия кажется определение данного языка в виде регулярного выражения. В связи с этим, как часть модуля лексического анализатора, был разработав компилятор языка регулярных выражений. Синтаксис данного языка представляет один из диалектов языка регулярных выражений для языка программирования Perl. При добавлении нового лексического типа в программу лексического анализатора регулярный язык данного Типа описывается в виде регулярного выражения, передаваемого в процедуру добавления .дариого лексического типа. ¿В, качестве результата. процедура добавления, i возвращает ¡неотрицательное целое, представляющее собой идентификатор добавленного ..лексического типа. Этот идентификатор будет потом возвращен в процессе исполнения алгоритма синтаксического анализа методом GetToken, если во входном тесте была распознана лексема, принадлежащая языку данного лексического типа.

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

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

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

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

Заключение

Основной целью работы являлось исследование особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков. Данную цель можно считать полностью реализованной. Все задачи, поставленные в работе, были выполнены. В качестве главного критерия эффективности работы алгоритма синтаксического анализа для открытого интерфейсного контекстно-свободного языка был предложен метод оценки вычислительной сложности алгоритма как функции от таких параметров входной контекстно-свободной грамматики, как ее объем, ветвистость и протяженность. На основании этого метода, была произведена оценка эффективности семейства 'алгоритмов Кока-Янгера-Касами и семейства алгоритмов Эрли. В работе был ввеДеп новый алгоритм - адаптированный для построения ' дёртвЁев^вывода "алгоритй Эрйи7 # йроведё'но доказательство корректности рзБйты Данного алгоритма. Введенный 'алгоритм также может применяться для "СиНтаксиЧеСкб'го анализа' контекстно-свободных языков, грамматики которых не удовлетворяют каким-либо ограничениям. В частности, адаптированный алгоритм Эрли позволяет производить построение деревьев вывода для языков, заданных неоднозначными грамматиками. Проблема построения всех деревьев вывода для неоднозначных контекстно-свободных языков приобрела особенную актуальность в последнее десятилетие и была решена в общем виде совсем недавно [10]. Однако, подходящего алгоритма синтаксического анализа, позволяющего производить построение всех деревьев вывода анализируемой строки для открытых языков, до настоящего времени не существовало. Адаптированный алгоритм Эрли дает возможность производить такое построение. В данной работе были выделены такие свойства контекстно-свободной грамматики, как объем, ветвистость и протяженность. Представляется интересным исследовать не сохраняются ли эти свойства при естественных преобразованиях грамматик, таких как преобразование исходной грамматики в нормальную бинарную форму или в форму Грейбах [1], и попытаться выделить какие-нибудь инварианты таких преобразований на основе полученных в работе свойств контекстно-свободной грамматики.

Список литературы

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

- Москва: Мир, 1978. - 612 с.

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

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

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

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

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

7. Graham S., Harrison M., Russo W. An improved Context-Free Recognizer//ACM TOPLAS.

- 1980: vol. 2. - № 3. - p. 415-462.

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

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

10. Scott E., Johnstone A., Hussain S. S. Tomita-Style Generalized LR Parsers//Royal Holloway . University of London. - 2000.. . i \

W.-TdmitaiiM1 An Efficient Au^entediConfext-Free Parking Algorithm, -fe ^Pittsburgh: . Carnegie-Mellon Univeisity.-1987.

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

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

Основные результаты диссертации изложены в следующих публикациях:

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

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

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

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

i í

I

í

Формат 60x84 1/16, Усл. Печ. Лист1,5 Тираж 100 экз. Заказ № 2027 Отпечатано «АллА Принт» Тел.: (095) 921-86-07 Факс: (095) 921-70-09 www.allaprint.ru

^0 3 34

РНБ Русский фонд

2006-4 19019

ВВЕДЕНИЕ.

Мотивация.

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

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

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

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

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

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

ГЛАВА 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], семантический анализатор никак не может повлиять на процесс построения дерева разбора. Поэтому, синтаксический анализатор будет производить построение всех деревьев разбора входной строки, а выбор соответствующего дерева разбора будет производиться семантическим анализатором после того, как процесс построения всех деревьев вывода входной строки будет закончен.

Заключение

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

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

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

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

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

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

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.