Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 1

1. Процессы перевода и компиляции. Основные фазы компиляции. Перевод и семантика.

2. Понятие атома. Оптимизация одного атома и цепочки атомов. Оптимизация операторов. Оптимизация циклов.

3. Задача.

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

________________________________________________________________________

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 2

1. Польская запись как важный пример перевода арифметических выражений.

2. Разбор с помощью детерминированного алгоритма перенос-свертка. Правоанализирующие LR(k) – грамматики, их свойства. LR(k) алгоритм разбора.

3. Задача.

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

________________________________________________________________________

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 3

1. Проблема описания бесконечного перевода конечными средствами. Транслятор как устройство, реализующее заданный перевод. Желательные качества транслятора.

2. LR(0) – грамматики. Построение детерминированного правого анализатора для LR(k) – грамматик.

3. Задача.

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

________________________________________________________________________

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 4

1. Два основных формализма, применяемые для определения перевода: схемы синтаксически управляемой трансляции и преобразователи.

2. Обработка ошибок при восходящем разборе. Замечания о реализации левых и правых анализаторов. Их временная и емкостная сложность.

3. Задача.

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

________________________________________________________________________

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 5

1. Транслирующие грамматики. Определение СУ-схемы. Выводимые пары цепочек.

2. Нисходящий однопроходный анализ без возвратов. Общий подход.

3. Задача.

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

________________________________________________________________________

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 6

1. Перевод как преобразование деревьев вывода. Понятие СУ-перевода. Простые СУ-переводы.

2. Левоанализируемые грамматики (LL(k)-грамматики). Их свойства.

3. Задача

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

________________________________________________________________________

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 7

1. Атрибутные транслирующие грамматики. Примеры наследуемых и синтезируемых атрибутов.

2. Простая (разделенная) LL(1) – грамматика.

3. Задача.

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

________________________________________________________________________

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 8

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

2. Предсказывающий алгоритм разбора для LL(k) – грамматик. Корректность k – предсказывающего алгоритма.

3. Задача.

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

________________________________________________________________________

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 9

1. Конечный преобразователь как простейший транслятор. Общая схема. Формальное определение. Принцип работы, понятие такта и конфигурации.

2. Разбор для LL(1) – грамматик. Разбор для LL(k) – грамматик. Обработка ошибок при нисходящем разборе.

3. Задача.

Экзаменатор, проф. Д.А. Ковригин

Зав. кафедрой, проф. С.Н. Митяков

Нижегородский государственный Технический университет Факультет информационных систем и технологий Кафедра «Прикладная математика»

(Экзамен по курсу «Формальные языки и алгоритмы») БИЛЕТ № 10