Kompilator
Fra Wikipedia, den frie encyklopedi
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.
Innhold |
[rediger] Faser
En kompilators oppgaver kategoriseres vanligvis i såkalte faser. Hovedfasene og deres underfaser er:
- Parsing (tolking av programkoden)
- Leksikalsk analyse
- Syntaktisk analyse
- Kontekstuell analyse
- Binding
- Typesjekking
- Kodegenerering
I første fase (tolkingen) analyseres programkodens riktighet i forhold til programmeringsspråkets spesifikasjon. Leksikalsk analyse går ut på å sette sammen enkelttegn til «ord», gjerne omtalt som atomer, mens den syntaktiske analysen går ut på å sette sammen atomene til setninger. Så langt tas det ikke hensyn til programmets betydning.
Den kontekstuelle analysens hovedoppgave er todelt. For det første sjekkes det at alle identifikatorer (variabel-/funksjonsnavn) er deklarert, og 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. Kontekstfri grammatikk er et mye brukt verktøy for å utføre kontekstuell analyse i en kompilator.
Dersom den syntaktiske og kontekstuelle analysen er vellykket, er programkoden som skal oversettese korrekt, og klar for oversetting til målspråket, vanligvis maskinkode eller assemblerspråk. Hovedutfordringen i denne 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.
[rediger] 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.
[rediger] 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.
[rediger] 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.
[rediger] 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
[rediger] 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.
[rediger] 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.
[rediger] 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.
