Opis
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. Spis treściPrzedmowa 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 tok