Вопросы по теории компиляторов

⇐ ПредыдущаяСтр 2 из 2

Вопросы по теории компиляторов

Классификация трансляторов. Компиляторы, интерпретаторы.
Структура компилятора. Этапы (фазы) компиляции, их назначение.
Лексический анализ. Задачи лексического анализа. Понятия лексемы и токена. Классы токенов.
Лексический анализ. Предпросмотр (backtracking, lookahead) и примеры его применения при лексическом анализе языков программирования.
Регулярные выражения. Назначение, базовые конструкции, составные конструкции.
Формальные языки. Алфавит языка.
Функция значения (meaning function).
Лексические спецификации. Использование лексических спецификаций для лексического анализа.
Правило «maximal munch». Проблемы применения и способы их решения.
Конечные автоматы в лексическом анализе. Понятия «accept» и «reject». Связь между конечными автоматами и регулярными языками.
Детерминированные и недетерминированные конечные автоматы (ДКА и НКА).
Этапы построения лексического анализатора. НКА для простых и составных регулярных выражений.
Построение НКА для сложного регулярного выражения.
Понятие ε-замыкания. Преобразование НКА в ДКА.
Программная реализация конечных автоматов.
Иерархия Хомского. Понятие грамматики. Проблема использования регулярных выражений в синтаксическом анализе.
Синтаксический анализ. Задачи синтаксического анализа. Понятие дерева разбора.
Контекстно-свободные грамматики (КСГ). Понятия терминала, нетерминала, продукции. Связь КСГ с лексическим анализом.
Порождения. Левое и правое порождения.
Неоднозначность. Проблемы использования неоднозначных грамматик в синтаксическом анализе. Примеры языков программирования, имеющих неоднозначные грамматики.
Способы устранения неоднозначностей. Понятие ассоциативности, связь ассоциативности и приоритетов с неоднозначными грамматиками.
Обработка ошибок компилятором. Способы обработки ошибок, их преимущества и недостатки.
Абстрактные синтаксические деревья (AST). Связь AST с деревьями разбора.
Классификация методов синтаксического анализа. Метод рекурсивного спуска: теория.
Метод рекурсивного спуска: программная реализация.
Левая рекурсия, связанные с ней проблемы и способы её устранения.
Предиктивный анализ. Понятие LL(k)-грамматик. Левая факторизация грамматики.
LL(1)-разбор.
First-множества в LL(1)-анализе.
Follow-множества в LL(1)-анализе.
Построение таблицы LL(1)-разбора. Выявление грамматик, не являющихся LL(1)-грамматиками.
Восходящий разбор: отличия от нисходящих методов, преимущества. Понятие свёртки.
Операции сдвига и свёртки в восходящем разборе. Виды конфликтов.
Семантический анализ. Задачи семантического анализа. Области видимости и способы их определения в различных языках.
Семантический анализ. Таблицы символов.
Семантический анализ. Понятие типа, виды типизации.
Оптимизация и генерация кода. Способы оптимизации. Проблемы оптимизации.

⇐ Предыдущая 12