Компиляторы, 3 курс, 5 семестр, 2016/17 — различия между версиями
(→Лекции) |
(Добавил ссылку на зачётные задания.) |
||
(не показано 17 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | + | Лектор: Булычев Дмитрий Юрьевич. | |
− | + | ||
https://github.com/dboulytchev/sample-compiler | https://github.com/dboulytchev/sample-compiler | ||
− | Образ с настроенным софтом для виртуальной машины: [https://www.dropbox.com/s/2ybus3fxyp0ln1d/CompilerCourse.ova?dl=0 OVA] | + | Образ с настроенным софтом для виртуальной машины: [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/1Dp9KYpRoPlIqDyMQVRrMIfODq09r268hYZYNM2rjzAI/edit?ts=585394f8#gid=0 зачётные задания]. |
+ | |||
+ | '''Вся информация на этой странице сдублирована из почты!''' | ||
+ | |||
+ | == Домашние задания == | ||
+ | === Домашнее задание от 13.09.2016 === | ||
+ | # Дописать интерпретатор стековой машины с символическим стеком (там надо поддержать оставшиеся 5 инструкций). | ||
+ | # Реализовать печать инструкций в правильном формате ассемблера x86 (см., например, https://en.wikibooks.org/wiki/X86_Assembly/GAS_Syntax). | ||
+ | # Реализовать правильное "обрамление" порожденной программы: | ||
+ | <syntaxhighlight lang="asm"> | ||
+ | .text | ||
+ | .globl main | ||
+ | |||
+ | main: | ||
+ | <тут идет текст ассемблерного порождения> | ||
+ | ret | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === Конструкции управления === | ||
+ | |||
+ | Базовые: | ||
+ | # <code>if E then S1 else S2 fi</code>, где <code>E</code> — выражение, а <code>S1</code> и <code>S2</code> — операторы. Если значение <code>E</code> вычисляется не в ноль, то исполняется <code>S1</code>, иначе — <code>S2</code>. | ||
+ | # <code>while E do S od</code>, где <code>E</code> — выражение, <code>S</code> — оператор. Если значение <code>E</code> вычисляется в не ноль, то исполняется <code>S</code>, а потом весь <code>while</code> заново; иначе не делается ничего. | ||
+ | |||
+ | Дополнительные: | ||
+ | # <code>if E1 then S1 {elif E2 then S2 elif E3 then S3} ... [else Sk] fi</code> эквивалентно: | ||
+ | <pre> | ||
+ | if E1 then S1 | ||
+ | else if E2 then S2 | ||
+ | else if E3 then S3 | ||
+ | .... | ||
+ | [else Sk] | ||
+ | fi | ||
+ | </pre> | ||
+ | <ol start="2"> | ||
+ | <li><code>repeat S until E</code> эквивалентно <code>S; while E == 0 do S od</code></li> | ||
+ | <li><code>for S1, E, S2 do S od</code> эквивалентно <code>S1; while E do S; S2 od</code></li> | ||
+ | </ol> | ||
+ | |||
+ | === Поддержка функций === | ||
+ | |||
+ | На уровне выражений язык расширяется конструкцией вызова функции: <code><ident> (<expr>, <expr>, ...)</code>. Список аргументов может быть пустым, но скобки нужны в любом случае. | ||
+ | |||
+ | На уровне операторов язык расширяется двумя конструкциями: | ||
+ | # <code><ident> (<expr> , <expr>, ... )</code> — вызов функции. Список аргументов может быть пустым, но скобки нужны в любом случае. | ||
+ | # <code>return <expr></code> — возврат значения. Выполнение функции должно всегда заканчиваться выполнением оператора <code>return</code>; если функция вызывается как оператор, то её результат теряется. | ||
+ | |||
+ | |||
+ | Кроме того, теперь перед самой программой может идти одно или несколько описаний функций. Каждое описание имеет следующий вид: | ||
+ | <pre> | ||
+ | fun <ident> (<ident> , <ident>, ... ) | ||
+ | begin | ||
+ | <stmt> | ||
+ | end | ||
+ | </pre> | ||
+ | Список формальных параметров може быть пуст, но скобки нужны в любом случае. | ||
+ | |||
+ | Правила видимости для переменных внутри функции: каждая функция "видит" свои параметры; все остальные используемые переменные считаются локальными для данного вызова функции. Глобальные переменные не видны. Функции могут быть рекурсивными, в том числе взаимно-рекурсивными. | ||
+ | |||
+ | Расширение системы команд стековой машины: | ||
+ | # <code>CALL of string * string list</code> — инструкция вызова. Получает имя функции и список имен её параметров. | ||
+ | # <code>RET</code> — возврат из функции. | ||
+ | # <code>END</code> — конец программы (завершает выполнение, даже если "хвост" инструкций не пуст). | ||
+ | |||
+ | Пример: | ||
+ | |||
+ | <pre> | ||
+ | fun fact (n) | ||
+ | begin | ||
+ | if n < 2 | ||
+ | then return 1 | ||
+ | else return n * fact (n-1) | ||
+ | fi | ||
+ | end | ||
+ | |||
+ | read (n); | ||
+ | write (fact (n)) | ||
+ | </pre> | ||
+ | |||
+ | === Builtins и строки === | ||
+ | |||
+ | Встроенная функция --- это (в нашем случае) некоторая предопределенная функция. Для | ||
+ | эталонного и стекового интерпретаторов встроенные функции реализованы на языке | ||
+ | реализации интерпретатора (в нашем случае --- OCaml), в нативном случае --- на | ||
+ | языке реализации рантайма (в нашем случае --- C). Встроенные функции могут оказать влияние | ||
+ | на входной и выходной потоки (но не на состояние), это надо учесть при реализации. | ||
+ | |||
+ | Соответственно, для поддержки встроенной функции в интерпретаторе надо, в случае, когда | ||
+ | вызываемая функция не обнаружена, проверить, не является ли она встроенной (по имени), и если | ||
+ | является, то соответствующим образом её отынтерпретировать. | ||
+ | |||
+ | Для поддержки строенной функции в стековой машине надо добавить в машину инструкцию | ||
+ | BUILTIN (f, n), где f --- имя функции, n --- количество её аргументов. Эту инструкцию надо генерировать | ||
+ | в стековом интерпретаторе в ситуации, когда встречается вызов неопределенной функции. | ||
+ | |||
+ | Для поддержки встроенных функций в нативном коде ничего специального не требуется --- | ||
+ | надо сгенерировать для инструкции BUILTIN точно такой же код, что и для инструкции CALL (ну и, | ||
+ | конечно, реализовать саму встроенную функцию в рантайме). | ||
+ | |||
+ | Следует избегать дублирования кода при реализации встроенных функций для эталонного и стекового | ||
+ | интерпретаторов (в обоих случаях это должен быть один и тот же код). | ||
+ | |||
+ | Соответственно, из AST языка пропадают конструкции READ и WRITE, из систем команд | ||
+ | стековой машины пропадают инструкции READ и WRITE (но добавляется BUILTIN). | ||
+ | |||
+ | Потребуются некоторые изменения в парсере: надо выбросить ключевые слова read и write и | ||
+ | убрать разбор соответствующих операторов. Теперь вместо read(x) надо будет писать x := read (). | ||
+ | Все тесты должны проходить по-старому (надеюсь, ни у кого не возникнет трудностей с переделыванием | ||
+ | существующих тестов на новый синтаксис). | ||
+ | |||
+ | Поддержка строковых значений в языке обеспечивается добавлением следующих конструкций: | ||
+ | # Строковых констант вида <code>"....."</code> в выражениях. Для их представления потребуется новый узел AST для выражений и новая инструкция SPUSH (s) в стековой машине. | ||
+ | # Целочисленных констант вида <code>'<один символ>'</code> в выражениях. Это просто синтаксический сахар на уровне парсера. | ||
+ | # Набора встроенных функций. | ||
+ | |||
+ | Заметим, что теперь значениями в программе являются не только целые числа, но и строки --- поэтому | ||
+ | на уровне интерпретатора предлагается завести модуль для значений: | ||
+ | |||
+ | <pre> | ||
+ | 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 | ||
+ | </pre> | ||
+ | |||
+ | Эти изменения надо "протянуть" через весь код (это не так страшно, как может показаться на первый взгляд). | ||
+ | Набор встроенных функций таков: | ||
+ | |||
+ | * <code>strmake (n, c)</code> --- делает строку длины n, заполненную символами с (n >= 0, иначе неизвестно, что), и возвращает эту строку. | ||
+ | * <code>strset (s, i, c)</code> --- присваивает i-му элементу строки s значение c и возвращает измененную строку. | ||
+ | * <code>strget (s, i)</code> --- возвращает i-й элемент строки s. | ||
+ | * <code>strdup (s)</code> --- возвращает копию строки s. | ||
+ | * <code>strcat (s1, s2)</code> --- возвращает конкатенацию строк s1 и s2. | ||
+ | * <code>strcmp (s1, s2)</code> --- сравнивает строки s1 и s2 лексикографически и возвращает -1, если s1<s2, 0, если s1=s2, и 1 --- иначе. | ||
+ | * <code>strlen (s)</code> --- возвращает длину строки s. | ||
+ | * <code>strsub (s, i, l)</code> --- возвращает подстроку длины l строки s, начиная с i-й позиции включительно (т.е. strcmp (s, strsub (s, 0, strlen (s))) == 0). | ||
+ | |||
+ | === Массивы === | ||
+ | Для поддержки массивов язык расширяется | ||
+ | |||
+ | # На уровне выражений --- конструкциями: | ||
+ | ## <code>[ expr_1, expr_2, ..., expr_k ]</code>, где <math>k \ge 0</math>, <code>expr_i</code> --- целое выражение. Это unboxed-массив целых. | ||
+ | ## <code>{ expr_1, expr_2, ..., expr_k }</code>, где <math>k \ge 0</math>, <code>expr_i</code> --- выражение, вычисляющееся в строку или массив. Это boxed-массив. | ||
+ | ## <code>expr [index]</code> --- выборка элемента массива; здесь expr --- выражение, вычисляющееся в массив (то есть идентификатор, выборка из массива или вызов функции), index --- целое выражение. | ||
+ | # На уровне операторов --- присваиванием вида <code>ident[index_1][index_2]...[index_k] := value</code>, где ident -- идентификатор массива, <code>index_i</code> --- целое выражение, value --- произвольное выражение. | ||
+ | # На уровне builtins --- функциями: | ||
+ | ## <code>arrlen (a)</code> --- возвращает число элементов массива а | ||
+ | ## <code>arrmake (n, v)</code> --- возвращает массив целых длины n, все элементы которого равны v. | ||
+ | ## <code>Arrmake (n, v)</code> --- возвращает boxed-массив массивов или строк длины n, все элементы которого равны v. | ||
+ | |||
+ | В интерпретатор добавлется новый вид значений: | ||
+ | <pre> | ||
+ | module Value = | ||
+ | struct | ||
+ | type t = .... | Array of value array | ||
+ | |||
+ | ... | ||
+ | |||
+ | let of_array = ... | ||
+ | let to_array = ... | ||
+ | end | ||
+ | </pre> | ||
+ | |||
+ | В стековую машину добавляются инструкции: | ||
+ | |||
+ | # <code>ARRAY of bool * int</code>; <code>ARRAY(boxed, n)</code> снимает со стека n значений, создает boxed или unboxed массив и кладет этот массив на стек. | ||
+ | # <code>ELEM</code> --- снимает со стека массив и индекс и кладет обратно элемент по данному индексу. | ||
+ | # <code>STA of string * int</code>; <code>STA (x, n)</code> снимает со стека n+1 значение i_1, i_2, ..., i_n, v и осуществляет присваивание <code>x[i_1][i_2]...[i_n] := v</code>. | ||
+ | |||
+ | == Документация == | ||
+ | === Система сборки (новая) === | ||
+ | Используется [http://opam.ocaml.org/ opam] - это пакетный менеджер для OCaml. | ||
+ | |||
+ | Подготовка (альтернативно можно запустить [https://gist.github.com/LDVSOFT/ea030ba8ec24f12c8c579522bd99e90a скрипт от Димы]): | ||
+ | # Требуется установить opam версии хотя бы 1.2.2. Есть в репозиториях Debian/Ubuntu (<code>sudo apt-get install opam</code>). | ||
+ | # Должен автоматически поставится компилятор ocaml. Проверяем версию: <code>ocaml -version</code>. | ||
+ | # Если версия хотя бы 4.02 - запускаем из домашнего каталога <code>opam init</code>. Если версия древнее — запускаем <code>opam init --comp 4.03.0</code>. | ||
+ | # Чтобы подцепить изменения в окружении в текущей сессии, надо запустить <code>eval `opam config env`</code>. Теперь версия компилятора точно должна быть хотя бы 4.02. | ||
+ | # Выполняем команды: | ||
+ | <pre> | ||
+ | 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 | ||
+ | </pre> | ||
+ | <ol start="6"> | ||
+ | <li>Также для сборки <code>runtime.o</code> на Debian/Ubuntu может потребоваться пакет <code>g++-multilib</code>.</li> | ||
+ | </ol> | ||
+ | |||
+ | Как собирать: | ||
+ | * Если вы находитесь в корне репозитория: <code>make -f Makefile.ob</code>. | ||
+ | * Если вы находитесь не в корне, а, скажем, в папке src, то надо добавить параметр <code>-C <путь-до-корня></code>: <code>make -C .. -f Makefile.ob</code>. |
Текущая версия на 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
.