Języki formalne
Podsumowanie wykładu
Hierarchia Chomsky ego
Języki formalne i techniki translacji - Wykład 15
Gramatyki typu 3 - regularne
Gramatyki typu 2 - bezkontekstowe
Maciek Gębala
Gramatyki typu 1 - kontekstowe
Gramatyki typu 0 - dowolne
12 czerwca 2013
Maciek Gębala Podsumowanie wykładu Maciek Gębala Podsumowanie wykładu
Języki formalne Kontekst kompilatora
Szkieletowy program z
ródłowy
Języki regularne
�!
Automaty skończone: deterministyczny (DFA),
Preprocesor
niedeterministyczny (NFA) i niedeterministyczny z �-ruchami
�!
(NFA�).
Program z
ródłowy
Wyrażenia regularne (RE).
�!
Gramatyki regularne. Kompilator
�!
Własności języków regularnych: operacje mnogościowe, lemat o
Program w asemblerze
pompowaniu.
�!
Assembler
Języki bezkontekstowe
�!
Gramatyki bezkontekstowe.
Przemieszczalny kod maszynowy
�!
Automaty ze stosem (PDA) - niedeterministyczne.
Konsolidator �! Biblioteki
Własności języków bezkontekstowych: operacje mnogościowe,
�!
lemat o pompowaniu, lemat Ogdena.
Bezwzględny kod maszynowy
Maciek Gębala Podsumowanie wykładu Maciek Gębala Podsumowanie wykładu
Fazy kompilatora Fazy kompilatora
Program z
ródłowy
Analiza leksykalna
�!
Analizator leksykalny
Ciąg znaków składający się na program z
ródłowy jest przekształcany
�!
w ciąg tokenów (symboli leksykalnych).
Analizator składniowy
�!
Analiza składniowa
Zarządzanie �! Analizator semantyczny Obsługa
Grupowanie symboli leksykalnych programu z
ródłowego w wyrażenia
tablicą �! błędów
gramatyczne (tworzenie drzewa wyprowadzenia).
symboli �! Generator kodu pośredniego
�!
Zstępujące (top-down)  analizatory przewidujące i gramatyki
Optymalizacja kodu
typu LL(k).
�!
Wstępujące (bottom-up)  analizatory redukujące, gramatyki
Generator kodu
operatorowe i LR(k), analizatory SLR, LR(1) i LALR.
�!
Program wynikowy
Maciek Gębala Podsumowanie wykładu Maciek Gębala Podsumowanie wykładu
Fazy kompilatora Fazy kompilatora
Analiza semantyczna
Kontrola programu pod względem poprawności semantycznej (np.
Optymalizacja kodu
kontrola typów) i zbieranie informacji do generowania kodu.
Poprawienie kodu pośredniego w taki sposób aby kod maszynowy
Atrybuty syntetyzowane i dziedziczone  definicje S-atrybutowe
działał szybciej.
i L-atrybutowe.
Graf przepływu.
Zależności kontekstowe.
Przydział rejestrów.
Generowanie kodu pośredniego
Generowanie kodu wynikowego
Reprezentacja programu dla pewnej abstrakcyjnej maszyny (łatwa do
Generowanie kodu wynikowego, najczęściej w asemblerze.
utworzenia i tłumaczenia na program wynikowy).
Translacja sterowana składnią.
Kod trójadresowy.
Maciek Gębala Podsumowanie wykładu Maciek Gębala Podsumowanie wykładu
Fazy kompilatora Grupowanie faz
Zarządzanie tablicą symboli
Przód kompilatora
Zapamiętywanie identyfikatorów używanych w programie z
ródłowym
Fazy zależne przede wszystkim od języka z
ródłowego i praktycznie
i zbieranie informacji o różnych atrybutach tych identyfikatorów.
niezależne od języka wynikowego. Zwykle składa się z analizatora
leksykalnego, składniowego i semantycznego oraz tablicy symboli,
Wykrywanie i zgłaszanie błędów
generatora kodu pośredniego i obsługi błędów.
Obsługa błędów w taki sposób aby nie przerywać kompilacji po
pierwszym błędzie. Błędy wykrywane są w fazie analizy.
Tył kompilatora
Tryb paniki.
Fazy zależne od maszyny docelowej a niezależne od języka
Poziom frazy.
z
ródłowego. Zwykle składa się z optymalizacji i generowania kodu
Produkcje dla błędów. z tablicą symboli i obsługą błędów.
Korekta globalna.
Maciek Gębala Podsumowanie wykładu Maciek Gębala Podsumowanie wykładu
Narzędzia
Schematy analizatorów
KONIEC
LEX - analiza leksykalna.
BISON - analiza składniowa, translacja sterowana składnią.
Maciek Gębala Podsumowanie wykładu Maciek Gębala Podsumowanie wykładu