Synopsis
Når vi benytter programmeringssprog i dagligdagen, tænker man sjældent over hvad det er, der compiler programkode som mennesker forstår, til maskinkode som maskinen forstår. Endvidere kan det være abstrakt at tænke på, at compilere faktisk er programmer selv. Men hvordan compiler man en compiler? Og hvordan kan compilere til sprog som C, selv være skrevet i C? Det lyder lige så svært som at hive sig selv op i håret, eller som det hedder på engelsk: "To pull oneself up by the bootstraps."
Om terminologi og notation
På dansk kalder man en compiler for en 'oversætter'. Jeg foretrækker at fordanske det engelske udtryk, men vil give denne artikel et mindre monotomt sprogbrug ved at omtale en compilers funktion for en oversættelse. For eksempel: "Compileren oversætter sprog A til B".
For at gøre beskrivelserne mere læsevenlige, vil jeg benytte mig af en tilfældig bestemt notation.
Hvis en compiler er skrevet i sproget A, og oversætter sproget B til sproget C, på en maskinarkitektur D, vil notationen være:
[D]A(B -> C) eller et "real world" eksempel: [Intel]C(C -> MIPS Assembler)
Introduktion
For at gøre det nemmere at overskue, skal man tænke sig til, at en compiler, godt kan skrives PÅ en arkitektur, som den ikke er tiltænkt TIL.
Man skal tænke på det i tre dele: Compileren skal oversætte fra et sprog, til et sprog, samt skrives i et sprog. I dette tilfælde kan to af disse sprog rent faktisk godt være ens, hvilket for eksempel gør sig gældende for C's compiler, der både oversætter fra C, til maskinkode, og er skrevet i C.
Tager man udgangspunkt i, at du har en processorarkitektur for hvilken der ikke eksisterer nogen compiler, er den åbenlyse løsning at man laver en compiler der oversætter fra sprog 'A', til sprog 'B', og som så er skrevet i sprog 'B'. Men hvis arkitekturen er helt ny, må sprog 'B' om nødvendigt være maskinkode, og at skrive en compiler i maskinkode kan være en kedelig affære. I stedet, kan der gøres det man kalder 'bootstrapping': Man skriver en compiler i sproget 'A', som skal lave det om til sproget 'B', og lader så compileren, compile sig selv. Resultatet er en compiler der oversætter fra A til B, skrevet i B.
At compile en compiler
Basalt set er intentionen med bootstrapping, at der bruges en compiler til at oversætte sig selv eller andre compilere. Til denne proces er det nødvendigt som udgangspunkt at have en maskine til at køre compileren på. Ofte er det tilfældet, at der allerede eksisterer en compiler til et bestemt programmeringssprog, men ikke til den ønskede arkitektur.
Lad os antage at vi ønsker en compiler der oversætter sproget ML til Pentium maskinkode, og vil have den til rent faktisk at kunne eksekveres på en Pentium. Vi har i forvejen adgang til en ML-compiler som genererer HP-RISC maskinkode og kan køre på en HP maskine, som vi også har adgang til.
En måde at udvikle den ønskede compiler på, er at lave en 'binær oversættelse', hvilket vil sige at man skriver en compiler der oversætter fra HP maskinkode, til Pentium maskinkode.
Bemærk at detaljen er her, at det oversatte produkt nu er en compiler i sig selv.
Dette vil give den nyligt genererede compiler mulighed for at køre på en Pentium arkitektur, men den vil stadig generere HP-kode. Vi kan løse dette problem med HP-til-Pentium compileren til at oversætte denne HP-kode til Pentium-kode. Dette har dog flere problemer:
- At tilføje et ekstra led til processen koster tid.
- Effektivitet vil gå tabt
- Vi mangler stadig at få HP-til-Pentium compileren til at køre på Pentium maskinen.
En bedre metode er at skrive compileren, der skal oversætte ML til Pentium maskinkode, i ML. Vi kan bruge ML-til-HP compileren til at oversætte dette:
ML(ML -> Pentium) -> [HP]HP(ML -> HP) -> HP(ML -> Pentium)
Hernæst kan man bruge ML-til-Pentium compileren og lade den compile sig selv:
ML(ML -> Pentium) -> [HP]HP(ML -> Pentium) -> Pentium(ML -> Pentium)
Den ønskede compiler er hermed en realitet. Denne compiler kan nu blive brugt til at oversætte sig selv på en Pentium arkitektur, hvilket kan være nyttigt hvis compileren senere bliver udvidet.
Fuld bootstrap
Ovenstående eksempel kan kun lykkes, hvis man allerede har en eksisterende compiler der oversætter fra det ønskede sprog (ML-til-HP compileren). Det bliver derfor også kaldt for en 'halv bootstrapping'. Hvis der ikke eksisterer en compiler i forvejen, hvilket for eksempel er tilfældet når man opfinder et nyt programmeringssprog, bliver man nødt til at benytte sig af en lidt mere indviklet procedure, kaldet 'fuld bootstrapping'.
En anvendt metode er at skrive en QAD (Quick and Dirty)-compiler, ved hjælp af et eksisterende programmeringssprog. Denne compiler behøver ikke nødvendigvis at generere maskinkode der virker på den arkitektur den er tiltænkt til, og behøver heller ikke at generere 'god' (optimeret) kode. Det vigtige er kun at den kan oversætte et program skrevet i det nye sprog, som kan eksekveres. Dernæst vil den 'rigtige' compiler blive skrevet i det nye programmeringssprog og bootstrappet ved brug af QAD compileren.
Lad os antage at vi vil lave et nyt programmeringssprog som kaldes 'M+'. Vi skriver så en compiler der kan oversætte M+ kode til ML kode, skrevet i ML. Det første skridt er at få oversat dette, så det kan køre på en eller anden maskine, for eksempel en HP arkitektur.
ML(M+ -> ML) -> [HP]HP(ML -> HP) -> HP(M+ -> ML)
QAD-compileren kan så bruges til at oversætte den 'rigtige' compiler:
M+(M+ -> HP) -> [HP]HP(M+ -> ML) -> ML(M+ -> HP)
Resultatet er så et ML program som skal oversættes:
ML(M+ -> HP) -> [HP]HP(ML -> HP) -> HP(M+ -> HP)
Dette giver en compiler med den ønskede funktionalitet, der dog vil køre langsomt. Grunden til det er, at den er blevet oversat ved hjælp af QAD-compileren (sammen med ML-compileren), og et bedre resultat vil opnås hvis man lader den nyligt genererede compiler, oversætte sig selv:
M+(M+ -> HP) [HP]HP(M+ -> HP) -> HP(M+ -> HP)
Dette vil generere en compiler med fuldstændig samme funktionalitet som den oven over, men siden den 'rigtige' compiler bliver benyttet til at oversætte, vil den køre hurtigere.
Bootstrapping i trin
Det er yderligere muligt at bygge sit nye programmeringssprog og den tilhørende compiler op i trin. Det første trin ville være at skrive en compiler for en lille del af sit sprog, ved kun at bruge den samme lille del til at skrive compileren. Denne compiler skal så bootstrappes på en af de tidligere beskrevne metoder, men man kan derefter benytte en gentagelsesmetode:
- Udvid sproget en smule
- Udvid compileren så den oversætter den udvidede delmængde af sproget, uden at bruge disse selv.
- Brug den tidligere compiler til at oversætte den nye.
Ved hvert trin, kan de delmængder af programmet der blev introduceret i det foregående trin, bruges i compileren. Selv når hele compileren er færdig, kan man bruge denne fremgangsmåde til at hæve kvaliteten af compileren.
Videre læsning
"Basics of Compiler Design", skevet af Torben Æ. Mogensen.
http://en.wikipedia.org/ (...)(compilers)
