Компиляторы, 3 курс, 5 семестр, 2016/17

Лектор: Булычев Дмитрий Юрьевич.

https://github.com/dboulytchev/sample-compiler

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

Результаты, зачётные задания.

Вся информация на этой странице сдублирована из почты!

Домашние задания

Домашнее задание от 13.09.2016

1. Дописать интерпретатор стековой машины с символическим стеком (там надо поддержать оставшиеся 5 инструкций).
2. Реализовать печать инструкций в правильном формате ассемблера x86 (см., например, https://en.wikibooks.org/wiki/X86_Assembly/GAS_Syntax).
3. Реализовать правильное "обрамление" порожденной программы:

            .text
            .globl main

main:
            <тут идет текст ассемблерного порождения>
            ret

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

Базовые:

1. if E then S1 else S2 fi, где E — выражение, а S1 и S2 — операторы. Если значение E вычисляется не в ноль, то исполняется S1, иначе — S2.
2. while E do S od, где E — выражение, S — оператор. Если значение E вычисляется в не ноль, то исполняется S, а потом весь while заново; иначе не делается ничего.

Дополнительные:

1. if E1 then S1 {elif E2 then S2 elif E3 then S3} ... [else Sk] fi эквивалентно:

    if E1 then S1
    else if E2 then S2
           else if E3 then S3
           ....
           [else Sk]
    fi 

2. repeat S until E эквивалентно S; while E == 0 do S od
3. for S1, E, S2 do S od эквивалентно S1; while E do S; S2 od

Поддержка функций

На уровне выражений язык расширяется конструкцией вызова функции: <ident> (<expr>, <expr>, ...). Список аргументов может быть пустым, но скобки нужны в любом случае.

На уровне операторов язык расширяется двумя конструкциями:

1. <ident> (<expr> , <expr>, ... ) — вызов функции. Список аргументов может быть пустым, но скобки нужны в любом случае.
2. return <expr> — возврат значения. Выполнение функции должно всегда заканчиваться выполнением оператора return; если функция вызывается как оператор, то её результат теряется.

Кроме того, теперь перед самой программой может идти одно или несколько описаний функций. Каждое описание имеет следующий вид:

fun <ident> (<ident> , <ident>, ... )
begin
    <stmt>
end

Список формальных параметров може быть пуст, но скобки нужны в любом случае.

Правила видимости для переменных внутри функции: каждая функция "видит" свои параметры; все остальные используемые переменные считаются локальными для данного вызова функции. Глобальные переменные не видны. Функции могут быть рекурсивными, в том числе взаимно-рекурсивными.

Расширение системы команд стековой машины:

1. CALL of string * string list — инструкция вызова. Получает имя функции и список имен её параметров.
2. RET — возврат из функции.
3. END — конец программы (завершает выполнение, даже если "хвост" инструкций не пуст).

Пример:

fun fact (n)
begin
  if n < 2
     then return 1
     else return n * fact (n-1)
  fi
end

read (n);
write (fact (n))

Builtins и строки

Встроенная функция --- это (в нашем случае) некоторая предопределенная функция. Для эталонного и стекового интерпретаторов встроенные функции реализованы на языке реализации интерпретатора (в нашем случае --- OCaml), в нативном случае --- на языке реализации рантайма (в нашем случае --- C). Встроенные функции могут оказать влияние на входной и выходной потоки (но не на состояние), это надо учесть при реализации.

Соответственно, для поддержки встроенной функции в интерпретаторе надо, в случае, когда вызываемая функция не обнаружена, проверить, не является ли она встроенной (по имени), и если является, то соответствующим образом её отынтерпретировать.

Для поддержки строенной функции в стековой машине надо добавить в машину инструкцию BUILTIN (f, n), где f --- имя функции, n --- количество её аргументов. Эту инструкцию надо генерировать в стековом интерпретаторе в ситуации, когда встречается вызов неопределенной функции.

Для поддержки встроенных функций в нативном коде ничего специального не требуется --- надо сгенерировать для инструкции BUILTIN точно такой же код, что и для инструкции CALL (ну и, конечно, реализовать саму встроенную функцию в рантайме).

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

Соответственно, из AST языка пропадают конструкции READ и WRITE, из систем команд стековой машины пропадают инструкции READ и WRITE (но добавляется BUILTIN).

Потребуются некоторые изменения в парсере: надо выбросить ключевые слова read и write и убрать разбор соответствующих операторов. Теперь вместо read(x) надо будет писать x := read (). Все тесты должны проходить по-старому (надеюсь, ни у кого не возникнет трудностей с переделыванием существующих тестов на новый синтаксис).

Поддержка строковых значений в языке обеспечивается добавлением следующих конструкций:

1. Строковых констант вида "....." в выражениях. Для их представления потребуется новый узел AST для выражений и новая инструкция SPUSH (s) в стековой машине.
2. Целочисленных констант вида '<один символ>' в выражениях. Это просто синтаксический сахар на уровне парсера.
3. Набора встроенных функций.

Заметим, что теперь значениями в программе являются не только целые числа, но и строки --- поэтому на уровне интерпретатора предлагается завести модуль для значений:

    module Value =
       struct
           type t = Int of int | String of bytes

           let of_int : int -> t = ...
           let of_string : bytes -> t = ...
           let to_int : t -> int = ...
           let to_string : t -> string = ...
       end

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

• strmake (n, c) --- делает строку длины n, заполненную символами с (n >= 0, иначе неизвестно, что), и возвращает эту строку.
• strset (s, i, c) --- присваивает i-му элементу строки s значение c и возвращает измененную строку.
• strget (s, i) --- возвращает i-й элемент строки s.
• strdup (s) --- возвращает копию строки s.
• strcat (s1, s2) --- возвращает конкатенацию строк s1 и s2.
• strcmp (s1, s2) --- сравнивает строки s1 и s2 лексикографически и возвращает -1, если s1<s2, 0, если s1=s2, и 1 --- иначе.
• strlen (s) --- возвращает длину строки s.
• strsub (s, i, l) --- возвращает подстроку длины l строки s, начиная с i-й позиции включительно (т.е. strcmp (s, strsub (s, 0, strlen (s))) == 0).

Массивы

Для поддержки массивов язык расширяется

1. На уровне выражений --- конструкциями:
   1. [ expr_1, expr_2, ..., expr_k ], где $k\geq 0$, expr_i --- целое выражение. Это unboxed-массив целых.
   2. { expr_1, expr_2, ..., expr_k }, где $k\geq 0$, expr_i --- выражение, вычисляющееся в строку или массив. Это boxed-массив.
   3. expr [index] --- выборка элемента массива; здесь expr --- выражение, вычисляющееся в массив (то есть идентификатор, выборка из массива или вызов функции), index --- целое выражение.
2. На уровне операторов --- присваиванием вида ident[index_1][index_2]...[index_k] := value, где ident -- идентификатор массива, index_i --- целое выражение, value --- произвольное выражение.
3. На уровне builtins --- функциями:
   1. arrlen (a) --- возвращает число элементов массива а
   2. arrmake (n, v) --- возвращает массив целых длины n, все элементы которого равны v.
   3. Arrmake (n, v) --- возвращает boxed-массив массивов или строк длины n, все элементы которого равны v.

В интерпретатор добавлется новый вид значений:

    module Value =
       struct
          type t = .... | Array of value array

          ...

          let of_array = ...
          let to_array = ...
       end

В стековую машину добавляются инструкции:

1. ARRAY of bool * int; ARRAY(boxed, n) снимает со стека n значений, создает boxed или unboxed массив и кладет этот массив на стек.
2. ELEM --- снимает со стека массив и индекс и кладет обратно элемент по данному индексу.
3. STA of string * int; STA (x, n) снимает со стека n+1 значение i_1, i_2, ..., i_n, v и осуществляет присваивание x[i_1][i_2]...[i_n] := v.

Документация

Система сборки (новая)

Используется opam - это пакетный менеджер для OCaml.

Подготовка (альтернативно можно запустить скрипт от Димы):

1. Требуется установить opam версии хотя бы 1.2.2. Есть в репозиториях Debian/Ubuntu (sudo apt-get install opam).
2. Должен автоматически поставится компилятор ocaml. Проверяем версию: ocaml -version.
3. Если версия хотя бы 4.02 - запускаем из домашнего каталога opam init. Если версия древнее — запускаем opam init --comp 4.03.0.
4. Чтобы подцепить изменения в окружении в текущей сессии, надо запустить eval `opam config env`. Теперь версия компилятора точно должна быть хотя бы 4.02.
5. Выполняем команды:

opam pin add logger https://github.com/dboulytchev/logger.git -y -n
opam pin add GT https://github.com/dboulytchev/GT.git -y -n
opam pin add ostap https://github.com/dboulytchev/ostap.git -y -n
opam pin add ocanren https://github.com/dboulytchev/ocanren.git -y -n 
opam install ostap
opam install ocanren

6. Также для сборки runtime.o на Debian/Ubuntu может потребоваться пакет g++-multilib.

Как собирать:

• Если вы находитесь в корне репозитория: make -f Makefile.ob.
• Если вы находитесь не в корне, а, скажем, в папке src, то надо добавить параметр -C <путь-до-корня>: make -C .. -f Makefile.ob.