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

• Автор: Лапшин, Владимир Анатольевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 140 с. : ил.

Содержание
ВВЕДЕНИЕ
Мотивация

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

свободной ГРАММАТИКЕ.

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

синтаксического анализа.

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

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

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

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

ГЛАВА 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 Особенности реализации семантических действий
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Но данное ограничение не является фундаментальным, так как известно (см. КС-грамматика может быть преобразована в данную форму. Конечно, такое преобразование имеет свои неудобства, так как преобразованная грамматика, хотя и эквивалентна исходной, все же имеет другой набор правил и, таким образом, не всегда понятна пользователю. Мы приведем оценку вычислительной сложности данного алгоритма как функции от объема входной грамматики во второй главе. Алгоритм Томиты [, ]. Данный алгоритм является развитием ЬЯ(к) анализатора [2, с. ДКА), построенным в соответствии с данным методом синтаксического анализа, применяются параллельно несколько магазинов. Чтобы оптимизировать хранение состояний и символов грамматики в магазинах, в алгоритме Томиты используется так называемый Магазин, структурированный с помощью графа (МСГ). В [] Томита представил несколько алгоритмов построения МСГ в процессе синтаксического анализа. Но ни один из них не работал корректно для всех типов КС-грамматик без ограничений. Однако, в [] был предложен метод модификации исходного ДКА таким образом, чтобы один из алгоритмов Томиты производил корректный разбор входной терминальной строки. Можно сказать, что модель синтаксического анализатора для данного метода является статической и время, необходимое для выделения статической информации из данной КС-грамматики, довольно велико. Поэтому, оценивать данный метод мы не будем. Алгоритм Эрли, описанный в [, ], а также его модификация, представленная в []. Данный алгоритм представляется наиболее подходящим для наших целей. Он не требует ни предварительного преобразования входной грамматики в специальную форму, как в случае алгоритма Кока-Янгсра-Касами, ни построения ДКА, как в случае алгоритма Томиты. Алгоритм Эрли отвечает на вопрос принадлежит или нет входная терминальная цепочка со языку Ь(р), но не строит вывода данной цепочки в грамматике (7 = {Лг,7/? Поэтому мы построим модифицированный алгоритм Эрли, который назовем адаптированным для построения деревьев вывода алгоритмом Эрли. Этот алгоритм строит множество деревьев вывода непосредственно во время своей работы и работает корректно также и для неоднозначных грамматик. В первой главе данной работы мы определим адаптированный для построения деревьев вывода алгоритм Эрли, докажем его корректность, а также определим алгоритм обхода всех построенных во время исполнения адаптированного алгоритма Эрли деревьев вывода сверху вниз и слева направо. Также, докажем корректность этого алгоритма. Во второй главе мы проведем оценку вычислительной сложности адаптированного для построения деревьев вывода алгоритма Эрли как функции от таких свойств входной грамматики как объем, ветвистость и протяженность. Содержание этих свойств будет определено ниже. Критериями выбора данного алгоритма являются как широта его применимости (данный алгоритм работает для любой контекстно-свободной грамматики без ограничений), так и отсутствие необходимости производить какие-либо дополнительные манипуляции с входной грамматикой до исполнения алгоритма синтаксического анализа и возможность построения всех деревьев вывода входной строки даже и для неоднозначных грамматик. В третьей главе мы опишем проблемы, возникшие при реализации динамической системы компиляции на основе адаптированного для построения деревьев вывода алгоритма Эрли, а также пути их решения. В процессе изучения различных алгоритмов синтаксического анализа было выделено три свойства контекстно-свободной грамматики, которые имеют влияние на вычислительную сложность алгоритмов синтаксического анализа. Эти свойства есть объем грамматики, ее ветвистость и протяженность. Определение 1. Пусть дана КС-грамматика <7 = {Лг,7/>,*? N -нетерминальные символы грамматики, Т - терминалы грамматики, Р -правила грамматики и 5 - начальный символ грамматики. Положим И=И+И, где Щ - количество нетерминалов и |Р| - количество правил грамматики. Величину |С? Определение 2. Пусть С = {ЛГ,Г,Р,5} КС-грамматика и РА - множество правил грамматики О с нетерминальным символом А в левой части.