Теория компиляторов

 

Для получения зачета/экзамена по дисциплине Теория компиляторов необходимо:

1.      Написать и защитить 3 контрольные работы.

2.      Ответить на теоретические вопросы.

Контрольная работа № 1

Дано: недетерминированный конечный автомат.

Задание 1: Написать грамматику, соответствующую исходному автомату.

Задание 2: Создать по исходному недетерминированному автомату эквивалентный ему детерминированный автомат.

Задание 3: Написать программу на языке Пролог, реализующую работу исходного автомата.

 

Защита выполненных заданий подразумевает:

1)      знание теории формальных грамматик (определения, иерархия Хомского и т.п.);

2)       знание теории конечных автоматов (определения, теорема о создании эквивалентных детерминированных автоматов и т.п.);

3)      знание основ языка Пролог (основные конструкции, система логического вывода, работа со списками, управление поиском (предикаты cut и fail) и т.д.)

Контрольная работа № 2

Дано: арифметическое выражение в инфиксной форме записи.

Требуется: перевести исходное выражение в польскую (постфиксную) форму записи тремя методами:

Задание 1: методом автоматов с магазинной памятью;

Задание 2: методом синтаксически управляемого перевода;

Задание 3: методом операторных грамматик.

 

Выполнение всех заданий подразумевает выдачу всей цепочки вывода.

 

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

Контрольная работа № 3

Дано: Фрагмент программы на языке высокого уровня.

 

Требуется: перевести исходное выражение в польскую (постфиксную) форму записи тремя методами:

 

Задание 1: Создать грамматику данного языка. Сформировать полную матрицу переходов в соответствии с созданной грамматикой. Расписать 5 процедур этой матрицы.

Задание 2: Написать синтаксический анализатор исходного языка на Прологе.

Задание 3: Перевести исходный фрагмент программы в польскую форму записи или тетрады.

 

Для защиты заданий требуется знание перевода основных конструкций и управляющих операторов во внутренние формы представления программ (в польскую форму и тетрады).

 

Теоретические вопросы

1.      Основные понятия. Транслятор, компилятор, интерпретатор. Структура компилятора

2.      Сканер. Работа с таблицами

3.      Хеш-функции

4.      Формальные языки. Грамматики. Иерархия Хомского

5.      Регулярные грамматики и конечные автоматы. Построение ДКА по НКА.

6.      Автоматы с магазинной памятью

7.      Операторные грамматики

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

9.      Матрицы переходов

10.  Внутренние формы представления программы. Польская форма. Тетрады

11.  Оптимизация программ

12.  Интерпретаторы. Структура, функции.