Как да бъдете * компилатор - направете компилатор с JavaScript

* Да! трябва да си компилатор. Това е страхотно.

Тази публикация се публикува под CC BY-NC-SA 4.0 лиценз. Кажете ми, ако превеждате на други езици, за да мога да добавя към списъка.

  • Японска версия от мен тук
  • Опростена китайска версия от @sqrtthree тук
  • Корейска версия от @ whello64 ​​тук
  • Испанска версия от @rodkings тук
  • Португалски Verizon от @CarolinaPascale, @CaiqueMitsuoka и @ felipesoares6_

Една прекрасна неделя в Бушвик, Бруклин. Намерих книга „Дизайн от числа“ на Джон Маеда в моята местна книжарница. В него беше поетапно обучение на езика за програмиране на DBN - език, направен в края на 90-те години в MIT Media Lab, предназначен да визуализира визуални концепции за компютърно програмиране.

DNB код извадка от http://dbn.media.mit.edu/introduction.html

Предполагам, че извеждането на SVG от DBN и пускането му в браузър би било интересен проект през 2016 г., а не инсталиране на Java среда за изпълнение на оригинален DBN изходен код.

Реших, че ще трябва да напиша DBN на SVG компилатор, така че търсенето на писане на компилатор започна. „Да направим компилатор“ звучи като много компютърни науки… но никога не съм обикалял възли в интервю за кодиране, мога ли да направя компилатор?

Моят въображаем компилатор, където кодът ще бъде наказан. Ако кодът е лош, той се записва в съобщение за грешка завинаги.

Нека първо се опитаме да бъдем компилатор

Компилаторът е механизъм, който взема част от кода и го превръща в нещо друго. Нека компилираме прост DBN код във физически чертеж.

В този DBN код има 3 команди, „Paper” определя цвета на хартията, „Pen” определя цвета на писалката, а „Line” изчертава линия. 100 в цветен параметър означава 100% черно или rgb (0%, 0%, 0%) в CSS. Изображението, произведено в DBN, винаги е в сиви скали. В DBN хартията е винаги 100 × 100, ширината на линията винаги е 1, а Line се дефинира чрез x y координати на началната точка и отброяването на крайната точка от долния ляв ъгъл.

Нека се опитаме сами да бъдем компилатор. Спрете тук, вземете хартия и химикалка и опитайте да съставите следния код като рисунка.

Хартия 0
Писалка 100
Ред 0 50 100 50

Начертахте ли черна линия в средата от лявата до дясната страна? Честито! Току-що станахте компилатор.

Компилиран резултат

Как работи компилаторът?

Нека да разгледаме какво точно се е случило в главата ни като съставител.

1. Лексикален анализ (токенизация)

Първото нещо, което направихме, беше да разделим всяка ключова дума (наречена жетони) от празно пространство. Докато разделяме думи, ние също така присвоихме примитивни типове на всеки символи, като „дума“ или „число“.

лексикален анализ

2. Разбор (синтактичен анализ)

След като парче текст се раздели на символи, ние преминахме през всеки от тях и се опитахме да намерим връзка между маркери.
В този случай групираме заедно числа, свързани с командната ключова дума. Правейки това, започваме да виждаме структура на кода.

морфологичен разбор

3. Трансформация

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

Трансформация

4. Генериране на код

И накрая, правим компилиран резултат, рисунка. В този момент ние просто следваме инструкциите, които направихме в предишната стъпка, за да нарисуваме.

Генериране на код

И това прави компилаторът!

Чертежът, който направихме, е компилираният резултат (като .exe файл, когато компилирате C код). Можем да предадем този чертеж на всеки или на всяко устройство (скенер, камера и т.н.), за да го „стартираме“ и всеки (или устройство) ще види черна линия в средата.

Нека направим компилатор

Сега, когато знаем как работят компилаторите, нека направим такъв в JavaScript. Този компилатор взема DBN код и ги превръща в SVG код.

1. Лексерова функция

Точно както можем да разделим английското изречение „Имам химикалка“ на [I, have, a, pen], лексикален анализатор разделя кодов низ на малки смислени парчета (маркери). В DBN всеки маркер се разграничава с бели интервали и се класифицира като „дума“ или „число“.

вход: "Хартия 100"
изход: [
  {type: "word", value: "Paper"}, {type: "number", value: 100}
]

2. Парсер функция

Парсер преминава през всеки токен, намира синтактична информация и изгражда обект, наречен AST (Абстрактно синтаксично дърво). Можете да мислите за AST като карта🗺 за нашия код - начин да разберете как е структуриран парче код.

В нашия код има 2 типа синтаксис „NumberLiteral“ и „CallExpression“. NumberLiteral означава, че стойността е число. Използва се като аргументи за CallExpression.

вход: [
  {type: "word", value: "Paper"}, {type: "number", value: 100}
]
изход: {
  "type": "Рисуване",
  "тяло": [{
    "type": "CallExpression",
    "name": "Хартия",
    "аргументи": [{"type": "NumberLiteral", "value": "100"}]
  }]
}

3. Трансформаторна функция

AST, който създадохме в предишната стъпка, е добре да опише какво се случва в кода, но не е полезно да създавате SVG файл от него.
Например. „Хартия“ е концепция, която съществува само в DBN парадигмата. В SVG може да използваме елемент, за да представим Paper. Трансформаторната функция преобразува AST в друга AST, която е SVG приятелска.

вход: {
  "type": "Рисуване",
  "тяло": [{
    "type": "CallExpression",
    "name": "Хартия",
    "аргументи": [{"type": "NumberLiteral", "value": "100"}]
  }]
}
изход: {
  "tag": "svg",
  "attr": {
    "ширина": 100,
    "височина": 100,
    "viewBox": "0 0 100 100",
    "xmlns": "http://www.w3.org/2000/svg",
    "версия": "1.1"
  }
  "тяло": [{
    "tag": "rect",
    "attr": {
      "x": 0,
      "у": 0,
      "ширина": 100,
      "височина": 100,
      "fill": "rgb (0%, 0%, 0%)"
    }
  }]
}

4. Функция на генератора

Като последна стъпка на този компилатор, генераторната функция създава SVG код въз основа на нов AST, който направихме в предишната стъпка.

вход: {
  "tag": "svg",
  "attr": {
    "ширина": 100,
    "височина": 100,
    "viewBox": "0 0 100 100",
    "xmlns": "http://www.w3.org/2000/svg",
    "версия": "1.1"
  }
  "тяло": [{
    "tag": "rect",
    "attr": {
      "x": 0,
      "у": 0,
      "ширина": 100,
      "височина": 100,
      "fill": "rgb (0%, 0%, 0%)"
    }
  }]
}
изход:

  
  

5. Сложете всичко заедно като компилатор

Нека наречем този компилатор „компилатор на sbn“ (SVG по компилатор на номера).
Създаваме sbn обект с лексери, парсери, трансформатори и генераторни методи. След това добавете метод "съставяне", за да извикате всички 4 метода във веригата.

Вече можем да предадем кодов низ на метода на компилиране и да извадим SVG.

Направих интерактивна демонстрация, която ви показва резултатите от всяка стъпка в този компилатор. Кодът за компилатор на sbn е публикуван на github. В момента добавям още функции в компилатора. Ако искате да проверите основния компилатор, който направихме в тази публикация, моля, разгледайте прост клон.

https://kosamari.github.io/sbn/

Не трябва ли компилаторът да използва рекурсия и преминаване и т.н.?

Да, всичко това са прекрасни техники за изграждане на компилатор, но това не означава, че първо трябва да използвате този подход.

Започнах като направих компилатор за малък подмножество от език за програмиране на DBN, много ограничен набор от малки функции. Оттогава разширих обхвата и сега планирам да добавя функции като променлива, блок код и цикли към този компилатор. В този момент би било добре да се използва тази техника, но не беше изискването да започнете.

Писането на компилатор е страхотно

Какво можете да направите, като направите свой собствен компилатор? Може би бихте могли да искате да направите нов език, подобен на JavaScript на испански ... какво ще кажете за скрипта на español?

// ES (скрипт за español)
función () {
  si (verdadero) {
    връщане «¡Хола!»
  }
}

Има хора, които са направили език за програмиране в Emoji (Emojicode) и в цветно изображение (Piet programming language). Възможностите са безкрайни!

Поуки от правенето на компилатор

Осъществяването на компилатор беше забавно, но най-важното - това ме научи много на разработката на софтуер. Ето няколко неща, които научих, докато правех своя компилатор.

Как си представям компилатор, след като сам си направя такъв

1. Добре е да имаш непознати неща.

Подобно на нашия лексикален анализатор, не е нужно да знаете всичко от самото начало. Ако наистина не разбирате парче код или технология, е добре да кажете „Има нещо, знам толкова много“ и да го прехвърлите към следващата стъпка. Не се стресирайте по въпроса, в крайна сметка ще стигнете до там

2. Не бъди глупак с лошо съобщение за грешка.

Ролята на Parser е да следва правилото и да проверява дали нещата са написани според тези правила. Така че много пъти се случва грешка. Когато това стане, опитайте се да изпратите полезни и приветливи съобщения. Лесно е да се каже „Не работи по този начин“ (например „ILLEGAL Token“ или „undefined is not function“ грешка в JavaScript), но вместо това, опитайте се да кажете на потребителите какво трябва да се случи, доколкото можете.

Това се отнася и за комуникацията в екипа. Когато някой е заседнал с въпрос, вместо да каже „да, това не работи“, може би можете да започнете да казвате „Бих google ключови думи като ___ и ___.“ Или „Препоръчвам ви да прочетете тази страница на документация.“ не трябва да вършите работата за тях, но със сигурност можете да им помогнете да вършат работата по-добре и по-бързо, като предоставите малко повече помощ.

Elm е език за програмиране, който обхваща този метод. Те поставят „Може би искате да опитате това?“ В съобщението си за грешка.

3. Контекстът е всичко

И накрая, точно както трансформаторът ни трансформира един тип AST в друг по-подходящ за крайния резултат, всичко е специфично за контекста.

Няма един перфектен начин да се правят нещата. Така че не правете само неща, защото е популярно или сте го правили преди, помислете първо за контекста. Нещата, които работят за един потребител, могат да бъдат катастрофа за друг потребител.

Също така оценявайте работата, която тези трансформатори вършат. Може да познавате добри трансформатори във вашия екип - някой, който наистина е добър в преодоляването на пропуските. Работата на трансформатори може да не създава директно код, но това е дяволски важна работа при производството на качествен продукт.

Надявам се, че ви е харесал този пост и се надявам да ви убедя колко страхотно е да се изгради и да бъде компилатор!

Това е откъс от беседата, която изнесох на JSConf Colombia 2016 в Меделин, Колумбия. Ако искате да знаете за беседата, разгледайте слайдовете тук.