Cum se scrie un compilator foarte simplu

Introducere

Un compilator tipic face următorii pași:

• Parsare: textul sursă este convertit într-un arbore de sintaxă abstract (AST).
• Rezoluția referințelor la alte module (C amână acest pas până la conectare).
• Validare semantică: eliminarea afirmațiilor corecte din punct de vedere sintactic care nu au sens, de ex cod inaccesibil sau declarații duplicat.
• Transformări echivalente și optimizare la nivel înalt: AST este transformat pentru a reprezenta un calcul mai eficient cu aceeași semantică. Aceasta include de ex. calcularea timpurie a subexpresiilor comune și a expresiilor constante, eliminarea atribuirilor locale excesive (vezi și SSA ) etc.
• Generarea codului: AST este transformat în cod liniar de nivel scăzut, cu salturi, alocarea registrului și altele asemenea. Unele apeluri de funcții pot fi inserate în această etapă, unele bucle derulate etc.
• Optimizare peephole: codul de nivel scăzut este scanat pentru a găsi ineficiențe locale simple care sunt eliminate.

Majoritatea compilatoarelor moderne (de exemplu, gcc și clang) repetă ultimii doi pași încă o dată. Folosesc un limbaj intermediar de nivel scăzut, dar independent de platformă, pentru generarea inițială de cod. Apoi, limba respectivă este convertită în cod specific platformei (x86, ARM, etc), făcând aproximativ același lucru într-un mod optimizat pentru platformă. Aceasta include de ex. utilizarea instrucțiunilor vectoriale atunci când este posibil, reordonarea instrucțiunilor pentru a crește eficiența predicției ramurilor și așa mai departe.

După aceea, codul obiect este gata pentru conectare. Majoritatea compilatoarelor de coduri native știu cum să apeleze un linker pentru a produce un executabil, dar nu este un pas de compilare în sine. În limbaje precum Java și C # link-ul poate fi complet dinamic, realizat de VM la timpul de încărcare.

Amintiți-vă noțiunile de bază

• Fă-l să funcționeze
• Fă-l frumos
• Fă-l eficient

Această secvență clasică se aplică tuturor dezvoltărilor de software, dar se repetă.

Concentrați-vă pe primul pas al secvenței. Creați cel mai simplu lucru care ar putea funcționa.

Citiți cărțile!

Citiți Dragon Book de Aho și Ullman. Aceasta este clasică și este încă destul de aplicabilă astăzi.

Designul modern al compilatorului este, de asemenea, lăudat.

Dacă acest lucru este prea greu pentru dvs. în acest moment, citiți mai întâi câteva informații despre analiză; includeți prezentări și exemple.

Asigurați-vă că vă simțiți bine să lucrați cu grafice, în special cu arbori. Aceste lucruri sunt din programele logice.

Definiți bine limba

Utilizați orice notație doriți, dar asigurați-vă că aveți o descriere completă și consecventă a limba. Aceasta include atât sintaxa, cât și semantica.

Este timpul să scrieți fragmente de cod în noua limbă ca cazuri de testare pentru viitorul compilator.

Utilizați limba preferată

Este complet OK să scrieți un compilator în Python sau Ruby sau orice altă limbă vă este ușoară.Folosiți algoritmi simpli pe care îi înțelegeți bine. Prima versiune nu trebuie să fie rapidă, eficientă sau completă. Trebuie doar să fie suficient de corect și ușor de modificat.

De asemenea, este OK să scrieți diferite etape ale unui compilator în diferite limbi, dacă este necesar.

Pregătiți-vă să scrieți multe de teste

Întreaga limbă ar trebui să fie acoperită de cazuri de testare; efectiv va fi definită de către aceștia. Familiarizați-vă cu cadrul de testare preferat. Scrieți teste din prima zi. Concentrați-vă pe testele „pozitive” care acceptă codul corect, spre deosebire de detectarea unui cod incorect.

Rulați toate testele în mod regulat. Remediați testele întrerupte înainte de a continua. Ar fi păcat să sfârșiți cu o problemă limbaj definit care nu poate accepta cod valid.

Creați un analizor bun

Generatorii de analizori sunt mulți . Alegeți orice Puteți, de asemenea, să vă scrieți propriul analizor de la zero, dar merită doar dacă sintaxa limbii dvs. este mort simplă.

Analizatorul ar trebui să detecteze și să raporteze erori de sintaxă. Scrieți o mulțime de cazuri de testare, atât pozitive, cât și negative ve; refolosiți codul pe care l-ați scris în timp ce definiți limba.

Ieșirea analizorului dvs. este un arbore de sintaxă abstract.

Dacă limba dvs. are module, ieșirea analizorului poate fi cea mai simplă reprezentare de „cod obiect” pe care îl generați. Există o mulțime de modalități simple de a arunca un copac într-un fișier și de a-l încărca rapid înapoi.

Creați un validator semantic

Cel mai probabil, limba dvs. permite construcții corecte din punct de vedere sintactic care pot face fără sens în anumite contexte. Un exemplu este o declarație duplicat a aceleiași variabile sau trecerea unui parametru de tip greșit. Validatorul va detecta astfel de erori privind arborele.

Validatorul va rezolva, de asemenea, referințele la alte module scrise în limba dvs., va încărca aceste alte module și le va utiliza în procesul de validare. De exemplu, acest pas se va asigura că numărul de parametri trecuți unei funcții dintr-un alt modul este corect.

Din nou, scrieți și executați o mulțime de cazuri de testare. Cazurile banale sunt la fel de indispensabile la depanare ca inteligente și complexe.

Generați cod

Utilizați cele mai simple tehnici pe care le cunoașteți. Adesea este bine să traduceți direct un construct de limbă (cum ar fi o instrucțiune if) într-un șablon de cod ușor parametrizat, nu diferit de un șablon HTML.

Din nou , ignorați eficiența și concentrați-vă pe corectitudine.

Vizați o mașină virtuală de nivel scăzut independentă de platformă

Presupun că ignorați lucrurile de nivel scăzut, cu excepția cazului în care sunteți „foarte interesat de hardware-specific Detalii. Aceste detalii sunt sângeroase și complexe.

Opțiunile dvs.:

• LLVM: permite generarea eficientă a codului mașinii, de obicei pentru x86 și ARM.
• CLR : țintește .NET, multiplatform; are un JIT bun.
• JVM: vizează lumea Java, destul de multiplatformă, are un JIT bun.

Ignorați optimizarea

Optimizarea este dificilă. Aproape întotdeauna optimizarea este prematură. Generați cod ineficient, dar corect. Implementați întreaga limbă înainte de a încerca să optimizați codul rezultat.

Desigur, optimizările banale sunt OK de introdus. Dar evitați orice lucruri viclene și păroase înainte ca compilatorul dvs. să fie stabil.

Deci, ce?

Dacă toate aceste lucruri nu vă sunt prea intimidante, vă rugăm să continuați! Pentru un limbaj simplu, fiecare dintre pași poate fi mai simplu decât ați putea crede.

Vederea unei „Hello world” dintr-un program creat de compilatorul dvs. ar putea merita efortul.

Comentarii

• Acesta este unul dintre cele mai bune răspunsuri pe care le-am văzut încă. ‘.
• Cred că a ratat o parte din întrebare … OP a dorit să scrie un compilator foarte de bază . Cred că treci dincolo de foarte simplu aici.
• @ marco-fiset , dimpotrivă, cred că ‘ este un răspuns remarcabil care spune OP-ului cum să facă un compilator foarte de bază, indicând în același timp capcanele de evitat și definind faze mai avansate.
• Acesta este unul dintre cele mai bune răspunsuri Am văzut vreodată în întregul univers Stack Exchange. Salutări!
• Vederea unui ‘ Hello world ‘ dintr-un program creat de compilatorul dvs. ar putea merita efortul. – INDEED

Jack Crenshaw „s Să construim un compilator , deși neterminat, este o introducere și un tutorial eminamente lizibil.

Nicklaus Wirth „s Construcția compilatorului este un manual foarte bun despre elementele de bază ale construcției simple a compilatorului. El se concentrează pe coborârea recursivă de sus în jos, care, să recunoaștem, este mult mai ușor decât lex / yacc sau flex / bizon. Compilatorul original PASCAL scris de grupul său a fost realizat în acest fel.

Alți oameni au menționat diferitele cărți Dragon.

Comentarii

• Unul dintre lucrurile frumoase despre Pascal este că totul trebuie definit sau declarat înainte de a fi folosit. Prin urmare, poate fi compilat într-o singură trecere. Turbo Pascal 3.0 este un astfel de exemplu și există o mulțime de documentație despre elementele interne aici .
• PASCAL a fost conceput special cu un treceți în minte compilarea și conectarea. Cartea compilatorului Wirth ‘ menționează compilatoarele multipass și adaugă că știa despre un compilator PL / I care a luat 70 (da, șaptezeci) de treceri.
• Declarație obligatorie înainte de utilizare datează din ALGOL. Tony Hoare și-a prins urechile de comitetul ALGOL când a încercat să sugereze adăugarea unor reguli de tip implicite, similar cu ceea ce avea FORTRAN. Știau deja despre problemele pe care aceasta le-ar putea crea, cu erori tipografice în nume și reguli implicite care creează erori interesante.
• Iată o versiune mai actualizată și mai finalizată a cărții de către autorul original însuși: stack.nl/~marcov/compiler.pdf Vă rugăm să modificați răspunsul și să adăugați acest lucru 🙂

Dacă într-adevăr doriți să scrieți numai cod care poate fi citit de mașină și nu este direcționat către o mașină virtuală, va trebui să citiți manualele Intel și să înțelegeți

• a. Conectarea și încărcarea codului executabil

• b. Formatele COFF și PE (pentru Windows), înțeleg alternativ formatul ELF (pentru Linux)

• c. Înțelegeți formatele de fișiere .COM (mai ușor decât PE)
• d. Înțelegeți asamblatorii
• e. Înțelegeți compilatoarele și motorul de generare a codului în compilatoare.

Făcut mult mai greu decât s-a spus. Vă sugerez să citiți Compilatori și Interpreti în C ++ ca punct de plecare (De Ronald Mak). În mod alternativ, „Lets build a compiler” de Crenshaw este în regulă.

Dacă nu doriți să faceți acest lucru, puteți scrie și propria VM și puteți scrie un generator de cod direcționat către VM respectivă.

• Un alt punct de plecare: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Great Book By Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Sfaturi: Aflați mai întâi Flex și Bison. Apoi continuați să creați propriul compilator / VM.

Noroc!

Comentarii

• Cred că vizează LLVM și nu codul real al mașinii este cel mai bun mod disponibil astăzi.
• Sunt de acord, urmăresc LLVM de ceva vreme și ar trebui să spun că a fost unul dintre cele mai bune lucruri pe care le-am văzut în ani în ceea ce privește efortul programatorului. trebuie să-l vizați!
• Dar MIPS și folosiți spim pentru a-l rula? Sau MIX ?
• @MichaelT Nu am folosit MIPS, dar sunt sigur că va fi bun.
• Set de instrucțiuni @PrototypeStark RISC, procesor din lumea reală care este încă în uz astăzi (înțelegând că va fi tradus în sisteme încorporate). Setul complet de instrucțiuni este la wikipedia . Privind pe net, există o mulțime de exemple și este folosit în multe clase academice ca țintă pentru programarea limbajului automat. Există un pic de activitate la SO .

Aș începe să scriu un compilator pentru Brainfuck . Este un limbaj destul de obtuz în care să programezi, dar are doar 8 instrucțiuni de implementat. Este „la fel de simplu pe cât puteți obține și există instrucțiuni C echivalente pentru comenzile implicate dacă găsiți că sintaxa deviază.

Comentarii

• Dar apoi, după ce aveți compilatorul BF gata, trebuie să scrieți codul în acesta 🙁
• @ 500-InternalServerError utilizați metoda subsetului C

Abordarea DIY pentru un compilator simplu ar putea arăta astfel (cel puțin așa arăta proiectul meu uni):

1. Definiți gramatica limbii. Fără context.
2. Dacă gramatica dvs. nu este încă LL (1), faceți-o acum. Rețineți că unele reguli care arătau ok în CF simplu gramatica poate deveni urâtă. Poate că limba dvs. este prea complexă …
3. Scrieți Lexer care taie fluxul de text în jetoane (cuvinte, numere, litere).
4. Scrieți de sus în jos analizor recursiv descendent pentru gramatica dvs., care acceptă sau respinge intrarea.
5. Adăugați generarea arborelui de sintaxă în analizorul dvs.
6. Scrieți ma generator de cod chine din arborele de sintaxă.
7. Profitați de & bere, sau puteți începe să vă gândiți cum să faceți un analizor mai inteligent sau să generați un cod mai bun.

să fie o mulțime de literatură care descrie fiecare pas în detaliu.

Comentarii

• Punctul 7 este ceea ce OP cere.
• 1-5 sunt irelevante și nu merită astfel o atentie stransa. 6 este partea cea mai interesantă.Din păcate, majoritatea cărților urmează același model, după infama carte a dragonului, acordând prea multă atenție analizei și lăsând transformarea codului în afara sferei de aplicare.