Системное программное обеспечение

Обзор курса

Курс состоит из лекций, семинаров и лабораторных работ.

Темы лекций

  1. Введение в компиляцию. Структура компилятора. Процесс компиляции.
  2. Классификация языков программирования
  3. Лексический анализ. Токены, шаблоны, лексемы. Языки
  4. Регулярные выражения. Распознавание шаблонов на основе недетерминированного конечного автомата
  5. Переход от недетерминированного к детерминированному конечному автомату
  6. Производные регулярных выражений Януша Бржозовски
  7. Синтаксический анализ. Понятие и роль синтаксического анализа
  8. Грамматики. Иерархия Хомского. Форма Бэкуса-Наура
  9. Нисходящий синтаксический анализ. Рекурсивный анализ
  10. Предиктивный анализ. LL(1)-анализ
  11. Восходящий синтаксический анализ. Метод перенос/свертка. LR-анализ
  12. Промежуточный код. Ориентированные ациклические графы. Трёхадресный код
  13. Выражения типов. Эквивалентность типов. Синтез и выведение. Проверка
  14. Машинно-независимая оптимизация. Источники оптимизации. Семантически-эквивалентные трансформации
  15. Организация памяти. Доступ к нелокальным данным. Управление кучей
  16. Генерация целевого кода. Распределение регистров. Адресация в целевом коде
  17. Локальная оптимизация. Параллелизм уровня команд. Конвейеризация. Оптимизация локальности

Лабораторные работы

  1. Лексический анализ
  2. Синтаксически анализ методом рекурсивного спуска
  3. Генераторы анализаторов
  4. Проверка типов
  5. Генерация трёхадресного кода
  6. Оптимизация трёхадресного кода
  7. Использование инструмента LLVM

Материалы

Исходные коды демонстраций доступны по адресу

Демонстрация работы различных парсеров (реализованных в виде автоматов с магазинной памятью) доступна по адресу https://lierdakil.github.io/parser-demo/index.html

Литература

  1. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2 изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4.
  2. Бенжамин Пирс. Типы в языках программирования. M.: “Лямбда-пресс”: “Добросвет”, 2014.