Вопросы сложности анализа конъюнктивных грамматик

• Автор: Охотин, Александр Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 240 с.

Оглавление
1 Введение

2 Определения и простейшие свойства

2.1 Грамматика

2.2 Формулы
2.3 Вывод

2.4 Длина вывода

2.5 Дерево вывода

2.6 Линейные конъюнктивные грамматики

2.7 Однозначные и неоднозначные грамматики

3 Выразительные возможности конъюнктивных

грамматик
3.1 Грамматики для классических не-контекстно-свободных языков
3.2 Грамматики для некоторых других абстрактных языков
3.3 Построение грамматик для языков всех вычислений данного вычислительного устройства
3.4 Грамматики для простейших языков программирования
4 Нормальные формы
4.1 е-конъюнкты
4.2 Единичные конъюнкты
4.3 Бинарная нормальная форма
4.4 Линейная нормальная форма
5 Распознавание и синтаксический анализ
5.1 Алгоритм для грамматик в бинарной нормальной форме .
5.2 Алгоритм для грамматик в линейной нормальной форме .
5.3 Алгоритм для грамматик общего вида
5.4 Алгоритм для линейных грамматик общего вида

Оглавление

5.5 Алгоритм нисходящего разбора
5.6 Метод рекурсивного спуска
5.7 Алгоритм восходящего разбора
5.8 Сравнение алгоритмов синтаксического анализа
6 Задача принадлежности
6.1 Полиномиальное решение задачи принадлежности
6.2 P-полнота задачи принадлежности
6.3 Р-полнога задачи принадлежности для линейных
конъюнктивных грамматик
7 Задача генерации строк
7.1 Постановка задачи как задачи распознавания свойств . . .
7.2 Сложность для конъюнктивных и линейных
конъюнктивных грамматик
7.3 Сложность задачи для распространённых вычислительных устройств
7.4 Анализ результатов
8 Вопросы описательной сложности
8.1 Терминология
8.2 Описание контекстно-свободных языков конъюнктивными грамматиками
8.3 Нерекурсивная оценка роста описательной сложности . . .
9 Дополнительные вопросы
9.1 Неразрешимые задачи
9.2 Сложность распознавания конъюнктивных языков по памяти
9.3 Связь с другими семействами языков
9.4 Рост длин строк из конъюнктивных языков
9.5 Конъюнктивные грамматики и системы языковых уравнений
10 Заключение
А Генератор синтаксических анализаторов Whale Calf
А.1 Введение
A.2 Написание грамматики
А.З Использование сгенерированных анализаторов
А.4 Алгоритмы синтаксического анализа
А.4.1 Табличный алгоритм для произвольных грамматик
А.4.2 Нисходящий конъюнктивный алгоритм SLL(&) . . .
Оглавление
А.4.3 Восходящий конъюнктивный 1^11-анализ
А.4.4 Алгоритмы для грамматик в нормальных формах .
Глава, 3. Выразительные возможности конъюнктивных грамматик
Индукционный переход п —> п + 1. Пусть строка имеет вид и' = аи (случай и' = Ъи рассматривается аналогично). Рассмотрим произвольную строку V £ Е*. Из (3.1) легко получаем, что аиси £ Ь(К) тогда и только тогда, когда ист £ Р) и ист € Ь{К). Из принадлежности строки иси языку Ь{Р) следует, что
V = хау (х £ £*, у = }и|) (3.3)
С другой стороны, строка иси, согласно предположению индукции, принадлежит Ь(К) тогда и только тогда, когда
у = хи (х Е Е*) (3.4)
Объединяя (3.3) и (3.4), получаем, что
аист = аисхау = аисхаи = и'схи' = и'сг'и' (х1 Е Е*) (3.5)
Наконец,
{хсу ] х,у Е {а, 6}*, |т| = |р|}П {исхи} = {юст ю Е {а, &}*} (3.6)
В [53] доказывается, что язык {гусго (ю £ {а, 6}*} не может быть представлен в виде пересечения конечного числа контекстно-свободных языков. С другой стороны, очевидно, что любое такое пересечение порождается некоторой конъюнктивной грамматикой. Поэтому семейство конъюнктивных языков строго включает в себя замыкание семейства контекстно-свободных языков относительно пересечения.
3.2 Грамматики для некоторых других абстрактных языков
В этом разделе будут построены конъюнктивные грамматики для некоторых представляющих интерес абстрактных языков. Методы построения грамматик, рассматриваемые в этом разделе, будут затем использованы в разделе 3.3 для построения грамматик для языков всех вычислений некоторых вычислительных устройств, а в разделе 3.4 будет приведена грамматика для модельного языка функционального программирования, построенная на основе приводимых здесь языковых конструкций.