Конструирование Компиляторов, Проведение Экзамена

Материал из eSyr's wiki.

Версия 19:57, 28 мая 2009

Условия проведения экзамена в 2008 году:

Досрочная сдача

Сдача теоретической и практической частей независимы, любую из них можно как получить досрочно, так и сдать на экзамене.

Теоретическая часть

Лектор на лекциях проводит две контрольные работы. Успешное их написание расценивается, как сдача теоретической части экзамена, иначе теоретическую часть придется писать на экзамене.

Список теоретических вопросов (2009 год)

//Sirian (Василий Хайрулин) 28.05.2009

Список вопросов был взят у лектора

Определение грамматик типа 0 по Хомскому

Определение грамматик типа 1 (неукорачивающих) по Хомскому

Определение детерминированной машины Тьюринга

Определение недетерминированной машины Тьюринга

Определение конфигурации машины Тьюринга

Определение языка, допускаемого машиной Тьюринга

Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга

Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга

Определение регулярного множества

Определение регулярного выражения

Определение праволинейной грамматики

Определение недетерминированного конечного автомата

Определение детерминированного конечного автомата

Объяснить разницу между недетерминированным и детерминированным конечным автоматом

Определение конфигурации конечного автомата

Определение языка, допускаемого конечным автоматом

Определение е-замыкания для подмножества состояний НКА

Определение расширенной функции переходов для ДКА

Определение расширенной функции переходов для НКА

Определение функции firstpos для поддерева в дереве регулярного выражения

Определение функции lastpos для поддерева в дереве регулярного выражения

Определение функции followpos для позиций в дереве регулярного выражения

Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА

Определение регулярной грамматики

Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА

Определение эквивалентных состояний ДКА

Определение различимых состояний ДКА

Определение контекстно-свободной грамматики без е-правил

Определение контекстно-свободной грамматики

Определение вывода в КС-грамматике

Определение языка, порождаемого КС-грамматикой

Определение сентенциальной формы

Определение однозначной КС-грамматики

Определение неоднозначной КС-грамматики

Определение недетерминированного МП автомата

Определение детерминированного МП автомата

Определение конфигурации МП автомата

Определение языка, допускаемого МП автоматом

Что означает, что недетерминированный МП автомат допускает опустошением магазина

Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами

Формулировка леммы о разрастании для КС-языков

Определение нормальной формы Хомского для КС-грамматики

Определение правостороннего вывода в КС-грамматике

Определение левостороннего вывода в КС-граммати

Какая грамматика называется леворекурсивной?

Определение множества FIRST1

Определение множества FOLLOW1

Определение LL(1) Грамматики

Определение LR(1) ситуации

Определение LR(1) грамматики

Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций?

Определение конфигурации LR-анализатора

Как меняется конфигурация LR-анализатора при дейстьвии reduce?

Какие типы действий выполняет LR-анализатор?

Как меняется конфигурация LR-анализатора при дейстьвии shift?

Что такое основа правой сентенциальной формы

Практическая часть

Все семинаристы проводят на итоговом занятии контрольную работу. Контрольная работа состоит из трех задач, за каждую дается +1 балл к базовым двум. Тем не менее, автоматы получают немногие.

Экзамен

Условия проведения

Весь поток пишет одновременно, в одной аудитории. Время отводится 3 часа (изначально планировалось 2ч 30мин, но экзаменаторы «намудрили с накрученностью задач» и добавили еще 30 минут).

Выдается 4 задачи и 2 теоретических вопроса.

Времени хватает вполне, и даже на спокойную проверку всех заданий остается.

Работы проверяют к вечеру, примерно к 17 часам. После объявления результатов возможна апелляция, проводимая с проверявшим работу. Случаи успешного оспаривания баллов достаточно распространены.

Критерии оценки

Разбалловка задач:

1. (1 балл) Построение минимального ДКА по регулярному выражению, построение соответствующей грамматики.
2. (2 балла) LR, LL. (P.S. LR(2) ни в одном условии строить было не нужно).
3. (1 балл) Генерация кода для логических/арифметических выражений.
4. (1 балл) Генерация оптимального кода методом сопоставления образцов.

Каждая задача делится на части. Например, в задаче 2: построил схему с замыканиями - столько то баллов из 2х, сделал таблицу - еще сколько то из 2х, разобрал цепочку - оставшиеся до 2х баллов. (что-то типа 0.7+0.7+0.6).

Теоретическая часть состоит из двух вопросов из списка определений и теормина. Корректное написание обоих вопросов или успешная сдача их на лекции расценивается в 0 баллов, каждый незачтенный вопрос — в -0.5 баллов.

(Информация от лектора: в 2009 году каждый незачтенный вопрос оценивается в -1 балл)

//Sirian (Василий Хайрулин) 28.05.2009

Максимум набирается 5 баллов, минимум -1.

Критерии оценки:

Пересдача

Условия проведения

Время отводится теперь 1.5 часа.

Выдается теперь уже 3 задачи и снова 2 теоретических вопроса (если в предыдущие попытки, вам удалось сдать хотя бы родну из теорий, то вы освобождаетесь от её сдачи на всех последующих попытках).

Работы проверяют чуть ли не к 12—13 часам. После объявления результатов возможна апелляция, проводимая с проверявшим работу. Случаи успешного оспаривания баллов достаточно распространены.

Критерии оценки

Разбалловка задач:

1. (1 балл) Построение минимального ДКА по регулярному выражению, построение соответствующей грамматики.
2. (1.5 балла) LR, LL. (P.S. LR(2) ни в одном условии строить было не нужно).
3. (1 балл) Генерация кода для логических/арифметических выражений или генерация оптимального кода методом сопоставления образцов.

Теоретическая часть абсолютна такая же. Если ранее, например на основном экзамене ты за них уже получил плюс, то далее этот теор. вопрос снимается.

Максимум набирается 3.5 баллов, минимум -1.

Критерии оценки:

5 можно получить только если набрать 3.5 и после разговора с лектором, в результате которого оценка может и понизиться.

Вторая пересдача

Условия проведения

Время отводится ещё меньше: 1 час, но задачи субъективно простые.

Выдается опять 3 задачи и снова 2 теоретических вопроса (если в предыдущие попытки, вам удалось сдать хотя бы одну из теорий, то вы совобождаетесь от её сдачи на всех последующих попытках).

Работы проверяют в течение 15-30 минут.

Критерии оценки

Разбалловка задач:

1. (1 балл) Построение минимального ДКА по регулярному выражению, построение соответствующей грамматики.
2. (1 балл) LR и LL. (P.S. LR(2) ни в одном условии строить было не нужно).
3. (1 балл) Генерация кода для логических/арифметических выражений или генерация оптимального кода методом сопоставления образцов.

Максимум набирается 3 балла, минимум -1.

Критерии оценки:

5 можно получить только если набрать 3 и после дополнительной усложненной задачи от лектора. Автору неизвестны попытки эту задачу получить и решить.