Hyvin yksinkertaisen kääntäjän kirjoittaminen

johdanto

Tyypillinen kääntäjä suorittaa seuraavat vaiheet:

• jäsentäminen: lähdeteksti muunnetaan abstraktiksi syntaksipuuksi (AST).
• Viittausten tarkkuus muihin moduuleihin (C lykkää tätä vaihetta linkittämiseen).
• Semanttinen vahvistus: syntaktisesti oikeiden lauseiden kitkeminen joilla ei ole mitään järkeä, esim saavuttamaton koodi tai kaksoisilmoitukset.
• Vastaavat muunnokset ja korkean tason optimointi: AST muunnetaan edustamaan tehokkaampaa laskentaa samalla semantiikalla. Tähän sisältyy mm. yleisten alilausekkeiden ja vakiolausekkeiden varhainen laskeminen, poistamalla liialliset paikalliset määritykset (katso myös SSA ) jne.
• Koodin luonti: AST on muunnetaan lineaariseksi matalan tason koodiksi hyppyillä, rekisterin allokoinnilla ja vastaavilla. Joitakin toimintokutsuja voidaan linjata tässä vaiheessa, joitain silmukoita voi purkaa jne.
• Silmukan optimointi: matalan tason koodi tarkistetaan yksinkertaisten paikallisten tehottomuuksien varalta, jotka eliminoidaan.

Useimmat nykyaikaiset kääntäjät (esimerkiksi gcc ja clang) toistavat kaksi viimeistä vaihetta vielä kerran. He käyttävät välitöntä matalan tason mutta alustasta riippumatonta kieltä alkukoodien luomiseen. Sitten kyseinen kieli muunnetaan alustakohtaiseksi koodiksi (x86, ARM jne.), Mikä tekee suunnilleen saman asian alustalle optimoidulla tavalla. Tähän sisältyy mm. vektoriohjeiden käyttö mahdollisuuksien mukaan, käskyjen uudelleenjärjestäminen haaraennusteiden tehokkuuden lisäämiseksi ja niin edelleen.

Sen jälkeen objektikoodi on valmis linkittämiseen. Useimmat natiivikoodin kääntäjät tietävät, kuinka linkkerille voidaan soittaa suoritettavan tiedoston tuottamiseksi, mutta se ei ole käännösvaihe sinänsä. Java- ja C # -linkit voivat olla täysin dynaamisia, virtuaalikoneen tekemät lataushetkellä.

Muista perusasiat

• Tee se toimivaksi
• Tee kauniista
• Tehosta siitä tehokasta

Tämä klassinen järjestys koskee kaikkea ohjelmistokehitystä, mutta sillä on toistoja.

Keskity jakson ensimmäiseen vaiheeseen. Luo yksinkertaisin asia, joka mahdollisesti toimii.

Lue kirjat!

Lue Ahon ja Ullmanin Lohikäärmekirja . Tämä on klassinen ja soveltuu edelleen nykyäänkin.

Moderni kääntäjän suunnittelu on myös ylistetty.

Jos nämä asiat ovat sinulle nyt liian vaikeita, lue ensin jäsentämisen introja; yleensä jäsennetään kirjastoja sisältää introja ja esimerkkejä.

Varmista, että työskentelet mukavasti kaavioiden, etenkin puiden, kanssa. Näistä asioista ohjelmat on tehty loogisella tasolla.

Määritä kielesi hyvin

Käytä mitä tahansa merkintää, mutta varmista, että sinulla on täydellinen ja johdonmukainen kuvaus Kieli. Tämä sisältää sekä syntaksin että semantiikan.

On korkea aika kirjoittaa koodinpätkät uudella kielellä testitapauksina tulevalle kääntäjälle.

Käytä suosikkikieliäsi

Kääntäjän kirjoittaminen Python- tai Ruby-kielellä tai millä tahansa kielellä on sinulle helppoa.Käytä yksinkertaisia algoritmeja, jotka ymmärrät hyvin. Ensimmäisen version ei tarvitse olla nopea, tehokas tai ominaisuuksien täydellinen. Sen on oltava vain riittävän oikea ja helppo muokata.

On myös OK kirjoittaa kääntäjän eri vaiheita tarvittaessa eri kielillä.

Valmistaudu kirjoittamaan paljon testeistä

Testitapausten tulisi kattaa koko kielesi; käytännössä ne määrittävät sen. Opi tuntemaan haluamasi testauskehys. Kirjoita testit alusta alkaen. Keskity ”positiivisiin” testeihin, jotka hyväksyvät oikean koodin, toisin kuin virheellisen koodin havaitseminen.

Suorita kaikki testit säännöllisesti. Korjaa rikkoutuneet testit ennen jatkamista. Olisi häpeä päätyä virheelliseen määritetty kieli, joka ei hyväksy kelvollista koodia.

Luo hyvä jäsennin

Parser-generaattoreita on monia . Valitse mitä haluat Haluat myös kirjoittaa oman jäsentimen tyhjästä, mutta se on sen arvoista vain, jos kielesi syntaksit ovat kuolleet yksinkertaiset.

Jäsentäjän tulisi tunnistaa syntaksivirheet ja ilmoittaa niistä. paljon testitapauksia, sekä positiivisia että negatiivisia ve; käytä kirjoittamaasi koodia uudelleen määritellessäsi kieltä.

Parserin tulos on abstrakti syntaksipuu.

Jos kielelläsi on moduuleja, jäsentimen tulos voi olla yksinkertaisin esitys. luomastasi ”objektikoodista”. On paljon yksinkertaisia tapoja pudottaa puu tiedostoon ja ladata se nopeasti takaisin.

Luo semanttinen vahvistaja

Todennäköisesti kielesi sallii syntaktisesti oikeat rakenteet, jotka saattavat tehdä ei ole mitään järkeä tietyissä yhteyksissä. Esimerkki on saman muuttujan kaksoisilmoitus tai väärän tyyppisen parametrin välittäminen. Vahvistin havaitsee tällaiset virheet katsellen puuta.

Validointilaite ratkaisee myös viittaukset muihin kielelläsi kirjoitettuihin moduuleihin, lataa nämä muut moduulit ja käyttää niitä validointiprosessissa. Esimerkiksi tässä vaiheessa varmistetaan, että toisesta moduulista funktiolle siirrettyjen parametrien määrä on oikea.

Kirjoita ja suorita uudelleen paljon testitapauksia. Triviaalitapaukset ovat yhtä välttämättömiä vianmäärityksessä kuin älykkäät ja monimutkaiset.

Luo koodi

Käytä yksinkertaisia tekniikoita, joita tiedät. Usein on hyvä kääntää kielirakenne (kuten if -lauseke) kevyesti parametrisoituun koodimalliin, toisin kuin HTML-malli.

Jälleen , sivuuttaa tehokkuus ja keskittyä oikeellisuuteen.

Kohdista alustasta riippumattomaan matalan tason virtuaalikoneeseen

Oletan, että ohitat matalan tason jutut, ellet ole kovin kiinnostunut laitteistokohtaisista yksityiskohdat. Nämä yksityiskohdat ovat ankaria ja monimutkaisia.

Vaihtoehdot:

• LLVM: mahdollistaa tehokkaan konekoodin luomisen, yleensä x86: lle ja ARM: lle.
• CLR : kohteet .NET, monialustainen; on hyvä JIT.
• JVM: kohdistaa Java-maailmaan, melko monitasoinen, on hyvä JIT.

Ohita optimointi

Optimointi on vaikeaa. Optimointi on melkein aina ennenaikaista. Luo tehoton, mutta oikea koodi. Ota koko kieli käyttöön ennen kuin yrität optimoida tuloksena olevan koodin.

Pienetkin optimoinnit ovat tietysti esiteltävissä. Mutta vältä ovelaa, karvaa tavaraa, ennen kuin kääntäjäsi on vakaa.

Joten mitä?

Jos kaikki nämä asiat eivät ole sinulle liian pelottavia, jatka! Yksinkertaisella kielellä jokainen vaihe voi olla yksinkertaisempi kuin luulisi.

”Hello world” -palvelun näkeminen kääntäjän luomasta ohjelmasta saattaa olla vaivan arvoista.

Kommentit

• Tämä on yksi parhaista vastauksista, joita olen ’ vielä nähnyt.
• Luulen, että sinä jäi osaksi kysymystä … OP halusi kirjoittaa hyvin yksinkertaisen kääntäjän. Luulen, että ylität tässä hyvin perustavanlaatuisen.
• @ marco-fiset , päinvastoin, mielestäni se on ’ on erinomainen vastaus, joka kertoo OP: lle, kuinka tehdä erittäin yksinkertainen kääntäjä, samalla kun se osoittaa ansat välttämiseksi ja määrittelee edistyneemmät vaiheet.
• Tämä on yksi parhaista vastauksista Olen koskaan nähnyt koko Stack Exchange -universumissa. Kiitos!
• ’ Hei maailma ’ -sivuston näkeminen kääntäjän luomasta ohjelmasta saattaa olla vaivan arvoista. – Sisäänrakennettu

Jack Crenshaw ”s Let s Build a Compiler on keskeneräinen, mutta on selvästi luettavissa oleva esittely ja opetusohjelma.

Nicklaus Wirth ”s Compiler Construction on erittäin hyvä oppikirja yksinkertaisen kääntäjän rakentamisen perusteista. Hän keskittyy ylhäältä alaspäin rekursiiviseen laskeutumiseen, joka on tosiasiallisesti paljon helpompaa kuin lex / yacc tai flex / bison. Hänen ryhmänsä kirjoittama alkuperäinen PASCAL-kääntäjä tehtiin tällä tavalla.

Muut ihmiset ovat maininneet Dragon-kirjat.

Kommentit

• Yksi Pascalin hienoista asioista on, että kaikki on määriteltävä tai ilmoitettava ennen käyttöä. Siksi se voidaan koota yhdellä kertaa. Turbo Pascal 3.0 on yksi tällainen esimerkki, ja sisäosista on paljon dokumentaatiota täällä .
• PASCAL on suunniteltu erityisesti yhden läpäise kokoaminen ja linkittäminen mielessä. Wirth ’ -sivuston kääntäjäkirjassa mainitaan monilähetyskääntäjät ja lisätään, että hän tiesi PL / I-kääntäjän, joka otti 70 (kyllä, seitsemänkymmentä) läpäisyä.
• Pakollinen ilmoitus ennen käyttöä on peräisin ALGOLista. Tony Hoare sai korvansa kiinni ALGOL-komitealta, kun hän yritti ehdottaa oletustyyppisten sääntöjen lisäämistä, samanlaisia kuin FORTRANilla. He tiesivät jo ongelmista, joita tämä saattoi aiheuttaa, nimien typografiset virheet ja oletussäännöt luovat mielenkiintoisia virheitä.
• Tässä on alkuperäisen kirjoittajan itse päivitetympi ja viimeistelty versio kirjasta: stack.nl/~marcov/compiler.pdf Muokkaa vastaustasi ja lisää tämä 🙂

Jos haluat todella kirjoittaa vain koneella luettavan koodin eikä kohdistaa virtuaalikoneeseen, sinun on luettava Intelin käyttöohjeet ja ymmärrettävä

• a. Suoritettavan koodin linkittäminen ja lataaminen

• b. COFF- ja PE-muodot (Windows), vaihtoehtoisesti ymmärrä ELF-muoto (Linux)

• c. Ymmärrä .COM-tiedostomuodot (helpompaa kuin PE)
• d. Ymmärrä kokoonpanijat
• e. Ymmärrä kääntäjät ja koodinmuokkausohjelma kääntäjissä.

Paljon vaikeampaa kuin sanottu. Ehdotan, että luet lähtökohtana kääntäjät ja tulkit C ++: ssa (kirjoittanut Ronald Mak). Vaihtoehtoisesti Crenshaw ”antaa rakentaa kääntäjän” on kunnossa.

Jos et halua tehdä niin, voit myös kirjoittaa oman virtuaalikoneesi ja kirjoittaa kyseiselle virtuaalikoneelle kohdistetun koodigeneraattorin.

• Toinen lähtökohta: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Hyvä kirja Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Vinkkejä: Opi Flex ja Bison ENSIN. Rakenna sitten oma kääntäjä / virtuaalikone.

Onnea!

Kommentit

• Mielestäni kohdistan LLVM: ään eikä todellinen konekoodi on paras tapa saada tänään.
• Olen samaa mieltä, olen seurannut LLVM: ää jo jonkin aikaa ja minun pitäisi sanoa, että se oli yksi parhaimmista asioista, joita olin nähnyt vuosien ajan ohjelmoijan ponnisteluissa tarvitaan kohdentamiseen!
• Entä MIPS ja käytä spim sen suorittamiseen? Tai MIX ?
• @MichaelT En ole käyttänyt MIPS: ää, mutta olen varma, että se on hyvä.
• @PrototypeStark RISC-käskysarja, reaalimaailman prosessori, joka on edelleen käytössä tänään (ymmärtämällä, että se voidaan kääntää sulautettuihin järjestelmiin). Koko ohjeisto on wikipediassa . Verkosta katsottuna on paljon esimerkkejä, ja sitä käytetään monissa akateemisissa luokissa konekielen ohjelmoinnin kohteena. Siellä on vähän aktiivisuutta SO .

Yksinkertaisen kääntäjän DIY-lähestymistapa voi näyttää tältä (ainakin miltä uni-projektini näytti):

1. Määritä kielioppi. Kontekstiton.
2. Jos kielioppi ei ole vielä LL (1), tee se nyt. Huomaa, että jotkut säännöt, jotka näyttivät ok tavallisella CF: llä kielioppi voi osoittautua ruma. Ehkä kielesi on liian monimutkainen …
3. Kirjoita Lexer, joka leikkaa tekstivirran rahakkeiksi (sanat, numerot, literaalit).
4. Kirjoita ylhäältä alas kieliopisi rekursiivinen laskeutumisen jäsennin, joka hyväksyy tai hylkää syötteen.
5. Lisää syntaksipuun luominen jäsentäjääsi.
6. Kirjoita ma chine-koodigeneraattori syntaksipuussa.
7. Voitto & Olut, vaihtoehtoisesti voit alkaa miettiä, miten tehdä älykkäämpi jäsennin tai luoda parempi koodi.

Siellä pitäisi olla olla runsaasti kirjallisuutta, joka kuvaa jokaista vaihetta yksityiskohtaisesti.

kommentit

• OP kysyy 7. kohtaa.
• 1–5 eivät ole merkityksellisiä eivätkä ansaitse tällaisia tarkkaa huomiota. 6 on mielenkiintoisin osa.Valitettavasti suurin osa kirjoista noudattaa samaa mallia surullisen lohikäärmekirjan jälkeen kiinnittäen liikaa huomiota jäsentämiseen ja koodimuunnosten jättämiseen soveltamisalan ulkopuolelle.