Вопросы к зачёту #

Зачёт — это альтернатива сдаче проекта.

Команда сама выбирает — сдавать проект или сдавать зачёт по теории. Есть ограничения:

Получить оценку «отлично» можно только путём сдачи проекта
Получить оценки «удовлетворительно» и «хорошо» можно как путём сдачи проекта, так и через зачёт по теории

Правила сдачи зачёта #

Зачёт сдаётся очно в формате, похожем на сдачу экзамена.

Каждый билет содержит три вопроса:
- Простой вопрос по теории (5 баллов)
- Сложный вопрос по теории (5 баллов)
- Практическое задание (10 баллов)
Каждый вопрос оценивается отдельно, при этом балл за вопрос умножается на один из коэффициентов: 0.6, 0.8 или 1.0
Баллы за все три вопроса складываются
Зачёт считается успешно сданным, если студент набрал не менее 10 баллов

Оценка вопросов по теории #

Каждый вопрос по теории имеет базовую оценку 5 баллов, которая умножается на коэффициент, выбираемый по таблице:

Критерий	5×0.6=3 (удовл. ответ)	5×0.8=4 (хороший ответ)	5×1.0=4 (отличный ответ)
Знает определения и может приводить примеры	обязательно	обязательно	обязательно
Отлично ориентируется во взаимосвязях между темами	—	обязательно	обязательно
Легко приводит примеры из личного опыта за рамками курса	—	—	обязательно

Оценка практического задания #

Практическое задание имеет базовую оценку 10 баллов, которая умножается на коэффициент, выбираемый по таблице:

Критерий	10×0.6=6 (удовл. ответ)	10×0.8=8 (хороший ответ)	10×1.0=10 (отличный ответ)
Число существенных ошибок	не более 3	не более 2	не более 1
Студент знает, как исправить ошибки	обязательно	обязательно	обязательно
Студент может описать плюсы и минусы решения	—	обязательно	обязательно
Студент может описать альтернативные решения	—	—	обязательно

Список вопросов #

Простой теоретический вопрос #

Что такое контекстно-свободная грамматика? Приведите пример. Какие ограничения имеют контекстно-свободные грамматики?
В чём цель лексического анализа? Как он связаны с иерархией грамматик Хомского?
В чём цель синтаксического анализа? Как он связаны с иерархией грамматик Хомского?
Опишите принцип написания синтаксического анализатора методом рекурсивного спуска.
Что такое регулярная грамматика? Приведите пример. Какие ограничения имеет регулярная грамматика?
Что такое левая рекурсия в грамматике? Приведите пример.
Что такое правая рекурсия в грамматике? Приведите пример.
Что такое левая факторизация в грамматике? Приведите пример.
Опишите разницу между выражением (expression) и инструкцией (statement) в императивных высокоуровневых языках программирования.
Опишите разницу между выражением (expression) и объявлением (declaration) в императивных высокоуровневых языках программирования.
Что такое AST (Abstract Syntax Tree)? Приведите пример.
Опишите, что такое сужающее преобразование типа (narrow cast) в языках программирования. Приведите пример.
Опишите, что такое расширяющее преобразование типа (wide cast) в языках программирования. Приведите пример.
Опишите, что такое вычисление по короткой схеме (short-circuit evaluation) в языках программирования. Приведите пример.

Сложный теоретический вопрос #

Чем отличается интерпретатор от компилятора?
Опишите правила построения EBNF грамматики (диалект ISO), приведите пример.
Опишите смысл лексического анализа и различие между лексемой и токеном.
Какие уровни есть в иерархии грамматик Хомского? Какие уровни используются при построении интерпретатора или компилятора языка программирования?
В чём разница между леворегулярной и праворегулярной грамматиками?
Что такое ДКА (детерминированный конечный автомат)? Чем он отличается от НКА (недетерминированного конечного автомата)?
Какой тип конечного автомата может разбирать контекстно-свободные грамматики?
Приведите пример контекстно-зависимой грамматики, которую нельзя свести к контекстно-свободной
Приведите примеры выражения на каком-либо языке программирования, для которых: а) изменение ассоциативности с левой на правую меняет результат; б) изменение приоритетов операций меняет результат
Почему для рекурсивного спуска нужно устранять левую рекурсию в грамматике?
Почему для рекурсивного спуска нужно устранять факторизацию рекурсию в грамматике?
Опишите разницу между динамическими и лексическими областями видимости в языках программирования. Какой из этих типов встречается чаще?
Чем AST (Abstract Syntax Tree) отличается от дерева разбора (Parse Tree)? Приведите пример AST и Parse Tree для одного и того же формального языка.
Опишите составляющие части концепции структурного программирования.

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

CPython (интерпретатор языка Python 3) использует виртуальную машину для исполнения интерпретируемого кода, а в процессе разбора строит AST. Нарисуйте диаграмму фаз компиляции и передаваемых между фазами данных для интерпретатора CPython.
SQLite (СУБД) для разбора SQL-запроса использует восходящий анализ алгоритмом LALR, с помощью которого строится AST, а для исполнения SQL-запросов создаёт план запроса в виде байт-кода на виртуальной машине VDBE. Нарисуйте диаграмму фаз компиляции и передаваемых между фазами данных при обработке SQL-запроса в SQLite.
Напишите EBNF-грамматику, позволяющую проверить корректность всех пар скобок в последовательности круглых, квадратных, фигурных скобок. Затем нарисуйте дерево разбора строки {()[()]} согласно этой грамматике.
Напишите EBNF-грамматику, позволяющую разобрать логическое выражение с лексемами identifier, "or", "and", "not", "(", ")" с учётом правильного приоритета операторов. Затем нарисуйте дерево разбора строки (a or b) and not (b or c) согласно этой грамматике.
Напишите EBNF-грамматику, позволяющую разобрать логическое выражение с лексемами letter, "∧" (логическое И), "∨" (логическое или), "¬" (отрицание), "(", ")" с учётом правильного приоритета операторов. Затем нарисуйте дерево разбора строки (a ∨ с) ∧ ¬(b ∨ с) согласно этой грамматике.
Напишите EBNF-грамматику, позволяющую разобрать слово, состоящее из следующих символов: буквы английского алфавита, дефис -, апостроф '. Дефисы могут быть только в середине слова, апострофы — в середине либо в конце.
Напишите EBNF-грамматику, позволяющую разобрать денежные в рублях формате “10 200,99”, где пробел используется как разделитель тысячных разрядов, а запятая — для отделения дробной части. Грамматика должна строго ограничивать количества цифр в каждой частию
Напишите EBNF-грамматику, позволяющую разобрать даты в формате “2025-12-31”, где первые 4 цифры содержат номер года, следующие 2 цифры — месяц, последние 2 цифры — число месяца. Грамматика должна ограничивать номер месяца числом от 1 до 12, а число месяца — числом от 1 до 31.
Переведите выражение (a + 3) * (b - 4) в постфиксную (обратную польскую) нотацию. Покажите с помощью рисунков или схем, как вычислить полученное выражение с помощью стека, если a = 10 и b = 7.
Напишите EBNF-грамматику, позволяющую разобрать арифметическое выражение с операторами +, -, *, / так, чтобы в грамматике не было левой рекурсии. Напишите вторую версию ENBF-грамматики, в которой нет правой рекурсии. Обе версии должны верно определять приоритет и ассоциативность всех арифметических операций.
Нарисуйте UML диаграмму классов (с указанием всех полей и методов) для абстрактного синтаксического дерева арифметического выражения с числами, бинарными операторами +, -, *, /, унарными операторами +, - и скобками.
Нарисуйте схему работы по каноничному варианту TDD (Test Driven Development). Опишите суть каждого шага на этой схеме.