Просмотр исходного текста страницы Языки программирования и компиляторы осень 2021

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

=== Обратная связь ===

Булычев Дмитрий (Юрьевич), <code>dboulytchev@gmail.ru></code>, <code>@senormouse</code>

Березун Даниил (Андреевич), <code>danya.berezun@gmail.com</code>

[https://t.me/joinchat/w2qy7Wwu6s85OGFi Телеграм-группа для оперативного общения]

=== Родственные курсы ===

[https://compscicenter.ru/courses/programming-language-semantics/2020-spring Семантика языков программирования ]

[https://compscicenter.ru/courses/formal-verification/2020-spring Основы формальной верификации]

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

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

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

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

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

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

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

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

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

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

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

* Конструкции управления как операторы.

* Конструкции управления как выражения. Указатели как значения --- за и против.

* Процедуры и функции. Варианты организации вызовов и передачи параметров.

* Массивы и строки. Варианты определения и реализации.

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

* Функции как значения.

* Функции высших порядков, дефункционализация, лямбда-лифтинг, построение замыканий.

* Арифметика с коррекцией (fixnum), автоматическое управление памятью, сборка мусора.

=== Конспекты ===

[[Медиа:01.pdf | Лекция 1. Абстрактный синтаксис. Операционная семантика. Интерпретаторы и кмопиляторы. Операционная семантика простого языка выражений. ]]

[[Медиа:02.pdf | Лекция 2. Линейные программы. Абстрактная стековая машина. Глубокое и поверхностное встраивание языков. ]]

Лекция 3. Архитектура и система команд процессора x86-32. Использование системы gcc при программировании на ассемблере. Структура ассемблерной программы с точки зрения компилятора. Символический интерпретатор стековых программ как генератор кода.

Лекция 4. Проблема преобразования конкретного синтаксиса в абстрактный. Проблемы, возникающие при использовании КС-разбора при реализации синтаксических анализаторов. Однопроходная схема разбора, атрибутные грамматики, L-атрибутные грамматики, монадические парсер-комбинаторы.

[[Медиа:03.pdf | Лекция 5. Конструкции управления. Синтаксические расширения, вопросы применимости. Расширение стековой машины. Проекции конструкций управления в стековую машину. Инварианты для символического интерпретатора.  ]]

[[Медиа:05.pdf | Лекция 6. Конструкции управления как выражения. Система атрибутов, корректность абстрактного синтаксического дерева. ]]

[[Медиа:06.pdf | Лекция 7. Функции и локальные области. ]]

[[Медиа:07.pdf | Лекция 8. Структуры данных. ]]

[[Медиа:08.pdf | Лекция 9. Сопоставление с образцом. ]]

=== Лекции курса 2020 года ===

[https://www.youtube.com/watch?v=Nk1WOuMFbio]

[https://www.youtube.com/watch?v=uv94_4nzw7I]

[https://www.youtube.com/watch?v=dtWWdXrzKdY]

[https://www.youtube.com/watch?v=YN1iYczgkxE]

[https://www.youtube.com/watch?v=ebx7oqKI6ik]

[https://www.youtube.com/watch?v=uRPKnr1XeZM]

[https://www.youtube.com/watch?v=VTRoyZFeHRY]

[https://www.youtube.com/watch?v=JdjbPKjCBwc]

[https://www.youtube.com/watch?v=UlqWE9N4vIs]

[https://www.youtube.com/watch?v=8sUrj_gAdWM]

[https://www.youtube.com/watch?v=_R-c3gkVUeA]

=== Критерии получения оценки ===

Еженедельно слушателям курса предлагается домашнее задание с небольшим сроком выполнения (1-2 недели). В конце семестра будет проходить обязательный финальный экзамен. К нему студент зарабатывает оценку по домашним заданиям по следующему правилу: 

- отлично -- сданы все домашние задания

- хорошо -- сданы все, кроме одного 

- удовлетворительно -- сданы все, кроме двух

На экзамене вам будет предложено «подтвердить» свою оценку, ответив на небольшой теоретический вопрос или прокомментировав собственный код. Будет возможность как повысить оценку ответом (в случае, если она была спорной), так и понизить.

=== Репозиторий домашних заданий ===

[https://github.com/danyaberezun/compilers-2021-autumn Домашние задания]

[https://docs.google.com/spreadsheets/d/1Cs9XFVvEuXq3CaIk3YT9YF5EXpbkU0MjO4g-ajPKps8/edit#gid=1169405764 Табличка с результатами автоматической проверки]

Каждое домашнее задание расположено в ветке, имя которой начинается с <code>A<номер домашнего задания></code>. Этот репозиторий необходимо склонировать к себе, а выполненное домашнее задание оформить пулл-реквестом.

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

[https://github.com/JetBrains-Research/Lama  репозиторий языка Lama]

[https://github.com/dboulytchev/compilers-2021-spring репозиторий для домашних заданий]

[https://ocaml.org среда программирования OCaml]

[https://gcc.gnu.org компилятор GCC]

[https://llvm.org инфраструктура LLVM]

[https://gcc.gnu.org/wiki/ListOfCompilerBooks cписок книжек про конструирование компиляторов]

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

* 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. Считается первой статьей по данному вопросу.

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

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