POLECAMY
Koszyk
Kompilatory
Reguły, metody i narzędzia
Wydawca:
Format:
pdf, ibuk
Języki programowania są sposobami zapisu przedstawiającymi obliczenia w sposób zrozumiały dla ludzi i dla maszyn. Świat, jaki dziś znamy, uzależniony jest od języków programowania, gdyż całe oprogramowanie działające na wszystkich komputerach zostało napisane w jakimś języku programowania. Jednak zanim możliwe będzie uruchomienie programu, musi on najpierw zostać przetłumaczony do postaci, w której komputer będzie mógł go wykonać. Tłumaczenie to odbywa się za pomocą specjalnych systemów programowych zwanych kompilatorami.
II edycja klasycznej książki, znanej na całym świecie jako Dragon Book, jest poświęcona projektowaniu i implementacji kompilatorów. W dokładniejszym zrozumieniu i przyswojeniu tematu, pomagają czytelnikowi liczne, rozbudowane ćwiczenia zawarte w każdym podrozdziale.
Dzięki lekturze poznasz:
- Podstawowe zagadnienia związane z architekturą komputerów oraz zasady języków programowania
- Omówienie analizy leksykalnej, wyrażeń regularnych, automatów skończonych i narzędzi generujących leksery
- Główne metody parsingu
- Podstawowe koncepcje definicji kierowanych składnią i translacji sterowanej składnią
- Zasady projektowania generatora kodu
- Technologie optymalizacji kodu
Nowe rozdziały obejmują takie zagadnienia jak:
- Środowiska wykonawcze, w tym: mechanizmy odśmiecania pamięci i zarządzanie stosem
- Optymalizacje na poziomie instrukcji
- Wykrywanie i wykorzystywanie równoległości w większej skali
- Analizy międzyproceduralne
Zasady i techniki projektowania kompilatorów mają zastosowanie w tak wielu dziedzinach, że na pewno każdy informatyk spotka się z nimi w swojej pracy wielokrotnie. Studiowanie pisania kompilatorów oznacza poznawanie takich zagadnień jak: języki programowania, architektura komputerów, teoria języka, algorytmy i inżynieria oprogramowania.
| Rok wydania | 2019 |
|---|---|
| Liczba stron | 1040 |
| Kategoria | Zastosowania informatyki |
| Wydawca | Wydawnictwo Naukowe PWN |
| Tłumaczenie | Marek Włodarz |
| ISBN-13 | 978-83-01-20381-8 |
| Numer wydania | 2 |
| Język publikacji | polski |
| Informacja o sprzedawcy | ePWN sp. z o.o. |
Ciekawe propozycje
Spis treści
| Przedmowa XXI | |
| 1. Wprowadzenie | 1 |
| 1.1. Translatory | 1 |
| 1.1.1. Ćwiczenia do podrozdziału 1.1 | 4 |
| 1.2. Struktura kompilatora | 4 |
| 1.2.1. Analiza leksykalna | 6 |
| 1.2.2. Analiza składniowa | 7 |
| 1.2.3. Analiza semantyczna | 9 |
| 1.2.4. Generowanie kodu posredniego | 9 |
| 1.2.5. Optymalizacja kodu | 10 |
| 1.2.6. Generowanie kodu | 11 |
| 1.2.7. Zarządzanie tablica symboli | 11 |
| 1.2.8. Grupowanie faz w przebiegi | 12 |
| 1.2.9. Narzędzia do budowania kompilatorów | 12 |
| 1.3. Ewolucja języków programowania | 13 |
| 1.3.1. Przejście na języki wyższego poziomu | 13 |
| 1.3.2. Wpływ na kompilatory | 14 |
| 1.3.3. Ćwiczenia do podrozdziału 1.3 | 15 |
| 1.4. Teoria konstruowania kompilatorów | 16 |
| 1.4.1. Modelowanie w projektowaniu i implementacji kompilatora | 16 |
| 1.4.2. Nauka o optymalizacji kodu | 16 |
| 1.5. Zastosowania technologii kompilatorów | 18 |
| 1.5.1. Implementacja języków programowania wysokiego poziomu | 19 |
| 1.5.2. Optymalizacje architektur komputerów | 21 |
| 1.5.3. Projekty nowych architektur komputerów | 22 |
| 1.5.4. Tłumaczenie programów | 24 |
| 1.5.5. Narzędzia niezawodności oprogramowania | 25 |
| 1.6. Podstawy języków programowania | 27 |
| 1.6.1. Rozróżnienie statyczny/dynamiczny | 28 |
| 1.6.2. Środowiska i stany | 28 |
| 1.6.3. Statyczny zasięg i struktura blokowa | 30 |
| 1.6.4. Jawna kontrola dostępu | 34 |
| 1.6.5. Zasięg dynamiczny | 34 |
| 1.6.6. Mechanizmy przekazywania parametrów | 36 |
| 1.6.7. Aliasowanie | 38 |
| 1.6.8. Ćwiczenia do podrozdziału 1.6 | 39 |
| 1.7. Podsumowanie | 40 |
| 1.8. Bibliografia | 41 |
| 2. Prosty translator sterowany składnia | 43 |
| 2.1. Wprowadzenie | 44 |
| 2.2. Definiowanie składni | 46 |
| 2.2.1. Definicja gramatyki | 46 |
| 2.2.2. Wyprowadzenia | 48 |
| 2.2.3. Drzewa rozbioru | 49 |
| 2.2.4. Niejednoznaczność | 51 |
| 2.2.5. Łączność operatorów | 52 |
| 2.2.6. Priorytety operatorów | 53 |
| 2.2.7. Ćwiczenia do podrozdziału 2.2 | 56 |
| 2.3. Translacja sterowana składnia | 57 |
| 2.3.1. Notacja postfiksowa | 58 |
| 2.3.2. Syntetyzowane atrybuty | 58 |
| 2.3.3. Proste definicje sterowane składnia | 60 |
| 2.3.4. Przechodzenie drzewa | 61 |
| 2.3.5. Schematy translacji | 63 |
| 2.3.6. Ćwiczenia do podrozdziału 2.3 | 65 |
| 2.4. Analiza składniowa | 66 |
| 2.4.1. Analiza zstępująca | 66 |
| 2.4.2. Analiza predykcyjna | 69 |
| 2.4.3. Kiedy używać e-produkcji | 71 |
| 2.4.4. Projektowanie parsera predykcyjnego | 72 |
| 2.4.5. Lewostronna rekurencja | 73 |
| 2.4.6. Ćwiczenia do podrozdziału 2.4 | 74 |
| 2.5. Translator dla prostych wyrażeń | 74 |
| 2.5.1. Składnia abstrakcyjna i konkretna | 75 |
| 2.5.2. Dostosowywanie schematu translacji | 76 |
| 2.5.3. Procedury dla nieterminali | 77 |
| 2.5.4. Upraszczanie translatora | 78 |
| 2.5.5. Kompletny program | 79 |
| 2.6. Analiza leksykalna | 82 |
| 2.6.1. Usuwanie białych znaków i komentarzy | 83 |
| 2.6.2. Czytanie z wyprzedzeniem | 84 |
| 2.6.3. Stałe | 84 |
| 2.6.4. Rozpoznawanie słów kluczowych i identyfikatorów | 85 |
| 2.6.5. Analizator leksykalny | 87 |
| 2.6.6. Ćwiczenia do podrozdziału 2.6 | 91 |
| 2.7. Tablice symboli | 91 |
| 2.7.1. Tablica symboli dla zasięgu | 93 |
| 2.7.2. Używanie tablic symboli | 96 |
| 2.8. Generowanie kodu pośredniego | 98 |
| 2.8.1. Dwa rodzaje reprezentacji pośrednich | 98 |
| 2.8.2. Konstruowanie drzew składniowych | 99 |
| 2.8.3. Kontrole statyczne | 104 |
| 2.8.4. Kod trójadresowy | 106 |
| 2.8.5. Ćwiczenia do podrozdziału 2.8 | 112 |
| 2.9. Podsumowanie | 112 |
| 3. Analiza leksykalna | 115 |
| 3.1. Rola analizatora leksykalnego | 115 |
| 3.1.1. Analiza leksykalna kontra analiza składniowa (parsing) | 117 |
| 3.1.2. Tokeny, wzorce i leksemy | 117 |
| 3.1.3. Atrybuty tokenów | 118 |
| 3.1.4. Błędy leksykalne | 120 |
| 3.1.5. Ćwiczenia do podrozdziału 3.1 | 121 |
| 3.2. Buforowanie wejścia | 121 |
| 3.2.1. Pary buforów | 122 |
| 3.2.2. Wartownicy | 123 |
| 3.3. Specyfikacje tokenów | 124 |
| 3.3.1. Ciągi i języki | 125 |
| 3.3.2. Działania na językach | 126 |
| 3.3.3. Wyrażenia regularne | 127 |
| 3.3.4. Definicje regularne | 129 |
| 3.3.5. Rozszerzenia wyrażeń regularnych | 130 |
| 3.3.6. Ćwiczenia do podrozdziału 3.3 | 131 |
| 3.4. Rozpoznawanie tokenów | 135 |
| 3.4.1. Diagramy przejść | 136 |
| 3.4.2. Rozpoznawanie zastrzeżonych słów i identyfikatorów | 139 |
| 3.4.3. Dokończenie przykładu | 140 |
| 3.4.4. Architektura analizatora leksykalnego opartego na diagramie przejść | 141 |
| 3.4.5. Ćwiczenia do podrozdziału 3.4 | 143 |
| 3.5. Lex – generator analizatorów leksykalnych | 147 |
| 3.5.1. Korzystanie z Lex | 147 |
| 3.5.2. Struktura programów w języku Lex | 148 |
| 3.5.3. Rozwiązywanie konfliktów w Lex | 152 |
| 3.5.4. Operator prawego kontekstu | 152 |
| 3.5.5. Ćwiczenia do podrozdziału 3.5 | 153 |
| 3.6. Automaty skończone | 154 |
| 3.6.1. Niedeterministyczne automaty skończone | 155 |
| 3.6.2. Tablice przejść | 156 |
| 3.6.3. Akceptowanie ciągów wejściowych przez automat | 156 |
| 3.6.4. Deterministyczne automaty skończone | 157 |
| 3.6.5. Ćwiczenia do podrozdziału 3.6 | 158 |
| 3.7. Od wyrażeń regularnych do automatów | 159 |
| 3.7.1. Konwertowanie NAS na DAS | 160 |
| 3.7.2. Symulacja NAS | 163 |
| 3.7.3. Wydajność symulacji NAS | 164 |
| 3.7.4. Konstruowanie NAS z wyrażenia regularnego | 166 |
| 3.7.5. Wydajność algorytmów przetwarzania ciągów | 170 |
| 3.7.6. Ćwiczenia do podrozdziału 3.7 | 174 |
| 3.8. Projektowanie generatora analizatorów leksykalnych | 174 |
| 3.8.1. Struktura generowanego analizatora | 174 |
| 3.8.2. Dopasowywanie wzorców na podstawie NAS | 177 |
| 3.8.3. DAS dla analizatorów leksykalnych | 178 |
| 3.8.4. Implementacja operatora prawego kontekstu | 179 |
| 3.8.5. Ćwiczenia do podrozdziału 3.8 | 180 |
| 3.9. Optymalizacja mechanizmów rozpoznających wzorce oparte na DAS | 180 |
| 3.9.1. Istotne stany w NAS | 181 |
| 3.9.2. Funkcje wyliczane z drzewa składniowego | 183 |
| 3.9.3. Obliczanie nullable, firstpos i lastpos | 184 |
| 3.9.4. Obliczanie followpos | 185 |
| 3.9.5. Bezpośrednie konwertowanie wyrażenia regularnego na DAS | 187 |
| 3.9.6. Minimalizacja liczby stanów w DAS | 189 |
| 3.9.7. Minimalizacja liczby stanów w analizatorach leksykalnych | 193 |
| 3.9.8. Wybieranie miedzy czasem a pamięcią w symulatorze DAS | 193 |
| 3.9.9. Ćwiczenia do podrozdziału 3.9 | 195 |
| 3.10. Podsumowanie | 195 |
| 3.11. Bibliografia | 197 |
| 4. Analiza składniowa | 201 |
| 4.1. Wprowadzenie | 202 |
| 4.1.1. Rola parsera | 202 |
| 4.1.2. Reprezentatywne gramatyki | 203 |
| 4.1.3. Obsługa błędów składniowych | 204 |
| 4.1.4. Strategie przywracania kontroli po błędzie | 205 |
| 4.2. Gramatyki bezkontekstowe | 207 |
| 4.2.1. Formalna definicja gramatyki bezkontekstowej | 207 |
| 4.2.2. Konwencje notacyjne | 209 |
| 4.2.3. Wyprowadzenie | 210 |
| 4.2.4. Drzewa rozbioru | 212 |
| 4.2.5. Niejednoznaczność | 214 |
| 4.2.6. Weryfikowanie języka wygenerowanego przez gramatykę | 214 |
| 4.2.7. Gramatyki bezkontekstowe a wyrażenia regularne | 216 |
| 4.2.8. Ćwiczenia do podrozdziału 4.2 | 217 |
| 4.3. Tworzenie gramatyki | 220 |
| 4.3.1. Analiza leksykalna a analiza składniowa | 220 |
| 4.3.2. Eliminowanie niejednoznaczności | 221 |
| 4.3.3. Eliminowanie rekurencji lewostronnej | 222 |
| 4.3.4. Lewostronna faktoryzacja | 225 |
| 4.3.5. Konstrukcje językowe niebędące bezkontekstowymi | 226 |
| 4.3.6. Ćwiczenia do podrozdziału 4.3 | 227 |
| 4.4. Analiza zstepująca | 228 |
| 4.4.1. Analiza oparta na zejściach rekurencyjnych | 229 |
| 4.4.2. FIRST oraz FOLLOW | 231 |
| 4.4.3. Gramatyki LL(1) | 233 |
| 4.4.4. Nierekurencyjna analiza predykcyjna | 237 |
| 4.4.5. Przywracanie po błędzie w analizie predykcyjnej | 239 |
| 4.4.6. Ćwiczenia do podrozdziału 4.4 | 242 |
| 4.5. Analiza wstępująca | 245 |
| 4.5.1. Redukcje | 245 |
| 4.5.2. Przycinanie uchwytów | 246 |
| 4.5.3. Analiza metoda przesuniecie-redukcja | 247 |
| 4.5.4. Konflikty w analizie metoda przesuniecie-redukcja | 249 |
| 4.5.5. Ćwiczenia do podrozdziału 4.5 | 251 |
| 4.6. Wprowadzenie do analizy LR: proste LR (SLR) | 252 |
| 4.6.1. Dlaczego parsery LR? | 252 |
| 4.6.2. Sytuacje i automat LR(0) | 253 |
| 4.6.3. Algorytm parsingu LR | 259 |
| 4.6.4. Konstruowanie tablic analizy SLR | 264 |
| 4.6.5. Żywotne prefiksy | 267 |
| 4.6.6. Ćwiczenia do podrozdziału 4.6 | 268 |
| 4.7. Bardziej skuteczne parsery LR | 270 |
| 4.7.1. Kanoniczne sytuacje LR(1) | 270 |
| 4.7.2. Konstruowanie zbiorów sytuacji LR(1) | 272 |
| 4.7.3. Tablice analizy kanonicznego LR(1) | 275 |
| 4.7.4. Konstruowanie tablic analizy LALR | 276 |
| 4.7.5. Wydajne konstruowanie tablic analizy LALR | 281 |
| 4.7.6. Kompresowanie tablic analizy LR | 286 |
| 4.7.7. Ćwiczenia do podrozdziału 4.7 | 288 |
| 4.8. Gramatyki niejednoznaczne | 289 |
| 4.8.1. Wykorzystanie priorytetów i łączności do rozwiązywania konfliktów | 289 |
| 4.8.2. Niejednoznaczność „wiszącego else” | 292 |
| 4.8.3. Przywracanie kontroli po błędzie w analizie LR | 294 |
| 4.8.4. Ćwiczenia do podrozdziału 4.8 | 297 |
| 4.9. Generatory parserów | 298 |
| 4.9.1. Generator parserów Yacc | 298 |
| 4.9.2. Używanie Yacc z gramatykami niejednoznacznymi | 302 |
| 4.9.3. Tworzenie analizatorów leksykalnych zgodnych z Yacc przy użyciu Lex | 305 |
| 4.9.4. Przywracanie kontroli po błędach w Yacc | 306 |
| 4.9.5. Ćwiczenia do podrozdziału 4.9 | 308 |
| 4.10. Podsumowanie | 308 |
| 4.11. Bibliografia | 311 |
| 5. Translacja sterowana składnia 315 | |
| 5.1. Definicje sterowane składnia | 316 |
| 5.1.1. Atrybuty dziedziczone i syntetyzowane | 316 |
| 5.1.2. Przetwarzanie SDD w węzłach drzewa rozbioru | 318 |
| 5.1.3. Ćwiczenia do podrozdziału 5.1 | 322 |
| 5.2. Kolejność przetwarzania w SDD | 322 |
| 5.2.1. Grafy zależności | 322 |
| 5.2.2. Porządkowanie obliczania atrybutów | 324 |
| 5.2.3. Definicje S-atrybutowane | 325 |
| 5.2.4. Definicje L-atrybutowane | 325 |
| 5.2.5. Reguły semantyczne z kontrolowanymi efektami ubocznymi | 327 |
| 5.2.6. Ćwiczenia do podrozdziału 5.2 | 329 |
| 5.3. Zastosowania translacji sterowanej składnia | 330 |
| 5.3.1. Konstruowanie drzew składniowych | 330 |
| 5.3.2. Struktura opisu typu | 334 |
| 5.3.3. Ćwiczenia do podrozdziału 5.3 | 336 |
| 5.4. Sterowane składnia schematy translacji | 336 |
| 5.4.1. Postfiksowe schematy translacji | 337 |
| 5.4.2. Implementacja postfiksowego SDT przez stos parsera | 338 |
| 5.4.3. SDT z akcjami wewnątrz produkcji | 339 |
| 5.4.4. Eliminowanie rekurencji lewostronnej z SDT | 341 |
| 5.4.5. SDT dla definicji L-atrybutowanych | 344 |
| 5.4.6. Ćwiczenia do podrozdziału 5.4 | 349 |
| 5.5. Implementacja L-atrybutowanych SDD | 350 |
| 5.5.1. Tłumaczenie podczas parsingu na podstawie zejść rekurencyjnych | 351 |
| 5.5.2. Generowanie kodu w locie | 354 |
| 5.5.3. L-atrybutowane SDD i parsing LL | 356 |
| 5.5.4. Analiza wstępujaca L-atrybutowanych SDD | 361 |
| 5.5.5. Ćwiczenia do podrozdziału 5.5 | 366 |
| 5.6. Podsumowanie | 366 |
| 5.7. Bibliografia | 368 |
| 6. Generowanie kodu pośredniego 371 | |
| 6.1. Odmiany drzew składniowych | 372 |
| 6.1.1. Skierowane grafy acykliczne dla wyrażeń | 373 |
| 6.1.2. Metoda numerowania wartości do konstruowania DAG | 374 |
| 6.1.3. Ćwiczenia do podrozdziału 6.1 | 377 |
| 6.2. Kod trójadresowy | 377 |
| 6.2.1. Adresy i instrukcje | 378 |
| 6.2.2. Czwórki | 380 |
| 6.2.3. Trójki | 381 |
| 6.2.4. Forma Static Single Assignment | 383 |
| 6.2.5. Ćwiczenia do podrozdziału 6.2 | 384 |
| 6.3. Typy i deklaracje | 384 |
| 6.3.1. Wyrażenia określające typy | 385 |
| 6.3.2. Równoważność typów | 386 |
| 6.3.3. Deklaracje | 387 |
| 6.3.4. Rozmieszczenie w pamięci dla nazw lokalnych | 388 |
| 6.3.5. Sekwencje deklaracji | 390 |
| 6.3.6. Pola rekordów i klas | 391 |
| 6.3.7. Ćwiczenia do podrozdziału 6.3 | 392 |
| 6.4. Translacja wyrażeń | 393 |
| 6.4.1. Operacje wewnątrz wyrażeń | 393 |
| 6.4.2. Tłumaczenie przyrostowe395 | |
| 6.4.3. Adresowanie elementów tablic | 395 |
| 6.4.4. Tłumaczenie odwołań do tablic | 397 |
| 6.4.5. Ćwiczenia do podrozdziału 6.4 | 399 |
| 6.5. Kontrola typów | 401 |
| 6.5.1. Reguły kontroli typów | 401 |
| 6.5.2. Konwersje typów | 402 |
| 6.5.3. Przeciążanie funkcji i operatorów | 405 |
| 6.5.4. Inferencja typów i funkcje polimorficzne | 405 |
| 6.5.5. Algorytm unifikacji | 410 |
| 6.5.6. Ćwiczenia do podrozdziału 6.5 | 413 |
| 6.6. Przepływ sterowania | 413 |
| 6.6.1. Wyrażenia logiczne | 414 |
| 6.6.2. Kod krótki | 415 |
| 6.6.3. Instrukcje sterujące | 415 |
| 6.6.4. Translacja wyrażeń logicznych | 418 |
| 6.6.5. Unikanie nadmiarowych skoków goto | 420 |
| 6.6.6. Wartości logiczne i skaczący kod | 422 |
| 6.6.7. Ćwiczenia do podrozdziału 6.6 | 423 |
| 6.7. Backpatching | 424 |
| 6.7.1. Jednoprzebiegowe generowanie kodu przy użyciu poprawiania wstecznego | 425 |
| 6.7.2. Backpatching wyrażeń logicznych | 426 |
| 6.7.3. Instrukcje sterujące | 429 |
| 6.7.4. Instrukcje break, continue i goto | 431 |
| 6.7.5. Ćwiczenia do podrozdziału 6.7 | 432 |
| 6.8. Instrukcje wyboru | 433 |
| 6.8.1. Translacja instrukcji switch | 433 |
| 6.8.2. Sterowana składnia translacja instrukcji switch | 435 |
| 6.8.3. Ćwiczenia do podrozdziału 6.8 | 436 |
| 6.9. Kod pośredni dla procedur | 437 |
| 6.10. Podsumowanie | 439 |
| 6.11. Bibliografia | 440 |
| 7. Środowiska wykonania | 443 |
| 7.1. Organizacja pamięci | 443 |
| 7.1.1. Alokacje statyczne kontra dynamiczne | 445 |
| 7.2. Stosowa rezerwacja pamięci | 446 |
| 7.2.1. Drzewa aktywacji | 446 |
| 7.2.2. Rekordy aktywacji | 450 |
| 7.2.3. Sekwencje wywołujące | 452 |
| 7.2.4. Dane zmiennej długości na stosie | 455 |
| 7.2.5. Ćwiczenia do podrozdziału 7.2 | 457 |
| 7.3. Dostęp do nielokalnych danych na stosie | 458 |
| 7.3.1. Dostęp do danych bez zagnieżdżonych procedur | 459 |
| 7.3.2. Problemy dotyczące zagnieżdżonych procedur | 459 |
| 7.3.3. Język z zagnieżdżonymi deklaracjami procedur | 460 |
| 7.3.4. Głębokość zagnieżdżenia | 460 |
| 7.3.5. Wiązania dostępu | 462 |
| 7.3.6. Manipulowanie wiązaniami dostępu | 464 |
| 7.3.7. Wiązania dostępu a parametry procedur | 465 |
| 7.3.8. Tablice display | 467 |
| 7.3.9. Ćwiczenia do podrozdziału 7.3 | 469 |
| 7.4. Zarządzanie sterta | 470 |
| 7.4.1. Zarządca pamięci | 470 |
| 7.4.2. Hierarchia pamięci komputera | 471 |
| 7.4.3. Lokalność w programach | 473 |
| 7.4.4. Redukowanie fragmentacji | 476 |
| 7.4.5. Ręczne zadania dealokacji | 479 |
| 7.4.6. Ćwiczenia do podrozdziału 7.4 | 482 |
| 7.5. Wprowadzenie do odśmiecania pamięci | 482 |
| 7.5.1. Cele projektowe odśmiecaczy pamięci | 483 |
| 7.5.2. Osiągalność | 486 |
| 7.5.3. Kolektory śmieci ze zliczaniem referencji | 488 |
| 7.5.4. Ćwiczenia do podrozdziału 7.5 | 490 |
| 7.6. Wprowadzenie do odśmiecania bazujacego na śledzeniu | 491 |
| 7.6.1. Podstawowy odśmiecacz Mark and Sweep | 491 |
| 7.6.2. Podstawowa abstrakcja | 493 |
| 7.6.3. Optymalizowanie znakowania i zamiatania | 495 |
| 7.6.4. Odsmiecacze Mark and Compact | 497 |
| 7.6.5. Odśmiecacze kopiujące | 500 |
| 7.6.6. Porównanie kosztów | 502 |
| 7.6.7. Ćwiczenia do podrozdziału 7.6 | 503 |
| 7.7. Odśmiecanie z krótkimi pauzami | 504 |
| 7.7.1. Przyrostowe zbieranie danych śmieciowych | 504 |
| 7.7.2. Przyrostowa analiza osiągalności | 506 |
| 7.7.3. Założenia odśmiecaczy częściowych | 508 |
| 7.7.4. Generacyjne zbieranie danych śmieciowych | 510 |
| 7.7.5. Algorytm pociągowy | 511 |
| 7.7.6. Ćwiczenia do podrozdziału 7.7 | 515 |
| 7.8. Zaawansowane zagadnienia związane ze sprzątaniem pamięci | 516 |
| 7.8.1. Równoległe i współbieżne odśmiecanie pamięci | 517 |
| 7.8.2. Częściowa relokacja obiektów | 519 |
| 7.8.3. Konserwatywne odśmiecanie dla języków niebezpiecznych typologicznie | 520 |
| 7.8.4. Słabe referencje | 521 |
| 7.8.5. Ćwiczenia do podrozdziału 7.8 | 522 |
| 7.9. Podsumowanie | 522 |
| 7.10. Bibliografia | 525 |
| 8. Generowanie kodu 527 | |
| 8.1. Zagadnienia projektowania generatora kodu | 528 |
| 8.1.1. Dane wejściowe generatora kodu | 529 |
| 8.1.2. Program docelowy | 529 |
| 8.1.3. Wybieranie rozkazów | 531 |
| 8.1.4. Przydzielanie rejestrów | 532 |
| 8.1.5. Kolejność wykonywania | 534 |
| 8.2. Język docelowy | 534 |
| 8.2.1. Prosty model maszyny docelowej | 534 |
| 8.2.2. Koszty programu i rozkazów | 537 |
| 8.2.3. Ćwiczenia do podrozdziału 8.2 | 538 |
| 8.3. Adresy w kodzie wynikowym | 540 |
| 8.3.1. Alokacje statyczne | 541 |
| 8.3.2. Alokacja na stosie | 543 |
| 8.3.3. Adresy czasu wykonania dla nazw | 546 |
| 8.3.4. Ćwiczenia do podrozdziału 8.3 | 546 |
| 8.4. Bloki podstawowe i grafy przepływu | 547 |
| 8.4.1. Bloki podstawowe | 548 |
| 8.4.2. Informacja o następnym użyciu | 550 |
| 8.4.3. Grafy przepływu | 551 |
| 8.4.4. Reprezentacje grafów przepływu | 553 |
| 8.4.5. Pętle | 553 |
| 8.4.6. Ćwiczenia do podrozdziału 8.4 | 554 |
| 8.5. Optymalizowanie bloków podstawowych | 555 |
| 8.5.1. Reprezentacja bloków podstawowych jako skierowanych grafów acyklicznych (DAG) | 555 |
| 8.5.2. Wyszukiwanie lokalnych podwyrażeń wspólnych | 556 |
| 8.5.3. Eliminowanie martwego kodu | 558 |
| 8.5.4. Korzystanie z tożsamości algebraicznych | 558 |
| 8.5.5. Reprezentacja odwołań do tablic | 560 |
| 8.5.6. Przypisania przy użyciu wskaźników i wywołania procedur | 562 |
| 8.5.7. Odtwarzanie bloków podstawowych z DAG562 | |
| 8.5.8. Ćwiczenia do podrozdziału 8.5 | 564 |
| 8.6. Prosty generator kodu | 565 |
| 8.6.1. Deskryptory rejestrów i adresów | 566 |
| 8.6.2. Algorytm generowania kodu | 567 |
| 8.6.3. Projekt funkcji getReg | 570 |
| 8.6.4. Ćwiczenia do podrozdziału 8.6 | 572 |
| 8.7. Optymalizacja przez szparkę | 572 |
| 8.7.1. Eliminowanie nadmiarowych ładowań i zapisów | 573 |
| 8.7.2. Eliminowanie nieosiągalnego kodu | 573 |
| 8.7.3. Optymalizacje przepływu sterowania | 574 |
| 8.7.4. Uproszczenia algebraiczne i redukcje mocy operatorów | 575 |
| 8.7.5. Użycie idiomów języka maszynowego | 576 |
| 8.7.6. Ćwiczenia do podrozdziału 8.7 | 576 |
| 8.8. Przydzielanie i przypisywanie rejestrów | 576 |
| 8.8.1. Globalny przydział rejestrów | 577 |
| 8.8.2. Liczniki użyć | 577 |
| 8.8.3. Przypisywanie rejestrów dla pętli zewnętrznych | 580 |
| 8.8.4. Przydział rejestrów przez kolorowanie grafu | 580 |
| 8.8.5. Ćwiczenia do podrozdziału 8.8 | 581 |
| 8.9. Dobór rozkazów przez przekształcanie drzewa | 581 |
| 8.9.1. Schematy translacji drzew | 582 |
| 8.9.2. Generowanie kodu przez kafelkowanie drzewa wejściowego | 584 |
| 8.9.3. Dopasowywanie wzorców przez parsing | 587 |
| 8.9.4. Procedury kontroli semantycznej | 589 |
| 8.9.5. Ogólne dopasowywanie drzew | 589 |
| 8.9.6. Ćwiczenia do podrozdziału 8.9 | 591 |
| 8.10. Generowanie optymalnego kodu dla wyrażeń | 591 |
| 8.10.1. Liczby Ershova | 591 |
| 8.10.2. Generowanie kodu na podstawie etykietowanego drzewa wyrażenia | 592 |
| 8.10.3. Obliczanie wyrażeń przy niedostatecznej liczbie rejestrów | 595 |
| 8.10.4. Ćwiczenia do podrozdziału 8.10 | 597 |
| 8.11. Generowanie kodu przy użyciu programowania dynamicznego | 597 |
| 8.11.1. Przetwarzanie po kolei | 598 |
| 8.11.2. Algorytm programowania dynamicznego | 599 |
| 8.11.3. Ćwiczenia do podrozdziału 8.11 | 602 |
| 8.12. Podsumowanie | 602 |
| 8.13. Bibliografia | 603 |
| 9. Optymalizacje niezależne od typu procesora 607 | |
| 9.1. Główne źródła optymalizacji | 608 |
| 9.1.1. Przyczyny nadmiarowości | 608 |
| 9.1.2. Bieżący przykład: Quicksort | 609 |
| 9.1.3. Transformacje zachowujące semantykę | 611 |
| 9.1.4. Globalne wspólne podwyrażenia | 612 |
| 9.1.5. Propagacja kopii | 614 |
| 9.1.6. Usuwanie martwego kodu | 615 |
| 9.1.7. Przemieszczenie kodu | 616 |
| 9.1.8. Zmienne indukcyjne i redukcja mocy | 616 |
| 9.1.9. Ćwiczenia do podrozdziału 9.1 | 619 |
| 9.2. Wprowadzenie do analizy przepływu danych | 621 |
| 9.2.1. Abstrakcja przepływu danych | 621 |
| 9.2.2. Schemat analizy przepływu danych | 623 |
| 9.2.3. Schematy przepływu danych dla bloków podstawowych | 625 |
| 9.2.4. Definicje osiągające | 626 |
| 9.2.5. Analiza żywotności zmiennych | 633 |
| 9.2.6. Wyrażenia dostępne | 635 |
| 9.2.7. Podsumowanie podrozdziału 9.2 | 639 |
| 9.2.8. Ćwiczenia do podrozdziału 9.2 | 640 |
| 9.3. Podstawy analizy przepływu danych | 642 |
| 9.3.1. Półkraty | 643 |
| 9.3.2. Funkcje transferu | 648 |
| 9.3.3. Algorytm iteracyjny dla ogólnego szkieletu | 650 |
| 9.3.4. Sens rozwiązania przepływu danych | 653 |
| 9.3.5. Ćwiczenia do podrozdziału 9.3 | 656 |
| 9.4. Propagacja stałych | 657 |
| 9.4.1. Wartości przepływu danych dla szkieletu propagacji stałych | 658 |
| 9.4.2. Funkcja spotkania dla szkieletu propagacji stałych | 659 |
| 9.4.3. Funkcje transferu dla szkieletu propagacji stałych | 659 |
| 9.4.4. Monotoniczność szkieletu propagacji stałych | 660 |
| 9.4.5. Niedystrybutywność szkieletu propagacji stałych | 660 |
| 9.4.6. Interpretacja wyników | 662 |
| 9.4.7. Ćwiczenia do podrozdziału 9.4 | 663 |
| 9.5. Eliminowanie częściowej nadmiarowości | 664 |
| 9.5.1. Źródła nadmiarowości | 665 |
| 9.5.2. Czy możliwe jest wyeliminowanie całej nadmiarowości? | 667 |
| 9.5.3. Problem opóźniającego przemieszczenia kodu | 669 |
| 9.5.4. Częściowa nadmiarowość | 670 |
| 9.5.5. Antycypowanie wyrażeń | 670 |
| 9.5.6. Algorytm opóźniającego przemieszczenia kodu | 671 |
| 9.5.7. Ćwiczenia do podrozdziału 9.5 | 681 |
| 9.6. Pętle w grafach przepływu | 682 |
| 9.6.1. Dominatory | 682 |
| 9.6.2. Porządkowanie w głąb | 686 |
| 9.6.3. Krawędzie w drzewie rozpinającym w głąb | 688 |
| 9.6.4. Krawędzie zwrotne i redukowalność | 690 |
| 9.6.5. Głębokość grafu przepływu | 691 |
| 9.6.6. Pętle naturalne | 691 |
| 9.6.7. Tempo zbieżności iteracyjnych algorytmów przepływu danych | 693 |
| 9.6.8. Ćwiczenia do podrozdziału 9.6 | 696 |
| 9.7. Analiza oparta na regionach | 698 |
| 9.7.1. Regiony | 699 |
| 9.7.2. Hierarchie regionów dla redukowalnych grafów przepływu | 700 |
| 9.7.3. Wprowadzenie do analizy opartej na regionach | 703 |
| 9.7.4. Konieczne założenia dotyczące funkcji transferu | 704 |
| 9.7.5. Algorytm dla analizy opartej na regionach | 706 |
| 9.7.6. Obsługa nieredukowalnych grafów przepływu | 710 |
| 9.7.7. Ćwiczenia do podrozdziału 9.7 | 712 |
| 9.8. Analiza symboliczna | 713 |
| 9.8.1. Afiniczne wyrażenia zmiennych referencyjnych | 713 |
| 9.8.2. Formułowanie problemu przepływu danych | 717 |
| 9.8.3. Analiza symboliczna oparta na regionach | 720 |
| 9.8.4. Ćwiczenia do podrozdziału 9.8 | 725 |
| 9.9. Podsumowanie | 726 |
| 9.10. Bibliografia | 729 |
| 10. Równoległość na poziomie instrukcji 733 | |
| 10.1. Architektury procesorów | 734 |
| 10.1.1. Potoki instrukcji i opóźnienia rozgałęzień | 734 |
| 10.1.2. Wykonywanie potokowe | 735 |
| 10.1.3. Zlecanie wielu instrukcji | 736 |
| 10.2. Ograniczenia szeregowania wykonania kodu | 737 |
| 10.2.1. Zależność danych | 737 |
| 10.2.2. Wyszukiwanie zależności miedzy dostępami do pamięci | 738 |
| 10.2.3. Kompromis miedzy wykorzystaniem rejestrów i równoległością | 740 |
| 10.2.4. Kolejność faz alokacji rejestrów i szeregowania kodu | 742 |
| 10.2.5. Zależność sterowania | 743 |
| 10.2.6. Wsparcie dla wykonania spekulatywnego | 744 |
| 10.2.7. Podstawowy model maszyny | 746 |
| 10.2.8. Ćwiczenia do podrozdziału 10.2 | 747 |
| 10.3. Szeregowanie wykonania dla bloków podstawowych | 749 |
| 10.3.1. Grafy zależności danych | 749 |
| 10.3.2. Szeregowanie listowe bloków podstawowych | 751 |
| 10.3.3. Priorytetowy porządek topologiczny | 752 |
| 10.3.4. Ćwiczenia do podrozdziału 10.3 | 753 |
| 10.4. Globalne szeregowanie kodu | 754 |
| 10.4.1. Elementarne przemieszczanie kodu | 755 |
| 10.4.2. Przemieszczanie kodu w górę | 757 |
| 10.4.3. Przemieszczanie kodu w dół | 758 |
| 10.4.4. Uaktualnianie zależności danych | 760 |
| 10.4.5. Globalne algorytmy szeregowania | 760 |
| 10.4.6. Zaawansowane techniki przemieszczania kodu | 764 |
| 10.4.7. Interakcja ze schedulerami dynamicznymi | 765 |
| 10.4.8. Ćwiczenia do podrozdziału 10.4 | 765 |
| 10.5. Potokowanie programowe | 766 |
| 10.5.1. Wprowadzenie | 766 |
| 10.5.2. Potokowanie programowe dla pętli | 769 |
| 10.5.3. Alokacja rejestrów i generowanie kodu | 771 |
| 10.5.4. Petle Do-Across | 772 |
| 10.5.5. Cele i ograniczenia potokowania programowego | 773 |
| 10.5.6. Algorytm potokowania programowego | 777 |
| 10.5.7. Szeregowanie acyklicznych grafów zależności danych | 778 |
| 10.5.8. Szeregowanie cyklicznych grafów zależności | 779 |
| 10.5.9. Usprawnienia algorytmów potokowania | 786 |
| 10.5.10.Modularne rozszerzanie zmiennych | 787 |
| 10.5.11. Instrukcje warunkowe | 790 |
| 10.5.12.Wsparcie sprzętowe dla potokowania programowego | 791 |
| 10.5.13. Ćwiczenia do podrozdziału 10.5 | 791 |
| 10.6. Podsumowanie | 793 |
| 10.7. Bibliografia | 795 |
| 11. Optymalizacja pod katem równoległości i lokalności 797 | |
| 11.1. Pojęcia podstawowe | 800 |
| 11.1.1. Wieloprocesorowość | 800 |
| 11.1.2. Równoległość w aplikacjach | 802 |
| 11.1.3. Równoległość na poziomie pętli | 804 |
| 11.1.4. Lokalność danych | 805 |
| 11.1.5. Wprowadzenie do teorii transformacji afinicznych | 807 |
| 11.2. Mnożenie macierzy: pogłębiony przykład | 811 |
| 11.2.1. Algorytm mnożenia macierzy | 812 |
| 11.2.2. Optymalizacje | 814 |
| 11.2.3. Interferencja cache | 817 |
| 11.2.4. Ćwiczenia do podrozdziału 11.2 | 818 |
| 11.3. Przestrzenie iteracji | 818 |
| 11.3.1. Konstruowanie przestrzeni iteracji z gniazda pętli | 818 |
| 11.3.2. Kolejność wykonywania gniazd pętli | 821 |
| 11.3.3. Postać macierzowa nierówności | 821 |
| 11.3.4. Uwzględnianie stałych symbolicznych | 822 |
| 11.3.5. Kontrolowanie kolejności wykonania | 823 |
| 11.3.6. Zmiana osi | 827 |
| 11.3.7. Ćwiczenia do podrozdziału 11.3 | 829 |
| 11.4. Afiniczne indeksy tablic | 831 |
| 11.4.1. Dostępy afiniczne | 831 |
| 11.4.2. Dostęp afiniczny i nieafiniczny w praktyce | 832 |
| 11.4.3. Ćwiczenia do podrozdziału 11.4 | 833 |
| 11.5. Ponowne użycie danych | 834 |
| 11.5.1. Rodzaje ponownego użycia | 835 |
| 11.5.2. Samodzielne ponowne użycie | 836 |
| 11.5.3. Samodzielne przestrzenne użycie ponowne | 839 |
| 11.5.4. Grupowe użycie ponowne | 841 |
| 11.5.5. Ćwiczenia do podrozdziału 11.5 | 844 |
| 11.6. Analiza zależności danych dla tablicy | 845 |
| 11.6.1. Definicja zależności danych miedzy dostępami do tablic | 846 |
| 11.6.2. Programowanie całkowitoliczbowe (liniowe) | 847 |
| 11.6.3. Test NWD | 848 |
| 11.6.4. Heurystyki dla całkowitoliczbowego programowania liniowego | 850 |
| 11.6.5. Rozwiązywanie ogólnych problemów programowania całkowitoliczbowego | 854 |
| 11.6.6. Podsumowanie podrozdziału 11.6 | 856 |
| 11.6.7. Ćwiczenia do podrozdziału 11.6 | 856 |
| 11.7. Wyszukiwanie równoległości niewymagającej synchronizacji | 858 |
| 11.7.1. Przykład wstępny | 858 |
| 11.7.2. Afiniczne podziały w przestrzeni | 861 |
| 11.7.3. Ograniczenia podziału w przestrzeni | 862 |
| 11.7.4. Rozwiązywanie ograniczeń podziału w przestrzeni | 865 |
| 11.7.5. Prosty algorytm generowania kodu | 869 |
| 11.7.6. Eliminowanie pustych iteracji | 872 |
| 11.7.7. Eliminowanie warunków z najbardziej wewnętrznych pętli | 874 |
| 11.7.8. Transformacje kodu źródłowego | 877 |
| 11.7.9. Ćwiczenia do podrozdziału 11.7 | 881 |
| 11.8. Synchronizacja miedzy pętlami równoległymi | 883 |
| 11.8.1. Stała liczba operacji synchronizujących | 883 |
| 11.8.2. Grafy zależności programu | 884 |
| 11.8.3. Czas hierarchiczny | 887 |
| 11.8.4. Algorytm zrównoleglania | 889 |
| 11.8.5. Ćwiczenia do podrozdziału 11.8 | 890 |
| 11.9. Potokowanie | 891 |
| 11.9.1. Czym jest potokowanie? | 891 |
| 11.9.2. Sukcesywna nadrelaksacja (Successive Over-Relaxation – SOR): przykład praktyczny | 893 |
| 11.9.3. W pełni przestawialne petle | 894 |
| 11.9.4. Potokowanie w pełni przestawialnych pętli | 896 |
| 11.9.5. Teoria ogólna | 897 |
| 11.9.6. Ograniczenia podziału w czasie | 898 |
| 11.9.7. Rozwiązywanie ograniczeń podziału w czasie przy użyciu lematu Farkasa | 902 |
| 11.9.8. Transformacje kodu | 905 |
| 11.9.9. Równoległość z minimalna synchronizacja | 909 |
| 11.9.10. Ćwiczenia do podrozdziału 11.9 | 912 |
| 11.10.Optymalizowanie lokalności | 914 |
| 11.10.1. Lokalność czasowa danych obliczanych | 914 |
| 11.10.2.Kontrakcja tablic | 915 |
| 11.10.3. Przeplatanie partycji | 918 |
| 11.10.4. Zbieranie wszystkiego razem | 922 |
| 11.10.5. Ćwiczenia do podrozdziału 11.10 | 923 |
| 11.11.Inne zastosowania transformacji afinicznych | 924 |
| 11.11.1. Maszyny z pamięcią rozproszona | 924 |
| 11.11.2. Procesory z jednoczesnym zlecaniem rozkazów | 925 |
| 11.11.3. Maszyny wektorowe i SIMD | 925 |
| 11.11.4.Wczesny odczyt danych | 926 |
| 11.12.Podsumowanie | 928 |
| 11.13.Bibliografia | 930 |
| 12. Analiza międzyproceduralna 935 | |
| 12.1. Podstawowe pojęcia | 936 |
| 12.1.1. Grafy wywołań | 936 |
| 12.1.2. Wrażliwość na kontekst | 938 |
| 12.1.3. Łańcuchy wywołań | 940 |
| 12.1.4. Analiza kontekstowa oparta na klonowaniu | 942 |
| 12.1.5. Analiza kontekstowa oparta na podsumowaniu | 944 |
| 12.1.6. Ćwiczenia do podrozdziału 12.1 | 946 |
| 12.2. Dlaczego potrzebna jest analiza międzyproceduralna? | 948 |
| 12.2.1. Wywołania metod wirtualnych | 948 |
| 12.2.2. Analiza aliasowania wskaźników | 949 |
| 12.2.3. Zrównoleglanie | 949 |
| 12.2.4. Wykrywanie błędów i podatności na ataki | 949 |
| 12.2.5. SQL injection | 950 |
| 12.2.6. Przepełnienie bufora | 952 |
| 12.3. Logiczna reprezentacja przepływu danych | 953 |
| 12.3.1. Wprowadzenie do Datalogu | 954 |
| 12.3.2. Reguły Datalogu | 955 |
| 12.3.3. Predykaty intensjonalne i ekstensjonalne | 956 |
| 12.3.4. Wykonywanie programów Datalogu | 959 |
| 12.3.5. Inkrementalne przetwarzanie programów Datalogu | 960 |
| 12.3.6. Problematyczne reguły Datalogu | 963 |
| 12.3.7. Ćwiczenia do podrozdziału 12.3 | 964 |
| 12.4. Prosty algorytm analizy wskaźników | 966 |
| 12.4.1. Dlaczego analiza wskaźników jest trudna | 966 |
| 12.4.2. Model dla wskaźników i referencji | 967 |
| 12.4.3. Niewrażliwość na przepływ sterowania | 968 |
| 12.4.4. Sformułowanie problemu w Datalogu | 969 |
| 12.4.5. Wykorzystanie informacji o typach | 971 |
| 12.4.6. Ćwiczenia do podrozdziału 12.4 | 973 |
| 12.5. Analiza międzyproceduralna niewrażliwa na kontekst | 974 |
| 12.5.1. Efekty wywołania metody | 974 |
| 12.5.2. Odkrywanie grafu wywołań w Datalogu | 976 |
| 12.5.3. Dynamiczne ładowanie i refleksja | 977 |
| 12.5.4. Ćwiczenie do podrozdziału 12.5 | 978 |
| 12.6. Analiza wskaźników z uwzględnieniem kontekstu | 978 |
| 12.6.1. Konteksty i łańcuchy wywołań | 979 |
| 12.6.2. Dodawanie kontekstu do reguł Datalogu | 982 |
| 12.6.3. Dodatkowe spostrzeżenia dotyczące wrażliwości | 983 |
| 12.6.4. Ćwiczenia do podrozdziału 12.6 | 983 |
| 12.7. Implementacja Datalogu przez BDD | 983 |
| 12.7.1. Binarne diagramy decyzyjne | 984 |
| 12.7.2. Przekształcenia BDD | 986 |
| 12.7.3. Reprezentowanie relacji przy uzyciu BDD | 987 |
| 12.7.4. Operacje na relacjach jako operacje na BDD | 988 |
| 12.7.5. Wykorzystanie BDD w analizie miejsc wskazywanych | 991 |
| 12.7.6. Ćwiczenia do podrozdziału 12.7 | 991 |
| 12.8. Podsumowanie | 992 |
| 12.9. Bibliografia | 995 |
| A. Pełny front-end kompilatora 999 | |
| A.1. Język źródłowy | 999 |
| A.2. Main | 1001 |
| A.3. Analizator leksykalny | 1001 |
| A.4. Tabele symboli oraz typy | 1004 |
| A.5. Kod pośredni dla wyrażeń | 1005 |
| A.6. Kod skaczący dla wyrażeń logicznych | 1008 |
| A.7. Kod pośredni dla instrukcji | 1012 |
| A.8. Parser | 1016 |
| A.9. Budowanie front-endu kompilatora | 1021 |
| B. Znajdowanie rozwiązań liniowo niezależnych 1023 | |
| Indeks | 1027 |
KUP NA PREZENT
Kompilatory
199,00 zł
Uzupełnij informacje na temat odbiorcy.
Produkt został pomyślnie dodany do koszyka.
Nieudana próba zakupu produktu. Spróbuj jeszcze raz.
Wypożyczaj w abonamencie!
Już od 2,66 zł za ebooka
