Разработка компиляторов

Внимание: информация на этой странице уточняется...

Цели изучения дисциплины

Теория компиляторов является одной из фундаментальных дисциплин в области программной инженерии. Она опирается в свою очередь на теорию формальных языков и грамматик. Целью данного курса является изучение теоретических основ и методов трансляции, а также приобретение практических навыков использования существующего инструментария для построения компиляторов.

В результате изучения дисциплины студенты должны:

  • знать устройство компиляторов
  • обладать знаниями в области контекстно-свободных грамматик
  • уметь описывать языки с использованием формальных грамматик
  • уметь строить синтаксические и лексические анализаторы
  • знать и уметь применять методы кодогенерации и оптимизации программ

Программа курса

  1. Основы компиляторов
    Основные понятия. Компиляторы и интерпретаторы. Входной язык, целевой язык, язык реализации. T-диаграммы. Прямой компилятор. Раскрутка. Кросс-трансляторы. Виртуальные машины. Компиляция "на лету".
  2. Теория языков
    Различные способы задания языков в компиляции: грамматики; конечные и магазинные автоматы. Соотношения между различными способами задания языков. Приложения в компиляции.
  3. Лексический анализ
    Основные задачи лексического анализа. Регулярные выражения. Использование конечных автоматов для лексического анализа. Утилита Lex. Использование механизма регулярных выражений
  4. Синтаксические анализаторы. Нисходящие анализаторы
    Синтаксический анализ. Контекстно-свободные грамматики. Нисходящие анализаторы. Метод рекурсивного спуска.
  5. Восходящие анализаторы
    Восходящие анализаторы. LR (k)-анализаторы. Построение LR (0)-анализатора. LR (1)-анализатор. LALR-анализаторы. Неоднозначные грамматики. Различные типы конфликтов. Разрешение конфликтов.

  6. Грамматики и YACC
    Генератор анализаторов YACC. Генерация синтаксических анализаторов по BNF описанию.

  7. Семантический анализ. Внутреннее представление
    Фаза контроля типов. Идентификация. Работа с таблицами. Идентификация. Работа с типами. Причины использования промежуточных языков в компиляторах. Различные формы промежуточных языков (ПЯ) в компиляторах:атрибутные деревья разбора; прямая и обратная польские записи; триады/тетрады; RTL.
  8. Управление памятью и сборка мусора
    Управление памятью с точки зрения разработчика компилятора. Проблемы управления памятью. Статическое и динамическое размещение памяти. Стековый механизм управления памятью. Управление кучей. Подсчет ссылок и разметка памяти.
  9. Оптимизация
    Задачи оптимизации. Виды оптимизирующих преобразований. Представления программы, используемые в оптимизирующих преобразованиях. Примеры оптимизирующих преобразований.
  10. Анализ потока управления
    Задачи анализа потока управления. Граф потока управления. Доминирование. Глубинное остовное дерево. Основные виды фрагментов графа потока управления и их свойства.
  11. Анализ потоков данных
    Определение анализа потоков данных. Достижимые определения и живые переменные. Формализация задач анализа потоков данных. Итеративный алгоритм для решения задач анализа потоков данных.