Hopp til innhold

Principles of Compiler Design

Fra Wikipedia, den frie encyklopedi
Principles of Compiler Design
Forfatter(e)Alfred Aho og Jeffrey Ullman
SpråkEngelsk
SjangerSakprosa, informasjons- og kommunikasjonsteknologi, kompilatorteknikk
Utgitt1. august 1977; 47 år siden (1977-08-01)
ForlagAddison-Wesley
Sider614

Principles of Compiler Design («prinsippene for kompilatorkonstruksjon») er en engelsk sakprosabok av informatikerne Alfred Aho og Jeffrey Ullman. Boken ble utgitt av det amerikanske forlaget Addison-Wesley den 1. august 1977,[1] og er en klassisk lærebok i konstruksjon av kompilatorer og kommandotolker for programmeringsspråk.[1] Den er inndelt i 15 kapitler og to appendikser. Den påvirket en hel generasjon av informatikere og dens innhold er fortsatt aktuelt, 47 år etter utgivelsen. Boken inneholder hele pseudokoden for generering av en kompilator.

Boken ble trykt ved Bell Laboratories i New Jersey ved å benytte troff, et program for tekstformatering i operativsystemet UNIX versjon 6. På denne tiden var UNIX knapt nok tilgjengelig utenfor Bell Laboratories.

Bokens fremside viser en ridder og en drage i kamp. Dragen er grønn og er merket med teksten «kompleksiteten ved kompilatorkonstruksjon» (Complexity of Compiler Construction), mens ridderens lanse bærer teksten LALR parsergenerator. I motivet på baksiden er dragen erstattet av vindmøller, og ridderen er Don Quixote.[1] Den blir populært kalt «drageboka».[2][3] Den blir også kalt «den grønne drageboka» eller «den gamle drageboka»,[3] for å skille den fra sin etterfølger, Compilers: Principles, Techniques, and Tools («den røde drageboka» eller «den nye drageboka»),[3] som utkom 1. januar 1986.[4] Tredje utgave utkom 10. september 2006;[5] den var purpur, og ble kalt «den purpurfargede drageboka».[6]

Den 1. januar 1990 utga Allen I. Holub boken Compiler Design in C.[7] Den inneholder implementasjonen av «dragebokens» pseudokode i programmeringsspråket C.[7]

Innhold

[rediger | rediger kilde]

Kapittel 1. Introduksjon til kompilatorer

[rediger | rediger kilde]

Kapittel 1, «introduksjon til kompilatorer» (Introduction to Compilers), er en generell innføring i kompilatorer.[8]

Kapittelet drøfter kompilatorer og oversettere,[9] og årsaken til at vi trenger oversettere.[10]

Deretter gjennomgås strukturen til en kompilator.[11]

Kapittelet fortsetter med å drøfte leksikalsk analyse,[12] syntaktisk analyse[13] og mellomkodegenerering.[14] Deretter følger en kort gjennomgang av optimaliserende kompilatorer,[15] før kapittelet går over til å behandle kodegenerering.[16] Kapittelet fortsetter med å behandle bokføring,[17] feilhåndtering[18] og verktøy for å lage kompilatorer.[19] Til slutt forklares det hvordan man kommer i gang med et kompilatorprosjekt.[20]

Kapittel 2. Programmeringsspråk

[rediger | rediger kilde]

Kapittel 2, «Programmeringsspråk» (Programming Languages), omhandler programmeringsspråk.[21] Kapittelet begynner med å drøfte høynivåspråk,[22] og fortsetter med definisjoner av programmeringsspråk.[23] Deretter behandles den leksikalske og syntaktiske struktur til et programmeringsspråk,[24] dataelementer,[25] datastrukturer,[26] operatorer,[27] tildelinger,[28] programvareenheter[29] datamiljøer[30] og parameteroverføringer.[31] Til slutt behandles lagringshåndtering.[32]

Kapittel 3. Endelige tilstandsmaskiner og leksikalsk analyse

[rediger | rediger kilde]

Kapittel 3, «Endelige tilstandsmaskiner og leksikalsk analyse» (Finite Automata and Lexical Analysis), omhandler leksikalsk analyse av et programmeringsspråk.[33] Kapittelet innleder med å drøfte rollen til den leksikalske analysator innenfor kompilatoren.[34] Deretter følger en enkel tilnærmelse for konstruksjon av leksikalske analysatorer,[35] etterfulgt av beskrivelse av regulære uttrykk.[36] Kapittelet fortsetter med beskrivelsen av en Finite Automata eller en endelig tilstandsmaskin,[37] og beskriver deretter hvordan regulære uttrykk kan omdannes til en endelig tilstandsmaskin.[38] 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).[39] Kapittelet fortsetter med å drøfte et språk for spesifikasjon av leksikalske analysatorer,[40] og forklarer implementasjonen av leksikalske analysatorer.[41] Deretter forklares det hvordan en scannergenerator kan fungere som det som metaforisk kalles en «sveitsisk lommekniv» (Swiss Army Knife).[42]

Kapittel 4. Den syntaktiske spesifikasjon av programmeringsspråk

[rediger | rediger kilde]

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

Kapittel 5. Grunnleggende parsingteknikker

[rediger | rediger kilde]

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

Kapittel 6. Automatisk konstruksjon av effektive parsere

[rediger | rediger kilde]

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

Kapittel 7. Syntaksrettet oversettelse

[rediger | rediger kilde]

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

Kapittel 8. Mer om oversettelse

[rediger | rediger kilde]

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

Kapittel 9. Symboltabeller

[rediger | rediger kilde]

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

Kapittel 10. Administrasjon av lagringsmedia under kjøring

[rediger | rediger kilde]

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

Kapittel 11. Deteksjon og retting av feil

[rediger | rediger kilde]

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.[91] Deretter behandles feil som kan oppdages under den leksikalske analysen og den syntaktiske analysen,[92] og til slutt behandles semantiske feil.[93]

Kapittel 12. Introduksjon til kodeoptimalisering

[rediger | rediger kilde]

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

Kapittel 13. Mer om løkkeoptimalisering

[rediger | rediger kilde]

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.[99] Deretter fortsetter det med å behandle reduserbare flytgrafer[100] og beregninger av løkkeinvarianter.[101] Deretter behandles eliminasjon av induksjonsvariabler.[102] Avslutningsvis behandles en del andre løkkeoptimaliseringer.[103]

Kapittel 14. Mer om dataflytanalyse

[rediger | rediger kilde]

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

Kapittel 15. Kodegenerering

[rediger | rediger kilde]

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

Appendiks A. En kikk på enkelte kompilatorer

[rediger | rediger kilde]

Appendiks A, «en kikk på enkelte kompilatorer» (A Look at Some Compilers), diskuterer strukturen til kompilatorer for C, Fortran og BLISS.[120]

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.[120]

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

Deretter følger en kort gjennomgang av kompilatoren FORTRAN-H for IBM System/370, og fire av dens 25 faser av kompilering.[121]

Til slutt gjennomgås BLISS-kompilatoren for PDP-11, og dens fem faser av kompilering.[122]

Appendiks B. Et programmeringsprosjekt

[rediger | rediger kilde]

Appendiks B, «et programmeringsprosjekt» (A Programming Project), presenterer en samling anbefalte øvelser for kompilatorkonstruksjon.[123] Forfatterne presenterer en delmengde av grammatikken til Pascal,[124] og forklarer dette språkets programstruktur[125] og leksikalske konvensjoner.[126]

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.[127]

Til slutt foreslås det enkelte utvidelser av språket.[128]

Referanser

[rediger | rediger kilde]
  1. ^ a b c Aho 1977
  2. ^ Macz 2002, side 219
  3. ^ a b c Raymond 1996, side 161
  4. ^ Aho 1986
  5. ^ Aho 2006
  6. ^ Where is The Purple Dragon Book?, rmathew.blogspot.no, rmathew, 6. september 2006
  7. ^ a b Holub 1990
  8. ^ Aho 1977, side 1-25
  9. ^ Aho 1977, side 1-3
  10. ^ Aho 1977, side 3-5
  11. ^ Aho 1977, side 5-10
  12. ^ Aho 1977, side 10-12
  13. ^ Aho 1977, side 12-13
  14. ^ Aho 1977, side 13-17
  15. ^ Aho 1977, side 17-19
  16. ^ Aho 1977, side 19-20
  17. ^ Aho 1977, side 20
  18. ^ Aho 1977, side 21
  19. ^ Aho 1977, side 21-23
  20. ^ Aho 1977, side 23-25
  21. ^ Aho 1977, side 26-72
  22. ^ Aho 1977, side 26-28
  23. ^ Aho 1977, side 28-32
  24. ^ Aho 1977, side 32-34
  25. ^ Aho 1977, side 34-38
  26. ^ Aho 1977, side 38-45
  27. ^ Aho 1977, side 45-49
  28. ^ Aho 1977, side 50-54
  29. ^ Aho 1977, side 55-57
  30. ^ Aho 1977, side 57-59
  31. ^ Aho 1977, side 59-63
  32. ^ Aho 1977, side 63-72
  33. ^ Aho 1977, side 73-124
  34. ^ Aho 1977, side 74-76
  35. ^ Aho 1977, side 76-82
  36. ^ Aho 1977, side 82-88
  37. ^ Aho 1977, side 88-94
  38. ^ Aho 1977, side 95-99
  39. ^ Aho 1977, side 99-103
  40. ^ Aho 1977, side 103-109
  41. ^ Aho 1977, side 109-118
  42. ^ Aho 1977, side 118-124
  43. ^ Aho 1977, side 125-144
  44. ^ Aho 1977, side 126-136
  45. ^ Aho 1977, side 129-136
  46. ^ Aho 1977, side 136-144
  47. ^ Aho 1977, side 145-196
  48. ^ Aho 1977, side 145-150
  49. ^ Aho 1977, side 150-158
  50. ^ Aho 1977, side 158-174
  51. ^ Aho 1977, side 174-184
  52. ^ Aho 1977, side 184-196
  53. ^ Aho 1977, side 198-245
  54. ^ Aho 1977, side 198-204
  55. ^ Aho 1977, side 204-211
  56. ^ Aho 1977, side 211-214
  57. ^ Aho 1977, side 214-219
  58. ^ Aho 1977, side 219-224
  59. ^ Aho 1977, side 225-229
  60. ^ Aho 1977, side 229-233
  61. ^ Aho 1977, side 233-236
  62. ^ Aho 1977, side 236-245
  63. ^ Aho 1977, side 245-295
  64. ^ Aho 1977, side 245-249
  65. ^ Aho 1977, side 249-254
  66. ^ Aho 1977, side 254
  67. ^ Aho 1977, side 254-258
  68. ^ Aho 1977, side 258-259
  69. ^ Aho 1977, side 259-265
  70. ^ Aho 1977, side 265-270
  71. ^ Aho 1977, side 270-281
  72. ^ Aho 1977, side 281-286
  73. ^ Aho 1977, side 286-290
  74. ^ Aho 1977, side 290-295
  75. ^ Aho 1977, side 296-317
  76. ^ Aho 1977, side 296-302
  77. ^ Aho 1977, side 303-306
  78. ^ Aho 1977, side 307-308
  79. ^ Aho 1977, side 308-311
  80. ^ Aho 1977, side 312-316
  81. ^ Aho 1977, side 317-327
  82. ^ Aho 1977, side 328-350
  83. ^ Aho 1977, side 328-335
  84. ^ Aho 1977, side 336-340
  85. ^ Aho 1977, side 340-350
  86. ^ Aho 1977, side 351-377
  87. ^ Aho 1977, side 351-355
  88. ^ Aho 1977, side 356-363
  89. ^ Aho 1977, side 364-376
  90. ^ Aho 1977, side 377-381
  91. ^ Aho 1977, side 382-388
  92. ^ Aho 1977, side 388-402
  93. ^ Aho 1977, side 402-405
  94. ^ Aho 1977, side 406-410
  95. ^ Aho 1977, side 410-418
  96. ^ Aho 1977, side 418-427
  97. ^ Aho 1977, side 427-429
  98. ^ Aho 1977, side 429-440
  99. ^ Aho 1977, side 441-447
  100. ^ Aho 1977, side 447-454
  101. ^ Aho 1977, side 454-466
  102. ^ Aho 1977, side 466-471
  103. ^ Aho 1977, side 471-478
  104. ^ Aho 1977, side 478-479
  105. ^ Aho 1977, side 479-481
  106. ^ Aho 1977, side 482-487
  107. ^ Aho 1977, side 487-489
  108. ^ Aho 1977, side 489-491
  109. ^ Aho 1977, side 491-497
  110. ^ Aho 1977, side 497-504
  111. ^ Aho 1977, side 504-517
  112. ^ Aho 1977, side 518
  113. ^ Aho 1977, side 518-519
  114. ^ a b Aho 1977, side 519
  115. ^ a b Aho 1977, side 520
  116. ^ Aho 1977, side 521
  117. ^ a b Aho 1977, side 522
  118. ^ Aho 1977, side 523-525
  119. ^ Aho 1977, side 525-552
  120. ^ a b c d Aho 1977, side 557
  121. ^ Aho 1977, side 558-560
  122. ^ Aho 1977, side 560-562
  123. ^ Aho 1977, side 563
  124. ^ Aho 1977, side 563-565
  125. ^ Aho 1977, side 566
  126. ^ Aho 1977, side 566-567
  127. ^ Aho 1977, side 567-568
  128. ^ Aho 1977, side 569

Litteratur

[rediger | rediger kilde]

Eksterne lenker

[rediger | rediger kilde]


Autoritetsdata
Hentet fra «https://no.wikipedia.org/w/index.php?title=Principles_of_Compiler_Design&oldid=24820707»