Sådan bliver du * en compiler - lav en compiler med JavaScript

*Ja! du skal være en compiler. Det er fantastisk.

Dette indlæg offentliggøres under CC BY-NC-SA 4.0-licens. Fortæl mig, hvis du oversætter til andre sprog, så jeg kan føje til listen.

  • Japansk version af mig her
  • Forenklet kinesisk version af @sqrtthree her
  • Koreansk version af @ whello64 ​​her
  • Spansk version af @rodkings her
  • Portugisisk Verizon af @CarolinaPascale, @CaiqueMitsuoka og @ felipesoares6_

En vidunderlig søndag i Bushwick, Brooklyn. Jeg fandt en bog "Design af numre" af John Maeda i min lokale boghandel. I det var trin for trin instruktion af DBN-programmeringssprog - et sprog lavet i slutningen af ​​90'erne på MIT Media Lab, designet til at introducere computerprogrammeringskoncepter på visuel måde.

DNB-kodeeksempel fra http://dbn.media.mit.edu/introduction.html

Jeg troede straks at gøre SVG ud af DBN og køre det i browser ville være et interessant projekt i 2016 snarere end at installere Java-miljø for at udføre den originale DBN-kildekode.

Jeg regnede med, at jeg bliver nødt til at skrive en DBN til SVG-compiler, så jagten på at skrive en compiler er begyndt. "At lave kompilator" lyder som en masse datalogi ... men jeg har aldrig gennemgået noder i kodningsinterview, kan jeg lave en compiler?

Min imaginære kompilator, hvor kode bliver straffet. Hvis koden er dårlig, indfanges den i en fejlmeddelelse for evigt.

Lad os prøve at være en compiler først

Compiler er en mekanisme, der tager et stykke kode og omdanner det til noget andet. Lad os samle simpel DBN-kode til en fysisk tegning.

Der er 3 kommandoer i denne DBN-kode, "Papir" definerer papirets farve, "Pen" definerer farven på pennen, og "Linie" tegner en linje. 100 i farveparameter betyder 100% sort eller rgb (0%, 0%, 0%) i CSS. Billedet produceret i DBN er altid i gråtoner. I DBN er et papir altid 100 × 100, linjebredde er altid 1, og linje defineres af x y-koordinater for start- og slutpunktetælling fra nederste venstre hjørne.

Lad os prøve at være en selvsamler. Stop her, tag et papir og en pen og prøv at udarbejde følgende kode som tegning.

Papir 0
Pen 100
Linie 0 50 100 50

Tegnede du en sort linje i midten fra venstre side til højre side? Tillykke! Du blev lige en compiler.

Samlet resultat

Hvordan fungerer en compiler?

Lad os se på hvad der lige skete i vores hoved som en kompilator.

1. Leksikalsk analyse (tokenisering)

Den første ting, vi gjorde, var at adskille hvert nøgleord (kaldet tokens) efter hvidt rum. Mens vi adskiller ord, tildelte vi også primitive typer til hver tokens, f.eks. “Ord” eller “nummer”.

leksikalsk analyse

2. Parsing (syntaktisk analyse)

Når en klods tekst er opdelt i tokens, gik vi gennem hver af dem og prøvede at finde et forhold mellem tokens.
I dette tilfælde grupperer vi numre, der er tilknyttet kommandosøgeord. Ved at gøre dette begynder vi at se en struktur af koden.

parsing

3. Transformation

Når vi analyserede syntaks ved at analysere, omdannede vi strukturen til noget, der var egnet til det endelige resultat. I dette tilfælde tegner vi et billede, så vi vil omdanne det til trinvis vejledning til mennesker.

Transformation

4. Generering af kode

Til sidst laver vi et samlet resultat, en tegning. På dette tidspunkt følger vi bare de instruktioner, vi lavede i forrige trin til at tegne.

Generering af kode

Og det er hvad en compiler gør!

Den tegning, vi lavede, er det kompilerede resultat (som .exe-fil, når du kompilerer C-kode). Vi kan videregive denne tegning til enhver eller enhver enhed (scanner, kamera osv.) For at "køre den", og alle (eller enhed) vil se en sort linje i midten.

Lad os lave en compiler

Nu hvor vi ved, hvordan kompilatorer fungerer, så lad os lave en i JavaScript. Denne kompilator tager DBN-kode og omdanner dem til SVG-kode.

1. Lexer-funktion

Ligesom vi kan dele den engelske sætning “Jeg har en pen” til [Jeg, har, en, pen], opdeler leksikalsk analysator en kodestreng i små meningsfulde bidder (tokens). I DBN afgrænses hvert token af ​​hvide rum og klassificeres som enten "ord" eller "antal".

input: "Papir 100"
produktion:[
  {type: "ord", værdi: "Papir"}, {type: "antal", værdi: 100}
]

2. Parser-funktion

Analyser går gennem hver token, finder syntaktisk information og bygger et objekt kaldet AST (Abstract Syntax Tree). Du kan tænke på AST som et kort🗺 for vores kode - en måde at forstå, hvordan et stykke kode er struktureret.

I vores kode er der 2 syntaksstyper “NumberLiteral” og “CallExpression”. NumberLiteral betyder, at værdien er et tal. Det bruges som argumenter for CallExpression.

input: [
  {type: "ord", værdi: "Papir"}, {type: "antal", værdi: 100}
]
output: {
  "type": "Tegning",
  "krop": [{
    "type": "CallExpression",
    "name": "Papir",
    "argumenter": [{"type": "NumberLiteral", "value": "100"}]
  }]
}

3. Transformatorfunktion

AST, vi oprettede i forrige trin, er gode til at beskrive, hvad der sker i koden, men det er ikke nyttigt at oprette SVG-fil ud af den.
For eksempel. "Papir" er et koncept, der kun findes i DBN-paradigme. I SVG bruger vi muligvis -elementet til at repræsentere et papir. Transformatorfunktion konverterer AST til en anden AST, der er SVG-venlig.

input: {
  "type": "Tegning",
  "krop": [{
    "type": "CallExpression",
    "name": "Papir",
    "argumenter": [{"type": "NumberLiteral", "value": "100"}]
  }]
}
output: {
  "tag": "svg",
  "attr": {
    "bredde": 100,
    "højde": 100,
    "viewBox": "0 0 100 100",
    "xmlns": "http://www.w3.org/2000/svg",
    "version": "1.1"
  },
  "krop": [{
    "tag": "rekt",
    "attr": {
      "x": 0,
      "y": 0,
      "bredde": 100,
      "højde": 100,
      "fyld": "rgb (0%, 0%, 0%)"
    }
  }]
}

4. Generatorfunktion

Som det sidste trin i denne kompilator opretter generatorfunktionen SVG-kode baseret på ny AST, vi lavede i forrige trin.

input: {
  "tag": "svg",
  "attr": {
    "bredde": 100,
    "højde": 100,
    "viewBox": "0 0 100 100",
    "xmlns": "http://www.w3.org/2000/svg",
    "version": "1.1"
  },
  "krop": [{
    "tag": "rekt",
    "attr": {
      "x": 0,
      "y": 0,
      "bredde": 100,
      "højde": 100,
      "fyld": "rgb (0%, 0%, 0%)"
    }
  }]
}
produktion:

  
  

5. Sæt det hele sammen som en kompilator

Lad os kalde denne kompilator "sbn-kompilatoren" (SVG by numbers compiler).
Vi opretter et sbn-objekt med lexer-, parser-, transformer- og generatormetoder. Tilføj derefter en "compile" -metode for at kalde alle 4 metoder i en kæde.

Vi kan nu videresende kodestreng til kompileringsmetoden og få SVG ud.

Jeg har lavet en interaktiv demo, der viser dig resultaterne af hvert trin i denne compiler. Kode til sbn compiler er placeret på github. Jeg tilføjer flere funktioner i kompilatoren i øjeblikket. Hvis du vil tjekke den grundlæggende kompilator, vi lavede i dette indlæg, skal du tjekke den enkle gren.

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

Bør ikke en compiler bruge rekursion og gennemgang osv.?

Ja, det er alle vidunderlige teknikker til at bygge en compiler, men det betyder ikke, at du skal tage denne tilgang først.

Jeg startede med at lave kompilator til et lille undergruppe af DBN-programmeringssprog, et meget begrænset lille funktionssæt. Siden da udvidede jeg rækkevidde og planlægger nu at tilføje funktioner som variabel, kodeblok og sløjfer til denne kompilator. Det ville være en god ide at bruge denne teknik på dette tidspunkt, men det var ikke kravet om at komme i gang.

At skrive compiler er fantastisk

Hvad kan du gøre ved at lave din egen compiler? Måske ønsker du måske at oprette nyt JavaScript-lignende sprog på spansk ... hvad med español-script?

// ES (español script)
función () {
  si (verdadero) {
    tilbage «¡Hola!»
  }
}

Der er mennesker, der lavede programmeringssprog i Emoji (Emojicode) og i farvet billede (Piet programmeringssprog). Mulighederne er uendelige!

Læring af at lave en compiler

At lave en compiler var sjovt, men vigtigst af alt lærte det mig meget om softwareudvikling. Her er et par ting, jeg lærte, mens jeg lavede min compiler.

Hvordan jeg forestiller mig compiler efter at have lavet en selv

1. Det er okay at have ukendte ting.

Ligesom vores leksikale analysator, behøver du ikke at vide alt fra begyndelsen. Hvis du ikke rigtig forstår et stykke kode eller teknologi, er det okay at bare sige "Der er en ting, jeg ved så meget" og videresende det til næste trin. Undlad at stresse med det, du kommer til sidst.

2. Vær ikke en idiot med dårlig fejlmeddelelse.

Parsers rolle er at følge reglen og kontrollere, om tingene er skrevet i henhold til disse regler. Så mange gange sker der fejl. Når det sker, kan du prøve at sende nyttige og indbydende beskeder. Det er let at sige "Det fungerer ikke på den måde" (som "ULIGT Token" eller "undefined is not a function" -fejl i JavaScript), men prøv i stedet at fortælle brugerne, hvad der skal ske så meget som du kan.

Dette gælder også for teamkommunikation. Når nogen sidder fast med et spørgsmål, i stedet for at sige "ja, det fungerer ikke", kan du måske begynde at sige "Jeg ville google nøgleord som ___ og ___." Eller "Jeg anbefaler at du læser denne side i dokumentation." Du don ' t har brug for at gøre arbejdet for dem, men du kan bestemt hjælpe dem med at udføre arbejdet bedre og hurtigere ved at give lidt mere hjælp.

Elm er et programmeringssprog, der omfavner denne metode. De satte ”Måske vil du prøve dette?” I deres fejlmeddelelse.

3. Kontekst er alt

Endelig, ligesom vores transformer transformerede en type AST til en anden, der er mere passende til det endelige resultat, er alt sammenhængsspecifikt.

Der er ingen perfekt måde at gøre tingene på. Så ikke bare gør ting, fordi det er populært, eller du har gjort det før, tænk først på konteksten. Ting, der fungerer for en bruger, kan være en katastrofe for en anden bruger.

Værdsætter også det arbejde, disse transformere udfører. Du kender måske gode transformere i dit team - en der er virkelig god til at bygge bro over hinanden. Disse arbejde med transformere opretter muligvis ikke direkte en kode, men det er et forbandet vigtigt arbejde med at fremstille kvalitetsprodukter.

Håber du nød dette indlæg, og håber, at jeg overbeviste dig, hvor fantastisk det er at bygge & være en compiler!

Dette er et uddrag fra den tale jeg holdt på JSConf Colombia 2016 i Medellin, Colombia. Hvis du vil vide om foredraget, så tjek dias her.