SoftCraft
разноликое программирование

Top.Mail.Ru

Основы разработки трансляторов

Содержание курса лекций

Тема 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) грамматику

Контрольные вопросы и задания

Тема 9. Применение диаграмм Вирта для построения КС(1) грамматик, используемых при нисходящем разборе слева направо

Чем удобны диаграммы Вирта

Избавление от левых или правых рекурсий

Преобразование исходных синтаксических правил к более простому виду

Преобразование КС(n) грамматик к грамматикам с просмотром вперед на меньшее число символов

Проверка грамматик на эквивалентность

Освобождение от пустых правил

Непосредственное использование правил с левой рекурсией

Использование синтаксиса для определения семантики

Доказательство принадлежности к КС(1) грамматике

В последний раз о распознавателе вложенности круглых скобок

Контрольные вопросы и задания

Тема 10. Разработка синтаксических диаграмм для распознавателя DPL

Преобразование пользовательского синтаксиса к КС(1) грамматике

Замена обозначений нетерминалов в исходных диаграммах Вирта

Диаграммы Вирта, полученные после подстановки лексем и замены названий на идентификаторы

Освобожнение от сквозных связей в демонстрационном языке

Модификация правил с одинаковыми начальными лексемами

Проверка принадлежности к КС(1) грамматике

Получение окончательных диаграмм Вирта демонстрационного языка

Окончательные диаграммы Вирта, описывающие синтаксис демонстрационного языка программирования DPL

Написание кода по разработанным диаграммам Вирта

Контрольные вопросы и задания

Тема 11. Семантический анализ

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

Семантическая модель программы

Построение дерева разбора

Построение объектной модели

Связь между построением семантической модели программы и генерацией кода

Построение элементов таблицы имен

Разработка абстрактных описаний элементов таблицы имен

Разработка структур данных по абстрактным описаниям

Обработка элемента таблицы имен

Организация элемента таблицы имен в DPL

Построение таблицы имен

Использование таблицы имен при выполнении операторов программы

Синтаксически управляемый перевод

Использование синтаксически управляемого перевода при построении таблиц имен

Построение таблицы имен для демонстрационного языка

Программная реализация построения таблицы имен для демонстрационного языка

Использование синтаксически управляемого перевода при работе с таблицей имен

Использование синтаксически управляемого перевода для работы с таблицей имен в трансляторе с демонстрационного языка

Программная реализация фрагмента работы с таблицей имен

Контрольные вопросы и задания

Тема 12. Синтаксически управляемый перевод при генерации промежуточного представления

Организация промежуточного представления программы

Формирование команд виртуальной машины

Основные отношения на уровне команд

Структура команд языка промежуточного представления

Организация промежуточных команд демонстрационного языка

Формат команды промежуточного представления и его реализация

Структура операнда демонстрационного языка

Генерация промежуточного представления

Генерация структур, представляющих константные операнды

Генерация промежуточного представления для переменной

Генерация промежуточного представления для выражений

Контрольные вопросы и задания

Используемые источники информации