Теория компиляторов
Для получения зачета/экзамена по дисциплине Теория компиляторов необходимо:
1. Написать и защитить 3 контрольные работы.
2. Ответить на теоретические вопросы.
Дано: недетерминированный конечный автомат.
Задание 1: Написать грамматику, соответствующую исходному автомату.
Задание 2: Создать по исходному недетерминированному автомату эквивалентный ему детерминированный автомат.
Задание 3: Написать программу на языке Пролог, реализующую работу исходного автомата.
Защита выполненных заданий подразумевает:
1) знание теории формальных грамматик (определения, иерархия Хомского и т.п.);
2) знание теории конечных автоматов (определения, теорема о создании эквивалентных детерминированных автоматов и т.п.);
3) знание основ языка Пролог (основные конструкции, система логического вывода, работа со списками, управление поиском (предикаты cut и fail) и т.д.)
Дано: арифметическое выражение в инфиксной форме записи.
Требуется: перевести исходное выражение в польскую (постфиксную) форму записи тремя методами:
Задание 1: методом автоматов с магазинной памятью;
Задание 2: методом синтаксически управляемого перевода;
Задание 3: методом операторных грамматик.
Выполнение всех заданий подразумевает выдачу всей цепочки вывода.
Для защиты заданий требуется знание всех используемых определений и терминов, а также алгоритмов перевода. В том числе: принципы синтаксические управляемого перевода, определение автомата с магазинной памятью, достоинства и недостатки метода операторных грамматик.
Дано: Фрагмент программы на языке высокого уровня.
Требуется: перевести исходное выражение в польскую (постфиксную) форму записи тремя методами:
Задание 1: Создать грамматику данного языка. Сформировать полную матрицу переходов в соответствии с созданной грамматикой. Расписать 5 процедур этой матрицы.
Задание 2: Написать синтаксический анализатор исходного языка на Прологе.
Задание 3: Перевести исходный фрагмент программы в польскую форму записи или тетрады.
Для защиты заданий требуется знание перевода основных конструкций и управляющих операторов во внутренние формы представления программ (в польскую форму и тетрады).
1. Основные понятия. Транслятор, компилятор, интерпретатор. Структура компилятора
2. Сканер. Работа с таблицами
3. Хеш-функции
4. Формальные языки. Грамматики. Иерархия Хомского
5. Регулярные грамматики и конечные автоматы. Построение ДКА по НКА.
6. Автоматы с магазинной памятью
7. Операторные грамматики
8. Синтаксически управляемый перевод
9. Матрицы переходов
10. Внутренние формы представления программы. Польская форма. Тетрады
11. Оптимизация программ
12. Интерпретаторы. Структура, функции.