Sådan skriver du en meget grundlæggende kompilator

Intro

En typisk compiler udfører følgende trin:

• Parsing: kildetekst konverteres til et abstrakt syntaks-træ (AST).
• Opløsning af referencer til andre moduler (C udsætter dette trin til linkning).
• Semantisk validering: udryddelse af syntaktisk korrekte udsagn der ikke giver mening, f.eks uopnåelig kode eller duplikaterklæringer.
• Ækvivalente transformationer og optimering på højt niveau: AST transformeres til at repræsentere en mere effektiv beregning med den samme semantik. Dette inkluderer f.eks. tidlig beregning af almindelige underudtryk og konstante udtryk, eliminering af overdreven lokale tildelinger (se også SSA ) osv.
• Kodegenerering: AST er omdannet til lineær lavniveau-kode med spring, registerallokering og lignende. Nogle funktionsopkald kan indføres på dette trin, nogle sløjfer rulles ud osv.
• Kiggehuloptimering: koden på lavt niveau scannes for enkle lokale ineffektiviteter, som elimineres.

De fleste moderne kompilatorer (for eksempel gcc og clang) gentager de sidste to trin igen. De bruger et mellemliggende lavt niveau, men platformuafhængigt sprog til indledende kodegenerering. Derefter konverteres dette sprog til platformsspecifik kode (x86, ARM osv.), Der gør omtrent det samme på en platform-optimeret måde. Dette inkluderer f.eks. brugen af vektorinstruktioner, når det er muligt, rækkefølge instruktioner for at øge effektiviteten af forudsigelse af grene osv.

Derefter er objektkoden klar til sammenkædning. De fleste kompilatorer med indbygget kode ved, hvordan man kalder en linker for at producere en eksekverbar, men det er ikke et kompileringstrin i sig selv. På sprog som Java og C # kan linkning være helt dynamisk, udført af VM på indlæsningstid. >

Husk de grundlæggende

• Få det til at fungere
• Gør det smukt
• Gør det effektivt

Denne klassiske rækkefølge gælder for al softwareudvikling, men bærer gentagelse.

Koncentrer dig om det første trin i sekvensen. Opret den enkleste ting, der muligvis fungerer.

Læs bøgerne!

Læs Dragon Book af Aho og Ullman. Dette er klassisk og er stadig ret anvendeligt i dag.

Modern Compiler Design roses også.

Hvis disse ting er for hårde for dig lige nu, skal du læse nogle introduktioner om parsing først; normalt parser biblioteker inkluderer introer og eksempler.

Sørg for, at du er fortrolig med at arbejde med grafer, især træer. Disse ting er de ting, programmer er lavet af på det logiske niveau.

Definer dit sprog godt

Brug den ønskede betegnelse, men sørg for at have en komplet og konsistent beskrivelse af din Sprog. Dette inkluderer både syntaks og semantik.

Det er på høje tid at skrive kodestykker på dit nye sprog som testcases for den fremtidige kompilator.

Brug dit yndlingssprog

Det er helt OK at skrive en compiler i Python eller Ruby eller hvilket sprog der er let for dig.Brug enkle algoritmer, du forstår godt. Den første version behøver ikke at være hurtig eller effektiv eller komplet med funktioner. Det skal kun være korrekt nok og let at ændre.

Det er også OK at skrive forskellige faser af en compiler på forskellige sprog, hvis det er nødvendigt.

Forbered dig på at skrive meget af tests

Hele dit sprog skal være dækket af testcases; effektivt vil det være defineret af dem. Bliv godt bekendt med din foretrukne testramme. Skriv tests fra dag ét. Koncentrer dig om “positive” tests, der accepterer korrekt kode i modsætning til detektering af forkert kode.

Kør alle testene regelmæssigt. Ret ødelagte tests, inden du fortsætter. Det ville være en skam at ende med en syg- defineret sprog, der ikke kan acceptere gyldig kode.

Opret en god parser

Parsergeneratorer er mange . Vælg hvad du vil Du kan også skrive din egen parser fra bunden, men det er kun det værd, hvis syntaksen for dit sprog er død enkel.

Parseren skal registrere og rapportere syntaksfejl. Skriv mange testsager, både positive og negati ve; genbrug den kode, du skrev, mens du definerede sproget.

Output af din parser er et abstrakt syntaks-træ.

Hvis dit sprog har moduler, kan output af parser muligvis være den enkleste repræsentation af “objektkode”, du genererer. Der er mange enkle måder at dumpe et træ til en fil og hurtigt indlæse det tilbage.

Opret en semantisk validator

Sandsynligvis giver dit sprog mulighed for syntaktisk korrekte konstruktioner, der kan gøre ingen mening i visse sammenhænge. Et eksempel er en duplikaterklæring af den samme variabel eller videregivelse af en parameter af en forkert type. Validatoren opdager sådanne fejl ved at se på træet.

Validatoren løser også referencer til andre moduler skrevet på dit sprog, indlæser disse andre moduler og bruger i valideringsprocessen. For eksempel vil dette trin sikre, at antallet af parametre, der sendes til en funktion fra et andet modul, er korrekt.

Skriv igen og kør mange testcases. Trivial cases er lige så uundværlige ved fejlfinding som smarte og komplekse.

Generer kode

Brug de enkleste teknikker, du kender. Ofte er det OK at oversætte en sprogkonstruktion direkte (som en if -erklæring) til en let parametreret kodeskabelon, ikke i modsætning til en HTML-skabelon.

Igen ignorere effektivitet og koncentrer dig om korrekthed.

Målret mod en platformuafhængig VM på lavt niveau

Jeg formoder, at du ignorerer ting på lavt niveau, medmindre du er meget interesseret i hardwarespecifik detaljer. Disse detaljer er blodige og komplekse.

Dine muligheder:

• LLVM: muliggør effektiv maskinkodegenerering, normalt til x86 og ARM.
• CLR : mål .NET, multiplatform; har en god JIT.
• JVM: målretter mod Java-verdenen, ret multiplatform, har en god JIT.

Ignorer optimering

Optimering er hård. Næsten altid er optimering for tidlig. Generer ineffektiv, men korrekt kode. Implementér hele sproget, inden du prøver at optimere den resulterende kode.

Selvfølgelig er trivielle optimeringer OK at indføre. Men undgå snedige, hårede ting, før din kompilator er stabil.

Så hvad?

Hvis alle disse ting ikke er for skræmmende for dig, skal du fortsætte! For et simpelt sprog kan hvert trin være enklere, end du måske tror.

At se en “Hej verden” fra et program, som din kompilator oprettede, kan være umagen værd.

Kommentarer

• Dette er et af de bedste svar, jeg ‘ har set endnu.
• Jeg tror du savnede en del af spørgsmålet … OPen ønskede at skrive en meget grundlæggende kompilator. Jeg tror, du går ud over meget grundlæggende her.
• @ marco-fiset , tværtimod, jeg tror det ‘ er et fremragende svar, der fortæller OP, hvordan man gør en meget grundlæggende kompilator, mens man påpeger fælderne for at undgå og definere mere avancerede faser.
• Dette er et af de bedste svar Jeg har nogensinde set i hele Stack Exchange-universet. Kudos!
• At se en ‘ Hej verden ‘ fra et program, som din kompilator oprettede, kan være umagen værd. – INDEED

Jack Crenshaw “s Lad os bygge en kompilator , mens den ikke er færdig, er en meget læsbar introduktion og vejledning.

Nicklaus Wirth “s Compiler Construction er en meget god lærebog om det grundlæggende i simpel kompilerkonstruktion. Han fokuserer på top-down rekursiv afstamning, som, lad os se det i øjnene, er MEGET lettere end lex / yacc eller flex / bison. Den originale PASCAL-kompilator, som hans gruppe skrev, blev gjort på denne måde.

Andre mennesker har nævnt de forskellige Dragon-bøger.

Kommentarer

• En af de gode ting ved Pascal er, at alt skal defineres eller erklæres, inden det bruges. Derfor kan den kompileres på én gang. Turbo Pascal 3.0 er et sådant eksempel, og der er meget dokumentation om de interne her .
• PASCAL blev specifikt designet med en- bestå kompilering og sammenkædning i tankerne. Wirth ‘ s kompilatorbog omtaler multipass-kompilatorer og tilføjer, at han kendte til en PL / I-kompilator, der tog 70 passager (ja, halvfjerds).
• Obligatorisk erklæring inden brug går tilbage til ALGOL. Tony Hoare fik sine ører fastgjort af ALGOL-udvalget, da han forsøgte at foreslå tilføjelse af standardtyperegler svarende til hvad FORTRAN havde. De vidste allerede om de problemer, dette kunne skabe, med typografiske fejl i navne og standardregler, der skabte interessante fejl.
• Her er en mere opdateret og færdig version af bogen af den originale forfatter selv: stack.nl/~marcov/compiler.pdf Rediger dit svar og tilføj dette 🙂

Hvis du virkelig kun vil skrive maskinlæsbar kode og ikke er målrettet mod en virtuel maskine, bliver du nødt til at læse Intel-manualer og forstå

• a. Linkning og indlæsning af eksekverbar kode

• b. COFF- og PE-formater (til windows), alternativt forstå ELF-format (til Linux)

• c. Forstå .COM-filformater (lettere end PE)
• d. Forstå samlere
• e. Forstå kompilatorer og kodegenereringsmotorer i kompilatorer.

Meget sværere udført end sagt. Jeg foreslår, at du læser Compilers and Interpreters i C ++ som udgangspunkt (Af Ronald Mak). Alternativt er “lad os bygge en compiler” af Crenshaw OK.

Hvis du ikke ønsker at gøre det, kan du lige så godt skrive din egen VM og skrive en kodegenerator målrettet mod den pågældende VM.

• Et andet udgangspunkt: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Fantastisk bog af Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Tips: Lær Flex og Bison FØRST. Fortsæt derefter med at opbygge din egen kompilator / VM.

Held og lykke!

Kommentarer

• Jeg tror, at jeg målretter mod LLVM og ikke ægte maskinkode handler om den bedste tilgængelige måde i dag.
• Jeg er enig, jeg har fulgt LLVM i nogen tid nu, og jeg skulle sige, at det var en af de bedste ting, jeg havde set i årevis med hensyn til programmørindsats behov for at målrette det!
• Hvad med MIPS og brug spim til at køre det? Eller MIX ?
• @MichaelT Jeg har ikke brugt MIPS, men jeg er sikker på, at det vil være godt.
• @PrototypeStark RISC instruktions sæt, den virkelige verdensprocessor, der stadig er i brug i dag (forståelse for at det kan oversættes til indlejrede systemer). Det fulde instruktions sæt findes på wikipedia . Når man ser på nettet, er der mange eksempler, og det bruges i mange akademiske klasser som et mål for maskinsprogsprogrammering. Der er en smule aktivitet i SO .

DIY tilgang til simpel kompilator kunne se sådan ud (i det mindste sådan lignede mit uni-projekt):

1. Definer sprogets grammatik. Kontekstfri.
2. Hvis din grammatik endnu ikke er LL (1), skal du gøre det nu. Bemærk, at nogle regler, der så ok ud i almindelig CF grammatik kan vise sig grim. Måske er dit sprog for komplekst …
3. Skriv Lexer, der skærer strøm af tekst i tokens (ord, tal, bogstaver).
4. Skriv ovenfra og ned rekursiv nedstigningsparser til din grammatik, som accepterer eller afviser input.
5. Tilføj syntaks-trægenerering i din parser.
6. Skriv ma chinekodegenerator fra syntaksetræet.
7. Fortjeneste & Øl, alternativt kan du begynde at tænke på, hvordan du laver en smartere parser eller genererer bedre kode.

Der skulle være masser af litteratur, der beskriver hvert trin i detaljer.

Kommentarer

• Det syvende punkt er, hvad OP spørger om.
• 1-5 er irrelevante og fortjener ikke sådan en tæt opmærksomhed. 6 er den mest interessante del.Desværre følger de fleste af bøgerne det samme mønster efter den berygtede dragonbog, hvor man lægger for meget vægt på parsing og efterlader kodeforandringer uden for omfanget.