Hvordan skrive en veldig grunnleggende kompilator

Intro

En typisk kompilator gjør følgende trinn:

• Parsing: kildetekst konverteres til et abstrakt syntaks-tre (AST).
• Oppløsning av referanser til andre moduler (C utsetter dette trinnet til lenking).
• Semantisk validering: lukking av syntaktisk korrekte utsagn som ikke gir mening, f.eks uoppnåelig kode eller dupliserte erklæringer.
• Tilsvarende transformasjoner og optimalisering på høyt nivå: AST er transformert til å representere en mer effektiv beregning med samme semantikk. Dette inkluderer f.eks. tidlig beregning av vanlige underuttrykk og konstante uttrykk, eliminering av overdreven lokale oppdrag (se også SSA ) osv.
• Kodegenerering: AST er forvandlet til lineær lavnivåkode, med hopp, registerfordeling og lignende. Noen funksjonsanrop kan legges inn på dette stadiet, noen sløyfer rulles ut osv.
• Optimalisering av kikkhull: koden på lavt nivå skannes for enkle lokale ineffektiviteter som elimineres.

De fleste moderne kompilatorer (for eksempel gcc og clang) gjentar de to siste trinnene en gang til. De bruker et mellomliggende lavnivå men plattformuavhengig språk for innledende kodegenerering. Deretter konverteres det språket til plattformspesifikk kode (x86, ARM, etc) og gjør omtrent det samme på en plattformoptimalisert måte. Dette inkluderer f.eks. bruk av vektorinstruksjoner når det er mulig, omorganisering av instruksjoner for å øke effektiviteten til forutsigelse av grenen, og så videre.

Etter det er objektkoden klar for lenking. De fleste kompilatorer med innfødt kode vet hvordan man kaller en linker for å produsere en kjørbar, men det er ikke et kompileringstrinn i seg selv. På språk som Java og C # kan det hende at linking er helt dynamisk, utført av VM på belastningstid.

Husk det grunnleggende

• Få det til å fungere
• Gjør det vakkert
• Gjør det effektivt

Denne klassiske sekvensen gjelder all programvareutvikling, men har gjentakelse.

Konsentrer deg om det første trinnet i sekvensen. Lag det enkleste som muligens kan fungere.

Les bøkene!

Les Dragon Book av Aho og Ullman. Dette er klassisk og er fortsatt ganske anvendelig i dag.

Modern Compiler Design får også skryt.

Hvis dette er for vanskelig for deg akkurat nå, kan du lese noen introer om parsing først; vanligvis parsebiblioteker inkluderer introer og eksempler.

Sørg for at du er komfortabel med å jobbe med grafer, spesielt trær. Disse tingene er ting programmene er laget av på det logiske nivået.

Definer språket ditt godt

Bruk den notasjonen du vil, men sørg for at du har en fullstendig og konsistent beskrivelse av Språk. Dette inkluderer både syntaks og semantikk.

Det er på høy tid å skrive kodebiter på det nye språket ditt som testtilfeller for den fremtidige kompilatoren.

Bruk favorittspråket ditt

Det er helt OK å skrive en kompilator på Python eller Ruby eller hvilket språk som er lett for deg.Bruk enkle algoritmer du forstår godt. Den første versjonen trenger ikke å være rask, effektiv eller komplett med funksjonen. Det trenger bare å være riktig nok og enkelt å endre.

Det er også OK å skrive forskjellige stadier av en kompilator på forskjellige språk, om nødvendig.

Forbered deg på å skrive mye av tester

Hele språket ditt skal dekkes av testtilfeller; effektivt blir det definert av dem. Gjør deg kjent med ditt foretrukne testrammeverk. Skriv tester fra dag én. Konsentrer deg om «positive» tester som godtar riktig kode, i motsetning til deteksjon av feil kode.

Kjør alle testene regelmessig. Løs ødelagte tester før du fortsetter. Det ville være synd å ende opp med en syk- definert språk som ikke kan godta gyldig kode.

Lag en god parser

Parsergeneratorer er mange . Velg hva du vil Du kan også skrive din egen parser fra bunnen av, men det er bare verdt det hvis syntaksen til språket ditt er død enkel.

Parseren skal oppdage og rapportere syntaksfeil. mange testsaker, både positive og negati ve; bruk koden du skrev mens du definerte språket på nytt.

Utdata fra parseren din er et abstrakt syntaks-tre.

Hvis språket ditt har moduler, kan utdataene til parseren være den enkleste representasjonen. av «objektkode» du genererer. Det er mange enkle måter å dumpe et tre til en fil og raskt laste det tilbake.

Lag en semantisk validator

Språket ditt gir sannsynligvis syntaktisk riktige konstruksjoner som kan gjøre ingen mening i visse sammenhenger. Et eksempel er en duplikaterklæring av den samme variabelen eller å sende en parameter av feil type. Validatoren vil oppdage slike feil når man ser på treet.

Validatoren vil også løse referanser til andre moduler skrevet på ditt språk, laste disse andre modulene og bruke i valideringsprosessen. For eksempel vil dette trinnet sørge for at antall parametere som sendes til en funksjon fra en annen modul er riktig.

Igjen, skriv og kjør mange testtilfeller. Trivial saker er like uunnværlige ved feilsøking som smarte og komplekse.

Generer kode

Bruk de enkleste teknikkene du kjenner. Ofte er det OK å direkte oversette en språkkonstruksjon (som en if -uttalelse) til en lett parametrisert kodemal, ikke ulikt en HTML-mal.

Igjen , ignorere effektivitet og konsentrer deg om korrekthet.

Målrett mot en plattformuavhengig VM på lavt nivå

Jeg antar at du ignorerer ting på lavt nivå med mindre du er veldig interessert i maskinvarespesifikk detaljer. Disse detaljene er blodige og komplekse.

Dine valg:

• LLVM: muliggjør effektiv generering av maskinkoder, vanligvis for x86 og ARM.
• CLR : mål .NET, multiplatform; har en god JIT.
• JVM: retter seg mot Java-verden, ganske multiplatform, har en god JIT.

Ignorer optimalisering

Optimalisering er vanskelig. Nesten alltid er optimalisering for tidlig. Generer ineffektiv, men riktig kode. Implementer hele språket før du prøver å optimalisere den resulterende koden.

Selvfølgelig er trivielle optimaliseringer OK å introdusere. Men unngå slu, hårete ting før kompilatoren din er stabil.

Så hva?

Hvis alt dette ikke er for skremmende for deg, så fortsett! For et enkelt språk kan hvert av trinnene være enklere enn du kanskje tror.

Å se en «Hello world» fra et program som kompilatoren din opprettet, kan være verdt innsatsen.

Kommentarer

• Dette er et av de beste svarene jeg ‘ har sett ennå.
• Jeg tror du savnet en del av spørsmålet … OP-en ønsket å skrive en veldig grunnleggende kompilator. Jeg tror du går utover veldig grunnleggende her.
• @ marco-fiset , tvert imot, jeg tror det ‘ er et enestående svar som forteller OP hvordan man gjør en veldig grunnleggende kompilator, mens man peker på fellene for å unngå og definere mer avanserte faser.
• Dette er et av de beste svarene Jeg har noen gang sett i hele Stack Exchange-universet. Kudos!
• Å se en ‘ Hello world ‘ fra et program som kompilatoren din opprettet, kan være verdt innsatsen. – INDEED

Jack Crenshaw «s La oss bygge en kompilator , mens den ikke er ferdig, er en veldig lesbar introduksjon og opplæring.

Nicklaus Wirth «s Kompilatorkonstruksjon er en veldig god lærebok om det grunnleggende om enkel kompilatorkonstruksjon. Han fokuserer på rekursiv nedstigning ovenfra og ned, som, la oss innse det, er MYE lettere enn lex / yacc eller flex / bison. Den originale PASCAL-kompilatoren som gruppen hans skrev, ble gjort på denne måten.

Andre mennesker har nevnt de forskjellige Dragon-bøkene.

Kommentarer

• Noe av det fine med Pascal, er at alt må defineres eller erklæres før det brukes. Derfor kan den samles i ett pass. Turbo Pascal 3.0 er et slikt eksempel, og det er mye dokumentasjon om internene her .
• PASCAL ble spesielt designet med en- passere kompilering og kobling i tankene. Wirth ‘ s kompilatorbok nevner flerkompilatorer, og legger til at han visste om en PL / I-kompilator som tok 70 pass (ja, sytti) pass.
• Obligatorisk erklæring før bruk dateres tilbake til ALGOL. Tony Hoare fikk ørene fast igjen av ALGOL-komiteen da han prøvde å foreslå å legge til standardtype regler, i likhet med det FORTRAN hadde. De visste allerede om problemene dette kunne skape, med typografiske feil i navn og standardregler som skapte interessante feil.
• Her er en mer oppdatert og ferdig versjon av boka av den opprinnelige forfatteren selv: stack.nl/~marcov/compiler.pdf Vennligst rediger svaret og legg til dette 🙂

Hvis du virkelig bare vil skrive maskinlesbar kode og ikke er målrettet mot en virtuell maskin, må du lese Intel-håndbøkene og forstå

• a. Kobling og lasting av kjørbar kode

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

• c. Forstå .COM-filformater (enklere enn PE)
• d. Forstå montører
• e. Forstå kompilatorer og kodegenerasjonsmotorer i kompilatorer.

Mye vanskeligere gjort enn sagt. Jeg foreslår at du leser Compilers and Interpreters i C ++ som utgangspunkt (av Ronald Mak). Alternativt er «la oss bygge en kompilator» av Crenshaw OK.

Hvis du ikke vil gjøre det, kan du like godt skrive din egen VM og skrive en kodegenerator rettet mot den virtuelle maskinen.

• Et annet utgangspunkt: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Flott bok av Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Tips: Lær Flex og Bison FØRST. Bygg deretter din egen kompilator / VM.

Lykke til!

Kommentarer

• Jeg tror jeg målretter mot LLVM og ikke ekte maskinkode handler om den beste måten å få i dag.
• Jeg er enig, jeg har fulgt LLVM en god stund nå, og jeg burde si at det var en av de beste tingene jeg hadde sett på mange år når det gjelder programmeringsinnsats. trengs for å målrette det!
• Hva med MIPS og bruk spim for å kjøre det? Eller MIX ?
• @MichaelT Jeg har ikke brukt MIPS, men jeg er sikker på at det vil være bra.
• @PrototypeStark RISC instruksjonssett, ekte prosessor som fremdeles er i bruk i dag (å forstå det vil kunne oversettes til innebygde systemer). Hele instruksjonssettet er på wikipedia . Ser på nettet, det er mange eksempler, og det brukes i mange akademiske klasser som et mål for maskinspråklig programmering. Det er litt aktivitet på den på SO .

DIY-tilnærming for enkel kompilator kan se slik ut (i det minste sånn uni-prosjektet mitt ut):

1. Definer språkets grammatikk. Kontekstfritt.
2. Hvis grammatikken din ikke er LL (1) ennå, gjør du den nå. Vær oppmerksom på at noen regler som så ok ut i vanlig CF grammatikk kan vise seg å være stygg. Kanskje språket ditt er for komplekst …
3. Skriv Lexer som kutter strøm av tekst i tokens (ord, tall, bokstaver).
4. Skriv ovenfra og ned rekursiv nedstigningsparser for grammatikken din, som godtar eller avviser input.
5. Legg til syntaks-tregenerering i parseren.
6. Skriv ma pinnekodegenerator fra syntakstreet.
7. Profitt & Øl, alternativt kan du begynne å tenke hvordan du gjør smartere parser eller genererer bedre kode.

Det burde være rikelig med litteratur som beskriver hvert trinn i detalj.

Kommentarer

• Det 7. punktet er hva OP spør om.
• 1-5 er irrelevante og fortjener ikke slike en nøye oppmerksomhet. 6 er den mest interessante delen.Dessverre følger de fleste bøkene det samme mønsteret, etter den beryktede dragen-boken, og legger for mye vekt på å analysere og etterlate kodetransformasjoner utenfor omfanget.