Компиляторы осень 2018

Материал из CSC Wiki
Перейти к:навигация, поиск

Булычев Дмитрий Юрьевич dboulytchev@gmail.com

Лекции

  • Лекции — краткий конспект лекций

Практика

  • Задание 1: написать интерпретатор языка выражений, заполнив соответствующие дыры в файле src/Exrp.ml. Напомню, что мы используем глубокое встраивание языка выражений в OCaml. Пример записи выражения можно найти в конце файла src/Embedding.ml.
  • Задание 2: в файл src/Syntax.ml (в соответствующие дыры) встроить интерпретатор языка выражений из задания 1, а также реализовать интерпретатор языка (с операторами); в файле src/SM.ml реализовать интерпретатор стековой машины и компилятор нашего языка в стековую машину.
  • Задание 3. Файл src/Language.ml --- бывший src/Syntax.ml, куда надо вставить уже реализованные вами функции, а также реализовать парсеры выражений и операторов. Нужные вам примеры написания парсеров на Ostap можно найти в конце файла туториал по Ostap. Не забудьте также поправить файл src/SM.ml, согласно предыдущему заданию. Обратите внимание, что тестов стало больше (см. папки regression/expressions и regression/deep-expressions). Пожалуйста, перед тем как открывать pull-request, убедитесь, что все тесты проходят.
  • Задание 4. Реализовать генератор кода как символический интерпретатор стековой машины. Не забудьте поставить gcc-multilib перед началом работы.
  • Задание 5. Обогатить язык конструкциями управления (if-then-elif-...-else-fi, skip, while-do, for-do, repeat-until). Иными словами:
  1. Реализовать синтаксический анализатор для конструкций управления;
  2. Реализовать интерпретатор исходного языка;
  3. Реализовать интерпретатор для расширенной стековой машины;
  4. Реализовать компилятор из расширенного языка в расширенную стековую машину;
  5. Реализовать символический интерпретатор стековой машины для генерации кода для x86.
  1. Операции над расширенным состоянием;
  2. Интерпретатор исходного языка с процедурами;
  3. Интерпретатор стековой машины;
  4. Компилятор языка с процедурами в код для стековой машины.
  • Задание 7 [Deadline: 06.11.2018]. Реализовать интерпретатор исходного языка с функциями, интерпретатор и компилятор для стековой машины.
  • Задание 8 [Deadline: 06.11.2018]. Дописать генератор кода для поддержки процедур и функций.
  • Задание 9 Реализовать поддержку встроенных функций, массивов и строк.
  • Задание 10 В контексте интерпретации реализовать S-выражения и сопоставление с образцом.
  • Задание 11 Реализовать (во всех режимах) встроенные функции, массивы, строки, S-выражения, сопоставление с образцом, арифметику с коррекцией. (NB: обратите внимание на README: устновите нужную версию GT)

Как сдавать домашние задания

  1. fork compiler-workout репозитория
  2. checkout ветки hw<номер_задания>
  3. pull request в ту же ветку в оригинальный репозиторий, озаглавленный [hw<номер_задания>] <ваша_фамилия_и_имя>
  4. если прошли тесты, буду проверять вручную

Рекомендуемая версия OCaml: 4.06.01

Отметка за курс

  1. Сданы задания с 1 по 7 (включительно) --- 3
  2. Сданы задания с 1 по 9 (включительно) --- 4
  3. Сданы задания с 1 по 11 (все) --- 5

Полезные ссылки

Литература

  1. «Compiler Construction», N.Wirth — одна из немногих книг, пользуясь которой можно действительно написать компилятор, не умея этого делать предварительно. Идеологически близка курсу, но использует другие технические подходы
  2. «Semantics with Applications. A formal introduction», F.Nielson, H-R.Nielson — аккуратное введение в семантику языков программирования
  3. «Semantics of context-free languages», D.Knuth — статья Кнута, в которой вводятся атрибутные грамматики
  4. «Monadic parser combinators», G.Hutton, E.Meijer — считается первой статьей по данному вопросу