Polski
ebook
Kompilatory Reguły, metody i narzędzia
Alfred V. Aho, Jeffrey Ullman, Monica S. Lam, Ravi Sethi
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.
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.
Opinie:
Wystaw opinię
Opinie, recenzje, testy:
Ten produkt nie ma jeszcze opinii
Twoja opinia
aby wystawić opinię.
Wydawnictwo: Wydawnictwo Naukowe PWN
Koszty dostawy:
- Przesyłka email dla e-book 0.00 zł brutto
Zapytaj o produkt
Opis produktu
- Tytuł
- Kompilatory
- Podtytuł
- Reguły, metody i narzędzia
- Autorzy
- Alfred V. Aho, Jeffrey Ullman, Monica S. Lam, Ravi Sethi
- Język
- polski
- Wydawnictwo
- Wydawnictwo Naukowe PWN
- Tłumaczenie
- Marek Włodarz
- ISBN
- 978-83-01-20381-8
- Rok wydania
- 2019 Warszawa
- Wydanie
- 2
- Liczba stron
- 1040
- Format
- 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
Prezentacja wideo produktu: Kompilatory Reguły, metody i narzędzia
Pobierz fragment
