МИЭМ

Системное программное обеспечение. Теория компиляторов

Вопросы к экзамену

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

Практические задания

Задание № 1

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

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

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

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

Задание № 2

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

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

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

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

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

Задание № 3

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

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

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

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

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