Literatura
Wprowadzenie
A.V. Aho, R. Sethi, J.D. Ullman,
Języki formalne i techniki translacji - Wykład 1
Kompilatory. Reguły, metody i narzędzia,
WNT, Warszawa 2002, (ISBN: 83-204-2656-1)
Maciek Gębala
J.E. Hopcroft, J.D. Ullman,
Wprowadzenie do teorii automatów, języków i obliczeń,
WNT, Warszawa 1994 (ISBN 83-01-11298-0)
20 lutego 2013
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Proces translacji Kompilacja typu analiza-synteza
Kompilator
Program czytający kod napisany w języku z
ródłowym i tłumaczący go
Analiza  rozłożenie programu na części składowe i stworzenie
na równoważny kod w języku wynikowym.
jego pośredniej reprezentacji.
Synteza  przekształcenie reprezentacji pośredniej na program
Program Program
wynikowy.
z
ródłowy - Kompilator - wynikowy
�!
Komunikaty o błędach
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Przykłady narzędzi dokonujących analizy Przykłady programów przypominających kompilatory
Edytory strukturalne
Formatory tekstu
Formatory kodu programu
Kompilatory do układów scalonych
Kontrolery statyczne
Interpretery zapytań
Interpretery
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Kontekst kompilatora Fazy kompilatora
Szkieletowy program z
ródłowy
Program z
ródłowy
�!
�!
Preprocesor
Analizator leksykalny
�!
�!
Program z
ródłowy
Analizator składniowy
�!
�!
Kompilator
Zarządzanie �! Analizator semantyczny Obsługa
�!
tablicą �! błędów
Program w asemblerze
symboli �! Generator kodu pośredniego
�!
�!
Assembler
Optymalizacja kodu
�!
�!
Przemieszczalny kod maszynowy
Generator kodu
�!
�!
Konsolidator �! Biblioteki
Program wynikowy
�!
Bezwzględny kod maszynowy
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Fazy kompilatora Fazy kompilatora
Analiza leksykalna
Ciąg znaków składający się na program z
ródłowy jest przekształcany
Zarządzanie tablicą symboli
w ciąg tokenów (symboli leksykalnych).
Zapamiętywanie identyfikatorów używanych w programie z
ródłowym
i zbieranie informacji o różnych atrybutach tych identyfikatorach.
Analiza składniowa
Grupowanie symboli leksykalnych programu z
ródłowego w wyrażenia
Wykrywanie i zgłaszanie błędów
gramatyczne (tworzenie drzewa wyprowadzenia).
Obsługa błędów w taki sposób aby nie przerywać kompilacji po
pierwszym błędzie. Błędy wykrywane są w fazie analizy.
Analiza semantyczna
Kontrola programu pod względem poprawności semantycznej (np.
kontrola typów) i zbieranie informacji do generowania kodu.
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Fazy kompilatora Grupowanie faz
Generowanie kodu pośredniego
Przód kompilatora
Reprezentacja programu dla pewnej abstrakcyjnej maszyny (łatwa do
Fazy zależne przede wszystkim od języka z
ródłowego i praktycznie
utworzenia i tłumaczenia na program wynikowy).
niezależne od języka wynikowego. Zwykle składa się z analizatora
leksykalnego, składniowego i semantycznego oraz tablicy symboli,
generatora kodu pośredniego i obsługi błędów.
Optymalizacja kodu
Poprawienie kodu pośredniego w taki sposób aby kod maszynowy
Tył kompilatora
działał szybciej.
Fazy zależne od maszyny docelowej a niezależne od języka
z
ródłowego. Zwykle składa się z optymalizacji i generowania kodu
Generowanie kodu wynikowego
z tablicą symboli i obsługą błędów.
Generowanie kodu wynikowego, najczęściej w asemblerze.
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Języki formalne Deterministyczny Automat Skończony (DFA)
Deterministyczny automat skończony to uporządkowana piątka
(Q, Ł, �, q0, F ) gdzie
Q  skończony zbiór stanów,
Ł  skończony alfabet wejściowy,
Podstawowe definicje
�  funkcja przejścia postaci Q � Ł Q,
Alfabet (Ł)  skończony zbiór symboli.
q0  stan początkowy,
Słowo  skończony ciąg symboli z alfabetu.
F ą" Q  zbiór stanów akceptujących.
Język  zbiór słów nad danym alfabetem (" - język pusty).
�  słowo puste.
Notacja
Ć
� możemy rozszerzyć do � : Q � Ł" Q zgodną z definicją
Ć Ć Ć
rekurencyjną �(q, �) = q i �(q, wa) = �(�(q, w), a).
Ć
Automat akceptuje słowo w jeśli �(q0, w) " F .
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Przykład Niedeterministyczny Automat Skończony (NFA)
M = ({q0, q1, q2, q3}, {0, 1}, �, q0, {q0})
Modyfikacja
� 0 1
Istnieje zero, jedno lub więcej przejść ze stanu przy tym samym
q0 q2 q1
symbolu wejściowym.
q1 q3 q0
� : Q � Ł 2Q
q2 q0 q3
q3 q1 q2
Automat niedeterministyczny akceptuje słowo w jeżeli istnieje
odpowiadający mu ciąg przejść ze stanu początkowego do stanu
akceptującego.
Rysunek i analiza na tablicy
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Przykład Niedeterministyczny Automat Skończony z �-ruchami
(NFA�)
M = ({q0, q1, q2, q3, q4}, {0, 1}, �, q0, {q2, q4})
� 0 1
q0 {q0, q3} {q0, q1}
q1 " {q2}
Dopuszczamy przejścia między stanami bez symboli wejściowych.
q2 {q2} {q2}
q3 {q4} "
� : Q � (Ł *" {�}) 2Q
q4 {q4} {q4}
Rysunek i analiza na tablicy
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie
Wyrażenia regularne (RE) Przykład
Niech L, L1, L2  języki nad alfabetem Ł. Wtedy
L1L2 = { xy : x " L1 '" y " L2 } (złożenie, konkatenacja)
L0 = {�}
Li+1 = LLi dla i > 0

" "

L" = Li (domknięcie Kleene ego) L+ = Li
(0 + 1)"(00 + 11)(0 + 1)"
i=0 i=1
(� + 0 + 00)[(1 + 11)(0 + 00)]"(� + 1 + 11)
Definicja
1
Wyrażenia regularne ", �, a reprezentują odpowiednio język
pusty, {�}, {a} dla a " Ł.
2
Jeżeli r i s są wyrażeniami regularnymi reprezentującymi
odpowiednio języki R i S to
(r + s) reprezentuje język R *" S,
(rs) reprezentuje język RS,
r" reprezentuje język R".
Maciek Gębala Wprowadzenie Maciek Gębala Wprowadzenie