Содержание к диссертации
Введение
ГЛАВА 1. Адаптированный для построения деревьев вывода алгоритм эрли 22
1.1 Введение 22
1.2 Адаптированный для построения деревьев вывода алгоритм Эрли 34
1.3 Алгоритм построения множества деревьев вывода входной строки по результатам работы адаптированного алгоритма Эрли 52
ГЛАВА 2. Выбор алгоритма синтаксического анализа 60
2.1 Введение. 60
2.1 Оценка вычислительной сложности адаптированного для построения деревьев вывода алгоритма эрли 68
2.2 Оценка вычислительной сложности алгоритма обхода деревьев, построенных в результате исполнения адаптированного алгоритма эрли .. 78
2.3 Оценка вычислительной сложности семейства алгоритмов кока-янгера-касами 80
ГЛАВА 3. Реализация разборщика 97
3.1 Введение 97
3.2 Реализация синтаксического анализатора 101
3.2.1 Интерфейс модуля синтаксического анализатора 101
3.2.2 Организация взаимодействия между модулями синтаксического анализатора 104
3.3 Реализация лексического анализатора 106
3.3.1 Интерфейс модуля лексического анализатора 106
3.3.2 Лексический тип как регулярный язык 109
3.3.3 Лексический тип как детерминированный конечный автомат 116
3.3.4 Алгоритм лексического анализа на основе лексических типов 122
3.4 Особенности реализации семантических действий 128
Заключение 133
Литература
- Адаптированный для построения деревьев вывода алгоритм Эрли
- Алгоритм построения множества деревьев вывода входной строки по результатам работы адаптированного алгоритма Эрли
- Оценка вычислительной сложности алгоритма обхода деревьев, построенных в результате исполнения адаптированного алгоритма эрли
- Организация взаимодействия между модулями синтаксического анализатора
Введение к работе
Актуальность темы работы
В последнее время большое значение приобрела задача построения синтаксических анализаторов для так называемых открытых контекстно-свободных языков, т.е. языков, задаваемых контекстно-свободной грамматикой, которая может быть расширена путем добавления новых сущностей, таких как нетерминальные и терминальные символы, а также правила грамматики. И расширение это может быть произведено произвольно между исполнениями алгоритма синтаксического анализа. Подобная ситуация часто встречается в языках интерфейса к системам представления знаний [2-4]. В таких системах множество понятия может расширяться, и вместе с каждым новым понятием удобно также вводить новые синтаксические элементы языка интерфейса данной системы, связанные с добавляемым понятием. Таким образом, расширение языка интерфейса производится вместе с расширением понятийной базы и позволяет пользователю общаться с системой на языке, специализированном в соответствии с областью знаний, в которой данный пользователь производит моделирование. В этом случае, алгоритм синтаксического анализа не только помогает системе «понять» команды пользователя но и отражает различные изменения понятийной базы. Поэтому имеет смысл говорить об открытых интерфейсных языках, или об интерфейсных языках открытого типа. Такие языки имеют следующие особенности:
-
В силу того, что язык является интерфейсным, входная терминальная строка для алгоритма синтаксического анализа имеет сравнительно небольшую длину.
-
В силу открытости языка и алгоритмической неразрешимости задачи распознавания однозначности КС-грамматики никакие ограничения на входную КС-грамматику наложить невозможно. * * *
-
В силу возможности расширения интерфейсного языка новыми сущностями, входная для алгоритма синтаксического анализа КС-грамматика часто имеет очень большое число сущностей по сравнению с длиной входной строки.
Синтаксический анализатор можно представить как вычислимую функцию Parse двух аргументов:
КС-грамматики G = {N,T,P,S), где N - нетерминальные символы языка, Т -терминалы, Р - правила языка и S - стартовый нетерминальный символ грамматики.
Входной строки m = л,..л„ длины |а>| = п, где а, є Т 1 ; < л.
Функция Parse производит построение и выдает в качестве результата множество деревьев вывода ТгСя (или единственное дерево, если грамматика G однозначная) входной строки а> в грамматике С, если она принадлежит языку L(G), заданному грамматикой G, или false - в противном случае.
В традиционной задаче построения синтаксического анализатора, см. например [1] (в дальнейшем мы будем следовать терминологии, введенной в данной книге), при вызовах функции Parse меняется только один параметр - входная строка ю. Функция Parse в этом случае имеет вид Parsec(a>). Поэтому анализ производительности естественно было
представлять как оценку функции EvQ(ri), где п - длина входной цепочки а», т.е. как зависимость производительности алгоритма от длины входной строки. Так как для данной контекстно-свободной грамматики G = {N,T,P,S) может существовать много различных
строк длины л, то мы разбиваем множество тйрвналНайкИОрШЧ'* М классы а>" равных
СПетеї
&>
по длине строк. Каждый такой класс а" терминальных строк длины \а>\ = п и представляется числом п. Функция EvG (и), определенная на множестве натуральных чисел N*, берет и в качестве параметра и выдает максимальное время анализа, выраженное в элементарных операциях, которые алгоритм анализа производит над сущностями грамматики G.
Главной целью данной работы является выяснение особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков. Эти особенности, очевидно, определяются свойствами языков, для которых производится синтаксический анализ. Эти свойства, в свою очередь, должны проявляться в особенностях грамматик, задающих данные языки. Выше были перечислены основные особые свойства таких грамматик. Но этого недостаточно, необходимо строго определить параметры грамматики, определяющей открытый интерфейсный язык, имеющие влияние на производительность алгоритма синтаксического анализа. Такие параметры будут определены немного позже: это объем грамматики, ее ветвистость и протяженность. Сейчас же нас интересует вопрос, каким образом можно выразить степень влияния этих параметров на алгоритм синтаксического анализа? Наиболее естественным представляется выразить степень влияния в параметрах вычислительной сложности алгоритма синтаксического анализа, что и сделано в настоящей работе. Для выяснения степени влияния особенностей открытого интерфейсного языка на алгоритм синтаксического анализа проведено исследование вычислительной сложности алгоритма определенной выше вычислимой функции Parse. Для того, чтобы не отвлекаться на несущественные детали, мы зафиксируем второй параметр функции Parse - входную строку т = в,...в,. Поэтому функция Parse{G,a) от двух параметров примет вид Parsea (G) от единственного параметра - входной контекстно-свободной грамматики G.
Таким образом, оказывается, что для выяснения особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков необходимо произвести оценку вычислительной сложности каждого алгоритма синтаксического анализа, который может быть использован для анализа открытых интерфейсных языков. Для этого сначала попытаемся выяснить, какие из известных в настоящее время алгоритмов синтаксического анализа подходят для анализа открытых интерфейсных языков. Затем из них выберем наиболее подходящий и попытаемся адаптировать его так, чтобы новый полученный алгоритм являлся, по возможности, наиболее оптимальным для синтаксического анализа открытых интерфейсных языков. На основании проведенной в данной работе оценки было выбрано два алгоритма: алгоритм Эрли [5-6] и алгоритм Кока-Янгера-Касами [8, 13]. Для использования алгоритма Кока-Янгера-Касами необходимо привлечь еще несколько алгоритмов, поэтому в данной работе приведено пять алгоритмов семейства алгоритма Кока-Янгера-Касами и проведена оценка их вычислительной сложности в терминах описанных выше параметров входной грамматики.
Особая ситуация возникла с алгоритмом Эрли. Данный алгоритм не строит деревьев вывода входной строки, но дает ответ лишь на вопрос выводится или нет данная входная строка в данной грамматике. Для наших же целей необходимо произвести построение всех деревьев вывода данной строки. Для этого в данной работе строится модификация алгоритма Эрли таким образом, чтобы он производил построение всех деревьев вывода входной строки во время своего исполнения. Заметим сразу, что эта задача достаточно трудна, и особенно, для неоднозначных грамматик. Достаточно отметить, что в разные годы ее пытались решить разные исследователи. Например, в начале 80-х годов Масари Томита пытался решить проблему построения всех деревьев вывода входной строки для неоднозначных грамматик, задающих естественные языки [12]. Это ему не удалось, поэтому Томита произвел модификацию известного алгоритма LR (к) -анализа [9]. Данная модификация теперь
известна как алгоритм Томиты или алгоритм GLR [11-12]. Известные в данное время реализации алгоритма Эрли [5-7] не производят построения дерева вывода входной строки вообще или производят такое построение только для однозначных грамматик. В данной
работе представлена модификация алгоритма Эрли, позволяющая строить все деревья вывода входной строки. Данная модификация названа адаптированным для построения деревьев вывода алгоритмом Эрли. В работе также произведена оценка вычислительной сложности функции Parse„(G), реализованной посредством адаптированного алгоритма Эрли, в терминах упоминавшихся выше параметров входной грамматики.
Цели диссертационной работы
Основное содержание работы состоит в исследовании особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков. Цели этого исследования заключаются в следующем:
На основе проведенного исследования особенностей синтаксического анализа открытых интерфейсных контекстно-свободных языков выделить метод оценки эффективности работы алгоритмов синтаксического анализа для таких языков. В качестве главного критерия такой оценки была выбрана вычислительная сложность алгоритма как функция от некоторых, определяемых в диссертационной работе, параметров входной контекстно-свободной грамматики.
Используя найденный метод оценки эффективности, провести сравнительный анализ существующих алгоритмов, подходящих для синтаксического анализа открытых интерфейсных контекстно-свободных языков.
- На основании проведенной оценки алгоритмов синтаксического анализа, выделить
наиболее подходящий для синтаксического анализа открытых интерфейсных контекстно-
свободных языков алгоритм синтаксического анализа.
На основании вышеуказанных целей диссертационной работы были поставлены следующие задачи:
Определить те параметры контекстно-свободной грамматики, которые влияют на вычисшггельную сложность алгоритмов синтаксического анализа. Таким образом, были выделены следующие параметры контекстно-свободной грамматики, влияющие на вычислительную сложность алгоритмов синтаксического анализа: объем грамматики, ее ветвистость и протяженность.
Выделить алгоритмы, подходящие для синтаксического анализа открытых интерфейсных контекстно-свободных языков, и провести оценку их вычислительной сложности как функции от объема, ветвистости и протяженности входной контекстно-свободной грамматики. Таким образом, в качестве основных кандидатов, были выделены алгоритм Кока-Янгера-Касами и алгоритм Эрли. Также была проведена оценка их вычислительной сложности как функции от выделенных ранее параметров входной грамматики.
Если при выборе наиболее подходящего для синтаксического анализа открытых интерфейсных контекстно-свободных языков алгоритма не будет найден подходящий, то попытаться создать новый алгоритм либо путем модификации какого-либо из известных алгоритмов синтаксического анализа, либо новый, приспособленный специально для анализа этого типа языков. С этой целью в работе был описан адаптированный алгоритм Эрли, а также было проведено доказательство корректности работы данного алгоритма.
После выбора наиболее подходящего для синтаксического анализа открытых интерфейсных контекстно-свободных языков алгоритма, необходимо реализовать его в виде системы динамической компиляции, которая позволит производить синтаксический анализа языков, задаваемых пополняющимися КС-грамматиками.
Методы исследований
Одним из основных методов исследования был анализ существующих алгоритмов синтаксического анализа на предмет широты их применимости, возможности построения выводов входных строк во входной для алгоритма контекстно-свободной грамматике и
производительности алгоритма как функции от выделенных на этапе исследования свойств КС-грамматики.
Другим методом исследования был метод оценки вычислительной сложности алгоритмов синтаксического анализа, где в качестве параметром для оценки выступали специфические свойства входных контекстно-свободных грамматик. Эти свойства также были определены в данной работе и есть объем, ветвистость и протяженность КС-грамматики.
И наконец, в работе используются методы описания формальных грамматик и описания алгоритмов синтаксического анализа для доказательства корректности работы алгоритмов.
Научная новизна
Все результаты диссертации являются новыми. Новым также является подход к задаче оценки вычислительной сложности алгоритмов синтаксического анализа. В качестве параметров оценки вычислительной сложности алгоритмов в данной работе выступает не длина входной строки, как это обычно производится при представлении новых алгоритмов синтаксического анализа, а параметры, выражающие характеристики входной грамматики. Определение таких характеристик также являлось целью данной работы и, в качестве результата, были выделены три характеристики: объем грамматики, ее ветвистость и протяженность.
В результате исследования был выделен наиболее подходящий для синтаксического анализа открытых интерфейсных языков алгоритм синтаксического анализа. Это алгоритм Эрли для распознавания выводимости входной терминальной строки во входной грамматике. Но, так как данный алгоритм не строит деревья вывода входной строки, а только отвечает, выводится или нет данная строка в данной грамматике, то была произведена модификация данного алгоритма и, таким образом, был получен новый алгоритм, названный адаптированным для построения деревьев вывода алгоритмом Эрли. Данный алгоритм применим к анализу неоднозначных контекстно-свободных языков. В работе впервые доказана корректность работы алгоритма, построенного автором.
Новым результатом также является полученная в работе оценка вычислительной сложности алгоритмов синтаксического анализа как зависимости от параметров входной контекстно-свободной грамматики.
Практическая и теоретическая ценность
Диссертационная работа имеет теоретический характер. В процессе исследования проведен обзор существующих в настоящий момент алгоритмов синтаксического анализа и предложен новый алгоритм, наиболее подходящий для синтаксического анализа открытых контекстно-свободных языков. На основе полученных в данной работе теоретических результатов была реализована система динамической компиляции. До настоящего времени не существовало подходящего алгоритма, позволяющего производить синтаксический анализ открытых контекстно-свободных языков. Поэтому, результаты, полученные в данной работе предоставляют инструмент для построения анализаторов для открытых КС-языков.
В данной работе также был предложен метод оценки вычислительной сложности алгоритмов синтаксического анализа и алгоритмов, производящих различные преобразования контекстно-свободных грамматик. На основании этого метода была произведена оценка нескольких, наиболее подходящих для анализа открытых интерфейсных языков, алгоритмов синтаксического анализа. Данный метод дает возможность оценки применимости тех или иных алгоритмов синтаксического анализа для анализа контекстно-свободных языков, имеющих большое число сущностей.
В работе была реализована система динамической компиляции на основе адаптированного для построения деревьев вывода алгоритма Эрли. Система представляет собой синтаксический анализатор с разделением процесса синтаксического анализа на два процесса: лексического и синтаксического анализа, на основе динамически пополняемых множества лексических типов и множества сущностей входной грамматики. Данная система
может применятся как генератор синтаксических анализаторов для динамически пополняемых языков, а также как синтаксический анализатор для языков интерфейса программных систем.
Апробация работы
Результаты работы были доложены:
на семинаре отдела систем математического обеспечения Вычислительного Центра РАН под руководством д. ф.-м. н. Серебрякова В. А.
на семинаре отделения научных исследований по проблемам информатики Всероссийского института научной и технической информации под руководством д. ф. н. Гиляревского Р. С.
Публикации
Основные результаты данной работы опубликованы в работах [1-4] списка опубликованных работ.
Объем работы
Диссертация содержит 140 страниц и состоит из введения, трех глав и списка литературы, содержащего 56 названий.
Адаптированный для построения деревьев вывода алгоритм Эрли
В данном разделе будет описан алгоритм, представляющий собой расширение оригинального алгоритма Эрли путем изменения составляющих элементов ситуации Эрли, как это определено ниже, и добавлением в алгоритм Эрли операций для работы над расширенными компонентами. Также, будет приведено доказательство корректности работы алгоритма. Сначала дадим формально некоторые определения понятий, которые были описаны неформально выше.
Пусть G = {N,T,P,S] - контекстно-свободная грамматика произвольного вида, где N - множество нетерминалов, Г-множество терминалов, Р -множество продукций и S -стартовый символ.
Определение 4. Пусть даны грамматика G = {N,T,P,S} и символ N[JT. Для каждой продукции - а/? є Р, гдеа 0 и /? 0, выражение вида Л -» а fi назовем помеченным правилом грамматики G. Таким образом, помеченное правило это правило грамматики с точкой в правой части.
Оригинальный алгоритм Эрли производил операции над специальными элементами - ситуациями Эрли. Оригинальная ситуация Эрли состояла из трех компонентов: помеченного правила грамматики, номера состояния Эрли, с которого началось распознавание данного правила, и терминальной строки предосмотра некоторой фиксированной длины. Мы модифицируем оригинальное определение ситуации Эрли путем введения двух дополнительных компонентов. Также, как показано в [41], использование предосмотров в алгоритме Эрли влияет только на операцию Predictor и не дает сколько-нибудь значащих преимуществ. Поэтому этот компонент использоваться не будет.
Определение 5. Ситуацией Эрли назовем четверку [Л- а»у9,/,/,{ }], где Л —» а р - помеченное правило грамматики G, О й / й Ы - некоторое число, / - ссылка на ситуацию Эрли и (/7)- список ссылок на ситуации Эрли.
Элементы / и {/ ) в определении ситуации Эрли имеют следующий смысл: если [A- aB p,i,l,{p) \ - ситуация Эрли, то / ссылается на ситуацию вида \А - а Bfi,i,l ,(p) , где точка в помеченном правиле стоит на символ левее. Каждый элемент р списка {р) ссылается на ситуацию вида
В - у»,У,/ ,(р) , с символом В в левой части правила и точкой в конце правой части помеченного правила. Определим теперь эквивалентность ситуаций Эрли. Определение 6. Две ситуации Эрли [Л- а /?,/,/,(/?)] и В- у54,1\{р) будем считать эквивалентными только и только, если Л-»а«/? = B- ydt i= j и I - V.
Алгоритм Эрли состоит в построении списка неэквивалентных ситуаций Эрли для каждого элемента входной терминальной строки, а также, для нулевой позиции при чтении входной строки. Формализуем данное построение в следующем определении.
Определение 7- Состоянием Эрли будем называть список неэквивалентных ситуаций Эрли, которому дан в соответствие некоторый номер 0 / \а \.
Замечание 1. Для оптимизации исполнения операции Predictor для каждого нетерминального символа А входной грамматики G будем держать список его альтернатив, т.е. правил вида А -» а с нетерминалом А в левой части.
Замечание 2. Если входная грамматика G не содержит правил с пустой правой частью (так называемых, є - правил), то возможно организовать работу алгоритма Эрли таким образом, чтобы каждая ситуация Эрли в некотором состоянии Эрли обрабатывалась каждой из процедур Scanner, Completer и Predictor только один раз, т.е. чтобы алгоритм Эрли работал без возвратов. Если входная грамматика G содержит правила вида А- А, то алгоритм может работать некорректно. Действительно, если Completer
добавляет в некоторое состояние Эрли ситуацию Эрли вида ПЛ-»,,/,{/?)"], алгоритм также должен добавить в данное состояние все ситуации вида
В-аА»р,т,Г,{р) , где ситуация B CfAfi,m,r,(p) уже принадлежит данному состоянию Эрли, Но, некоторые из таких ситуаций могут быть еще не добавлены в данное состояние. Поэтому, для обеспечения корректной работы алгоритма Эрли, необходимо эту проблему каким-то образом разрешить. Существует много методов решения данной проблемы: Эрли, в своей диссертационной работе [45], советовал каждый раз, когда в состояния Эрли добавляется ситуация вида [A— ;k,lJpY\ запоминать нетерминал Л и, при добавлении последующих ситуаций, проверять в них помеченные правила на предмет того, не находится ли точка в правой части правила перед таким нетерминальным символом. И, если находится, то добавлять в грамматику также и ситуацию, в которой точка находится после этого нетерминала. Мы будем следовать рекомендации Эрли.
Алгоритм построения множества деревьев вывода входной строки по результатам работы адаптированного алгоритма Эрли
Как было указано выше, в целью алгоритма 1 является проверка факта, выводится или нет входная терминальная строка в данной грамматике. Разбор входной строки не строится. Но, в процессе исполнения алгоритма 1, который представляет собой модификацию оригинального алгоритма Эрли, фактически, производится построение всевозможных деревьев разбора входной терминальной строки. Компонент / ситуации [A- Xl...Xi»Xk+{...Xm,j,l,(ip) ], которая является узлом дерева разбора, помеченным символом Хк, ссылается на левый узел того же уровня, что и узел Хк, помеченный символом Хк_г Если символ Хк, это нетерминал входной грамматики G = {N,T,P,S}\ то список (р) содержит ссылки на ситуации «нижнего» уровня, которые представляют различные способы вывода Хк= а ...ап для некоторых р и і. Если символ Хк является терминальным, то узел, помеченный символом Если символ Хк, представляет собой лист, дерева разбора. Ниже мы приведем алгоритм, который, по построенным, в процессе исполнения алгоритма 1, множествам ситуаций Эрли, производит обход построенных деревьев, обрабатывая каждый уровень слева направо и, таким образом, строя множество левых выводов входной строки, соответствующих построенным в процессе исполнения алгоритма 1, деревьям. Алгоритм 2. Вход: 1. Контекстно-свободная грамматика G = {N,T,P,S], где Л - множество нетерминалов, Т - множество терминалов, Р - множество продукций и S - стартовый символ. 2. Вектор V размера и + 1 состояний Эрли построенный в процессе выполнения алгоритма 1 для данной входной строки. Выход: 1. Множество деревьев разбора TrGul представляющее множество левых разборов строки со или сообщение об ошибке. Метод:
Если в К [и] нет ни одной ситуации вида [S -»а; О,1,(р} \, то coeL(G) И выходом будет ошибка. В противном случае положить TrGa) = {{5)}, где (5) - корневой узел дерева разбора, соответствующий ситуации [S — a;0,lUp)l, положить в список SI, соответствующий данному дереву, ссылку на ситуацию fs- a;0J,(pf\ и выполнить рекурсивную процедуру Restore [5- a«,0,/,(;?)],{s), [(5),5/] ) для каждого элемента множества ТгСб) = {(5)}. Рекурсивная процедура Restore определяется следующим образом: Параметры: 1. [ - Х,...Х1!«,/,/, )]-ситуацияЭрли. 2. Р - родительский узел в дереве разбора ТгСш, 3. [(5),5/] - пара, состоящая из (5) - корневой узел дерева разбора, которому принадлежит узел Р и 5/ - список ссылок на ситуации, которые уже были обработаны процедурой Restore при построении дерева (S). procedure Restore[\_A -» Xl...Xm;i,l,{p} ],P,[(s),Sl ]) { Шагі. Положить локальный для данного вызова процедуры магазин v = 0. Положить ref = \_А- Xt...Xm;i,l,{p) . Шаг 2. Повторять шаг 3, пока ref! = null. После этого перейти к шагу 4. ШагЗ. Пусть ref А х1.„хк.хш...хт;,г,(р) Если, XkeN, тогда втолкнуть список (р) в магазин v. В противном случае, ХкєТ. Втолкнуть символ Хк в магазин v. Положить ref = I . Шаг 4.
Повторять шаги 5-6 пока не пуст магазин v. Шаг 5. Выталкиваем элемент магазина v, если это символ Хк є Г, то создать листовой узел, помеченный Хк, в дереве (5) и сделать его дочерним узлом узла Р. Иначе, это список (р),- Тогда, создать копию (5) дерева (5) и копию SI списка iS7. Для каждого элемента р списка (/?) , ссылки на который нет в списке SI , проделать шаг 6. После чего удалить (5) и-SI .. Шаг б. Пусть р = \Хк — гр ,1",1р) I. Если это первое исполнения шага 6 в данном вызове процедуры Restore, то создать в дереве (S) узел Р , помеченный-символом Хк, сделать его дочерним узлом узла Р, добавить р в список SI, и вызвать процедуру
Restorel \:Xk- rj;/,/ ,(/?) L.P , [(5),5/] . В противном случае, создать копию (5) дерева (5) и копию SI" списка 5/ , создать в дереве (5) узел Р , помеченный символом Хк, сделать его дочерним узлом узла Р, добавить р в список SI", и вызвать процедуру Restorel \xk Tj;t,r,{pf , Р\ {S} ,St" J. } Для доказательства корректности работы алгоритма 2 необходимо: 1. Показать, что алгоритме всегда заканчивает свою работу за конечное число шагов. 2. Показать, что алгоритм 2 строит множество всех деревьев вывода входной строки о) - а, ...ап. Покажем сначала, что алгоритм 2 всегда заканчивает свою работу за конечное число шагов. Лемма 4. Алгоритм 2 всегда заканчивает свою работу за конечное число шагов.
Действительно, ввиду леммы 2, каждое состояние Эрли содержит ограниченное число ситуаций. Поэтому, в каждом списке SI может быть также ограниченное число ситуаций. Количество элементов в каждом списке {/ ), ситуации уА- - Xv..Xm ,iJ,{p\\, обрабатываемой процедурой Restore, также ограничено количеством ситуаций, принадлежащих одному состоянию Эрли. Поэтому, предполагая, что в каждом вызове процедуры Restore создается несколько копий списка Si для каждого нетерминального узла Xt, правила А- Xv..Xm, мы; все равно получим конечное число списков SL Это, в совокупности, дает нам конечное число шагов алгоритма 2.
Теорема 2. Алгоритм 2 по результатам работы алгоритма 1, примененного к терминальной строке co = av..a„ и КС-грамматике G = {N,T,P,S], строит множество всех деревьев вывода данной терминальной строки со = av..a„.
Как мы уже показали, алгоритм 2 всегда заканчивает свою работу за конечное число шагов. Покажем теперь ,что алгоритм 2 корректно строит все деревья разбора входной строки со. Т.е. что, если существует некоторый вывод S=$ at...an, то алгоритм 2 обязательно построит дерево TrGe , соответствующее данном выводу. Пусть k = S at...an некоторый вывод входной строки a) = av..an. Как известно (например [2, с. 164]), для данного вывода существует дерево, соответствующее этому выводу. Обозначим его через Тк. Покажем ,что алгоритм 2, в процессе своей работы, построит дерево вывода TrGa i равное дереву Тк. Доказательство будем вести индукцией по порядку вызовов процедуры Restore.. База индукции. Так как Тк - это дерево вывода входной строки со = о, ...а„ в грамматике G = {N,T,P,S}, то его головной узел должен быть помечен начальным нетерминальным символом S грамматики G. Покажем, что алгоритм 2 также строит деревья, головным узлом каждого из которых является нетерминал S. Действительно, первым шагом алгоритма 2 перед вызовами процедуры Restore будет создание деревьев и добавление в каждое дерево головного узла, помеченного нетерминалом S. Пусть дочерние узлы узла, помеченного символом S в дереве вывода Тк есть Хх.„Хк. Покажем, что существует ситуация \S Xv..Xk;,l,(pj\, принадлежащая состоянию КПюП, с которой в качестве параметра будет вызвана процедура Restore.
Оценка вычислительной сложности алгоритма обхода деревьев, построенных в результате исполнения адаптированного алгоритма эрли
В данном разделе мы оценим вычислительную сложность алгоритма 2, который, по построенным, в процессе исполнения алгоритма 1, множествам расширенных ситуаций Эрли, производит обход. построенных деревьев, обрабатывая каждый уровень слева направо и, таким образом, строя множество левых разборов, соответствующих построенным в процессе исполнения алгоритма 1, деревьям.
При оценке вычислительной сложности алгоритма мы, также как и при оценке алгоритма 1; будем считать элементарными все операции с расширенной ситуацией Эрли, а также, элементарные операции, при манипуляции со списками расширенных ситуаций Эрли - состояниями Эрли. Кроме того, в процессе исполнения алгоритма 2 происходит манипулирование содержимым магазина, в котором хранятся ситуации Эрли, эти операции мы также будем считать элементарными.
Теорема 4. Максимальное время выполнения алгоритма 2 есть функция 0(РхМр) для однозначных грамматик и функция оП х/ хМ " ] для неоднозначных.
Оценим время, затрачиваемое на вызов процедуры Restore. Каждую из операций шагов 2 и 3 можно считать постоянными. Максимальное количество повторений шага 3 равно МР. Количество повторений шага 5 также равно Мр. На шаге 5 производится для каждого элемента списка (/?) производится поиск по элементам списка
Ввиду того, что максимальное количество элементов в списке известно, возможно организовать список в виде битового вектора, каждый элемент которого: является признаком присутствия данной ситуации в списке. Таким образом, проверку на присутствие данной ситуации в списке можно организовать за; постоянное время. Максимальное количество элементов в списке (/?) есть, в силу леммы 2, 1 для однозначных грамматик и FPX\G)\X±——- - для неоднозначных. Поэтому, время выполнения процедуры Restore есть функция порядка МР для однозначных грамматик и Fp хМр хky x- -j—-——х- для неоднозначных.
Теперь оценим количество вызовов процедуры Restore. Максимальное количество ситуаций с точкой в конце правой части помеченного правила во всех состояниях Эрли К[/], 0 » есть / J с J »J для однозначных грамматик и Рхй х -.——У- для неоднозначных. Поэтому, в каждом списке SI также может быть ,,-.,2 її і 2 (JWP 4-ІСУІ)! максимум элементовРхй)[ для однозначных и яхр :х -г—— ІСУ I » 1 К р Ш для неоднозначных грамматик. Для того, чтобы найти, максимальное количество списков 5/, которые могут быть построены во время исполнения алгоритма 2, заметим ,что на каждом исполнении процедуры Restore может порождаться максимум Fp х х (Мр+\со\)\ (о\\Мр\ списков. Поэтому, умножив максимальное количество ситуаций в списке на максимальное количество списков, получим максимальное количество вызовов процедуры Restore. Это число есть рхй для однозначных грамматик и: . . . Г (М.+Ш . . (Мр+\а \)\ \РЫш х -,—— -xFpx GJ х-Ц—;——— для неоднозначных. 1,11 \й \Шр\ F \ о\\МР\
Умножив количество вызовов процедуры Restore на время исполнения одной процедуры, получим время исполнения алгоритма 2, т.е. это время равно 0([.Pxu)j,xMf V для однозначных грамматик и 1Г2 (МР+\б \)\ . . (МР+\со\)\ . . (Мр+\а \)\ Н И х хКхшх\ ; х рхМ„хУх\ и = 1111 Ы!МР! \ о\\Мр\ F f \(й\тр\ О х х/г/хМ 4):
Алгоритм Кока-Янгера-Касами был определен в работах [47, 54]. Мы будем рассматривать наиболее известную интерпретацию этого алгоритма определенную в [2, с. 353]. Там же можно найти доказательство корректности, как первого, так и второго алгоритмов.
Алгоритм Кока-Янгера-Касами берет на вход грамматику в так называемой нормальной форме Хомского. Определим данное понятие строго [2, с. 176].
Определеннее. Грамматика G = {N,T,P,S] называется, грамматикой в нормальной форме Хомского (или в бинарной нормальной форме), если каждое правило из Р имеет один из следующих видов: 1. А-ВС, где A,B,CGN.
Организация взаимодействия между модулями синтаксического анализатора
Для более надежной организации работы модуля синтаксического анализа необходим разбить его, по крайней мере, на два подмодуля.
Первый І подмодуль, который будет хранить информацию касательно входной грамматики, будет называться модулем грамматики и будет реализован в виде отдельного объекта Grammar. Приведем описание методов; данного модуля.
1. AddTerminal производит добавление нового терминального символа в грамматику, представляемую данным объектом Grammar. Метод берет два параметра: имя терминального символа и неотрицательное целое, возвращенное модулем лексического анализатора при добавлении лексического типа, представляющего данный терминальный символ, в коллекцию лексических типов модуля лексического анализатора. В качестве значения метод возвращает целое число - идентификатор данного терминального символа в данной грамматике.
2., AddNonterminal производит добавление нетерминального символа в грамматику, представленную;данным объектом Grammar. В качестве единственного параметра метод получает имя нетерминального символа. Метод возвращает неотрицательное целое число, являющееся идентификатором данного нетерминального символа в данной грамматике.
3. AddRule производит добавление правила в грамматику, представленную данным объектом Grammar. Метод берет два параметра: имя нетерминала в левой части правила и списке имен, символов грамматики в правой части правила. Все символы грамматики должны быть уже добавлены в грамматику с помощью описанных выше методов. Метод возвращает неотрицательное целое, представляющее собой идентификатор данного правила в данном объекте Grammar.
4. SetStartSymbol устанавливает нетерминал, чье имя передается как параметр метода, как начальный нетерминальный символ грамматики. В качестве значения метод возвращает идентификатор данного нетерминала в грамматике, представленной данным объектом Grammar.
5. Clear производит очистку грамматики, т.е. удаление всех нетерминальных и терминальных символов, а также правил грамматики.
Реализация объекта Grammar показана на рисунке ниже.
Модуль синтаксического анализатора Parser содержит в качестве подобъектов модуль лексического анализатора и объект Grammar. Во время исполнения метода Run модуль синтаксического анализатора оперирует объектами Item, которые представляют собой реализацию ситуации Эрли на уровне модуля синтаксического анализатора. Каждый объект Item, представляющий правило [A- a fi,iJ»(p}\ содержит идентификатор правила А ар - неотрицательное целое число, которое было возвращено методом AddRule при добавлении данного правила в объект Grammar, номер позиции точки в правой части помеченного правила А—»а /?,. номер состояния Эрли /, ссылку / как пару (номер состояния Эрли, номер ситуации
Эрли в данном состоянии Эрли) и список ссылок (р\, также, как: и для ссылки 7, представленных парами (номер состояния, номер ситуации). Также объект Item содержит правило грамматики в виде вектора символов входной грамматики, что дает возможность сравнивать символы после точки в правой части правила при осуществлении операций алгоритма Эрли. Подробное описание реализации внутренних структур данных модуля синтаксического анализатора мы здесь не приводим.
Как уже упоминалось выше, лексический анализатор можно представить как распознаватель слов. Каждое из них принадлежит определенному классу, называемому лексическим типом. Лексический тип имеет номер, который представлен в синтаксическом анализаторе как обозначение терминального символа. Фактически, лексический тип представляет собой регулярный язык. В процессе чтения входного текста, лексический анализатор распознает, какому классу принадлежит данная часть текста, которую, обычно, называют словом или токеном. Лексический анализатор возвращает в качестве распознанного терминального символа лексический тип данного слова, семантическим атрибутом которого является распознанный текст. Часто, когда все лексические типы языка известны заранее, т.е. если язык не является открытым, конкретному лексическому типу привязывают специальную функцию, проводящую преобразование распознанного текста в соответствии с семантикой данного лексического типа., Например, если лексический тип представляет собой вещественное число, то распознанный текст преобразуется в соответствующее вещественное число, записанное в формате платформы реализации лексического анализатора.
