Kompilator

En kompilator er et dataprogram som oversetter – kompilerer – et dataprogram skrevet i et programmeringsspråk (kalt kildekode) til et kjørbart program (maskinkode). Dette kan sammenlignes med å være tolk for to personer som snakker forskjellig språk; tolken oversetter det den ene sier, slik at den andre personen klarer å dra nytte av – dvs. forstå – informasjonen.

Oppbygningen av en kompilator

Det er vanlig å dele moderne kompilatorer inn i tre hovedkomponenter eller stadier, som hver utfører et sett med oppgaver. Disse er «front-end», «middle-end» eller optimaliseringsstadiet, og «back-end». I praksis er ikke inndelingen fullt så enkel, men dette hovedprinsippet gjør det lettere å kombinere de ulike delene fritt, slik at man kan gjenbruke deler for ulike språk. For eksempel kan man bruke den samme backenden for ulike kildespråk.

Noen av de vanligste oppgavene som gjennomføres av de ulike delene er:

1. Frontend
   • Skanning (innlesing av programmet)
   • Parsing (tolking av programkoden)
   • Typesjekking
   • Binding
2. Optimaliseringsstadiet
   • Analyser
   • Optimaliseringer
   • Transformasjoner
3. Backend
   • Instruksjonsvalg
   • Registerallokering
   • Bestemme rekkefølgen av instruksjoner

Frontendens oppgave er å forstå programkoden ^:s6. Med andre ord analyseres programkodens riktighet i forhold til programmeringsspråkets spesifikasjon. Det første steget i denne prosessen er leksikalsk analyse eller skanning. Programmet leses inn i form av en tekstbasert fil, og skanneren setter sammen enkelttegn til ord, gjerne omtalt som «tokens» ^:s6. Deretter setter den syntaktiske analysen, også kjent som «parsing», sammen «tokens» til setninger. Historisk sett har dette blitt gjort av såkalte parsergeneratorer, men i moderne kompilatorer (f.eks. GCC/Clang for C/C++ og javac for Java) gjøres dette av håndskrevne rekursiv-descent parsere. Parseren sjekker også om rekkefølgen på ordene stemmer overens i henhold til spesifikasjonen av språket, kalt språkets syntaks. Dette steget produserer gjerne et abstrakt syntakstre (AST). Syntakstreet forenkler bort detaljene i programkoden og lar oss fokusere på den hierarkiske strukturen ^:s7. Noe som gjør det enklere å jobbe videre med programmet.

Videre gjennomføres den kontekstuelle analysen, som tar hensyn til språkets semantikk. Denne delen er todelt. For det første sjekkes det at alle identifikatorer (variabel-/funksjonsnavn) er deklarert, og at enhver bruk av en identifikator assosieres med den rette deklarasjonen. Denne operasjonen kalles binding. Deretter sjekkes det at alle uttrykk og variabler er av riktig type. Med dette menes f.eks. at heltallsvariabler kun kan sammenlignes med andre heltallsvariabler, og at aritmetiske operasjoner kun kan utføres på tall og ikke variabler av andre typer ^:s8. Kontekstfri grammatikk er et mye brukt verktøy for å utføre kontekstuell analyse i en kompilator. Dersom den kontekstuelle analysen er vellykket, har kompilatoren validert riktigheten av programmet, og den kan gå videre til neste steg. Før den går videre til optimaliseringsstadiet konverteres ofte AST-representasjonen til en mellomliggende representasjon (engelsk: «intermediate representation», forkortet til IR). Som regel er dette en forenklet versjon av assemblerkode ^:s7. Vanlige former i en historisk sammenheng er tre-adresse-kode (engelsk: «three-address code», med forkortelsen TAC) og «static single assignment» (SSA)-form. Dagens kompilatorer bruker IR-er som bygger på de samme prinsippene som TAC, men med mer til. Eksempler på moderne IR-er er LLVM-IR i LLVM-prosjektets Clang og GIMPLE i GCC. En annen fremvoksende IR som brukes for nyere prosjekter er «Multi-Level Intermediate Representation» (MLIR), som bygger videre på LLVM men muliggjør bl.a. flere lag med representasjoner samtidig .

Optimaliseringsstadiet gjennomfører analyser (f.eks. på dataflyten eller kontrollflyten i programmet), samt transformasjoner som har som hensikt å forbedre programmet på ulike vis, omtalt som optimaliseringer. Optimaliseringsstadiet tar inn den mellomliggende representasjonen produsert fra frontenden og produserer en representasjon som er semantisk ekvivalent med den opprinnelige ^:p8. Med semantisk ekvivalent mener vi at oppførselen til programmet er den samme. Dette er et viktig prinsipp innen kompilator-utforming. Vi sier at kompilatoren må være konservativ og ikke må gjøre om på programmets semantikk ^:s24. I realiteten finnes det unntak til denne regelen, for eksempel i tilfeller hvor programmet forårsaker udefinert oppførsel.

Etter at optimaliseringer og transformasjoner har blitt gjennomført, er programmet klart for oversetting til målspråket, vanligvis maskinkode eller assemblerspråk. Dette gjøres av backenden, og dens oppgave er å oversette fra IR-instruksjoner til instruksjoner i målmaskinens arkitektur. Eksempler på oppgaver som gjennomføres i denne delen er: instruksjonsvalg, registerallokering og bestemmelse av instruksjonsrekkefølgen. Instruksjonsvalg innebærer å velge riktig maskininstruksjon for hver operasjon i IR-en. Registerallokering og -tildeling dekker valg av hvilke verdier som skal være lett tilgjengelige i maskinens registre. Til slutt må kompilatoren også bestemme den beste rekkefølgen for utførelsen av instruksjonene ^:s505-506. I tillegg til disse oppgavene, gjennomfører backenden ofte optimaliseringer som er spesifikke til målmaskinens arkitektur. Et eksempel er automatisk vektorisering, som utnytter parallellprosessering ved å transformere kode slik at flere dataelementer kan prosesseres samtidig ved hjelp av SIMD-vektorinstruksjoner . Ved dette stadiet utføres også kikkehulloptimalisering, hvor hovedprinsippet er å erstatte et lite utvalg instruksjoner med andre instruksjoner som er mer effektive på maskinvaren programmet kompileres til ^:s204. Hovedutfordringen i backend-fasen er å fylle det «semantiske gapet» mellom kildespråket og målspråket. Det semantiske gapet er et uttrykk for det at mer komplekse språklige konstruksjoner kan uttrykkes i programmeringsspråket som det oversettes fra enn maskinkoden det oversettes til.

Pass

Et pass i en kompilator er en fullstendig gjennomgang av hele programkoden eller en representasjon av programkoden. En kompilator kan benytte alt fra ett enkelt pass til mange pass. En vanlig løsning er å utføre ett pass for hver kompileringsfase, men dette er ikke strengt nødvendig.

Prinsipielt skilles det mellom singelpass- og multipasskompilering. Singelpasskompilatorer går gjennom koden kun én gang, og dette får konsekvenser for hvilke strukturer språket kan tillate. F.eks. kan man i programmeringsspråk som skal kompileres av en singelpasskompilator kun referere til variabler og funksjoner som er deklarert tidligere i koden, mens man for multipasskompilatorer ikke har noen slik restriksjon. For multipasskompilatorer er man avhengig av å konstruere en midlertidig representasjon av koden allerede i det første passet, slik at senere pass ikke skal være nødt til å gjøre oppgavene til første pass på nytt. Vanligvis representeres programkoden vha. syntakstrær når det skal kommuniseres mellom passene.

Effektivitet

Som med de fleste andre dataprogrammer, ønsker man at en kompilator skal være effektiv i betytningen «rask». I motsetning til andre dataprogrammer skiller man for kompilatorer mellom to typer effektivitet: effektivitet under kompilering og effektivitet av det kompilerte programmet. Vanligvis vil det være slik at det er mer arbeid forbundet med å generere effektiv maskinkode, slik at effektivitet under kjørefasen vil gå på bekostning av effektiviteten under kompilering. Ved utforming av kompilatorer må man derfor foreta en avveining og vurdere hvor man ønsker effektiviteten.

Effektivitet under kompilering

Med tanke på programmereren som benytter seg av kompiliatoren, bør kompilatoren bruke så kort tid som mulig på å oversette et program. Det er også ønskelig at tiden det tar å kompilere et program er proporsjonal med programmets størrelse (f.eks. målt i antall linjer); altså at kompilatorens kompleksitet er O(n). I praksis kan dette være vanskelig å få til, fordi både antall identifikatorer i et program og antall bruksforekomster av identikatorene typisk er O(n), slik at den totale kompleksiteten fort blir O(n²). Med smart bruk av hashing for oppslag i tabellen over tilgjengelige identifikatorer, er det imidlertid mulig å komme veldig nær O(n) for hele kompilatoren.

Effektivitet under kjørefasen (optimalisering)

Kompilatoren skal også generere et kjørbart program som er så effektivt som mulig. For å få til dette benytter den ulike former for optimalisering. De vanligste teknikkene er:

• Effektiv bruk av registre for registermaskiner
• Konstantsubstitusjon
• Eliminasjon av felles deluttrykk
• Kodeflytting
• Løkkesplitting og løkkefusjonering
• Utrulling av løkker

Feilrapportering

Som med alle andre dataprogrammer, forventer brukeren av kompilatoren (altså programmereren) at den skal gi en fornuftig feilmelding når noe går galt. Brukeren av det kompilerte programmet forventer også å få fornuftige feilmeldinger fra det ferdige programmet. Dette leder oss til for kompilatorer å skille mellom feilrapportering under kompilering og feilrapportering under kjørefasen.

Feilrapportering under kompilering

Under kompilering av programkode skal kompilatoren finne og rapportere:

• Leksikalske feil, altså feil i oppbygningen av enkeltatomer
• Syntaktiske feil, altså feil i setningsstrukturen
• Typefeil, altså bruk av variabler med feil type
• Blokkfeil, f.eks. bruk av variable som ikke er deklarert, eller som er deklarert i en annen blokk.

De to første av disse feiltypene kalles ofte syntaksfeil, og de to siste kontekstfeil.

Å finne og rapportere den første feilforekomsten i programkoden som skal oversettes er som regel forholdsvis enkelt. Dersom brukeren av kompilatoren ønsker seg å få se alle feilene i programkoden, blir det hele imidlertid langt mer kompilsert. Dette skyldes at kompilatoren da må lese videre i programkoden på tross av at det allerede har forekommet en feil. Kompilatoren må da gjøre antagelser om hva som egentlig var ment der feilen forekom. Dersom kompilatoren gjør feil gjetning på dette punktet, kan senere feilmeldinger bli vanskelige å tolke, og i verste fall det rene nonsens.

Feilrapportering under kjøring

De vanligste typene kjørefasefeil er:

• Overflyt, altså at verdien av en variabel blir for stor til at den kan representeres av minnet som er satt av til formålet
• Null-divisjon, altså at en variabel divisor blir null
• Indeksering uten for rammene av en tabell
• Typefeil for dynamisk typede språk (for statisk typede språk finnes disse under kompilering)
• Blokkfeil for dynamisk bundne språk (for statisk bundne språk finnes disse under kompilering)

Den som utvikler kompilatoren må ta stilling til om disse feilene skal tas hånd om av programvaren eller av maskinvaren. Dersom den skal tas hånd om av programvaren, må det genereres ekstra kode av kodegeneratoren (kompileringens siste fase) som sjekker for alle mulige feil. Slik kode vil imidlertid gjøre både det resulterende programmet og selve kompileringen tregere, så det må også foretas en avveining mellom effektivitet og kvalitet på feilrapporter.