Hur man skriver en mycket grundläggande kompilator

Intro

En typisk kompilator gör följande steg:

• Parsing: källtext konverteras till ett abstrakt syntaxträd (AST).
• Upplösning av referenser till andra moduler (C skjuter upp detta steg till länkning).
• Semantisk validering: rensning av syntaktiskt korrekta uttalanden som inte är vettiga, t.ex. oåtkomlig kod eller dubblettdeklarationer.
• Motsvarande transformationer och högnivåoptimering: AST transformeras för att representera en mer effektiv beräkning med samma semantik. Detta inkluderar t.ex. tidig beräkning av vanliga deluttryck och konstanta uttryck, eliminering av överdrivna lokala tilldelningar (se även SSA ), etc.
• Kodgenerering: AST är omvandlas till linjär lågnivåkod, med hopp, registerallokering och liknande. Vissa funktionssamtal kan läggas in i detta skede, vissa slingor rullas upp osv.
• Kikhåloptimering: koden på låg nivå skannas för enkla lokala ineffektiviteter som elimineras.

De flesta moderna kompilatorer (till exempel gcc och clang) upprepar de två sista stegen en gång till. De använder ett mellanliggande lågnivå men plattformsoberoende språk för inledande kodgenerering. Sedan omvandlas det språket till plattformsspecifik kod (x86, ARM, etc) och gör ungefär samma sak på ett plattformsoptimerat sätt. Detta inkluderar t.ex. användningen av vektorinstruktioner när det är möjligt, inställning av instruktioner för att öka grenprediktionseffektiviteten och så vidare.

Därefter är objektkoden redo för länkning. De flesta kompilatorer för inbyggd kod vet hur man kallar en länkare för att producera en körbar, men det är inte ett kompileringssteg i sig. På språk som Java och C # kan länkning vara helt dynamisk, gjort av den virtuella datorn vid laddningstid.

Kom ihåg grunderna

• Få det att fungera
• Gör det vackert
• Gör det effektivt

Den här klassiska sekvensen gäller all mjukvaruutveckling men upprepas.

Koncentrera dig om det första steget i sekvensen. Skapa det enklaste som kan fungera.

Läs böckerna!

Läs Dragon Book av Aho och Ullman. Detta är klassiskt och är fortfarande ganska tillämpligt idag.

Modern Compiler Design hyllas också.

Om det här är för svårt för dig just nu, läs några introduktioner om tolkning först; vanligtvis tolkar bibliotek inkludera introduktioner och exempel.

Se till att du är bekväm med att arbeta med grafer, särskilt träd. Dessa saker är de saker som programmen är gjorda av på den logiska nivån.

Definiera ditt språk väl

Använd vilken notation du vill, men se till att du har en fullständig och konsekvent beskrivning av din språk. Detta inkluderar både syntax och semantik.

Det är hög tid att skriva kodavsnitt på ditt nya språk som testfall för den framtida kompilatorn.

Använd ditt favoritspråk

Det är helt OK att skriva en kompilator i Python eller Ruby eller vilket språk som helst som är lätt för dig.Använd enkla algoritmer som du förstår väl. Den första versionen behöver inte vara snabb, effektiv eller komplett med funktioner. Det behöver bara vara tillräckligt korrekt och enkelt att ändra.

Det är också OK att skriva olika steg i en kompilator på olika språk, om det behövs.

Förbered dig på att skriva mycket av test

Hela ditt språk ska täckas av testfall, det kommer faktiskt att definieras av dem. Bli väl förtrogen med ditt föredragna testramverk. Skriv test från dag ett. Koncentrera dig om ”positiva” tester som accepterar korrekt kod, i motsats till upptäckt av felaktig kod.

Kör alla tester regelbundet. Fixa trasiga tester innan du fortsätter. Det skulle vara synd att avsluta med en sjuk definierat språk som inte kan acceptera giltig kod.

Skapa en bra parser

Parsergeneratorer är många . Välj vad du än Du kan också skriva din egen parser från grunden, men det är bara värt det om syntax för ditt språk är död enkel.

Parsern ska upptäcka och rapportera syntaxfel. Skriv många testfall, både positiva och negativa ve; återanvänd koden du skrev medan du definierade språket.

Utdata från din parser är ett abstrakt syntaxträd.

Om ditt språk har moduler, kan utdata från parser vara den enklaste representationen. av ”objektkod” du genererar. Det finns många enkla sätt att dumpa ett träd till en fil och snabbt ladda tillbaka det.

Skapa en semantisk validator

Troligtvis tillåter ditt språk syntaktiskt korrekta konstruktioner som kan göra ingen mening i vissa sammanhang. Ett exempel är en dubblettdeklaration av samma variabel eller att passera en parameter av fel typ. Valideraren kommer att upptäcka sådana fel när man tittar på trädet.

Valideraren kommer också att lösa referenser till andra moduler skrivna på ditt språk, ladda dessa andra moduler och använda i valideringsprocessen. Till exempel kommer detta steg att se till att antalet parametrar som skickas till en funktion från en annan modul är korrekt.

Återigen, skriv och kör många testfall. Trivialfall är lika oumbärliga vid felsökning som smarta och komplexa.

Skapa kod

Använd de enklaste teknikerna du känner till. Ofta är det OK att direkt översätta en språkkonstruktion (som ett if uttalande) till en lätt parametriserad kodmall, inte till skillnad från en HTML-mall.

Återigen , ignorera effektivitet och koncentrera dig på korrekthet.

Rikta in en plattformsoberoende VM på låg nivå

Jag antar att du ignorerar saker på låg nivå om du inte är mycket intresserad av hårdvaruspecifik detaljer. Dessa detaljer är blodiga och komplexa.

Dina alternativ:

• LLVM: möjliggör effektiv maskinkodgenerering, vanligtvis för x86 och ARM.
• CLR : mål .NET, multiplatform; har en bra JIT.
• JVM: riktar sig mot Java-världen, ganska multiplatform, har en bra JIT.

Ignorera optimering

Optimering är svår. Optimering är nästan alltid för tidig. Generera ineffektiv men korrekt kod. Implementera hela språket innan du försöker optimera den resulterande koden.

Naturligtvis är triviala optimeringar OK att införa. Men undvik alla listiga, håriga saker innan din kompilator är stabil.

Så vad?

Om allt det här inte är för skrämmande för dig, fortsätt! För ett enkelt språk kan vart och ett av stegen vara enklare än du kanske tror.

Att se en ”Hello world” från ett program som din kompilator skapade kan vara värt ansträngningen.

Kommentarer

• Detta är ett av de bästa svaren jag ’ har sett än.
• Jag tror att du missade en del av frågan … OP ville skriva en mycket grundläggande kompilator. Jag tror att du går utöver väldigt grundläggande här.
• @ marco-fiset , tvärtom tror jag att det ’ är ett enastående svar som berättar för OP hur man gör en mycket grundläggande kompilator, samtidigt som man pekar på fällorna för att undvika och definiera mer avancerade faser.
• Detta är ett av de bästa svaren Jag har någonsin sett i hela Stack Exchange-universum. Kudos!
• Att se en ’ Hello world ’ från ett program som din kompilator skapade kan vara värt ansträngningen. – INDEED

Jack Crenshaw ”s Låt oss bygga en kompilator , medan de är oavslutade, är en mycket läsbar introduktion och handledning.

Nicklaus Wirth ”s Kompilatorkonstruktion är en mycket bra lärobok om grunderna för enkel kompilatorkonstruktion. Han fokuserar på rekursiv nedstigning uppifrån och ner, som, låt oss inse det, är mycket lättare än lex / yacc eller flex / bison. Den ursprungliga PASCAL-kompilatorn som hans grupp skrev gjordes på detta sätt.

Andra har nämnt de olika Dragon-böckerna.

Kommentarer

• En av de trevliga sakerna med Pascal är att allt måste definieras eller deklareras innan det används. Därför kan den sammanställas i ett steg. Turbo Pascal 3.0 är ett sådant exempel, och det finns mycket dokumentation om de inre här .
• PASCAL utformades specifikt med en- passera sammanställning och länkning i åtanke. Wirth ’ s kompilatorbok nämner kompassers för flera passager och tillägger att han kände till en PL / I-kompilator som tog 70 pass (ja, sjuttio) pass. före användning går tillbaka till ALGOL. Tony Hoare fick tillbaka öronen av ALGOL-kommittén när han försökte föreslå att man skulle lägga till standardtypregler, liknande det som FORTRAN hade. De visste redan om problemen detta kunde skapa, med typografiska fel i namn och standardregler som skapade intressanta buggar.
• Här är en mer uppdaterad och färdig version av boken av originalförfattaren själv: stack.nl/~marcov/compiler.pdf Redigera ditt svar och lägg till det här 🙂

Om du bara vill skriva maskinläsbar kod och inte riktas mot en virtuell maskin, måste du läsa Intels manualer och förstå

• a. Länka och ladda körbar kod

• b. COFF- och PE-format (för Windows), alternativt förstå ELF-format (för Linux)

• c. Förstå .COM-filformat (enklare än PE)
• d. Förstå montörer
• e. Förstå kompilatorer och kodgenereringsmotorer i kompilatorer.

Mycket svårare gjort än sagt. Jag föreslår att du läser kompilatorer och tolkar i C ++ som utgångspunkt (av Ronald Mak). Alternativt är ”lets build a compiler” av Crenshaw okej.

Om du inte vill göra det kan du lika gärna skriva din egen virtuella dator och skriva en kodgenerator riktad mot den virtuella datorn. p>

• En annan utgångspunkt: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Bra bok av Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Tips: Lär dig Flex och Bison FÖRST. Fortsätt sedan med att bygga din egen kompilator / VM.

Lycka till!

Kommentarer

• Jag tror att jag riktar in mig på LLVM och inte verklig maskinkod handlar om det bästa sättet som finns idag.
• Jag håller med, jag har följt LLVM en stund nu och jag borde säga att det var en av de bästa sakerna jag sett på flera år när det gäller programmeringsinsats. behövs för att rikta in det!
• Vad sägs om MIPS och använda spim för att köra det? Eller MIX ?
• @MichaelT Jag har inte använt MIPS men jag är säker på att det kommer att bli bra.
• @PrototypeStark RISC instruktionsuppsättning, verklig processor som fortfarande används idag (förståelse för att den kan översättas till inbäddade system). Den fullständiga instruktionsuppsättningen finns på wikipedia . När man tittar på nätet finns det många exempel och det används i många akademiska klasser som ett mål för programmering av maskinspråk. Det finns lite aktivitet på SO .

DIY-tillvägagångssätt för enkel kompilator kan se ut så här (åtminstone såg mitt uni-projekt ut):

1. Definiera språkets grammatik. Innehållsfritt.
2. Om din grammatik inte är LL (1) ännu, gör det nu. Observera att vissa regler som såg ut i vanligt CF grammatik kan bli ful. Kanske är ditt språk för komplicerat …
3. Skriv Lexer som skär textflödet i tokens (ord, siffror, bokstäver).
4. Skriv uppifrån och ner rekursiv nedstigningsparserare för din grammatik, som accepterar eller avvisar inmatning.
5. Lägg till syntaxträdgenerering i din parser.
6. Skriv ma chinekodgenerator från syntaxträdet.
7. Vinst & Öl, alternativt kan du börja tänka på hur man gör smartare parser eller genererar bättre kod.

Det borde ha gott om litteratur som beskriver varje steg i detalj.

Kommentarer

• Den sjunde punkten är vad OP frågar om.
• 1-5 är irrelevanta och förtjänar inte sådana en noggrann uppmärksamhet. 6 är den mest intressanta delen.Tyvärr följer de flesta böcker samma mönster, efter den ökända drakeboken, med uppmärksamhet åt att analysera och lämna kodomvandlingar utanför räckvidden.