Hoe een heel eenvoudige compiler te schrijven

Intro

Een typische compiler voert de volgende stappen uit:

• Parseren: de brontekst wordt geconverteerd naar een abstracte syntaxisboom (AST).
• Oplossing van verwijzingen naar andere modules (C stelt deze stap uit tot koppelen).
• Semantische validatie: syntactisch correcte uitspraken verwijderen dat slaat nergens op, bijv onbereikbare code of dubbele declaraties.
• Equivalente transformaties en optimalisatie op hoog niveau: de AST wordt getransformeerd om een efficiëntere berekening met dezelfde semantiek weer te geven. Dit omvat b.v. vroege berekening van veelvoorkomende subexpressies en constante expressies, eliminatie van buitensporige lokale toewijzingen (zie ook SSA ), enz.
• Codegeneratie: de AST is omgezet in lineaire low-level code, met sprongen, registertoewijzing en dergelijke. Sommige functieaanroepen kunnen in dit stadium worden geïntegreerd, sommige lussen worden uitgerold, enz.
• Kijkgaatje-optimalisatie: de code op laag niveau wordt gescand op eenvoudige lokale inefficiënties die worden geëlimineerd.

De meeste moderne compilers (bijvoorbeeld gcc en clang) herhalen de laatste twee stappen nog een keer. Ze gebruiken een tussenliggende, maar platformonafhankelijke taal voor de eerste codegeneratie. Vervolgens wordt die taal omgezet in platformspecifieke code (x86, ARM, enz.), Die ongeveer hetzelfde doet op een platform-geoptimaliseerde manier. Dit omvat b.v. het gebruik van vectorinstructies waar mogelijk, het opnieuw ordenen van instructies om de voorspellingsefficiëntie van de vertakkingen te verhogen, enzovoort.

Daarna is de objectcode klaar om te koppelen. De meeste compilers met native code weten hoe ze een linker moeten aanroepen om een uitvoerbaar bestand te produceren, maar het is niet per se een compilatiestap. In talen als Java en C # kan het koppelen volledig dynamisch zijn, gedaan door de VM tijdens het laden.

Onthoud de basis

• Laat het werken
• Maak het mooi
• Maak het efficiënt

Deze klassieke reeks is van toepassing op alle softwareontwikkeling, maar draagt herhaling.

Concentreer je op de eerste stap van de reeks. Creëer het eenvoudigste dat mogelijk zou kunnen werken.

Lees de boeken!

Lees het Drakenboek van Aho en Ullman. Dit is klassiek en is nog steeds behoorlijk van toepassing.

Modern Compiler Design wordt ook geprezen.

Als dit spul op dit moment te moeilijk voor je is, lees dan eerst enkele intros over het parseren; meestal het parseren van bibliotheken neem intros en voorbeelden op.

Zorg ervoor dat u vertrouwd bent met het werken met grafieken, vooral met bomen. Dit zijn de dingen waar programmas op logisch niveau van gemaakt zijn.

Definieer je taal goed

Gebruik de notatie die je wilt, maar zorg ervoor dat je een volledige en consistente beschrijving hebt van je taal. taal. Dit omvat zowel syntaxis als semantiek.

Het wordt hoog tijd om stukjes code in je nieuwe taal te schrijven als testgevallen voor de toekomstige compiler.

Gebruik je favoriete taal

Het is helemaal oké om een compiler te schrijven in Python of Ruby of welke taal dan ook die gemakkelijk voor je is.Gebruik eenvoudige algoritmen die u goed begrijpt. De eerste versie hoeft niet snel of efficiënt te zijn, of compleet te zijn. Het hoeft alleen correct genoeg te zijn en gemakkelijk te wijzigen.

Het is ook oké om verschillende stadia van een compiler in verschillende talen te schrijven, indien nodig.

Bereid je voor om veel te schrijven van tests

Uw volledige taal zou moeten worden gedekt door testcases; in feite wordt het door hen gedefinieerd . Maak goed vertrouwd met uw favoriete testkader. Schrijf tests vanaf de eerste dag. Concentreer u op ‘positieve’ tests die de juiste code accepteren, in plaats van het detecteren van onjuiste code.

Voer alle tests regelmatig uit. Herstel defecte tests voordat u verdergaat. Het zou zonde zijn als u een slechte code krijgt. gedefinieerde taal die geen geldige code kan accepteren.

Maak een goede parser

Er zijn veel parsergeneratoren . Kies wat je wilt U kunt ook uw eigen parser helemaal opnieuw schrijven, maar het is het alleen waard als de syntaxis van uw taal dood eenvoudig is.

De parser moet syntaxisfouten detecteren en rapporteren. veel testcases, zowel positief als negatief ve; hergebruik de code die je hebt geschreven tijdens het definiëren van de taal.

De uitvoer van je parser is een abstracte syntaxisboom.

Als je taal modules heeft, is de uitvoer van de parser misschien wel de eenvoudigste weergave van “objectcode” die u genereert. Er zijn tal van eenvoudige manieren om een boom in een bestand te dumpen en het snel weer te laden.

Maak een semantische validator

Hoogstwaarschijnlijk staat uw taal syntactisch correcte constructies toe die kunnen maken geen zin in bepaalde contexten. Een voorbeeld is een dubbele declaratie van dezelfde variabele of het doorgeven van een parameter van een verkeerd type. De validator zal dergelijke fouten detecteren door naar de boom te kijken.

De validator zal ook verwijzingen naar andere modules in uw taal oplossen, deze andere modules laden en gebruiken in het validatieproces. Deze stap zorgt er bijvoorbeeld voor dat het aantal parameters dat door een andere module aan een functie wordt doorgegeven correct is.

Nogmaals, schrijf en voer veel testgevallen uit. Trivial cases zijn net zo onmisbaar bij het oplossen van problemen als slim en complex.

Genereer code

Gebruik de eenvoudigste technieken die u kent. Vaak is het oké om een taalconstructie (zoals een if -instructie) direct te vertalen naar een licht geparametriseerde codesjabloon, vergelijkbaar met een HTML-sjabloon.

Nogmaals , negeer efficiëntie en concentreer u op juistheid.

Richt u op een platformonafhankelijke low-level VM

Ik veronderstel dat u low-level dingen negeert, tenzij u “zeer geïnteresseerd bent in hardware-specifieke details. Deze details zijn bloederig en complex.

Uw opties:

• LLVM: maakt efficiënte machinecode-generatie mogelijk, meestal voor x86 en ARM.
• CLR : doelen .NET, multiplatform; heeft een goede JIT.
• JVM: richt zich op Java, redelijk multiplatform, heeft een goede JIT.

Negeer optimalisatie

Optimalisatie is moeilijk. Optimalisatie is bijna altijd voorbarig. Genereer inefficiënte maar correcte code. Implementeer de hele taal voordat u probeert de resulterende code te optimaliseren.

Natuurlijk zijn triviale optimalisaties oké om te introduceren. Maar vermijd sluwe, harige dingen voordat je compiler stabiel is.

En wat dan nog?

Als al deze dingen niet te intimiderend voor je zijn, ga dan verder! Voor een eenvoudige taal zijn alle stappen misschien eenvoudiger dan u misschien denkt.

Het is misschien de moeite waard om een “Hallo wereld” te zien van een programma dat uw compiler heeft gemaakt.

Opmerkingen

• Dit is een van de beste antwoorden die ik ‘ heb gezien.
• Ik denk dat je miste een deel van de vraag … Het OP wilde een zeer eenvoudige compiler schrijven. Ik denk dat je hier verder gaat dan heel basic.
• @ marco-fiset , integendeel, ik denk dat het ‘ is een uitstekend antwoord dat het OP vertelt hoe het een zeer eenvoudige compiler moet maken, terwijl het wijst op de valstrikken om te vermijden en meer geavanceerde fasen te definiëren.
• Dit is een van de beste antwoorden Ik heb het ooit gezien in het hele Stack Exchange-universum. Een pluim!
• Het zien van een ‘ Hallo wereld ‘ van een programma dat je compiler heeft gemaakt, is misschien de moeite waard. – INDEED

Jack Crenshaw “s Laten we een compiler bouwen , hoewel onvoltooid, is een uitstekend leesbare inleiding en tutorial.

Nicklaus Wirth “s Compilerconstructie is een zeer goed leerboek over de basisprincipes van eenvoudige compilerconstructie. Hij concentreert zich op top-down recursieve afdaling, wat, laten we eerlijk zijn, VEEL gemakkelijker is dan lex / yacc of flex / bison. De originele PASCAL-compiler die zijn groep schreef, werd op deze manier gedaan.

Andere mensen hebben de verschillende Dragon-boeken genoemd.

Opmerkingen

• Een van de leuke dingen van Pascal, is dat alles moet worden gedefinieerd of gedeclareerd voordat het wordt gebruikt. Daarom kan het in één keer worden samengesteld. Turbo Pascal 3.0 is zon voorbeeld, en er is hier veel documentatie over de internals.
• PASCAL is specifiek ontworpen met één pass compilatie en koppeling in gedachten. Wirth ‘ s compileerboek vermeldt multipass compilers, en voegt eraan toe dat hij een PL / I-compiler kende die 70 (ja, zeventig) passes had gemaakt.
• Verplichte declaratie voor gebruik dateert van ALGOL. Tony Hoare kreeg zijn oren naar achteren door de ALGOL-commissie toen hij probeerde voor te stellen om standaardregels toe te voegen, vergelijkbaar met wat FORTRAN had. Ze wisten al van de problemen die dit zou kunnen veroorzaken, met typografische fouten in namen en standaardregels die interessante bugs veroorzaken.
• Hier is een meer bijgewerkte en voltooide versie van het boek door de oorspronkelijke auteur zelf: stack.nl/~marcov/compiler.pdf Bewerk je antwoord en voeg dit toe 🙂

Als u echt alleen machinaal leesbare code wilt schrijven en niet gericht op een virtuele machine, dan moet u Intel-handleidingen lezen en begrijpen

• een. Uitvoerbare code koppelen en laden

• b. COFF- en PE-formaten (voor Windows), als alternatief ELF-formaat (voor Linux) begrijpen

• c. Begrijp .COM-bestandsindelingen (gemakkelijker dan PE)
• d. Begrijp assembleurs
• e. Begrijp compilers en code-generatie-engine in compilers.

Veel moeilijker gedaan dan gezegd. Ik raad je aan om Compilers en tolken in C ++ als uitgangspunt te lezen (door Ronald Mak). Als alternatief is “laten we een compiler bouwen” door Crenshaw OK.

Als je dat niet wilt doen, kun je net zo goed je eigen VM schrijven en een codegenerator schrijven die op die VM is gericht.

• Nog een startpunt: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Geweldig boek van Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Tips: leer eerst Flex en Bizon. Bouw dan je eigen compiler / VM.

Veel succes!

Reacties

• Ik denk dat ik me richt op LLVM en niet echte machinecode is ongeveer de beste manier die vandaag beschikbaar is.
• Ik ben het ermee eens, ik volg LLVM al een tijdje en ik zou moeten zeggen dat het een van de beste dingen was die ik in jaren had gezien in termen van programmeurinspanning nodig om het te targeten!
• Hoe zit het met MIPS en gebruik spim om het uit te voeren? Of MIX ?
• @MichaelT Ik heb MIPS niet gebruikt, maar ik weet zeker dat het goed zal zijn.
• @PrototypeStark RISC-instructieset, echte processor die nog steeds in gebruik is (begrijpend dat het vertaalbaar zal zijn naar ingebedde systemen). De volledige instructieset staat op wikipedia . Kijkend op het net zijn er veel voorbeelden en het wordt in veel academische klassen gebruikt als een doelwit voor het programmeren van machinetaal. Er is een beetje activiteit op SO .

Ik “zou eigenlijk beginnen met het schrijven van een compiler voor Brainfuck . Het is een nogal stompe taal om in te programmeren, maar het heeft alleen 8 instructies om te implementeren. Het is ongeveer zo eenvoudig als je maar kunt krijgen en er zijn gelijkwaardige C-instructies voor de betreffende commandos als je de syntaxis onaangenaam vindt.

Opmerkingen

• Maar als je eenmaal je BF-compiler klaar hebt, moet je je code erin schrijven 🙁
• @ 500-InternalServerError gebruik de C-subset-methode

DIY-aanpak voor een eenvoudige compiler zou er als volgt uit kunnen zien (zo zag mijn uni-project er tenminste uit):

1. Definieer de grammatica van de taal. Contextvrij.
2. Als je grammatica nog niet LL (1) is, doe het dan nu. Merk op dat sommige regels er goed uitzagen in gewone CF grammatica kan lelijk blijken. Misschien is uw taal te complex …
3. Schrijf Lexer die de tekststroom in tokens (woorden, cijfers, letterlijke letters) splitst.
4. Schrijf van boven naar beneden recursieve descent parser voor uw grammatica, die invoer accepteert of weigert.
5. Voeg syntaxisboomgeneratie toe aan uw parser.
6. Schrijf ma chine-codegenerator uit de syntaxisboom.
7. Profit & Bier, je kunt ook gaan nadenken over hoe je slimmere parser kunt doen of betere code kunt genereren.

Dat zou moeten zorg voor voldoende literatuur die elke stap in detail beschrijft.

Reacties

• Het 7e punt is waar OP naar vraagt.
• 1-5 zijn niet relevant en verdienen dat niet een goede aandacht. 6 is het meest interessante deel.Helaas volgen de meeste boeken hetzelfde patroon, na het beruchte drakenboek, waarbij teveel aandacht wordt besteed aan het ontleden en het buiten bereik laten van codetransformaties.