Языки программирования и компиляторы
Заочный курс / весна 2018, посмотреть все семестры

Данный курс представляет собой начальное введение в область языков программирования, компиляторов и других языковых инструментов. Будут сформулированы некоторые основные понятия и подходы в данной области, такие, как операционная семантика языков программирования, промежуточное представление программ, интерпретация, преобразования программ и т.д., и показано, как эти понятия и подходы решают важные и интересные практические задачи. Предполагается, что слушатели в процессе выполнения заданий к концу курса реализуют полноценный компилятор в машинный код для простого, но вполне функционального языка императивного программирования, содержащего выражения, присваивания, конструкции управления, функции и динамические структуры данных. В качестве основного инструмента в рамках курса будет использована cреда программирования OCaml.

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

1) Из истории вопроса. Программирующие программы.

2) Языки программирования и машинные архитектуры. Что происходит с программой при трансляции. Понятие среды трансляции (toolchain). Раскрутка компилятора (bootstrapping).

3) Как устроен компилятор. Промежуточное представление и просмотры. Программа и библиотека поддержки времени исполнения. Компилятор GCC, инфраструктура LLVM.

4) Канонический интерпретатор. Операционная семантика как способ описания канонического интерпретатора. Простейший язык: выражения и присваивания.

5) Стадия синтаксического анализа - мифы и реальность. Построение атрибутированного дерева. Встраиваимые языки (embedded languages). Поверхностное (shallow) и глубокое (deep) встраивание.

6) Стековая машина. Система команд, операционная семантика. Интерпретатор стековой машины.

7) Компилятор языка выражений в стековую машину. Корректность/частичная корректность компилятора, её обоснование.

8) Символический интерпретатор стековой машины как генератор кода.

9) Система команд x86. Память, регистры, режимы адресации. Среда трансляции GCC, устройство ассемблерного файла, метки и директивы.

10) Генератор кода для выражений и присваиваний. Тестирование.

11) Конструкции управления. Расширение интерпретатора. Расширение стековой машины. Расширение компилятора для стековой машины. Генерация кода для конструкций управления. Тестирование.

12) Процедуры и функции. Варианты организации вызовов и передачи параметров. Расширение интерпретатора. Расширение стековой машины. Расширение компилятора для стековой машины. Генерация кода для функций. Тестирование.

13) Динамические структуры данных. Дисциплины управления динамической памятью.

14) Символические выражения и сопоставление с образцом.

Полезные ссылки и литература

ocaml.org - среда программирования OCaml;

gcc.gnu.org - компилятор GCC;

llvm.org - инфраструктура LLVM;

gcc.gnu.org/wiki/ListOfCompilerBooks - список книжек про конструирование компиляторов.

N.Wirth. Compiler Construction. Книжка Вирта, одна из немногих, пользуясь которой можно действительно написать компилятор, не умея этого делать предварительно. Идеологически близка курсу, но использует другие технические подходы.

F.Nielson, H-R.Nielson. Semantics with Applications. A formal introduction. Аккуратное введение в семантику языков программирования.

D.Knuth. Semantics of context-free languages. Статья Кнута, в которой вводятся атрибутные грамматики.

G.Hutton, E.Meijer. Monadic parser combinators. Считается первой статьей по данному вопросу.

http://www.felixcloutier.com/x86 - описание системы команд x86.

Некоторые предварительные требования

Основы архитектуры и принципы функционирования ЭВМ, основы программирования на ассемблере.

Основы функционального программирования (алгебраические типы данных, сопоставление с образцом, функции высших порядков, параметрический полиморфизм, рекурсия).

Дата и время Название Место Материалы
14 февраля
18:00–19:20
Введение, лекция Таймс, 2 этаж, ауд.204 слайдывидео, другие
21 февраля
18:00–19:20
Операционая семантика большого шага, лекция Таймс, 2 этаж, ауд.204 слайдывидео
28 февраля
18:00–19:20
Синтаксический анализ, лекция Таймс, 2 этаж, ауд.204 видео
07 марта
18:00–19:20
Генератор кода как символический интерпретатор стековой машины, лекция Таймс, 2 этаж, ауд.204 видео
14 марта
18:00–19:20
Структурная индукция. Корректность компилятора выражений, лекция Таймс, 2 этаж, ауд.204 слайдывидео
21 марта
18:00–19:20
Конструкции управления, лекция Таймс, 2 этаж, ауд.204 слайдывидео
28 марта
18:00–19:20
Процедуры, лекция Таймс, 2 этаж, ауд.204 слайдывидео
04 апреля
18:00–19:20
Функции, лекция Таймс, 2 этаж, ауд.204 слайдывидео
11 апреля
18:00–19:20
Организация вызовов функций в машинном коде, соглашения о вызовах, лекция Таймс, 2 этаж, ауд.204 видео
18 апреля
18:00–19:20
Зоопарк функций, лекция Таймс, 2 этаж, ауд.204 видео
25 апреля
18:00–19:20
Встроенные функции, массивы, строки, лекция Таймс, 2 этаж, ауд.204 видео
04 мая
18:00–19:20
S-выражения, сопоставление с образцом, лекция Таймс, 2 этаж, ауд.204 видео
16 мая
18:00–19:20
Встроенные функции, массивы, строки, S-выражения в машинном коде, лекция Таймс, 2 этаж, ауд.204 видео
23 мая
18:00–19:20
Компиляция сопоставления с образцом, лекция Таймс, 2 этаж, ауд.204 видео