Исследование и разработка эффективных методов реализации языков программирования

• Автор: Лийб, Дональд Бернхардович
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Таллин
• Количество страниц: 152 c. : ил

1. ОБЗОР МЕТОДОВ И ПРОБЛЕМ, СВЯЗАННЫХ С ФУНКЦИЯМИ ПРЕДШЕСТВОВАНИЯ

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

1.2. Понятие класса грамматик, обладающих функциями предшествования

1.3. Способы доказательства существования функции предшествования

1.4. Методы построения функции предшествования

1.4.1. Методы вычисления функции предшествования

1.4.2. Методы нахождения функции предшествования

1.5. Функции предшествования как часть синтаксического анализатора

1.5.1. Проблемы нахождения отношения "?"

1.5.2. Проблемы редуцирования

Выводы
2. ОПТИМИЗАЦИЯ ПАМЯТИ АНАЛИЗАТОРА ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ, РЕДУЦИРУЕМОЙ С (1,1) - ОГРАНИЧЕННЫМ КАНОНИЧЕСКИМ К0НТЕКСТ0М40
2.1. Приведение грамматики предшествования к виду,
обладающему двумя функциями предшествования
2.1.1. Нахождение циклов в матрице предшествования
2.1.2. Частные виды стратификации для преобразования грамматик предшествования
2.1.3. Алгоритм нахождения функции предшествования,
при помощи преобразования исходной грамматики 55 предшествования

2.2. Метод проведения редуцирования 0(4,1] - ограниченн-ным каноническим контекстом при функциях предшествования
2.2.1. Определение минимального (1,1) - ограниченного канонического контекста
2.2.2. Определение упорядоченных векторов
2.3. Обработка ошибок при упорядоченных векторах и функциях предшествования
2.4. Модифицированный алгоритм синтаксического анализа
для грамматик предшествования
Выводы
3. ТЕХНОЛОГИЯ И СРЕДСТВА РЕАЛИЗАЦИИ
3.1. Система построения трансляторов ELM А
3.1.1. Конструктор и анализатор системы E.LM А
3.2. Инструментальное средство на базе системы ELM А
3.2.1. Обработка аналитических выкладок
3.2.2. Надстройка над базой данных
3.3. Опыт минимизации транслятора, работающего при
помощи модифицированного анализатора
3.3.1. Характеристика языков, реализованных в
системе ELM А
3.3.2. Эффективность нахождения функции предшествования и упорядоченных векторов
3.3.3. Пример вычисления функции предшествования и упорядоченных векторов на языке DAMAL
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ I

ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ

^ А У* £
р*=[и^Л
Далее докажем, что стратификации направо и налево не образуют новых циклов в графе линеаризации и грамматика предшествования сохраняет свойство Ц2(к) при к^О или 1с>0.
Теорема 2.1. Стратификация направо для отношения
= в грамматике предшествования не приводит к образованию новых циклов в графе линеаризации.
Доказательство. Пусть б'=-БТ (6;У у) и
/к = ^ X 1 А -> иХУуе (Уу) У
Стратификация направо может породить циклы в графе линеаризации, если удовлетворен критерий .
Рассмотрим, какие расширения отношений предшествования влечет за собой стратификация направо.
Отношение = расширяется за счет пар (Х;и„) , X & /^ , причем количество их останется прежним. Таким образом получаем:
=6' “ К 1(М) IX £ Ч^) О у Х,ик) | X* IV.
Очевидно, что Л61= ^ ;У)]| и
л;--л; и{(ик,2)
Эти дополнения к отношениям == и ТС'” изменяют множества отношений <• следующим образом
<-6,= <-6и [(Х,У)Х^]Кх<й^у у
Поскольку перед стратификацией направо X“ ^ ^У^| , то изменения в отношениях ==• и <• приводят к ликвидации цикла графа линеаризации, т.е. отношение заменяется на <• , в связи с
Чем ПРОИСХОДИТ переориентация ДУГИ ИЗ (ХГ), , Уу|) в (Хл ,УГ.У
Отношение •> может изменяться следующим образом
>6'= >6 и ии«.с)1и*еЧ.У