Пишемо хобі-компілятор підмножини Scala

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Ще на початку кар’єри я зацікавився, як IDE «розуміють» код, а потім — і як працюють компілятори.

Довгий час інтерес залишався теоретичним, так як життя вносило інші пріоритети. Але в 2020 році нарешті написав компілятор. Мова називається Cool 2020 і являє собою підмножину Scala. Компілятор генерує x86-64 виконувані файли. Працює на Windows і Linux.

Ця стаття для вас, якщо хочете почитати про досвід написання компілятора невеликої, навчальної мови, яка, однак, зберігає багато функцій повновагових мов програмування, включаючи класи, статичну типізацію і навіть найпростіший варіант зіставлення зі зразком (pattern matching).

Це не туторіал

Моя мета — розповісти про досвід написання компілятора. Про те, які рішення знадобилося прийняти до і в процесі розробки. З якими складнощами довелося зіткнутися. Описати структуру коду проекту з висоти пташиного польоту. Поділитися парою цікавих посилань на думки і досвід гуру, знайдених на просторах інтернету.

Якщо вам цікавий саме туторіал, прогортайте в кінець статті. Там є посилання на навчальні матеріали. На мою думку, вони дійсно дуже якісні і зрозумілі. Вважаю безглуздим писати ще один туторіал, що в будь-якому випадку вийшов би слабший існуючих.

Але навіщо?!

В ті часи, коли жарт «як пропатчити KDE2 під FreeBSD» був ще відносно свіжим, я влаштувався на проект, написаний на C++.

Працювали ми в Visual Studio 6.0. А незадовго після мого приходу колеги показали мені ще й Visual Assist. Це плагін, який покращує і розширює функції Visual Studio по роботі з C++ кодом. Він справив дуже сильне враження: здавалося, що це штучний інтелект — не менше.

Хоч основна робота і йшла на Windows, побудову і запуск проекту ми підтримували і під Linux. Для роботи з кодом під Linux використовували KDevelop і Eclipse CDT. На той момент ці середовища розробки не витримували порівняння навіть з «чистою» Visual Studio, а Visual Assist випереджав їх на десятиліття. В інтернеті тоді, на прохання підказати IDE під Linux, найпопулярнішою відповіддю була лекція про те, чому командне оточення Unix — це і є найпросунутіша IDE.

Тут-то я і зрозумів, це мій шанс зробити внесок у спільноту open source! Сам Лінус Торвальдс потисне мені руку. А може бути, навіть компанія Red Hat подарує пакет акцій. І потрібно-то всього нічого — поліпшити одну з С++ IDE під Linux, щоб вона стала як мінімум не гірше аналогів під Windows. Напевно, так я вперше і задався питанням, як IDE і компілятори «розуміють» код.

Але планам не судилося збутися. Я змінив роботу і став писати на C#. Тому C++ IDE, компілятори і Linux на довгий час відійшли на другий план ...

Нарешті в 2019-м я вирішив, що час уже взяти і розібратися у внутрішній кухні компіляторів. Почалося все з онлайн-курсу Алекса Айкена. Ну а закінчилася ця пригода написанням свого хоч і іграшкового, але цілком робочого компілятора.

Що будемо компілювати?

Давайте поглянемо на приклад, а подробиці розберемо трохи пізніше. Невелика закінчена програма на нашій мові програмування буде виглядати ось так.

class QuickSort() extends IO() {
  def quicksort(array: ArrayAny, lo: Int, hi: Int): Unit = {
    if (lo < hi) {
      var p: Int = partition(array, lo, hi);
      quicksort(array, lo, p - 1);
      quicksort(array, p + 1, hi)
    } else ()
  };
    
  def partition(array: ArrayAny, lo: Int, hi: Int): Int = {
    var pivot: Int = array.get(lo) match { case i: Int => i };
    var p: Int = lo;
    var i: Int = lo + 1;
    while (i <= hi) {
      if (((array.get(i)) match { case i: Int => i }) <= pivot)
        array_swap(array, i, { p = p + 1; p })
      else
        ();
      i = i + 1
    };
    
    array_swap(array, p, lo);
    p
  };
    
  def array_swap(array: ArrayAny, p: Int, q: Int): Unit = {
    var tmp: Any = array.get(p);
    array.set(p, array.get(q));
    array.set(q, tmp)
  };
    
  def out_array(array: ArrayAny): Unit = {
    var i: Int = 0;
    while (i < array.length()) {
      array.get(i) match {
        case i: Int => out_int(i); out_string(" ")
      };
        
      i = i + 1
    };
    
    out_nl()
  };
    
  {
    var array: ArrayAny = new ArrayAny(5);
    array.set(0, 30);
    array.set(1, 20);
    array.set(2, 50);
    array.set(3, 40);
    array.set(4, 10);
    
    out_array(array);
    quicksort(array, 0, array.length() - 1);
    out_array(array)
  };
}

class Main() {
  { new QuickSort() };
}

Запустити код можна за посиланням.

Алекс Айкен в своєму курсі з компіляторів розглядає мову Classroom Object Oriented Language або Cool. Не дивлячись на те що цей курс був одним з моїх основних навчальних ресурсів, я вирішив транслювати іншу мову — Cool 2020. Хоч назви і схожі, мови серйозно відрізняються. Алекс Айкен сам винайшов і спроектував мову Cool. У той час як Cool 2020 — це підмножина Scala (з кількома мінімальними несумісностями). Його виділив зі Scala і описав Джон Бойланд.

Чому саме підмножина Scala?

Напевно, у будь-якої платформи онлайн-курсів є так званий Honor Code. Один з пунктів якого забороняє публікувати онлайн відповіді до вправ курсу. Теоретично, такий пункт можна зрозуміти і як заборону на публікацію коду, написаного в рамках курсу.

Швидкий пошук показує, що на github, тим не менш, є багато репозиторіїв з рішеннями завдань курсу Compilers. Але ми простих шляхів не шукаємо, тому підберемо іншу навчальну мову програмування, щоб точно не порушити умови Honor Code.

Cool 2020 — варіант, який сподобався найбільше. Граматику цієї підмножини Scala можна подивитися в репозиторії проекту. Зверніть увагу, граматика написана без урахування пріоритетів операторів, які описані тут.

По-перше, синтаксис Cool 2020 виглядає досить сучасно. Значить, при написанні проекту доведеться вирішувати завдання наближені до виникаючих при розробці сучасних промислових компіляторів. А завдяки тому, що мова навчальна, ми збережемо обсяг робіт в розумних для хобі межах.

Наприклад, конструктор є частиною оголошення класу, а не окремим його членом. Розглянемо клас Greeter. Конструктор класу приймає один параметр — name. Також, компілятор автоматично додає до класу атрибут name, який отримує значення параметра конструктора name. Атрибут name використовується в методі speak.

class Greeter(var name: String) {
    var io: IO = new IO();
    
    def speak(): Unit = {
        io.out_string("Hello, " + name + "!");
        io.out_nl()
    };
}

class Main() { { new Greeter("World").speak() }; }

По-друге, ми зможемо користуватися інструментами призначеними для Scala. Зокрема, підсвічуванням синтаксису в редакторі, коли будемо писати код на Cool 2020. Ще, нам буде дуже корисною пісочниця Scala. Там можна запускати тестові програми на Cool 2020, щоб перевірити різні мовні тонкощі.

Ось код необхідний для запуску програм на Cool 2020 в пісочниці.

class ArrayAny(len: Int) {
  var _array = new Array[Any](len);
  def length(): Int = _array.length;
  def get(i: Int): Any = _array(i);
  def set(i: Int, value: Any): Unit = _array(i) = value;
}

class IO {
  def out_string(s: String): Unit = print(s);
  def out_int(i: Int): Unit = print(i);
  def out_nl(): Unit = println();
}

object Program {
  def main(args: Array[String]): Unit = {
    new Main()
  };
}

Як будемо компілювати?

Ось так.

Але щоб прийти до такого результату, непогано було б написати компілятор. А щоб його написати, треба вирішити якою мовою програмування це робити.

У 2016 або 17 році на Coursera я натрапив на курс Programming Languages. Частина А присвячена мові програмування Standard ML (SML). Веде курс виключно талановитий викладач. Може бути, тому мова мені дуже сподобався. Особливо враження справило те, яким гнучким і потужним може бути зіставлення зі зразком (pattern matching).

На платформі .NET існує мова з одного c SML сімейства — F#. Тому для C# розробника, зацікавленого в SML, наступний логічний крок — уважніше роздивитися мову програмування F#. Так я і зробив: написав на F # кілька невеликих програмок і чекав можливості спробувати його в проекті побільше.

Іграшковий компілятор — якраз проект побільше. До того ж, в інтернеті часто зустрічається думка, що мови сімейства SML добре підходять для такого завдання. А в одній з версій класичного підручника Modern Compiler Implementation приклади коду дані на SML. Отже, вирішено! Будемо писати на F#.

Хочу зазначити. Я планував дотримуватися функціонального стилю в коді, щоб вивчити і попрактикувати навички функціонального програмування. Але швидко зрозумів, що вивчення ФП і способів трансляції програм одночасно — не тягну. В результаті код в репозиторії написаний на F# з використанням об’єктно-орієнтованого і імперативного підходів.

Помилки часу компіляції

Перш ніж приступати до програмування, важливо вирішити, як компілятор має поводитися в разі виявлення помилок у коді, написаному користувачем.

Найпростіший варіант — виводити діагностичне повідомлення і зупиняти трансляцію, як тільки виявлена ​​перша помилка. Але якщо в програмі міститься кілька помилок, користувачеві доведеться кілька разів перезапускати компілятор, щоб виявити і виправити їх всі. Це не дуже зручно.

Інша стратегія — в разі виявлення помилки продовжити розбір вихідного коду, спробувати знайти якомога більше помилок за один раз. Мета такого підходу — не змушувати користувача запускати компілятор кілька разів, щоб виправити всі помилки компіляції в програмі.

Мінус цієї стратегії — вона призводить до відчутного ускладнення коду компілятора. Так як створює необхідність реалізувати евристики придушення каскадних помилок компіляції.

Що таке каскадні помилки? У прикладі коду нижче міститься одна помилка — в рядку 2 пропущена закриваюча дужка.

/* 1 */ class CascadingError {
/* 2 */     def force(: Unit = {
/* 3 */     };
/* 4 */ }

Але компілятор Scala діагностує дві помилки. Так як перша — справжня — помилка «заплутує» його. Друга помилка — каскадна.

CascadingError.scala:2: error: identifier expected but ':' found.
    def speak(: Unit = {
              ^
CascadingError.scala:3: error: ':' expected but ';' found.
    };
     ^

У нетривіальних випадках каскадні помилки можуть настільки зашумлювати діагностичні повідомлення, що користувачі шукають спосіб зупинити компілятор після першої знайденої помилки. Тому що незрозуміло, які з них необхідно виправити, а які — фантомні і можуть зникнути після правки реальних помилок.

Звичайно, існує і компромісний варіант. Зразком може виступити підхід, який застосовують в компіляторі C#. Ерік Ліпперт описав його на StackOverflow:

Briefly, the way the compiler works is it tries to get the program through a series of stages...

The idea is that if an early stage gets an error, we might not be able to successfully complete a later stage without (1) going into an infinite loop, (2) crashing, or (3) reporting crazy «cascading» errors. So what happens is, you get one error, you fix it, and then suddenly the next stage of compilation can run, and it finds a bunch more errors.

...

The up side of this design is that (1) you get the errors that are the most «fundamental» first, without a lot of noisy, crazy cascading errors, and (2) the compiler is more robust because it doesn’t have to try to do analysis on programs where the basic invariants of the language are broken. The down side is of course your scenario: that you have fifty errors, you fix them all, and suddenly fifty more appear. (выделение жирным моё. — М.Н.)

Підтвердження словами Еріка Ліпперта можна знайти у вихідному коді компілятора C#. Метод CompileAndEmit класу Microsoft.CodeAnalysis.CommonCompiler координує основний обсяг робіт пов’язаних з трансляцією C# і VB.NET. Зверніть увагу на виклики compilation.GetDiagnostics з різними значеннями з перерахування CompilationStage. З них починаються перевірки: чи вдало пройшла чергова фаза трансляції, необхідно зупинитися або можна переходити до наступної стадії.

Етапи компіляції

Описаним в цитаті шляхом підемо і ми. Звісно, в сильно спрощеному вигляді. Розіб’ємо процес трансляції на типові для багатопрохідних компіляторів етапи.

• Лексичний аналіз;
• Синтаксичний аналіз;
• Семантичний аналіз;
• Генерація x86-64 асемблера.

В рамках окремого етапу, спробуємо діагностувати максимальну кількість помилок. Але кожну наступну стадію трансляції будемо запускати, тільки якщо поточна не виявила помилок. Скажімо, якщо під час синтаксичного аналізу буде виявлено проблеми, семантичний аналіз запущений не буде.

Те ж саме стосується і переходу від лексичного аналізу до синтаксичного. Якщо не всі лексеми (вони ж — токени) вдається відкрити розпізнати, синтаксичний аналіз не почнеться, замість цього ми виконаємо зупинку.

У коді проекту сказане ілюструє CompileToAsmStep.fs і метод Invoke класу EmitExeHandler.

До речі, це якраз один з тих моментів, де ми сильно спрощуємо собі життя. У випадку C# лексичний і синтаксичний аналіз виконуються одночасно. Якщо лексичний аналізатор (лексер) не може розпізнати чергову лексему, синтаксичний аналізатор (парсер) все одно продовжує розбір коду. (По завершенню синтаксичного аналізу, семантичний, звичайно, запущений не буде — трансляція перерветься.)

Лексика і синтаксис

Насамперед нам будуть потрібні лексичний і синтаксичний аналізатори.

Завдання лексичного аналізатора полягає в тому, щоб у вхідному тексті, що складається з ланцюжка окремих символів, розпізнати лексеми, такі як числа, рядки, ідентифікатори, ключові слова, оператори, і т.д. Також в нашому випадку необхідно відкинути коментарі та прогалини.

Далі, синтаксичний аналізатор спробує перетворити вхідний потік лексем в абстрактне синтаксичне дерево (AST).

AST — це відображення структури тексту програми у вигляді дерева. Іншими словами, замість послідовності символів, з якою складно зробити щось корисне, у нас з’являється повноцінна структура даних. Саме навколо AST ми організуємо роботу наступних етапів компіляції.

Текст програми

class Main() { 
  var io: IO = new IO();

  {
    io.out_string(
          "Hello, World!");
    io.out_nl()
  }; 
}

AST, серіалізоване у JSON

{ "classes": [
  { "name": "Main", 
    "varformals": [],
    "extends": { "type": "Any", 
                 "actuals": [] },
    "body": [
     { "kind": "attribute", 
       "name": "io", "type": "IO",
       "value": { "kind": "new", 
                  "type": "IO", 
                  "actuals": [] } },
     { "kind": "block",
       "statements": [
        { "kind": "stmt",
          "expr": 
          { "kind": "dispatch",
            "receiver": "io",
            "method": "out_string", 
            "actuals": [ "\"Hello, World!\"" ] } 
        },
        { "kind": "expr",
          "expr": 
          { "kind": "dispatch", 
            "receiver": "io",
            "method": "out_nl", 
            "actuals": [] } 
        }
      ]
     }
    ] } ] }

Існує кілька шляхів отримати AST з вихідного коду. Для нас головний критерій вибору в даному випадку — отримати навчальний досвід хоча б мінімально схожий на реальний досвід розробки промислових компіляторів.

Для більшості не іграшкових компіляторів їх команди реалізували лексичний і синтаксичний аналізатори вручну. Зокрема до таких відносяться компілятори GCC, Clang, D, Rust, Swift, Go, Java, TypeScript, C #, VB.NET.

Ось що говорить один з розробників компілятора C# про причини такого рішення.

Hello, I work on the C# compiler and we use a handwritten recursive-descent parser. Here are a few of the more important reasons for doing so:

• Incremental re-parsing. If a user in the IDE changes the document, we need to reparse the file, but we want to do this while using as little memory as possible. To this end, we re-use AST nodes from previous parses.
• Better error reporting. Parser generators are known for producing terrible errors. While you can hack around this, by using recursive-descent, you can get information from further «up» the tree to make it more relevant to the context in which the error occurred.
• Resilient parsing. This is the big one! If you give our parser a string that is illegal according to the grammar, our parser will still give you a syntax tree! (We’ll also spit errors out). But getting a syntax tree regardless of the actual validity of the program being passed in means that the IDE can give autocomplete and report type-checking error messages. As an example, the code `var x = velocity.` is invalid C#. However, in order to give autocomplete on `velocity.`, that code needs to be parsed into an AST, and then typechecked, and then we can extract the members on the type in order to provide a good user experience.

Досить показовою здається історія GCC. У проекті використовувався генератор парсерів Bison. Але в 2004 році розробники GCC вирішили переключитися на написаний вручну синтаксичний аналізатор. Мабуть, це виявилося простіше, ніж спробувати обійти обмеження Bison. В журналі змін можна прочитати наступне.

A hand-written recursive-descent C++ parser has replaced the YACC-derived C++ parser from previous GCC releases. The new parser contains much improved infrastructure needed for better parsing of C++ source codes, handling of extensions, and clean separation (where possible) between proper semantics analysis and parsing.

Виходячи зі сказаного вище ми будемо писати лексичний і синтаксичний аналізатори вручну. Насправді, це нескладно.

Про те як написати лексер дуже добре розказано в безкоштовній книзі Роберта Ністрома Crafting Interpreters. І там же так само добре описані парсери, що працюють за методом рекурсивного спуску. Наш парсер теж буде працювати за цим методом.

Код лексера можна подивитися в Lexer.fs, почавши, наприклад, з методу GetNext. Код парсера — в Parser.fs з точкою входу в статичному методі Parser.Parse.

Семантика

Наступний після синтаксичного аналіз етап — семантичний аналіз.

Ерік Ліпперт в статті How many passes? розповідає, які проходи виконує компілятор C#. Спойлер: їх більше двадцяти! Багато з них пов’язано з семантикою.

Ми виконаємо семантичний аналіз в три проходи. Послідовним запуском стадій аналізу і перевіркою їх результатів займається метод Translator.Translate.

Перший прохід — найпростіший. Створимо словник, в якому ключем буде ім’я класу, а значенням — вузол цього класу в AST. Цей словник буде нам потрібен під час другого проходу, коли ми будемо зустрічатися з іменами класів в процесі обробки різних вузлів AST.

Якщо зустрінемо два або кілька класів з однаковим ім’ям, діагностуємо помилку і зупинимо процес компіляції.

Функція collect_class_nodes в Translator.fs реалізує перший прохід.

В межах другого проходу ми проаналізуємо визначення класів, їх атрибути і методи, але не будемо «заглядати» всередину коду методів. По ходу справи сформуємо каталог класів, в якому за іменем класу можна знайти інформацію про нього — перелік атрибутів і методів з їх параметрами і типом значення, що вони повертають. Він стане в нагоді під час третього проходу. І перевіримо:

• Чи є цикли в ієрархії спадкування;
• Чи існують визначення всіх класів, імена яких використовуються в програмі;
• Чи немає методів, в списку параметрів яких повторюються імена параметрів;
• Відсутній ще ряд подібних помилок.

Якщо виявимо семантичні проблеми на другому проході, видамо діагностичне повідомлення для кожної з них і на цьому завершимо трансляцію.

За організацію другого проходу відповідає ClassSymbolCollector. Робота цього класу починається з виклику його методу ClassSymbolCollector.Collect.

Тепер, коли у нас є каталог класів, можна запустити третій прохід. Для чого нам знадобився каталог? Припустимо ми аналізуємо виклик методу instance.some_method(). Завдяки каталогу ми зможемо зрозуміти, чи існує some_method в класі, з яким оголошена змінна або параметр instance.

Так як на третьому проході ми розглядаємо код всередині методів, це вдалий момент переконатися, що в тексті програми немає спроб привласнити змінній типу Int рядкове значення. Або викликати метод, що очікує параметр типу String з аргументом типу Int. Або інших подібних помилок.

Для третього проходу семантичного аналізу вимагається таблиця символів. Таблиця символів описує, чи пов’язано в області видимості поточного методу, скажімо, ім’я foo з параметром методу, або локальної змінної, або атрибутом класу. Код міститься в класі SymbolTable.

Крім діагностики семантичних помилок, результатом роботи третього проходу може бути нове дерево з тією ж структурою, що і AST, але доповнене інформацією про типи вузлів, описом змінних або параметрів для відповідних вузлів і тому подібною інформацією. Щоб скоротити обсяг робіт, замість побудови такого дерева ми сумістимо третій прохід з генерацією асемблера.

Код третього проходу можна побачити в класі ExprTranslator. Щоб почати виконання цього проходу, необхідно викликати метод ExprTranslator.Translate.

Асемблер

Ми отримали AST як результат парсинга. І переконалися, що програма, яку ми транслюємо, не містить синтаксичних або семантичних помилок. Час виконати зворотний обхід AST і в процесі згенерувати код на мові асемблера, який пізніше перетворимо в виконуваний файл.

Чомусь і курс Compilers і багато інших навчальних матеріалів розповідають, як згенерувати асемблер для архітектури MIPS. Взагалі-то фундаментальні принципи генерації асемблера не змінюються, з якою б архітектурою набору команд ми не працювали.

Але на практиці особисто мені куди цікавіше було генерувати асемблер x86-64. Адже асемблер під архітектуру MIPS доведеться запускати в емуляторі, якщо тільки ви не власник робочої станції SGI або Tesla Model S. У той час як виконувані файли, отримані асемблюванням і лінковкою коду на мові асемблера x86-64, можна запускати прямо в Windows або Linux.

Як наслідок рішення генерувати «рідні» виконувані файли, ми отримуємо і дуже важливу практичну перевагу. Ми зможемо автоматизувати компіляцію, запуск і перевірку результатів роботи тестових програм.

Приклад тесту. Якщо результати компіляції або роботи програми не співпадуть з коментарями DIAG і OUT відповідно, тест вважається не пройденим.

class Main() {
  {
    var io: IO = new IO();
    io.out_string("Hello, Cool2020!");
    io.out_nl()
  };
}
// DIAG: Build succeeded: Errors: 0. Warnings: 0
// OUT: Hello, Cool2020!

Вирази

Конструкції управління потоком виконання перетворюються в асемблер нескладно. Уявіть, як би ви організували цикл, якби в розпорядженні у вас були тільки оператори if і goto. У першому наближенні так само це робиться і на асемблері.

Трансляція виразів — завдання цікавіше. Програма на асемблері складається з послідовності інструкцій, кожна з яких приймає від нуля до трьох операндів.

Не існує жодної інструкції, яка могла б обчислити найпростіший вираз типу a + b + c + d. Хоча б тому що банально не існує інструкції, що приймає чотири операнда. А вирази ж можуть бути і складніше: містити дужки, інші математичні операції, виклики методів...

Як бути? Ідея в тому, щоб «вдати», що замість одного складного у нас багато простих виразів. Прості вирази повинні тривіально транслюватися в асемблер. Проілюструємо задумку псевдокодом.

Складний вираз

a + b + c + d

Багато простих виразів

var tmp0: Int;
var tmp1: Int;
var result: Int;

tmp0 = a;
tmp1 = b;
tmp0 = tmp0 + tmp1; // tmp0 = a + b

tmp1 = c;
tmp0 = tmp0 + tmp1; // tmp0 = a + b + c
    
tmp1 = d;
tmp0 = tmp0 + tmp1; // tmp0 = a + b + c + d
    
result = tmp0       // result = a + b + c + d

Щоб зрозуміти, як застосувати цю ідею на практиці, давайте розберемо приклад.

Перетворимо вихідний вираз.

• Додамо в вираз a + b + c + d дужки, вийде ([(a + b) + c] + d). (Квадратні дужки — так само як і круглі — позначають арифметичне групування і використовуються для простоти читання.)
• Тепер перенесемо знаки плюс вліво, щоб вони розташувалися перед складовими. В результаті: (+ [+ (+ a b) c] d).
• Останню форму виразу вже можна розуміти як опис структури бінарного дерева, але давайте накреслимо його в більш наочному вигляді.

+ 
├── + 
│   ├── + 
│   │   ├── a 
│   │   └── b
│   └── c
└── d

Виконаємо зворотний обхід (Post-order або LRN) цього дерева. Домовимося, що функція зворотного обходу буде друкувати асемблерну інструкцію, відповідно до відвідуваного вузла дерева, і повертати ім’я регістра, в якому під час виконання програми буде міститися результат обчислення значення для піддерева з коренем в поточному вузлі.

Простежимо за процесом зворотного обходу. (Використано синтаксис AT&T)

# Входимо в кореневий вузол `+`
# З двома піддеревами `[+ (+ a b) c]` і `d`
# Рекурсивно викликаємо функцію зворотного обходу для лівого піддерева
#
#   Входимо в вузол `+` піддерева `[+ (+ a b) c]`
#   З двома піддеревами `(+ a b)` і `c`
#   Рекурсивно викликаємо функцію зворотного обходу для лівого піддерева
#
#     Входимо в вузол `+` піддерева `(+ a b)`
#     З двома листовими вузлами `a` і` b`
#     Рекурсивно викликаємо функцію зворотного обходу для лівого піддерева
#
#       Входимо в вузол `a`
#       Вибираємо незайнятий регістр %rbx для завантаження значення `a`
#       Друкуємо асемблерну інструкцію
mov    a,   %rbx
#       Повертаємо ім'я регістра %rbx
#       Під час виконання він буде містити значення за адресою `a`
#       Залишаємо вузол `a`
#
#     Рекурсивно викликаємо функцію зворотного обходу для правого піддерева
#
#       Входимо в вузол `b`
#       Вибираємо незайнятий регістр %r10 для завантаження значення `b`
#       Друкуємо асемблерну інструкцію
mov    b,   %r10
#       Повертаємо ім'я регістра %r10
#       Під час виконання він буде містити значення за адресою `b`
#       Залишаємо вузол `b`
#
#     Друкуємо асемблерну інструкцію для (+ a b)
#     %rbx = a
#     %r10 = b
add    %r10, %rbx # %rbx = %rbx + %r10
#     Відзначаємо %r10 як незайнятий
#     Повертаємо ім'я регістра %rbx
#     Під час виконання він буде містити `a + b`
#     Залишаємо вузол `+` піддерева `(+ a b)`
#
#   Рекурсивно викликаємо функцію зворотного обходу для правого піддерева
#
#     Входимо в вузол `c` піддерева` [+ (+ a b) c] `
#     Вибираємо незайнятий регістр% r10 для завантаження значення `c`
#     Друкуємо асемблерну інструкцію
mov    c,   %r10
#     Повертаємо ім'я регістра %r10
#     Під час виконання він буде містити значення за адресою `c`
#     Залишаємо вузол `c`
#
#   Друкуємо асемблерну інструкцію для `[+ (+ a b) c]`
#   %rbx = a + b
#   %r10 = c
add    %r10, %rbx # %rbx = %rbx + %r10
#   Відзначаємо% r10 як незайнятий
#   Повертаємо ім'я регістра %rbx
#   Під час виконання він буде містити `(a + b) + c`
#   Залишаємо вузол `+` піддерева `[+ (+ a b) c]`
#
# Рекурсивно викликаємо функцію зворотного обходу для правого піддерева
#
#   Входимо в вузол `d` дерева` (+ [+ (+ a b) c] d) `
#   Вибираємо незайнятий регістр %r10 для завантаження значення `d`
#   Друкуємо асемблерну інструкцію
mov    d,   %r10
#   Повертаємо ім'я регістра %r10
#   Під час виконання він буде містити значення за адресою `d`
#   Залишаємо вузол `d`
#
# Друкуємо асемблерну інструкцію для `(+ [+ (+ a b) c] d)`
# %rbx = (a + b) + c
# %r10 = d
add    %r10, %rbx
# Відзначаємо %r10 як незайнятий
# Повертаємо ім'я регістра %rbx
# Під час виконання він буде містити `((a + b) + c) + d`
# Залишаємо кореневий вузол `+`

Па-ба-ба-бам, ми перетворили арифметичний вираз в асемблер. Регістр %rbx буде містити значення виразу під час виконання програми. Помилуємося результатом наостанок.

Вираз

 a + b + c + d

Асемблер (синтаксис AT&T)

mov    a,    %rbx
mov    b,    %r10
add    %r10, %rbx
mov    c,    %r10
add    %r10, %rbx
mov    d,    %r10
add    %r10, %rbx

Генерація асемблера починається в методі Translator.Translate з виклику ProgramTranslator.Translate. У число класів, завдання яких — генерувати асемблер, входять ProgramTranslator, ClassTranslator, ExprTranslator і AsmBuilder.

Бібліотека середовища виконання

У Cool 2020 є кілька вбудованих класів. Плюс до цього, хоч вони безпосередньо і не доступні з коду, написаного користувачем, є процедури виділення пам’яті, копіювання об’єктів і кілька процедур аварійного завершення програми в різних неприпустимих сценаріях. Ще одним важливим елементом рантайму є точка входу в процес, про яку розповім трохи докладніше далі.

Весь перерахований код міститься в бібліотеці середовища виконання (runtime library або просто рантайм).

Стенфордський курс Compilers забезпечує студентів готової бібліотекою середовища виконання. Вона написана під архітектуру MIPS, передбачає Unix-подібну операційну систему і реалізує класи, вбудовані в мову Cool.

Нагадаю, що в той же час ми вирішили генерувати асемблер під x86-64, підтримувати Windows і Linux і транслювати підмножину Scala, вбудовані класи якої відрізняються від Cool.

Очевидно, використовувати готову бібліотеку середовища виконання з курсу Compilers не вийде. Ми можемо тільки вивчити її код і застосувати отримані знання для написання своєї.

Крім вивчення готового рантайм з курсу Compilers, в написанні складних процедур на мові асемблера може допомогти сервіс Compiler Explorer (він же — godbolt.org).

Наприклад, таким чином я отримав першу версію процедури переведення рядка в число: написав алгоритм на C і перетворив на асемблер за допомогою Compiler Explorer. Довелося сильно переробити код процедури, але написати її з нуля мені було б значно складніше.

Що вміє наш рантайм?

Код рантайму складається з трьох частин. Одна з них — rt_common.s. Вона загальна і не залежить від платформи. Саме rt_common.s містить точку входу в процес — процедуру main. До завдань main входить виклик процедури ініціалізації залежної від платформи частини коду, створення екземпляра класу Main і виклик його конструктора, завершення процесу.

Погляньмо на код точки входу.

Асемблер (синтаксис AT&T)

  .global main
main:
  call  .Platform.init

  # A class 'Main' must be present
  # in every Cool2020 program.
  # Create a new instance of 'Main'.
  movq  $Main_proto_obj, %rdi
  call  .Runtime.copy_object

  # 'Main..ctor' is a Cool2020 
  # program's entry point.
  # Pass a reference to the newly 
  # created 'Main' instance in %rdi.
  # Invoke the constructor.
  movq  %rax, %rdi
  call  Main..ctor

  xorq  %rdi, %rdi
  jmp   .Platform.exit_process

Псевдокод

def main() = {
  .Platform.init();

  new Main();

  .Platform.exit_process(0)
}

Також rt_common.s включає в себе код конструкторів і методів вбудованих класів. У IO включені методи введення/виведення. ArrayAny — клас масивів з типом елемента Any. String — клас рядків з методами concat і substring. Існує і пара інших, але про них — іншим разом. А також — як я згадував раніше — процедура копіювання об’єктів і кілька процедур аварійного завершення програми: в разі звернення до null посилання, виходу за межі масиву і т.д.

Залежні від платформи rt_windows.s і rt_linux.s містять по п’ять процедур.

.Platform.init відповідає за платформо-залежну ініціалізацію. В даний момент це підготовка до розподілу пам’яті під час виконання програми. А .Platform.alloc — якраз процедура виділення пам’яті.

.Platform.out_string і .Platform.in_string виконують запис рядка в stdout і читання з stdin відповідно.

І, нарешті, найважливіша процедура .Platform.exit_process завершує процес.

А ще rt_windows і rt_linux містять мітку .Platform.ascii_new_line, що вказує на послідовність символів кінця рядка для даної платформи.

rt_windows.s і rt_linux.s не залежать від стандартної бібліотеки C або будь-якої іншої бібліотеки. Вони звертаються безпосередньо до Win API на Windows, або виконують системні виклики на Linux.

Для того щоб викликати функції Win API з асемблера потрібно дотримуватися The Microsoft x64 Calling Convention і дуже важливо пам’ятати про таке поняття, як shadow space.

З Linux все трохи простіше — про shadow space піклуватися немає необхідності. Для виконання системних викликів потрібно додержуватись угод System V ABI. Перелік системних викликів з параметрами і коротким описом можна знайти в Linux System Call Table.

Чого не вміє наш рантайм?

Варити каву. Збирати сміття. На даний момент програми на Cool 2020 розподіляють пам’ять, але ніколи не звільняють її в процесі своєї роботи.

Реалізація збирача сміття з поколіннями вбудована в рантайм курсу Compilers, крім того в інтернеті доступні приклади реалізації збирачів сміття і навчальні матеріали.

Так що коли-небудь і наш рантайм обзаведеться кодом по збірці сміття. Варіння кави, напевно, не буде.

Компонування виконуваного файлу

Отже! Ми згенерували асемблер для програми на Cool 2020. І у нас є файли рантайму, написані на асемблері. Залишилося зробити не так багато дій, щоб нарешті отримати виконуваний файл.

По-перше, програма асемблер отримує на вхід текст на мові асемблера, а на вихід видає файл з машинним кодом — об’єктний файл. Так, ви правильно зрозуміли, потрібно пройтися асемблером по асемблеру (є в цьому якась поезія), щоб отримати об’єктні файли.

Об’єктні файли вже містять машинний код, але запустити їх на виконання ще не можна. Щоб отримати виконуваний файл, об’єктні файли програми і рантайму потрібно зібрати воєдино за допомогою компоновщика (лінкер).

Ми від початку брали курс на написання багатоплатформного компілятора, тому логічним вибором асемблера і компоновщика будуть утиліти з пакету GNU Binutils as і ld.

Для Linux цей пакет — просто стандарт, який є, напевно, в кожному дистрибутиві. Наприклад, в Убунту пакет так і називається binutils.

Встановити GNU Binutils на Windows теж дуже просто. Утиліти поширюються в складі пакету MinGW. Якщо ви не знаєте, що таке MinGW, то не заморочуйтесь прямо зараз. Головне, що після його встановлення ми отримаємо as і ld.

Ось тут в пункті 3 розповідається звідки можна завантажити графічні інсталятор і як ним користуватися. (Просунуті користувачі можуть вибрати альтернативний спосіб. Встановіть MSYS2. Тепер у вас є bash і pacman. Виконайте команду pacman -S mingw-w64-x86_64-toolchain, щоб отримати найсвіжішу версію MinGW.)

На Windows обов’язково додайте шлях до as і ld до змінної оточення PATH. Інакше наш компілятор їх не знайде і не зможе генерувати виконувані файли.

Запускає as і ld і перевіряє результати їх роботи код, розташований в EmitExeHandler.Invoke.

Ось ми і досягли того моменту, коли з вихідного тексту програми на Cool 2020 можемо створювати виконувані файли. Тепер у нас є все необхідне, щоб записати гіфку з розділу «Як будемо компілювати».

Проміжні відображення і оптимізації

Наш компілятор не генерує проміжне відображення (intermediate representation, IR) програми і не виконує ніяких оптимізацій. Проміжне відображення і оптимізація коду — виключно важливі теми в розробці компіляторів, але і дуже трудомісткі. У зв’язку з чим я прийняв рішення винести їх за межі проекту, принаймні на даному етапі. Мені здається, це абсолютно не заважає вивчати фундаментальні принципи побудови компіляторів. Більш того, розібратися з IR та оптимізаціями набагато простіше, коли є впевнене розуміння базових речей.

Проміжні відображення і оптимізації — дуже важливі і цікаві теми в розробці компіляторів. Команди промислових компіляторів приділяють їм величезну кількість сил і уваги, адже якість виконуваних оптимізацій безпосередньо впливає на споживання пам’яті та швидкість виконання програм. Тому я зібрав декілька посилань на цю тему в розділі «Просунуті питання».

Якщо вам хочеться розібратися глибше

Дуже раджу безкоштовну книгу Роберта Ністрома Crafting Interpreters. Хоч ми і розмовляємо про компілятори, нехай вас не відштовхує слово «Interpreters» в назві. До моменту коли ви дочитаєте до частини книги специфічної саме для інтерпретаторів, ви познайомитеся з безліччю тем однаково важливих для розуміння як інтерпретаторів так і компіляторів. Автор пояснює дуже дохідливо і точно.

Alex Aiken, Compilers. Можна сказати, класичний курс по компіляторам. Створив його Стенфордський професор Алекс Айкен. Очікувано, в порівнянні з Crafting Interpreters, в лекціях набагато більше уваги приділено теорії. Наприклад, Crafting Interpreters тільки згадує про існування техніки парсинга LR(1), а курс Compilers розповідає про неї в подробицях.

Чомусь і курс Compilers і багато інших навчальних матеріалів розповідають, як згенерувати асемблер для архітектури MIPS. А нам більше підходить асемблер x86-64. Тому буде корисна безкоштовна книга Дугласа Тейна Introduction to Compilers and Language Design. Яка, крім усього іншого, розповідає, як працювати з асемблером x86-64 і як в нього транслюються різні конструкції високорівневих мов.

Хто ж стане дивитися стрім Fortnite на Twitch, якщо можна можна подивитися запис того, як Іммо Ландверт пише компілятор в прямому ефірі на YouTube? Код можна знайти в репозиторії проекту.

Просунуті питання

Лекція про те, що таке проміжне відображення (IR). Від слухачів не вимагається попередніх знань. При цьому лекція побудована на прикладі одного з найбільш широко використовуваних і популярних IR — LLVM IR. 2019 EuroLLVM Developers ’Meeting: V. Bridgers & F. Piovezan «LLVM IR Tutorial — Phis, GEPs ...»

Безкоштовний курс для самостійного вивчення від Корнельського університету, який, крім інших цікавих тем, обговорює IR і оптимізації. Збираюся його подивитися найближчим часом. CS 6120: Advanced Compilers: The Self-Guided Online Course.