Компиляторы, 3 курс, 5 семестр, 2016/17 — различия между версиями
(→Массивы) |
(Добавил ссылку на зачётные задания.) |
||
Строка 6: | Строка 6: | ||
Образ с настроенным софтом для виртуальной машины: [https://www.dropbox.com/s/2ybus3fxyp0ln1d/CompilerCourse.ova?dl=0 OVA] (логин внутри: <code>me</code>, пароль: <code>me</code>). | Образ с настроенным софтом для виртуальной машины: [https://www.dropbox.com/s/2ybus3fxyp0ln1d/CompilerCourse.ova?dl=0 OVA] (логин внутри: <code>me</code>, пароль: <code>me</code>). | ||
− | [https://docs.google.com/spreadsheets/d/1LCcCdSg37du3SfDVyndm5jwgndzCl0OmwRlG8bGVQ4M/edit?ts=57f74d1e#gid=0 Результаты] | + | [https://docs.google.com/spreadsheets/d/1LCcCdSg37du3SfDVyndm5jwgndzCl0OmwRlG8bGVQ4M/edit?ts=57f74d1e#gid=0 Результаты], |
+ | [https://docs.google.com/spreadsheets/d/1Dp9KYpRoPlIqDyMQVRrMIfODq09r268hYZYNM2rjzAI/edit?ts=585394f8#gid=0 зачётные задания]. | ||
'''Вся информация на этой странице сдублирована из почты!''' | '''Вся информация на этой странице сдублирована из почты!''' |
Текущая версия на 21:50, 18 декабря 2016
Лектор: Булычев Дмитрий Юрьевич.
https://github.com/dboulytchev/sample-compiler
Образ с настроенным софтом для виртуальной машины: OVA (логин внутри: me
, пароль: me
).
Вся информация на этой странице сдублирована из почты!
Содержание
Домашние задания
Домашнее задание от 13.09.2016
- Дописать интерпретатор стековой машины с символическим стеком (там надо поддержать оставшиеся 5 инструкций).
- Реализовать печать инструкций в правильном формате ассемблера x86 (см., например, https://en.wikibooks.org/wiki/X86_Assembly/GAS_Syntax).
- Реализовать правильное "обрамление" порожденной программы:
.text
.globl main
main:
<тут идет текст ассемблерного порождения>
ret
Конструкции управления
Базовые:
-
if E then S1 else S2 fi
, гдеE
— выражение, аS1
иS2
— операторы. Если значениеE
вычисляется не в ноль, то исполняетсяS1
, иначе —S2
. -
while E do S od
, гдеE
— выражение,S
— оператор. Если значениеE
вычисляется в не ноль, то исполняетсяS
, а потом весьwhile
заново; иначе не делается ничего.
Дополнительные:
-
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
repeat S until E
эквивалентноS; while E == 0 do S od
for S1, E, S2 do S od
эквивалентноS1; while E do S; S2 od
Поддержка функций
На уровне выражений язык расширяется конструкцией вызова функции: <ident> (<expr>, <expr>, ...)
. Список аргументов может быть пустым, но скобки нужны в любом случае.
На уровне операторов язык расширяется двумя конструкциями:
-
<ident> (<expr> , <expr>, ... )
— вызов функции. Список аргументов может быть пустым, но скобки нужны в любом случае. -
return <expr>
— возврат значения. Выполнение функции должно всегда заканчиваться выполнением оператораreturn
; если функция вызывается как оператор, то её результат теряется.
Кроме того, теперь перед самой программой может идти одно или несколько описаний функций. Каждое описание имеет следующий вид:
fun <ident> (<ident> , <ident>, ... ) begin <stmt> end
Список формальных параметров може быть пуст, но скобки нужны в любом случае.
Правила видимости для переменных внутри функции: каждая функция "видит" свои параметры; все остальные используемые переменные считаются локальными для данного вызова функции. Глобальные переменные не видны. Функции могут быть рекурсивными, в том числе взаимно-рекурсивными.
Расширение системы команд стековой машины:
-
CALL of string * string list
— инструкция вызова. Получает имя функции и список имен её параметров. -
RET
— возврат из функции. -
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 (). Все тесты должны проходить по-старому (надеюсь, ни у кого не возникнет трудностей с переделыванием существующих тестов на новый синтаксис).
Поддержка строковых значений в языке обеспечивается добавлением следующих конструкций:
- Строковых констант вида
"....."
в выражениях. Для их представления потребуется новый узел AST для выражений и новая инструкция SPUSH (s) в стековой машине. - Целочисленных констант вида
'<один символ>'
в выражениях. Это просто синтаксический сахар на уровне парсера. - Набора встроенных функций.
Заметим, что теперь значениями в программе являются не только целые числа, но и строки --- поэтому на уровне интерпретатора предлагается завести модуль для значений:
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).
Массивы
Для поддержки массивов язык расширяется
- На уровне выражений --- конструкциями:
-
[ expr_1, expr_2, ..., expr_k ]
, где ,expr_i
--- целое выражение. Это unboxed-массив целых. -
{ expr_1, expr_2, ..., expr_k }
, где ,expr_i
--- выражение, вычисляющееся в строку или массив. Это boxed-массив. -
expr [index]
--- выборка элемента массива; здесь expr --- выражение, вычисляющееся в массив (то есть идентификатор, выборка из массива или вызов функции), index --- целое выражение.
-
- На уровне операторов --- присваиванием вида
ident[index_1][index_2]...[index_k] := value
, где ident -- идентификатор массива,index_i
--- целое выражение, value --- произвольное выражение. - На уровне builtins --- функциями:
-
arrlen (a)
--- возвращает число элементов массива а -
arrmake (n, v)
--- возвращает массив целых длины n, все элементы которого равны v. -
Arrmake (n, v)
--- возвращает boxed-массив массивов или строк длины n, все элементы которого равны v.
-
В интерпретатор добавлется новый вид значений:
module Value = struct type t = .... | Array of value array ... let of_array = ... let to_array = ... end
В стековую машину добавляются инструкции:
-
ARRAY of bool * int
;ARRAY(boxed, n)
снимает со стека n значений, создает boxed или unboxed массив и кладет этот массив на стек. -
ELEM
--- снимает со стека массив и индекс и кладет обратно элемент по данному индексу. -
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.
Подготовка (альтернативно можно запустить скрипт от Димы):
- Требуется установить opam версии хотя бы 1.2.2. Есть в репозиториях Debian/Ubuntu (
sudo apt-get install opam
). - Должен автоматически поставится компилятор ocaml. Проверяем версию:
ocaml -version
. - Если версия хотя бы 4.02 - запускаем из домашнего каталога
opam init
. Если версия древнее — запускаемopam init --comp 4.03.0
. - Чтобы подцепить изменения в окружении в текущей сессии, надо запустить
eval `opam config env`
. Теперь версия компилятора точно должна быть хотя бы 4.02. - Выполняем команды:
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
- Также для сборки
runtime.o
на Debian/Ubuntu может потребоваться пакетg++-multilib
.
Как собирать:
- Если вы находитесь в корне репозитория:
make -f Makefile.ob
. - Если вы находитесь не в корне, а, скажем, в папке src, то надо добавить параметр
-C <путь-до-корня>
:make -C .. -f Makefile.ob
.