Redigerer Principles of Compiler Design (avsnitt)

==Innhold==
===Kapittel 1. Introduksjon til kompilatorer===
Kapittel 1, «introduksjon til kompilatorer» (''Introduction to Compilers''), er en generell innføring i kompilatorer.<ref name="Aho1977_1-25" />

Kapittelet drøfter kompilatorer og oversettere,<ref name="Aho1977_1-3" /> og årsaken til at vi trenger oversettere.<ref name="Aho1977_3-5" />

Deretter gjennomgås strukturen til en kompilator.<ref name="Aho1977_5-10" /> 

Kapittelet fortsetter med å drøfte leksikalsk analyse,<ref name="Aho1977_10-12" /> syntaktisk analyse<ref name="Aho1977_12-13" /> og mellomkodegenerering.<ref name="Aho1977_13-17" /> Deretter følger en kort gjennomgang av optimaliserende kompilatorer,<ref name="Aho1977_17-19" /> før kapittelet går over til å behandle kodegenerering.<ref name="Aho1977_19-20" /> Kapittelet fortsetter med å behandle [[bokføring (programmering)|bokføring]],<ref name="Aho1977_20" /> feilhåndtering<ref name="Aho1977_21" /> og verktøy for å lage kompilatorer.<ref name="Aho1977_21-23" /> Til slutt forklares det hvordan man kommer i gang med et kompilatorprosjekt.<ref name="Aho1977_23-25" />

===Kapittel 2. Programmeringsspråk===
Kapittel 2, «Programmeringsspråk» (''Programming Languages''), omhandler [[programmeringsspråk]].<ref name="Aho1977_26-72" /> Kapittelet begynner med å drøfte [[høynivåspråk]],<ref name="Aho1977_26-28" /> og fortsetter med definisjoner av programmeringsspråk.<ref name="Aho1977_28-32" /> Deretter behandles den leksikalske og syntaktiske struktur til et programmeringsspråk,<ref name="Aho1977_32-34" /> [[dataelement]]er,<ref name="Aho1977_34-38" /> [[datastruktur]]er,<ref name="Aho1977_38-45" /> [[operator]]er,<ref name="Aho1977_45-49" /> [[Tildeling (informatikk)|tildelinger]],<ref name="Aho1977_50-54" /> programvareenheter<ref name="Aho1977_55-57" /> datamiljøer<ref name="Aho1977_57-59" /> og [[parameter (informatikk)|parameteroverføringer]].<ref name="Aho1977_59-63" /> Til slutt behandles lagringshåndtering.<ref name="Aho1977_63-72" />

===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.<ref name="Aho1977_73-124" /> Kapittelet innleder med å drøfte rollen til den leksikalske analysator innenfor kompilatoren.<ref name="Aho1977_74-76" /> Deretter følger en enkel tilnærmelse for konstruksjon av leksikalske analysatorer,<ref name="Aho1977_76-82" /> etterfulgt av beskrivelse av [[Regulært uttrykk|regulære uttrykk]].<ref name="Aho1977_82-88" /> Kapittelet fortsetter med beskrivelsen av en Finite Automata eller en [[endelig tilstandsmaskin]],<ref name="Aho1977_88-94" /> og beskriver deretter hvordan regulære uttrykk kan omdannes til en endelig tilstandsmaskin.<ref name="Aho1977_95-99" /> 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).<ref name="Aho1977_99-103" /> Kapittelet fortsetter med å drøfte et språk for spesifikasjon av leksikalske analysatorer,<ref name="Aho1977_103-109" /> og forklarer implementasjonen av leksikalske analysatorer.<ref name="Aho1977_109-118" /> Deretter forklares det hvordan en scannergenerator kan fungere som det som metaforisk kalles en «sveitsisk lommekniv» (''Swiss Army Knife'').<ref name="Aho1977_118-124" />

===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 [[Syntaks (programmering)|syntaksen]] i et programmeringsspråk.<ref name="Aho1977_125-144" /> Kapittelet behandler [[kontekstfri grammatikk]]<ref name="Aho1977_126-136" />, derivasjoner og parsertrær<ref name="Aho1977_129-136" /> og til slutt kapabilitetene til kontekstfri grammatikk.<ref name="Aho1977_136-144" />

===Kapittel 5. Grunnleggende parsingteknikker===
Kapittel 5, «grunnleggende parsingteknikker» (''Basic Parsing Techniques''), beskriver ulike former for [[parser|parsing]].<ref name="Aho1977_145-196" /> Kapittelet innledes med å drøfte parsere generelt.<ref name="Aho1977_145-150" /> Deretter omtales [[skift-reduser-parser]]e,<ref name="Aho1977_150-158" /> [[operator-presedens-parser]]e,<ref name="Aho1977_158-174" /> [[ovenfra-ned-parser]]e,<ref name="Aho1977_174-184" /> og til slutt [[prediktiv parser|prediktive parsere]].<ref name="Aho1977_184-196" />

===Kapittel 6. Automatisk konstruksjon av effektive parsere===
Kapittel 6, «automatisk konstruksjon av effektive parsere» (''Automatic Construction of Efficient Parsers''), dreier seg blant annet om [[parsergenerator]]er.<ref name="Aho1977_198-245" /> Kapittelet begynner med å beskrive [[LR-parser]]e<ref name="Aho1977_198-204" /> og den kanoniske samling av LR(0)-elementer.<ref name="Aho1977_204-211" /> Deretter fortsetter det med å beskrive konstruksjon av [[Simpel LR-parser|SLR-parsingtabeller]],<ref name="Aho1977_211-214" /> konstruksjon av [[kanonisk LR-parser|kanonisk LR-parsertabeller]]<ref name="Aho1977_214-219" /> og konstruksjon av [[LALR-parser|LALR-parsertabeller]].<ref name="Aho1977_219-224" /> Deretter behandles bruken av tvetydig grammatikk<ref name="Aho1977_225-229" /> og en automatisk parsergenerator, i dette tilfellet [[Yacc]].<ref name="Aho1977_229-233" /> Til slutt behandles implementasjon av LR-parsingtabeller<ref name="Aho1977_233-236" /> og konstruksjon av et LALR elementsett.<ref name="Aho1977_236-245" />

===Kapittel 7. Syntaksrettet oversettelse===
Kapittel 7, «syntaksrettet oversettelse» (''Syntax-Directed Translation''), dreier seg om [[syntaksrettet oversettelse]].<ref name="Aho1977_245-295" /> Kapittelet drøfter ulike former for spørsmål ved [[kodegenerering (kompilatorer)|mellomkodegenerering]] relatert til semantiske aksjoner og oversettelser av parsertreet,<ref name="Aho1977_245-249" /> Deretter behandles forskjellige implementasjoner av syntaksrettede oversettelser,<ref name="Aho1977_249-254" />, etterfulgt av en drøfting av [[mellomliggende representasjon]],<ref name="Aho1977_254" /> [[omvendt polsk notasjon]],<ref name="Aho1977_254-258" /> parsertrær og syntakstrær,<ref name="Aho1977_258-259" /> [[tre-adresse-kode]]r, [[nibble]]r (4 biter) og [[tupel|tupler]],<ref name="Aho1977_259-265" /> oversettelser av tildelingstrær,<ref name="Aho1977_265-270" /> [[boolsk uttrykk|boolske uttrykk]],<ref name="Aho1977_270-281" /> setninger som stanser flytkontrollen<ref name="Aho1977_281-286" /> oversettelse av omvendte polske notasjoner<ref name="Aho1977_286-290" /> og oversettelse med en ovenfra-ned parser.<ref name="Aho1977_290-295" />

===Kapittel 8. Mer om oversettelse===
Kapittel 8, «mer om oversettelse» (''More About Translation''), fortsetter drøftelsen av oversettelser.<ref name="Aho1977_296-317" /> Kapitlet begynner med å gjennomgå tabellreferanser i aritmetiske uttrykk,<ref name="Aho1977_296-302" /> og fortsetter med å behandle prosedyrekall,<ref name="Aho1977_303-306"/> deklarasjoner,<ref name="Aho1977_307-308"/> [[switch-setning|''case''-setninger]]<ref name="Aho1977_308-311"/> og [[Record|''record''-datastrukturer]].<ref name="Aho1977_312-316"/> Avslutningsvis omtales datastrukturene i [[PL/I]]-lignende programmeringsspråk.<ref name="Aho1977_317-327"/>

===Kapittel 9. Symboltabeller===
Kapittel 9, «symboltabeller» (''Symbol Tables''), behandler [[symboltabell]]er.<ref name="Aho1977_328-350"/> Kapitlet begynner med å drøfte innholdet i en symboltabell,<ref name="Aho1977_328-335"/> og drøfter deretter datastrukturer for symboltabeller,<ref name="Aho1977_336-340"/> før det til slutt drøfter informasjonens gyldighetsområder.<ref name="Aho1977_341-350"/>

===Kapittel 10. Administrasjon av lagringsmedia under kjøring===
Kapittel 10, «administrasjon av lagringsmedia under kjøring» (''Run-time Storage Administration''), omhandler behandling av lagringsmedia.<ref name="Aho1977_351-377"/> Først beskrives en implementasjon av en enkel [[Stakk (datastruktur)|stakkallokering]].<ref name="Aho1977_351-355"/> Deretter beskrives en implementasjon av blokkstrukturerte programmeringsspråk.<ref name="Aho1977_356-363"/> Deretter beskrives lagringsallokering i [[Fortran]],<ref name="Aho1977_364-376"/> og til slutt lagringsallokering i blokkstrukturerte språk.<ref name="Aho1977_377-381"/>

===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.<ref name="Aho1977_382-388"/> Deretter behandles feil som kan oppdages under den leksikalske analysen og den syntaktiske analysen,<ref name="Aho1977_388-402"/> og til slutt behandles semantiske feil.<ref name="Aho1977_402-405"/> 

===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.<ref name="Aho1977_406-410"/> Deretter behandles [[løkkeoptimalisering]].<ref name="Aho1977_410-418"/> I neste omgang beskrives [[Rettet asyklisk graf|rettede asykliske grafer]] som en presentasjon av grunnleggende blokker.<ref name="Aho1977_418-427"/> Kapittelet beskriver verditall og algebraiske lover,<ref name="Aho1977_427-429"/> før det avsluttes med en global dataflytanalyse.<ref name="Aho1977_429-440"/>

===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 [[dominator (grafteori)|dominatorer]], en [[kontrollflytgraf]] hvor node ''d'' dominerer en node ''n''.<ref name="Aho1977_441-447"/> Deretter fortsetter det med å behandle [[intervall (grafteori)|reduserbare flytgrafer]]<ref name="Aho1977_447-454"/> og beregninger av [[løkkeinvariant]]er.<ref name="Aho1977_454-466"/> Deretter behandles eliminasjon av [[Matematisk induksjon|induksjonsvariabler]].<ref name="Aho1977_466-471"/> Avslutningsvis behandles en del andre løkkeoptimaliseringer.<ref name="Aho1977_471-478"/>

===Kapittel 14. Mer om dataflytanalyse===
Kapittel 14, «mer om dataflytanalyse» (''More About Data-Flow Analysis''), fortsetter drøftelsen av [[dataflytanalyse]]r. Etter å ha gjort en del grunnleggende definisjoner,<ref name="Aho1977_478-479"/> beskrives ''constant folding'' som en måte å gjenkjenne og evaluere konstanter i uttrykk under kompilering i stedet for at de beregnes under kjøring.<ref name="Aho1977_479-481"/> Deretter beskrives [[tilgjengelige uttrykk]], som er en analysealgoritme for å bestemme mengden med uttrykk som ikke behøves å beregnes på nytt.<ref name="Aho1977_482-487"/> Videre beskrives behandlingen av [[copy propagation]].<ref name="Aho1977_487-489"/> Etter å ha behandlet en [[dataflytanalyse|baklengs analyse]] av dataflyten,<ref name="Aho1977_489-491"/> kommer boken inn på ''«svært opptatte uttrykk»'' og ''kodeheising''.<ref name="Aho1977_491-497"/> Deretter beskrives fire former for dataflytanalyser: To som følger dataflyten fremover, og to som følger dataflyten bakover.<ref name="Aho1977_497-504"/> Avslutningsvis beskrives dataflytanalyser mellom prosedyrer.<ref name="Aho1977_504-517"/>

===Kapittel 15. Kodegenerering===
Kapittel 15, «kodegenerering» (''Code Generation''), diskuterer [[Kodegenerering (kompilatorer)|generering av kode]].<ref name="Aho1977_518"/> Det drøftes ulike alternativer, som generering av absolutt [[maskinkode]], relokaliserbar maskinkode ([[objektfil]]er), [[assembler]]kode eller et annet programmeringsspråk.<ref name="Aho1977_518-519"/> [[ALTRAN]] og [[Ratfor]] brukes som eksempler på det siste, i forbindelse med Fortran.<ref name="Aho1977_519"/> Deretter drøftes kodegeneratorens miljø,<ref name="Aho1977_519"/> [[adresseområde]]ne til navn under [[utførelse (informatikk)|utførelse]],<ref name="Aho1977_520"/> problemer forbundet med kodegenerering,<ref name="Aho1977_521"/> valg av [[Instruksjon (datamaskin)|instruksjoner]] som skal genereres,<ref name="Aho1977_520"/> i hvilken rekkefølge beregninger skal utføres,<ref name="Aho1977_522"/> og hvilke [[prosessorregister]]e som skal brukes.<ref name="Aho1977_522"/> Deretter beskrives en abstrakt modell for en datamaskin,<ref name="Aho1977_523-525"/> og pseudokoden for en kodegenerator.<ref name="Aho1977_525-552"/>

===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 (programmeringsspråk)|C]], Fortran og [[BLISS]].<ref name="Aho1977_557"/>

Tre ulike C-kompilatorer diskuteres: [[Dennis Ritchie]]'s (1941&ndash;2011) kompilator for [[minidatamaskin]]en [[PDP-11]] og [[Stephen Curtis Johnson]]'s [[Portable C Compiler]] for [[stormaskin]]ene [[Honeywell 6000-serien|Honeywell 6070]] og [[IBM System/370]].<ref name="Aho1977_557"/>

Den førstnevnte benyttet en rekursiv descendant parser, mens de to sistnevnte var implementert ved hjelp av en [[LALR-parser]].<ref name="Aho1977_557"/> Alle disse kompilatorene hadde to pass, og PDP-11 kompilatoren manglet et tredje pass for kodeoptimaliseringer.<ref name="Aho1977_557"/>

Deretter følger en kort gjennomgang av kompilatoren FORTRAN-H for IBM System/370, og fire av dens 25 faser av kompilering.<ref name="Aho1977_558-560"/> 

Til slutt gjennomgås BLISS-kompilatoren for PDP-11, og dens fem faser av kompilering.<ref name="Aho1977_560-562"/>

===Appendiks B. Et programmeringsprosjekt===
Appendiks B, «et programmeringsprosjekt» (''A Programming Project''), presenterer en samling anbefalte øvelser for kompilatorkonstruksjon.<ref name="Aho1977_563"/> Forfatterne presenterer en delmengde av grammatikken til [[Pascal (programmeringsspråk)|Pascal]],<ref name="Aho1977_563-565"/> og forklarer dette språkets programstruktur<ref name="Aho1977_566"/> og leksikalske konvensjoner.<ref name="Aho1977_566-567"/>

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''.<ref name="Aho1977_567-568"/>

Til slutt foreslås det enkelte utvidelser av språket.<ref name="Aho1977_569"/>