Jeg skrev et programmeringssprog. Sådan kan du også.

I løbet af de sidste 6 måneder har jeg arbejdet på et programmeringssprog kaldet Pinecone. Jeg vil ikke kalde det modent endnu, men det har allerede nok funktioner, der fungerer til at være anvendelige, såsom:

  • variabler
  • funktioner
  • brugerdefinerede strukturer

Hvis du er interesseret i det, skal du tjekke Pinecones landingsside eller dens GitHub repo.

Jeg er ikke ekspert. Da jeg startede dette projekt, havde jeg ingen anelse om, hvad jeg lavede, og det gør jeg stadig ikke. Jeg har taget nul klasser om sprogoprettelse, kun læst lidt om det online og ikke fulgt meget af de råd, jeg har fået.

Og alligevel lavede jeg stadig et helt nyt sprog. Og det fungerer. Så jeg må gøre noget rigtigt.

I dette indlæg dykker jeg under emhætten og viser dig den rørledning, Pinecone (og andre programmeringssprog) bruger til at gøre kildekode til magi.

Jeg vil også berøre nogle af de kompromiser, jeg har foretaget, og hvorfor jeg tog de beslutninger, jeg tog.

Dette er på ingen måde en komplet tutorial om at skrive et programmeringssprog, men det er et godt udgangspunkt, hvis du er nysgerrig efter sprogudvikling.

Kom godt i gang

"Jeg har absolut ingen idé om, hvor jeg endda ville starte" er noget, jeg hører meget, når jeg fortæller andre udviklere, at jeg skriver et sprog. Hvis det er din reaktion, gennemgår jeg nu nogle indledende beslutninger, der træffes, og de skridt, der tages, når du starter et nyt sprog.

Kompileret vs fortolket

Der er to hovedtyper af sprog: kompileret og fortolket:

  • En kompilator finder ud af alt, hvad et program vil gøre, forvandler det til "maskinkode" (et format, som computeren kan køre rigtig hurtigt) og gemmer det, der skal udføres senere.
  • En tolk går gennem kildekoden linje for linje og finder ud af, hvad den laver, når den går.

Teknisk set kan ethvert sprog kompileres eller fortolkes, men det ene eller det andet giver normalt mere mening for et bestemt sprog. Generelt har tolkning en tendens til at være mere fleksibel, mens kompilering har en højere ydeevne. Men dette skraber kun overfladen af ​​et meget komplekst emne.

Jeg sætter stor pris på ydeevne, og jeg så manglen på programmeringssprog, der både er højtydende og enkelhedsorienterede, så jeg gik med kompileret til Pinecone.

Dette var en vigtig beslutning at tage tidligt, fordi mange beslutninger om sprogdesign er påvirket af det (for eksempel er statisk skrivning en stor fordel for kompilerede sprog, men ikke så meget for fortolkede sprog).

På trods af at Pinecone er designet med kompilering i tankerne, har den en fuldt funktionel tolk, som var den eneste måde at køre den på i et stykke tid. Der er en række grunde til dette, som jeg vil forklare senere.

Valg af sprog

Jeg ved, det er lidt meta, men et programmeringssprog er i sig selv et program, og derfor skal du skrive det på et sprog. Jeg valgte C ++ på grund af dens ydeevne og store funktionssæt. Jeg nyder faktisk også at arbejde i C ++.

Hvis du skriver et tolket sprog, giver det meget mening at skrive det på et kompileret sprog (som C, C ++ eller Swift), fordi den performance, der er tabt på sproget for din tolk og den tolk, der fortolker din tolk, vil sammensættes.

Hvis du planlægger at kompilere, er et langsommere sprog (som Python eller JavaScript) mere acceptabelt. Kompileringstid kan være dårlig, men efter min mening er det ikke nær så stor en aftale som dårlig køretid.

Design på højt niveau

Et programmeringssprog er generelt struktureret som en pipeline. Det vil sige, det har flere faser. Hvert trin har data formateret på en bestemt, veldefineret måde. Det har også funktioner til at omdanne data fra hvert trin til det næste.

Den første fase er en streng, der indeholder hele inputkildefilen. Den sidste fase er noget, der kan køres. Dette bliver alt sammen tydeligt, når vi går igennem Pinecone-rørledningen trin for trin.

Lexing

Det første trin i de fleste programmeringssprog er lexing eller tokenisering. 'Lex' er en forkortelse for leksikalsk analyse, et meget fancy ord til at opdele en masse tekst i tokens. Ordet 'tokenizer' giver meget mere mening, men 'lexer' er så sjovt at sige, at jeg alligevel bruger det.

Poletter

Et token er en lille enhed af et sprog. Et token kan være et variabel- eller funktionsnavn (AKA en identifikator), en operator eller et tal.

Lexers opgave

Lexeren formodes at tage en streng indeholdende hele kildekoden til en værdi af filer og spytte en liste indeholdende hvert token.

Fremtidige faser i rørledningen henviser ikke til den oprindelige kildekode, så lexeren skal producere alle de oplysninger, der er nødvendige for dem. Årsagen til dette relativt strenge pipelineformat er, at lexeren kan udføre opgaver såsom at fjerne kommentarer eller detektere, om noget er et nummer eller en identifikator. Du vil holde den logik låst inde i lexeren, begge så du ikke behøver at tænke på disse regler, når du skriver resten af ​​sproget, og så du kan ændre denne type syntaks alt på ét sted.

Flex

Den dag, jeg startede sproget, var det første, jeg skrev, en simpel lexer. Kort efter begyndte jeg at lære om værktøjer, der angiveligt ville gøre lexing enklere og mindre buggy.

Det dominerende værktøj er Flex, et program der genererer lexers. Du giver den en fil, der har en særlig syntaks til at beskrive sprogets grammatik. Derefter genererer det et C-program, der lexes en streng og producerer den ønskede output.

Min beslutning

Jeg valgte at beholde den lexer, jeg skrev indtil videre. I sidste ende så jeg ikke væsentlige fordele ved at bruge Flex, i det mindste ikke nok til at retfærdiggøre at tilføje en afhængighed og komplicere byggeprocessen.

Min lexer er kun et par hundrede linjer lang og giver mig sjældent problemer. Rulning af min egen lexer giver mig også mere fleksibilitet, såsom muligheden for at føje en operatør til sproget uden at redigere flere filer.

Analyse

Den anden fase af rørledningen er parseren. Parseren omdanner en liste med tokens til et knudetræ. Et træ, der bruges til lagring af denne type data, kaldes et abstrakt syntaks-træ eller AST. I det mindste i Pinecone har AST ingen information om typer eller hvilke identifikatorer der er hvilke. Det er simpelthen strukturerede tokens.

Parseropgaver

Parseren tilføjer struktur til den ordnede liste over tokens, lexeren producerer. For at stoppe tvetydigheder skal parseren tage højde for parentes og rækkefølgen af ​​operationer. Simpelthen at parsere operatører er ikke meget vanskeligt, men efterhånden som flere sprogkonstruktioner tilføjes, kan parsing blive meget kompleks.

Bison

Igen var der en beslutning om at inddrage et tredjepartsbibliotek. Det dominerende parsebibliotek er Bison. Bison fungerer meget som Flex. Du skriver en fil i et brugerdefineret format, der gemmer grammatikoplysningerne, og derefter bruger Bison det til at generere et C-program, der skal udføre din parsing. Jeg valgte ikke at bruge Bison.

Hvorfor brugerdefineret er bedre

Med lexeren var beslutningen om at bruge min egen kode ret åbenbar. En lexer er et så trivielt program, at ikke at skrive min egen føltes næsten lige så fjollet som ikke at skrive min egen 'venstre-pad'.

Med parseren er det en anden sag. Min Pinecone-parser er i øjeblikket 750 linjer lang, og jeg har skrevet tre af dem, fordi de to første var papirkurven.

Jeg tog oprindeligt min beslutning af en række årsager, og selvom den ikke er gået helt glat, holder de fleste af dem sandt. De vigtigste er som følger:

  • Minimer kontekstskift i workflow: kontekstskift mellem C ++ og Pinecone er dårligt nok uden at smide Bison's grammatikgrammatik
  • Hold byggeriet simpelt: Hver gang grammatikken ændres, skal Bison køres inden bygningen. Dette kan automatiseres, men det bliver smertefuldt, når der skiftes mellem byggesystemer.
  • Jeg kan godt lide at bygge cool lort: Jeg lavede ikke Pinecone, fordi jeg troede, det ville være let, så hvorfor skulle jeg delegere en central rolle, når jeg selv kunne gøre det? En brugerdefineret parser er muligvis ikke triviel, men den er fuldstændig gennemførlig.

I begyndelsen var jeg ikke helt sikker på, om jeg skulle ned ad en levedygtig vej, men jeg fik tillid til, hvad Walter Bright (en udvikler af en tidlig version af C ++ og skaberen af ​​D-sproget) havde at sige om emne:

"Lidt mere kontroversielt ville jeg ikke gider at spilde tid med lexer- eller parsergeneratorer og andre såkaldte" compiler compilers. " De er spild af tid. At skrive en lexer og parser er en lille procentdel af jobbet med at skrive en compiler. Brug af en generator tager cirka lige så lang tid som at skrive en i hånden, og det vil gifte dig med generatoren (hvilket betyder noget, når du porterer compileren til en ny platform). Og generatorer har også det uheldige ry for at udsende elendige fejlmeddelelser. ”

Handlingstræ

Vi har nu forladt området med almindelige, universelle udtryk, eller i det mindste ved jeg ikke mere, hvad udtrykkene er. Fra min forståelse er det, jeg kalder 'handlingstræet', mest beslægtet med LLVM's IR (mellemrepræsentation).

Der er en subtil men meget signifikant forskel mellem handlingstræet og det abstrakte syntakstræ. Det tog mig et stykke tid at finde ud af, at der endda skulle være en forskel mellem dem (hvilket bidrog til behovet for omskrivning af parseren).

Action Tree vs AST

Enkelt sagt er handlingstræet AST med kontekst. Denne sammenhæng er info såsom hvilken type en funktion returnerer, eller at to steder, hvor en variabel bruges, faktisk bruger den samme variabel. Fordi det er nødvendigt at finde ud af og huske al denne kontekst, har den kode, der genererer handlingstræet, brug for mange navneopslagstabeller og andre tingamabobs.

Kørsel af Action Tree

Når vi først har handlingstræet, er det let at køre koden. Hver handlingsknudepunkt har en funktion 'execute', der tager noget input, gør hvad handlingen skal (inklusive muligvis kald af subhandling) og returnerer handlingens output. Dette er tolk i aktion.

Kompileringsmuligheder

"Men vent!" Jeg hører dig sige, "skal Pinecone ikke kompileres?" Ja det er. Men kompilering er sværere end at fortolke. Der er et par mulige tilgange.

Byg min egen kompilator

Dette lød først som en god idé for mig. Jeg elsker at lave ting selv, og jeg har kløet efter en undskyldning for at blive god til montering.

Desværre er det ikke så let at skrive en bærbar kompilator som at skrive maskinkode til hvert sprogelement. På grund af antallet af arkitekturer og operativsystemer er det upraktisk for enhver person at skrive en cross-platform compiler backend.

Selv holdene bag Swift, Rust og Clang vil ikke bekymre sig om det hele alene, så i stedet bruger de alle ...

LLVM

LLVM er en samling kompilatorværktøjer. Det er dybest set et bibliotek, der vil gøre dit sprog til en kompileret eksekverbar binær. Det virkede som det perfekte valg, så jeg sprang lige ind. Desværre kontrollerede jeg ikke, hvor dybt vandet var, og jeg druknede straks.

LLVM er, selvom det ikke er hårdt monteringssprog, gigantisk komplekst bibliotek hårdt. Det er ikke umuligt at bruge, og de har gode tutorials, men jeg indså, at jeg skulle få lidt øvelse, før jeg var klar til fuldt ud at implementere en Pinecone-kompilator med den.

Transpiling

Jeg ville have en slags kompileret pinecone, og jeg ville have det hurtigt, så jeg vendte mig til en metode, jeg vidste, at jeg kunne få til at arbejde: transpiling.

Jeg skrev en Pinecone til C ++ transpiller og tilføjede muligheden for automatisk at kompilere outputkilden med GCC. Dette fungerer i øjeblikket for næsten alle Pinecone-programmer (selvom der er et par edge-tilfælde, der bryder det). Det er ikke en særlig bærbar eller skalerbar løsning, men den fungerer i øjeblikket.

Fremtid

Forudsat at jeg fortsætter med at udvikle Pinecone, vil det få LLVM-kompilering support før eller senere. Jeg formoder ikke materiel, hvor meget jeg arbejder på det, transportøren vil aldrig være helt stabil, og fordelene ved LLVM er mange. Det er bare et spørgsmål om, hvornår jeg har tid til at lave nogle prøveprojekter i LLVM og få fat på det.

Indtil da er tolken fantastisk til trivielle programmer, og C ++ transpiling fungerer til de fleste ting, der har brug for mere ydeevne.

Konklusion

Jeg håber, jeg har gjort programmeringssprog lidt mindre mystiske for dig. Hvis du ønsker at lave en selv, kan jeg varmt anbefale det. Der er masser af implementeringsdetaljer at finde ud af, men omridset her skal være nok til at komme i gang.

Her er mit råd på højt niveau til at komme i gang (husk, jeg ved ikke rigtig, hvad jeg laver, så tag det med et saltkorn):

  • Hvis du er i tvivl, skal du fortolke det. Tolkede sprog er generelt lettere at designe, bygge og lære. Jeg fraråder dig ikke at skrive en samlet, hvis du ved, det er hvad du vil gøre, men hvis du er ved hegnet, ville jeg fortolke det.
  • Når det kommer til lexers og parsers, skal du gøre hvad du vil. Der er gyldige argumenter for og imod at skrive din egen. I sidste ende, hvis du tænker over dit design og implementerer alt på en fornuftig måde, betyder det ikke rigtig noget.
  • Lær af den rørledning, jeg endte med. En masse prøving og fejl gik i design af den rørledning, jeg har nu. Jeg har forsøgt at eliminere AST'er, AST'er, der bliver til handlingstræer på plads og andre forfærdelige ideer. Denne pipeline fungerer, så ændr den ikke, medmindre du har en rigtig god idé.
  • Hvis du ikke har tid eller motivation til at implementere et komplekst sprog til generelle formål, kan du prøve at implementere et esoterisk sprog som Brainfuck. Disse tolke kan være så korte som et par hundrede linjer.

Jeg beklager meget få, når det kommer til Pinecone-udvikling. Jeg lavede en række dårlige valg undervejs, men jeg har omskrevet det meste af koden, der er påvirket af sådanne fejl.

Lige nu er Pinecone i en god nok tilstand, at den fungerer godt og let kan forbedres. At skrive pinecone har været en meget lærerig og behagelig oplevelse for mig, og det er lige ved at komme i gang.