Содержание курса лекций
Тема 1. Общие сведения о трансляторах
Цели и задачи дисциплины
Основные понятия и определения
Общие особенности языков программирования и трансляторов
Обобщенная структура транслятора
Варианты взаимодействия блоков транслятора
Многопроходная организация взаимодействия блоков транслятора
Однопроходная организация взаимодействия блоков транслятора
Комбинированные взаимодействия блоков транслятора
Контрольные вопросы и задания
Тема 2. Основы теории языков и формальных грамматик
Способы определения языков
Формальные грамматики
Грамматики с ограничениями на правила
Способы записи синтаксиса языка
Метаязык Хомского
Метаязык Хомского-Щутценберже
Бэкуса-Наура формы (БНФ)
Распознаватели
Контрольные вопросы и задания
Тема 3. Демонстрационный язык программирования
Источники вдохновения для создания демонстрационного
языка
Синтаксис и семантика DPL
Элементарные конструкции
Составные конструкции. Организация программы
Краткое описание семантики языка
Примеры программ на DPL
Пример 1. Алгоритм Евклида (нахождение наибольшего общего делителя)
Пример 2. Одновременное нахождение наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК)
Пример 3. Суммирование n элементов из входного потока
Пример 4. Сортировка элементов вектора
Описание пользовательского синтаксиса с использованием диаграмм Вирта
Контрольные вопросы и задания
Тема 4. Организация лексического анализа
Назначение и необходимость фазы лексического анализа
Транслитератор
Грамматики и распознаватели для лексического анализа
Связь между диаграммой Вирта и конечным автоматом
Связь между диаграммами Вирта и праволинейными грамматиками. Преобразование правой рекурсии в итерацию
Связь между диаграммами Вирта и грамматиками с левой рекурсией. Преобразование левой рекурсии в итерацию
Методы лексического анализа
Организация непрямого лексического анализатора
Организация прямого лексического анализатора
Контрольные вопросы и задания
Тема 5. Лексический анализатор демонстрационного языка программирования
Транслитератор DPL
Общая организация транслитератора
Программная реализация транслитератора
Непрямой лексический анализатор DPL
Диаграммы Вирта для отдельных автоматов
непрямого лексического анализатора
Программная реализация отдельных автоматов
Общая структура непрямого лексического анализатора
Прямой лексический анализатор DPL
Контрольные вопросы и задания
Тема 6. Общие принципы организации синтаксического разбора
Назначение синтаксического разбора
Классификация методов синтаксического разбора
Методы разбора
Последовательность разбора
Использование просмотра вперед
Использование возвратов
Резюме
Контрольные вопросы и задания
Тема 7. Применение автоматов с магазинной памятью
для нисходящего разбора слева направо
Необходимость использования автоматов с магазинной памятью
Организация автомата с магазинной памятью
Общая связь между грамматиками и автоматами с магазинной памятью
Связь между S-грамматикой и автоматом с магазинной памятью
Обобщенный алгоритм построения нисходящего АМП для S - грамматики
S-грамматика и распознавание вложенности скобок
Построение автомата с магазинной памятью по q-грамматике
Построение нисходящего автомата
Примеры построения АМП по q-грамматике
Распознавание вложенности скобок и q-грамматика
LL(1) - грамматики
Программная реализация нисходящего автомата с магазинной памятью
Разработка программы по таблице переходов АМП
Разработка программы с использованием метода рекурсивного спуска
Контрольные вопросы и задания
Тема 8. Использование динамически порождаемых автоматов для нисходящего разбора слева направо
Семантический разрыв между формальными грамматиками и автоматами с магазинной памятью
Модель динамически порождаемых конечных автоматов
Графический метаязык для описания динамически порождаемых конечных автоматов
Использование диаграмм Вирта для представления динамически порождаемых конечных автоматов, распознающих КС(1) грамматику
Контрольные вопросы и задания
Используемые источники информации
|