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

• Автор: Федорченко, Людмила Николаевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 160 с. : ил.

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

1.2. Способы задания синтаксических структур.

1.3. Эквивалентные преобразования грамматик

в инструментальных средствах УассВ1зоп

1.4. Эквивалентность как отношение подобия на синтаксических структурах.

Выводы по главе

Глава 2. ОПРЕДЕЛЕНИЕ И РАСПОЗНАВАНИЕ КОНТЕКСТНОСВОБОДНЫХ ЯЗЫКОВ

С ПОМОЩЬЮ СИНТАКСИЧЕСКИХ ГРАФСХЕМ.

2.1. Основные понятия

2.2. Контекстносвободные грамматики в регулярной форме

2.3. Выводимость в КСРграмматике

2.4. Синтаксическая графсхема.
2.5. Рекуррентный алгоритм построения синтаксической графсхемы.
2.6. Достижимые вершины в синтаксической графсхеме
2.7. Синтез распознающих автоматов для КСР грамматик
2.8. Свойства синтаксической графсхемы
2.9. Леммы о существовании состояний распознавателя
в синтаксической графсхеме
2 Основная теорема о языке.
Выводы по главе
Глава 3. РЕГУЛЯРИЗАЦИЯ КОНТЕКСТНОСВОБОДНЫХ ГРАММАТИК .
3.1. Синтаксическая модель языка
3.2. Этап предварительной подготовки грамматики.
3.3.Этапы обработки исходного текста грамматики.
3.4. Рекурсивные нетерминалы
3.4.1. Левая и правая рекурсии
1 I
3.4.2. Свойство самовложенности.
3.5. Подстановка нетерминала
3.6. Исключение рекурсивных нетерминалов
3.7. Число состояний распознавателя, синтезируемого
по КСРграмматике.
3.8. Минимизация регулярных выражений и
состояний распознавателя.
Выводы по главе
Глава 4. ИНСТРУМЕНТАЛЬНАЯ СИСТЕМА ЭКВИВАЛЕНТНЫХ
ПРЕОБРАЗОВАНИЙ БулвТ
4.1. Описание, спецификации и дизайн системы.
4.2. Экранное размещение синтаксической графсхемы.
4.3. Интерфейс пользователя
4.4. Генерация тестов в системе ЭупСТ
4.6.Пример преобразования рекурсивного нетерминала.
Выводы по главе
Заключение
Библиографический список использованной литературы.
Приложение 1. Основные термины
Приложение 2. Примеры применения метода
регуляризации грамматик
Приложение 3 Доказательства лемм и теорем.
Основные обозначения и сокращения
БНФ БэкусаНаура Форма

x

x
I I Ii i Ii i
ii i i
ii
x xi
ii
x xi
i
IX
КС контекстносвободный
КЗ контекстнозависимый
КСГ контекстносвободная грамматика
КСРграмматика контекстносвободная грамматика в регулярной форме
i i i, i iv
i i i, iv

i
ii
I I iii
I I i i
ii i
x i
ii i
i ii
СПТ система построения трансляторов
МПпреобразователь преобразователь с магазинной памятью
СГС синтаксическая графсхема
ГА Граф для нетерминала А
Детерминированный конечный автомат
МПавтомат Магазинный автомат автомат с магазинной памятью
Введение


Новый алгоритм регуляризации трансляционных контекстносвободных грамматик с помощью их эквивалентных преобразований, позволяющий аппроксимировать входной язык регулярными множествами слов, применимость которого показана, на фрагментах реальных языков программирования, обеспечивающий высокий процент повышения эффективности, по сравнению с известными методами в системах построения трансляторов xi, . Новый способ задания модели реализуемого языка с использованием формального понятия синтаксической графсхемы грамматики, повышающий наглядность е представления по сравнению с традиционными текстовыми формами записи в виде регулярных выражений. Экспериментальная реализация инструментального средства x i в виде программного продукта на языке Паскаль в системе i 7. Кбайт, подтверждающая теоретические результаты работы на ряде экспериментов по автоматической генерации анализаторов для нескольких представительных подмножеств языков Си, Паскаль, АЛГОЛ. Реализация языка программирования предполагает описание его синтаксической модели в виде специальной грамматики трансляционной, которая, помимо основной своей функции порождения цепочек языка, позволяет задавать трансляции, необходимые разработчикам. Такая двойственная природа грамматик с одной стороны порождающая, с другой анализирующая нашла сво отражение в многообразии их типов и видов в практике построения трансляторов компиляторов, конверторов, интеллектуальных редакторов, любых языковых процессоров. Способ задания трансляций, которые рассматривается как отношение на множестве 7,х, где I,входной язык, Ь2 выходной язык, называется спецификацией реализуемого языка. Диапазон таких спецификаций, или метаязыков, простирается от обычной БНФ , x , и языков разметки типа , до грамматик , двухуровневые грамматик А. Ван Вейнгаардена , , аффиксных грамматик Костера , и многих других видов грамматик и метаязыков ,, , ,. Другими словами, метаязыки, которые используются для определения синтаксиса и семантики транслируемых языков, являются разновидностью специальных грамматик, которые можно объединить и называть трансляционными грамматиками1. Разнообразие спецификаций языков достигло некоторой степени насыщения, поэтому затруднн их выбор при разработке языкового процессора. Необходимо, вопервых, создать новый способ задания трансляций, который был бы универсален по отношению к синтаксическим моделям любого типа, вовторых, применить простые известные методы разбора и анализа языков, способные к развитию на более широкий класс языков. При разрешении конфликтных ситуаций в процессе построения анализатора языка. В случае задания трансляций с помощью, контекстносвободных грамматик в регулярной форме КСРграмматик предлагаемая в работе процедура эквивалентных преобразований и регуляризация грамматики как предельный случай этой процедуры позволяют устранить обе эти причины. Рассмотрим причины, вызывающие преобразования грамматик при построении транслятора более подробно. В теорииформальных грамматикбыла описана иерархия из классов грамматик и языков иерархия Н. Хомского, вложенных последовательно один в другой, от регулярных до рекурсивноперечислимых тип 0, которые представлены на рисунке 1. Рис. Множество грамматик типа 0 эквивалентно классу машин Тьюринга, что говорит об их большой выразительной мощности. Теоретики языков в противоположность разработчикам трансляторов стремятся описать язык наиболее выразительными и мощными формализмами, пытаясь вместить в единую формализацию как можно больше свойств языка, например, формализовать семантику, в частности, статическую, которую, в отличие от динамической семантики, можно обработать на фазе синтаксического анализа. Так появились двухуровневые грамматики, наиболее известнымииз которых являются аффиксные грамматики и грамматики А. Ван Вейнгаардена, порождающая мощность которых даже больше, чеммощность рекурсивноперечислимых множеств. Однако практическое использование таких грамматик ограничено ввиду отсутствия механизма построения эффективных анализаторов языков, порождаемых этими грамматиками.