Principles of Compiler Design

Kapittel 1. Introduksjon til kompilatorer

Kapittel 1, «introduksjon til kompilatorer» (Introduction to Compilers), er en generell innføring i kompilatorer. Kapittelet begynner med å drøfte kompilatorer og oversettere, og årsaken til at vi trenger oversettere. Deretter gjennomgås strukturen til en kompilator. Kapittelet fortsetter med å drøfte leksikalsk analyse, syntaktisk analyse og mellomkodegenerering. Deretter følger en kort gjennomgang av optimaliserende kompilatorer, før kapittelet går over til å behandle kodegenerering. Kapittelet fortsetter med å behandle bokføring, feilhåndtering og verktøy for å lage kompilatorer. Til slutt forklares det hvordan man kommer i gang med et kompilatorprosjekt.

Kapittel 2. Programmeringsspråk

Kapittel 2, «Programmeringsspråk» (Programming Languages), omhandler programmeringsspråk. Kapittelet begynner med å drøfte høynivåspråk, og fortsetter med definisjoner av programmeringsspråk. Deretter behandles den leksikalske og syntaktiske struktur til et programmeringsspråk, dataelementer, datastrukturer, operatorer, tildelinger, programvareenheter datamiljøer og parameteroverføringer. Til slutt behandles lagringshåndtering.

Kapittel 3. Endelige tilstandsmaskiner og leksikalsk analyse

Kapittel 3, «Endelige tilstandsmaskiner og leksikalsk analyse» (Finite Automata and Lexical Analysis), omhandler leksikalsk analyse av et programmeringsspråk. Kapittelet innleder med å drøfte rollen til den leksikalske analysator innenfor kompilatoren. Deretter følger en enkel tilnærmelse for konstruksjon av leksikalske analysatorer, etterfulgt av beskrivelse av regulære uttrykk. Kapittelet fortsetter med beskrivelsen av en Finite Automata eller en endelig tilstandsmaskin, og beskriver deretter hvordan regulære uttrykk kan omdannes til en endelig tilstandsmaskin. Deretter beskrives det hvordan man minimaliserer antall tilstander i en deterministisk endelig tilstandsmaskin (DFA), som er konstruert ut fra en ikke-deterministisk endelig tilstandsmaskin (NFA). Kapittelet fortsetter med å drøfte et språk for spesifikasjon av leksikalske analysatorer, og forklarer implementasjonen av leksikalske analysatorer. Deretter forklares det hvordan en scannergenerator kan fungere som det som metaforisk kalles en «sveitsisk lommekniv» (Swiss Army Knife).

Kapittel 4. Den syntaktiske spesifikasjon av programmeringsspråk

Kapittel 4, «den syntaktiske spesifikasjon av programmeringsspråk» (The Syntactic Specification of Programming Languages), behandler måter å spesifisere syntaksen i et programmeringsspråk. Kapittelet behandler kontekstfri grammatikk, derivasjoner og parsertrær og til slutt kapabilitetene til kontekstfri grammatikk.

Kapittel 5. Grunnleggende parsingteknikker

Kapittel 5, «grunnleggende parsingteknikker» (Basic Parsing Techniques), beskriver ulike former for parsing. Kapittelet innledes med å drøfte parsere generelt. Deretter omtales skift-reduser-parsere, operator-presedens-parsere, ovenfra-ned-parsere, og til slutt prediktive parsere.

Kapittel 6. Automatisk konstruksjon av effektive parsere

Kapittel 6, «automatisk konstruksjon av effektive parsere» (Automatic Construction of Efficient Parsers), dreier seg blant annet om parsergeneratorer. Kapittelet begynner med å beskrive LR-parsere og den kanoniske samling av LR(0)-elementer. Deretter fortsetter det med å beskrive konstruksjon av SLR-parsingtabeller, konstruksjon av kanonisk LR-parsertabeller og konstruksjon av LALR-parsertabeller. Deretter behandles bruken av tvetydig grammatikk og en automatisk parsergenerator, i dette tilfellet Yacc. Til slutt behandles implementasjon av LR-parsingtabeller og konstruksjon av et LALR elementsett.

Kapittel 7. Syntaksrettet oversettelse

Kapittel 7, «syntaksrettet oversettelse» (Syntax-Directed Translation), dreier seg om syntaksrettet oversettelse. Kapittelet drøfter ulike former for spørsmål ved mellomkodegenerering relatert til semantiske aksjoner og oversettelser av parsertreet, Deretter behandles forskjellige implementasjoner av syntaksrettede oversettelser,, etterfulgt av en drøfting av mellomliggende representasjon, omvendt polsk notasjon, parsertrær og syntakstrær, tre-adresse-koder, nibbler (4 biter) og tupler, oversettelser av tildelingstrær, boolske uttrykk, setninger som stanser flytkontrollen oversettelse av omvendte polske notasjoner og oversettelse med en ovenfra-ned parser.

Kapittel 8. Mer om oversettelse

Kapittel 8, «mer om oversettelse» (More About Translation), fortsetter drøftelsen av oversettelser. Kapitlet begynner med å gjennomgå tabellreferanser i aritmetiske uttrykk, og fortsetter med å behandle prosedyrekall, deklarasjoner, case-setninger og record-datastrukturer. Avslutningsvis omtales datastrukturene i PL/I-lignende programmeringsspråk.

Kapittel 9. Symboltabeller

Kapittel 9, «symboltabeller» (Symbol Tables), behandler symboltabeller. Kapitlet begynner med å drøfte innholdet i en symboltabell, og drøfter deretter datastrukturer for symboltabeller, før det til slutt drøfter informasjonens gyldighetsområder.

Kapittel 10. Administrasjon av lagringsmedia under kjøring

Kapittel 10, «administrasjon av lagringsmedia under kjøring» (Run-time Storage Administration), omhandler behandling av lagringsmedia. Først beskrives en implementasjon av en enkel stakkallokering. Deretter beskrives en implementasjon av blokkstrukturerte programmeringsspråk. Deretter beskrives lagringsallokering i Fortran, og til slutt lagringsallokering i blokkstrukturerte språk.

Kapittel 11. Deteksjon og retting av feil

Kapittel 11, «deteksjon og retting av feil» (Error Dedection and Recovery), omhandler feilbehandling. Kapittelet innledes med å beskrive feilrapportering og ulike typer feil, leksikalske, syntaktiske og semantiske. Deretter behandles feil som kan oppdages under den leksikalske analysen og den syntaktiske analysen, og til slutt behandles semantiske feil.

Kapittel 12. Introduksjon til kodeoptimalisering

Kapittel 12, «introduksjon til kodeoptimalisering» (Introduction to Code Optimization), innleder drøftingen av programvareoptimalisering. Innledningsvis gis en oppsummering av ulike former for optimalisering. Deretter behandles løkkeoptimalisering. I neste omgang beskrives rettede asykliske grafer som en presentasjon av grunnleggende blokker. Kapittelet beskriver verditall og algebraiske lover, før det avsluttes med en global dataflytanalyse.

Kapittel 13. Mer om løkkeoptimalisering

Kapittel 13, «mer om løkkeoptimalisering» (More About Loop Optimization), utdyper drøftelsen av løkkeoptimalisering. Kapittelet starter med å behandle dominatorer, en kontrollflytgraf hvor node d dominerer en node n. Deretter fortsetter det med å behandle reduserbare flytgrafer og beregninger av løkkeinvarianter. Deretter behandles eliminasjon av induksjonsvariabler. Avslutningsvis behandles en del andre løkkeoptimaliseringer.

Kapittel 14. Mer om dataflytanalyse

Kapittel 14, «mer om dataflytanalyse» (More About Data-Flow Analysis), fortsetter drøftelsen av dataflytanalyser. Etter å ha gjort en del grunnleggende definisjoner, beskrives constant folding som en måte å gjenkjenne og evaluere konstanter i uttrykk under kompilering i stedet for at de beregnes under kjøring. Deretter beskrives tilgjengelige uttrykk, som er en analysealgoritme for å bestemme mengden med uttrykk som ikke behøves å beregnes på nytt. Videre beskrives behandlingen av copy propagation. Etter å ha behandlet en baklengs analyse av dataflyten, kommer boken inn på «svært opptatte uttrykk» og kodeheising. Deretter beskrives fire former for dataflytanalyser: To som følger dataflyten fremover, og to som følger dataflyten bakover. Avslutningsvis beskrives dataflytanalyser mellom prosedyrer.

Kapittel 15. Kodegenerering

Kapittel 15, «kodegenerering» (Code Generation), diskuterer generering av kode. Det drøftes ulike alternativer, som generering av absolutt maskinkode, relokaliserbar maskinkode (objektfiler), assemblerkode eller et annet programmeringsspråk. ALTRAN og Ratfor brukes som eksempler på det siste, i forbindelse med Fortran. Deretter drøftes kodegeneratorens miljø, adresseområdene til navn under utførelse, problemer forbundet med kodegenerering, valg av instruksjoner som skal genereres, i hvilken rekkefølge beregninger skal utføres, og hvilke prosessorregistere som skal brukes. Deretter beskrives en abstrakt modell for en datamaskin, og pseudokoden for en kodegenerator.

Appendiks A. En kikk på enkelte kompilatorer

Appendiks A, «en kikk på enkelte kompilatorer» (A Look at Some Compilers), diskuterer strukturen til kompilatorer for C, Fortran og BLISS. Tre ulike C-kompilatorer diskuteres: Dennis Ritchie's (1941–2011) kompilator for minidatamaskinen PDP-11 og Stephen Curtis Johnson's Portable C Compiler for stormaskinene Honeywell 6070 og IBM System/370. Den førstnevnte benyttet en rekursiv descendant parser, mens de to sistnevnte var implementert ved hjelp av en LALR-parser. Alle disse kompilatorene hadde to pass, og PDP-11 kompilatoren manglet et tredje pass for kodeoptimaliseringer. Deretter følger en kort gjennomgang for kompilatoren FORTRAN-H for IBM System/370, og fire av dens 25 faser av kompilering. Til slutt gjennomgås BLISS-kompilatoren for PDP-11, og dens fem faser av kompilering.

Appendiks B. Et programmeringsprosjekt

Appendiks B, «et programmeringsprosjekt» (A Programming Project), presenterer en samling anbefalte øvelser for kompilatorkonstruksjon. Forfatterne presenterer en delmengde av grammatikken til Pascal, og forklarer dette språkets programstruktur og leksikalske konvensjoner. Deretter foreslås det, som øvelser, å lage en symboltabell, en kommandotolk for kvadrupler (nibler), en leksikalsk analysator, rutiner for semantikk for å generere kvadrupler, en parser, rutiner for feilhåndtering og evaluering av kompilatoren ved hjelp av en profiler. Til slutt foreslås det enkelte utvidelser av språket.