Jak napsat velmi základní překladač

Úvod

Typický kompilátor provede následující kroky:

• Analýza: zdrojový text je převeden na abstraktní syntaxový strom (AST).
• Rozlišení odkazů na jiné moduly (C tento krok odloží až do propojení).
• Sémantická validace: vyřazení syntakticky správných příkazů to nedává smysl, např nedosažitelný kód nebo duplicitní deklarace.
• Ekvivalentní transformace a optimalizace na vysoké úrovni: AST je transformován tak, aby představoval efektivnější výpočet se stejnou sémantikou. To zahrnuje např. včasný výpočet běžných dílčích výrazů a konstantních výrazů, eliminující nadměrné místní přiřazení (viz také SSA ) atd.
• Generování kódu: AST je transformovány do lineárního nízkoúrovňového kódu se skoky, přidělením registrů a podobně. Některá volání funkcí mohou být v této fázi inline, některá smyčky rozvinuta atd.
• Optimalizace kukátka: nízkoúrovňový kód je skenován kvůli jednoduché místní neefektivnosti, která je eliminována.

Většina moderních překladačů (například gcc a clang) opakuje poslední dva kroky ještě jednou. Pro počáteční generování kódu používají střední, ale na platformě nezávislý jazyk. Pak se tento jazyk převede na kód specifický pro platformu (x86, ARM atd.), Který zhruba stejným způsobem provede platformově optimalizovaný způsob. To zahrnuje např. použití vektorových instrukcí, pokud je to možné, přeskupení instrukcí ke zvýšení efektivity predikce větví atd.

Poté je objektový kód připraven k propojení. Většina překladačů nativního kódu ví, jak zavolat linkeru, aby vytvořil spustitelný soubor, ale není to kompilační krok sám o sobě. V jazycích, jako je Java a C #, může být propojení zcela dynamické, provádí jej VM v době načítání.

Pamatujte si základní

• Ať to funguje
• Ať je to krásné
• Zefektivnění

Tato klasická sekvence platí pro veškerý vývoj softwaru, ale nese se opakovaně.

Soustřeďte se na první krok sekvence. Vytvořte nejjednodušší věc, která by mohla fungovat.

Přečtěte si knihy!

Přečtěte si Dračí knihu od Aho a Ullmana. Je to klasické a dnes je docela dobře použitelné.

Moderní design kompilátoru .

Pokud je to pro vás právě teď příliš těžké, přečtěte si nejprve úvod do analýzy, obvykle parsování knihoven zahrňte úvod a příklady.

Ujistěte se, že vám práce s grafy, zejména stromy, vyhovuje. Jedná se o věci, ze kterých jsou vytvářeny programy na logické úrovni.

Definujte svůj jazyk dobře

Použijte jakýkoli zápis, který chcete, ale ujistěte se, že máte úplný a konzistentní popis svého Jazyk. To zahrnuje jak syntaxi, tak sémantiku.

Je nejvyšší čas napsat úryvky kódu ve vašem novém jazyce jako testovací případy pro budoucí kompilátor.

Použijte svůj oblíbený jazyk

Je naprosto v pořádku psát překladač v jazyce Python nebo Ruby nebo v jakémkoli jazyce, který je pro vás snadný.Použijte jednoduché algoritmy, kterým dobře rozumíte. První verze nemusí být rychlá, efektivní nebo úplná. Musí to být jen dostatečně správné a snadno upravitelné.

Je také v pořádku psát různé fáze kompilátoru v různých jazycích, pokud je to potřeba.

Připravte se psát hodně testů

Celý váš jazyk by měl být zahrnut do testovacích případů; ve skutečnosti to budou definovány . Seznamte se dobře s preferovaným testovacím rámcem. Testy pište od prvního dne. Soustřeďte se na „pozitivní“ testy, které přijímají správný kód, na rozdíl od detekce nesprávného kódu.

Pravidelně spusťte všechny testy. Než budete pokračovat, opravte poškozené testy. Byla by škoda skončit se špatným definovaný jazyk, který nemůže přijmout platný kód.

Vytvořte dobrý analyzátor

Generátorů analyzátorů je mnoho . Vyberte si cokoli chcete. Můžete také psát svůj vlastní parser od začátku, ale stojí to za to, pokud je syntaxe vašeho jazyka mrtvá jednoduchá.

Analyzátor by měl detekovat a hlásit syntaktické chyby. Napsat mnoho testovacích případů, pozitivních i negati ve; znovu použijte kód, který jste napsali při definování jazyka.

Výstupem vašeho syntaktického analyzátoru je abstraktní syntaxový strom.

Pokud váš jazyk obsahuje moduly, výstup syntaktického analyzátoru může být nejjednodušší reprezentací „objektového kódu“, který vygenerujete. Existuje spousta jednoduchých způsobů, jak vypsat strom do souboru a rychle ho načíst zpět.

Vytvořit sémantický validátor

Váš jazyk s největší pravděpodobností umožňuje syntakticky správné konstrukce, které mohou vytvářet v určitých kontextech nemá smysl. Příkladem je duplicitní deklarace stejné proměnné nebo předání parametru nesprávného typu. Validátor detekuje takové chyby při pohledu na strom.

Validátor také vyřeší odkazy na další moduly napsané ve vašem jazyce, načte tyto další moduly a použije je v procesu ověřování. Tento krok například zajistí, že počet parametrů předaných funkci z jiného modulu je správný.

Opět napište a spusťte spoustu testovacích případů. Triviální případy jsou při řešení problémů stejně nepostradatelné jako chytré a složité.

Generovat kód

Použijte nejjednodušší techniky, které znáte. Často je v pořádku přímo přeložit jazykovou konstrukci (například if) na lehce parametrizovanou šablonu kódu, na rozdíl od šablony HTML.

Znovu , ignorujte účinnost a soustřeďte se na správnost.

Zaměřte se na nízkoúrovňový virtuální počítač nezávislý na platformě

Předpokládám, že ignorujete věci na nízké úrovni, pokud vás příliš nezajímají hardwarové podrobnosti. Tyto podrobnosti jsou krvavé a složité.

Vaše možnosti:

• LLVM: umožňuje efektivní generování strojového kódu, obvykle pro x86 a ARM.
• CLR : cíle .NET, multiplatformní; má dobrý JIT.
• JVM: zaměřuje se na svět Javy, je docela multiplatformní, má dobrý JIT.

Ignorovat optimalizaci

Optimalizace je těžká. Optimalizace je téměř vždy předčasná. Vygenerujte neefektivní, ale správný kód. Než se pokusíte optimalizovat výsledný kód, implementujte celý jazyk.

Triviální optimalizace jsou samozřejmě v pořádku. Ale vyvarujte se jakýchkoli mazaných, chlupatých věcí, než bude kompilátor stabilní.

Tak co?

Pokud pro vás všechny tyto věci nejsou příliš zastrašující, pokračujte! U jednoduchého jazyka může být každý z těchto kroků jednodušší, než si myslíte.

Vidět „Hello world“ z programu, který vytvořil váš kompilátor, může stát za tu námahu.

Komentáře

• Toto je jedna z nejlepších odpovědí, jaké jsem zatím ‚ viděl.
• Myslím, že vy vynechal část otázky … OP chtěl napsat velmi základní kompilátor. Myslím, že tu jdeš nad rámec velmi jednoduchého.
• @ marco-fiset , naopak si myslím, že je vynikající odpověď, která OP řekne, jak udělat velmi základní překladač, a zároveň upozorní na pasti, kterým je třeba se vyhnout, a definuje pokročilejší fáze.
• Toto je jedna z nejlepších odpovědí Nikdy jsem neviděl v celém vesmíru Stack Exchange. Kudos!
• Vidět ‚ Hello world ‚ z programu, který vytvořil váš kompilátor, může stát za tu námahu. – NEDOSTATOČNÍ

Jack Crenshaw „s Nechť je „Sestavení kompilátoru , přestože je nedokončené, mimořádně čitelným úvodem a výukovým programem.

Pokud opravdu chcete psát pouze strojově čitelný kód, který není zaměřen na virtuální stroj, budete si muset přečíst manuály Intel a porozumět

• a. Propojení a načtení spustitelného kódu

• b. Formáty COFF a PE (pro Windows), alternativně pochopte formát ELF (pro Linux)

• c. Pochopte formáty souborů .COM (jednodušší než PE)
• d. Pochopte montéry
• e. Pochopte kompilátory a generátor kódu v kompilátorech.

Je to mnohem těžší, než bylo řečeno. Navrhuji, abyste si jako výchozí bod přečetli překladače a tlumočníky v jazyce C ++ (autor Ronald Mak). Alternativně je „umožňuje sestavit kompilátor“ od Crenshawa v pořádku.

Pokud to nechcete dělat, můžete také napsat svůj vlastní VM a napsat generátor kódu zaměřený na tento VM.

• Další výchozí bod: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• skvělá kniha Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Tipy: Naučte se PRVNÍ Flex a Bison. Pak pokračujte v sestavování vlastního kompilátoru / virtuálního počítače.

Hodně štěstí!

Komentáře

• Myslím, že cílení na LLVM a ne skutečný strojový kód představuje nejlepší způsob, jak je dnes k dispozici.
• Souhlasím, už nějakou dobu sleduji LLVM a měl bych říci, že to byla jedna z nejlepších věcí, které jsem za poslední roky viděl, co se týče programátorského úsilí je třeba to zacílit!
• A co MIPS a spustit jej pomocí spim ? Nebo MIX ?
• @MichaelT Nepoužíval jsem MIPS, ale jsem si jistý, že to bude dobré.
• @PrototypeStark RISC instrukční sada, procesor reálného světa, který se dnes ještě používá (pochopíme, že bude přeložitelný do vestavěných systémů). Celá sada pokynů je na wikipedia . Při pohledu na síť existuje spousta příkladů a používá se v mnoha akademických třídách jako cíl programování strojového jazyka. Na SO je trochu aktivity.

Já bych vlastně začal psát překladač pro Brainfuck . Programovat je to docela tupý jazyk, ale má pouze 8 pokynů k provedení. Je to asi tak jednoduché, jak jen můžete získat, a existují ekvivalentní pokyny C pro příslušné příkazy, pokud zjistíte, že je syntaxe mimo.

Komentáře

• Ale pak, jakmile budete mít připravený kompilátor BF, musíte do něj napsat svůj kód 🙁
• @ 500-InternalServerError použijte metodu podmnožiny C

DIY přístup pro jednoduchý překladač může vypadat takto (alespoň tak vypadal můj uni projekt):

1. Definujte gramatiku jazyka. Bezkontextový.
2. Pokud vaše gramatika ještě není LL (1), udělejte to hned. Všimněte si, že některá pravidla, která vypadala v jednoduchém CF dobře, gramatika se může ukázat ošklivá. Možná je váš jazyk příliš složitý …
3. Napište Lexer, který rozdělí proud textu na tokeny (slova, čísla, literály).
4. Pište shora dolů analyzátor rekurzivního sestupu pro vaši gramatiku, který přijímá nebo odmítá vstup.
5. Přidejte do syntaktického analyzátoru generování syntaxe.
6. Napište ma generátor čínského kódu ze stromu syntaxe.
7. Zisk & Pivo, případně můžete začít přemýšlet, jak udělat chytřejší analyzátor nebo vygenerovat lepší kód.

Mělo by mít spoustu literatury popisující každý krok podrobně.

Komentáře

• Sedmý bod je to, na co se OP ptá.
• 1-5 jsou irelevantní a nezaslouží si to velkou pozornost. 6 je nejzajímavější část.Bohužel většina knih se řídí stejným vzorem, po neslavné knize draků věnuje příliš velkou pozornost analýze a ponechání transformovaných kódů mimo rozsah.