1.      Аннотация программы

Курс посвящен введению в методы трансляции программ и охватывает следующие темы: модель транслятора, основы теории языков и формальных грамматик, организация лексического анализа и синтаксического разбора, генерация и оптимизация кода и автоматическая генерация трансляторов.

2.      Содержание программы

1.     Общие сведения о трансляторах

Основные понятия и определения. Общие особенности языков программирования и трансляторов. Обобщенная структура транслятора. Варианты взаимодействия блоков транслятора: многопроходная организация взаимодействия, однопроходная организация взаимодействия, комбинированные взаимодействия блоков транслятора.

2.     Основы теории языков и формальных грамматик

Способы определения языков. Формальные грамматики. Грамматики с ограничениями на правила. Способы записи синтаксиса языка: метаязык Хомского, метаязык Хомского-Щутценберже, Бэкуса-Наура формы (БНФ).

3.     Организация лексического анализа

Назначение и необходимость фазы лексического анализа. Транслитератор. Грамматики и распознаватели для лексического анализа. Связь между синтаксическими диаграммами и конечным автоматом. Связь между синтаксическими диаграммами и праволинейными грамматиками. Преобразование правой рекурсии в итерацию. Связь между синтаксическими диаграммами и грамматиками с левой рекурсией. Преобразование левой рекурсии в итерацию. Методы лексического анализа: организация непрямого лексического анализатора, организация прямого лексического анализатора.

4.     Организация синтаксического разбора

Назначение синтаксического разбора. Классификация методов синтаксического разбора. Последовательность разбора. Использование просмотра вперед. Использование возвратов.

Применение автоматов с магазинной памятью для нисходящего разбора слева направо

Необходимость использования автоматов с магазинной памятью. Организация автомата с магазинной памятью. Общая связь между грамматиками и автоматами с магазинной памятью. Связь между S-грамматикой и автоматом с магазинной памятью. Построение автомата с магазинной памятью по q-грамматике. LL(1) - грамматики. Программная реализация нисходящего автомата с магазинной памятью.

Использование динамически порождаемых автоматов для нисходящего разбора слева направо

Семантический разрыв между формальными грамматиками и автоматами с магазинной памятью. Модель динамически порождаемых конечных автоматов. Графический метаязык для описания динамически порождаемых конечных автоматов. Использование синтаксических диаграмм для представления динамически порождаемых конечных автоматов, распознающих КС(1) грамматику.

5.     Генерация кода

Распределение оперативной памяти. Организация таблиц компилятора. Процедура генерации кода. Основные методы оптимизации кода.

6.     Автоматическая генерация трансляторов

Краткий обзор программных средств автоматической генерации интерпретаторов и компиляторов: LEX, YACC, BIZON и др.

3.      Распределение часов

4.      Основная литература

1.     Ахо А., Ульман Д., Сети Р. Компиляторы: принципы, технологии, инструментарий. - М.: Вильямс, 2001.

2.     Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.

3.     Костельцов А.В. Построение интерпретаторов и компиляторов: использование программ BIZON, BYACC, ZUBR. - М.: Наука и техника, 2001.