Jak se stát * kompilátorem - vytvořte kompilátor s JavaScriptem

*Ano! měli byste být kompilátorem. Je to úžasné.

Tento příspěvek je publikován pod licencí CC BY-NC-SA 4.0. Dejte nám vědět, pokud překládáte do jiných jazyků, abych mohl přidat do seznamu.

  • Japonská verze zde
  • Zjednodušená čínská verze @sqrtthree zde
  • Korejská verze od @ whello64 ​​zde
  • Španělská verze od @rodkings zde
  • Portugalština Verizon @CarolinaPascale, @CaiqueMitsuoka a @ felipesoares6_

Jedna nádherná neděle v Bushwicku v Brooklynu. Našel jsem knihu „Design by Numbers“ od Johna Maedy v mém místním knihkupectví. Byla to krok za krokem výuka programovacího jazyka DBN - jazyk vytvořený koncem 90. let v MIT Media Lab, jehož cílem je vizuální představení konceptů počítačového programování.

Ukázka kódu DNB z http://dbn.media.mit.edu/introduction.html

Okamžitě jsem si myslel, že vyřazení SVG z DBN a jeho spuštění v prohlížeči by bylo zajímavým projektem v roce 2016, než instalací Java prostředí pro spuštění původního zdrojového kódu DBN.

Myslel jsem, že budu muset napsat kompilátor DBN do SVG kompilátoru, takže se začalo hledat psaní kompilátoru. „Vytváření kompilátoru“ zní jako spousta počítačových věd ... ale nikdy jsem neprošel uzly v kódovacím rozhovoru, mohu vytvořit kompilátor?

Můj imaginární kompilátor, kde bude kód potrestán. Pokud je kód špatný, je zachycen navždy v chybové zprávě.

Zkusme se nejprve kompilátorem

Kompilátor je mechanismus, který vezme kus kódu a přemění jej v něco jiného. Zkompilujeme jednoduchý kód DBN do fyzického výkresu.

V tomto kódu DBN jsou 3 příkazy, „papír“ definuje barvu papíru, „pero“ definuje barvu pera a „čára“ nakreslí čáru. 100 v barevném parametru znamená 100% černou nebo rgb (0%, 0%, 0%) v CSS. Obraz vytvořený v DBN je vždy ve stupních šedi. V DBN je papír vždy 100 × 100, šířka čáry je vždy 1 a čára je definována souřadnicemi x y počátečního bodu a počítání koncového bodu z levého dolního rohu.

Zkusme být sami překladačem. Zastavte se, uchopte papír a pero a zkuste sestavit následující kód jako výkres.

Příspěvek 0
Pero 100
Řádek 0 50 100 50

Nakreslili jste černou čáru uprostřed zleva doprava? Gratulujeme! Právě jste se stal kompilátorem.

Zkompilovaný výsledek

Jak kompilátor funguje?

Podívejme se, co se právě stalo v naší hlavě jako překladač.

1. Lexikální analýza (tokenizace)

První věc, kterou jsme udělali, bylo oddělit každé klíčové slovo (nazývané tokeny) mezerou. Zatímco oddělujeme slova, každému tokenu jsme přidělili také primitivní typy, například „slovo“ nebo „číslo“.

lexikální analýza

2. Analýza (syntaktická analýza)

Jakmile se část textu rozdělí na žetony, prošli jsme si každý z nich a pokusili se najít vztah mezi žetony.
V tomto případě spojíme čísla spojená s klíčovým slovem příkazu. Tímto způsobem začneme vidět strukturu kódu.

Analýza

3. Transformace

Jakmile jsme analyzovali syntaxi analýzou, transformovali jsme strukturu na něco vhodného pro konečný výsledek. V tomto případě se chystáme nakreslit obrázek, takže ho převedeme na instrukce pro člověka krok za krokem.

Proměna

4. Generování kódu

Nakonec vytvoříme kompilovaný výsledek, kresbu. V tomto okamžiku se budeme řídit pouze pokyny, které jsme v předchozím kroku nakreslili.

Generování kódu

A to je to, co kompilátor dělá!

Výkres, který jsme vytvořili, je kompilovaným výsledkem (jako soubor .exe při kompilaci kódu C). Tento výkres můžeme předat komukoli nebo jakémukoli zařízení (skeneru, fotoaparátu atd.), Aby „spustil“ a všichni (nebo zařízení) uvidí uprostřed černou čáru.

Vytvořme kompilátor

Nyní, když víme, jak kompilátory fungují, vytvořme jeden v JavaScriptu. Tento kompilátor vezme kód DBN a změní je na kód SVG.

1. Funkce Lexer

Stejně jako můžeme rozdělit anglickou větu „Mám pero“ na [I, have, a, pen], lexikální analyzátor rozdělí řetězec kódu na malé smysluplné kousky (tokeny). V DBN je každý token ohraničen mezerami a klasifikován jako „slovo“ nebo „číslo“.

vstup: "papír 100"
výstup:[
  {type: "word", value: "Paper"}, {type: "number", value: 100}
]

2. Funkce parseru

Analyzátor projde jednotlivé tokeny, najde syntaktické informace a vytvoří objekt nazvaný AST (Abstract Syntax Tree). Můžete si představit AST jako mapu🗺 našeho kódu - způsob, jak pochopit, jak je část kódu strukturována.

V našem kódu jsou 2 typy syntaxe „NumberLiteral“ a „CallExpression“. NumberLiteral znamená, že hodnota je číslo. Používá se jako argumenty pro CallExpression.

vstup: [
  {type: "word", value: "Paper"}, {type: "number", value: 100}
]
výstup: {
  "type": "Drawing",
  "body": [{
    "type": "CallExpression",
    "name": "Paper",
    "argumenty": [{"type": "NumberLiteral", "value": "100"}]
  }]
}

3. Funkce transformátoru

AST, kterou jsme vytvořili v předchozím kroku, je dobré popsat, co se v kódu děje, ale není užitečné z něj vytvářet soubor SVG.
Například. „Papír“ je koncept, který existuje pouze v paradigmatu DBN. Ve SVG bychom mohli použít prvek k reprezentaci papíru. Funkce transformátoru převádí AST na jiné AST, které je přátelské ke SVG.

vstup: {
  "type": "Drawing",
  "body": [{
    "type": "CallExpression",
    "name": "Paper",
    "argumenty": [{"type": "NumberLiteral", "value": "100"}]
  }]
}
výstup: {
  "tag": "svg",
  "attr": {
    "width": 100,
    "výška": 100,
    "viewBox": "0 0 100 100",
    "xmlns": "http://www.w3.org/2000/svg",
    "version": "1.1"
  },
  "body": [{
    "tag": "rect",
    "attr": {
      "x": 0,
      "y": 0,
      "width": 100,
      "výška": 100,
      "fill": "rgb (0%, 0%, 0%)"
    }
  }]
}

4. Funkce generátoru

Jako poslední krok tohoto kompilátoru vytváří funkce generátoru SVG kód založený na novém AST, který jsme vytvořili v předchozím kroku.

vstup: {
  "tag": "svg",
  "attr": {
    "width": 100,
    "výška": 100,
    "viewBox": "0 0 100 100",
    "xmlns": "http://www.w3.org/2000/svg",
    "version": "1.1"
  },
  "body": [{
    "tag": "rect",
    "attr": {
      "x": 0,
      "y": 0,
      "width": 100,
      "výška": 100,
      "fill": "rgb (0%, 0%, 0%)"
    }
  }]
}
výstup:

  
  

5. Dejte vše dohromady jako kompilátor

Nazvěme tento kompilátor „kompilátorem sbn“ (kompilátor SVG podle čísel).
Vytváříme sbn objekt metodami lexer, syntaktický analyzátor, transformátor a generátor. Poté přidejte metodu „kompilace“, abyste zavolali všechny 4 metody v řetězci.

Nyní můžeme předat kódový řetězec kompilační metodě a dostat SVG ven.

Udělal jsem interaktivní demo, které vám ukáže výsledky jednotlivých kroků v tomto kompilátoru. Kód pro kompilátor sbn je zveřejněn na githubu. Momentálně přidávám do kompilátoru více funkcí. Pokud chcete zkontrolovat základní kompilátor, který jsme vytvořili v tomto příspěvku, podívejte se na jednoduchou větev.

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

Neměl by kompilátor používat rekurzi a traversal atd.?

Ano, to vše jsou úžasné techniky pro sestavení kompilátoru, ale to neznamená, že musíte nejprve přistoupit k tomuto přístupu.

Začal jsem vytvářením kompilátoru pro malou podmnožinu programovacího jazyka DBN, velmi omezenou malou sadu funkcí. Od té doby jsem rozšířil rozsah a nyní plánuji přidávat do tohoto kompilátoru funkce jako proměnná, blok kódu a smyčky. V tuto chvíli by bylo dobré použít tuto techniku, ale nebylo to začátek.

Psaní kompilátoru je úžasné

Co můžete udělat vytvořením vlastního kompilátoru? Možná budete chtít vytvořit nový jazyk podobný JavaScriptu ve španělštině ... a co español skript?

// ES (español skript)
función () {
  si (verdadero) {
    návrat «« Hola! »
  }
}

Existují lidé, kteří vytvořili programovací jazyk v Emoji (Emojicode) a barevném obrázku (Piet programovací jazyk). Možnosti jsou nekonečné!

Poučení z kompilátoru

Vytvoření kompilátoru bylo zábavné, ale hlavně mě to hodně naučilo o vývoji softwaru. Zde je několik věcí, které jsem se naučil při vytváření kompilátoru.

Jak si představím kompilátor poté, co jsem si sám vytvořil

1. Je v pořádku mít neznámé věci.

Stejně jako náš lexikální analyzátor nemusíte vědět všechno od začátku. Pokud opravdu nerozumíte nějakému kódu nebo technologii, je v pořádku říct: „Existuje něco, vím toho tolik“ a předejte jej k dalšímu kroku. Nemějte na to stres, nakonec se tam dostanete.

2. Nebuď blbec se špatnou chybovou zprávou.

Role Parsera je řídit se pravidlem a kontrolovat, zda jsou věci psány podle těchto pravidel. Mnohokrát se tak stane chyba. Pokud ano, zkuste odeslat užitečné a uvítací zprávy. Je snadné říci: „Nefunguje to tak“ (například „ILLEGAL Token“ nebo „undefined není funkce“ chyba v JavaScriptu), ale místo toho zkuste uživatelům sdělit, co by se mělo stát co nejvíce.

To platí také pro týmovou komunikaci. Když se někdo zasekne s otázkou, místo toho, abyste řekli „ano, to nefunguje“, možná můžete začít říkat „doporučil bych google klíčová slova jako ___ a ___.“ Nebo „doporučuji přečíst tuto stránku v dokumentaci.“ Nemusíte dělat práci za ně, ale určitě jim můžete pomoci dělat práci lépe a rychleji poskytnutím trochu větší pomoci.

Elm je programovací jazyk, který zahrnuje tuto metodu. Do své chybové zprávy vložili „Možná to chcete vyzkoušet?“.

3. Kontext je všechno

A konečně, stejně jako náš transformátor transformoval jeden typ AST na jiný, který lépe vyhovuje konečnému výsledku, vše je kontextové.

Neexistuje nikdo dokonalý způsob, jak dělat věci. Takže nedělejte věci, protože je to populární nebo jste to už udělali dříve, nejdřív přemýšlejte o kontextu. Věci, které fungují pro jednoho uživatele, mohou být katastrofou pro jiného uživatele.

Oceňujte také práci těchto transformátorů. Možná víte dobré transformátory ve svém týmu - někoho, kdo je opravdu dobrý v překlenutí mezer. Práce transformátorů nemusí přímo vytvářet kód, ale je to zatraceně důležitá práce při výrobě kvalitního produktu.

Doufám, že se vám tento příspěvek líbil, a doufám, že jsem vás přesvědčil, jak úžasné je stavět a být kompilátorem!

Toto je výňatek z přednášky, kterou jsem přednesl na konferenci JSConf Colombia 2016 v Medellinu v Kolumbii. Pokud se chcete o řeči dozvědět, podívejte se na snímky zde.