Projekt kompilatora - szybki przewodnik

Komputery to wyważona mieszanka oprogramowania i sprzętu. Sprzęt to tylko element mechanicznego urządzenia, którego funkcje są kontrolowane przez kompatybilne oprogramowanie. Sprzęt rozumie instrukcje w postaci opłaty elektronicznej, która jest odpowiednikiem języka binarnego w programowaniu. Język binarny ma tylko dwa alfabety, 0 i 1. Aby poinstruować, kody sprzętowe muszą być zapisane w formacie binarnym, czyli po prostu ciągiem jedynek i zer. Pisanie takich kodów byłoby trudnym i uciążliwym zadaniem dla programistów komputerowych, dlatego mamy kompilatory do pisania takich kodów.

System przetwarzania języka

Dowiedzieliśmy się, że każdy system komputerowy składa się ze sprzętu i oprogramowania. Sprzęt rozumie język, którego ludzie nie rozumieją. Dlatego piszemy programy w języku wysokiego poziomu, który jest nam łatwiejszy do zrozumienia i zapamiętania. Programy te są następnie wprowadzane do szeregu narzędzi i składników systemu operacyjnego, aby uzyskać żądany kod, który może być używany przez maszynę. Jest to znane jako system przetwarzania języka.

Język wysokiego poziomu jest konwertowany na język binarny w różnych fazach. ZAcompilerjest programem, który konwertuje język wysokiego poziomu na język asemblera. Podobnie plikassembler jest programem, który konwertuje język asemblera na język maszynowy.

Najpierw zrozumiemy, jak program wykorzystujący kompilator C jest wykonywany na maszynie hosta.

  • Użytkownik pisze program w języku C (język wysokiego poziomu).

  • Kompilator C, kompiluje program i tłumaczy go na program asemblera (język niskiego poziomu).

  • Następnie asembler tłumaczy program asemblera na kod maszynowy (obiekt).

  • Narzędzie konsolidatora służy do łączenia wszystkich części programu razem w celu wykonania (wykonywalny kod maszynowy).

  • Program ładujący ładuje je wszystkie do pamięci, a następnie program jest wykonywany.

Zanim zagłębimy się bezpośrednio w koncepcje kompilatorów, powinniśmy zrozumieć kilka innych narzędzi, które ściśle współpracują z kompilatorami.

Preprocesor

Preprocesor, ogólnie uważany za część kompilatora, to narzędzie, które generuje dane wejściowe dla kompilatorów. Zajmuje się przetwarzaniem makr, rozszerzaniem, włączaniem plików, rozszerzaniem języka itp.

Interpretator

Interpreter, podobnie jak kompilator, tłumaczy język wysokiego poziomu na język maszynowy niskiego poziomu. Różnica polega na sposobie, w jaki odczytują kod źródłowy lub dane wejściowe. Kompilator odczytuje od razu cały kod źródłowy, tworzy tokeny, sprawdza semantykę, generuje kod pośredni, wykonuje cały program i może obejmować wiele przebiegów. W przeciwieństwie do tego interpreter odczytuje instrukcję z wejścia, konwertuje ją na kod pośredni, wykonuje ją, a następnie przyjmuje kolejną instrukcję w kolejności. Jeśli wystąpi błąd, interpreter zatrzymuje wykonywanie i zgłasza go. podczas gdy kompilator czyta cały program, nawet jeśli napotka kilka błędów.

Monter

Asembler tłumaczy programy w języku asemblera na kod maszynowy. Wyjście asemblera nazywa się plikiem obiektowym, który zawiera kombinację instrukcji maszynowych oraz dane wymagane do umieszczenia tych instrukcji w pamięci.

Łącznik

Linker to program komputerowy, który łączy i scala różne pliki obiektowe w celu utworzenia pliku wykonywalnego. Wszystkie te pliki mogły zostać skompilowane przez oddzielne asemblery. Głównym zadaniem konsolidatora jest wyszukanie i zlokalizowanie modułu / procedur w programie, do którego się odwołuje, oraz określenie lokalizacji pamięci, do której te kody zostaną załadowane, dzięki czemu instrukcja programu będzie miała odniesienia bezwzględne.

Ładowarka

Loader jest częścią systemu operacyjnego i odpowiada za ładowanie plików wykonywalnych do pamięci i ich wykonywanie. Oblicza rozmiar programu (instrukcje i dane) i tworzy dla niego miejsce w pamięci. Inicjuje różne rejestry, aby zainicjować wykonanie.

Kompilator krzyżowy

Kompilator działający na platformie (A) i zdolny do generowania kodu wykonywalnego dla platformy (B) nazywany jest kompilatorem krzyżowym.

Kompilator źródła do źródła

Kompilator, który pobiera kod źródłowy jednego języka programowania i tłumaczy go na kod źródłowy innego języka programowania, nazywany jest kompilatorem źródłowym.

Architektura kompilatora

Kompilator można ogólnie podzielić na dwie fazy w zależności od sposobu kompilacji.

Faza analizy

Znany jako front-end kompilatora, analysis kompilator odczytuje program źródłowy, dzieli go na części podstawowe, a następnie sprawdza błędy leksykalne, gramatyczne i składniowe. Faza analizy generuje pośrednią reprezentację programu źródłowego i tabelę symboli, która powinna zostać przekazana do fazy syntezy jako wejście .

Faza syntezy

Znany jako zaplecze kompilatora, plik synthesis phase generuje program docelowy za pomocą reprezentacji pośredniego kodu źródłowego i tablicy symboli.

Kompilator może mieć wiele faz i przebiegów.

  • Pass : Przebieg odnosi się do przejścia kompilatora przez cały program.

  • Phase: Faza kompilatora jest rozróżnialnym etapem, który pobiera dane wejściowe z poprzedniego etapu, przetwarza i dostarcza dane wyjściowe, które mogą być użyte jako dane wejściowe dla następnego etapu. Pas może mieć więcej niż jedną fazę.

Fazy ​​kompilatora

Proces kompilacji to sekwencja różnych faz. Każda faza pobiera dane wejściowe z poprzedniego etapu, ma własną reprezentację programu źródłowego i przekazuje dane wyjściowe do następnej fazy kompilatora. Rozumiemy fazy pracy kompilatora.

Analiza leksykalna

Pierwsza faza skanera działa jako skaner tekstu. Ta faza skanuje kod źródłowy jako strumień znaków i konwertuje go na zrozumiałe leksemy. Analizator leksykalny przedstawia te leksemy w postaci tokenów jako:

<token-name, attribute-value>

Analiza składni

Następna faza nazywa się analizą składni lub parsing. Pobiera token wygenerowany przez analizę leksykalną jako dane wejściowe i generuje drzewo parsowania (lub drzewo składniowe). W tej fazie aranżacje tokenów są sprawdzane z gramatyką kodu źródłowego, tj. Parser sprawdza, czy wyrażenie złożone przez tokeny jest poprawne składniowo.

Analiza semantyczna

Analiza semantyczna sprawdza, czy skonstruowane drzewo parsowania jest zgodne z regułami języka. Na przykład przypisanie wartości odbywa się między zgodnymi typami danych i dodaniem ciągu do liczby całkowitej. Ponadto analizator semantyczny śledzi identyfikatory, ich typy i wyrażenia; czy identyfikatory są zadeklarowane przed użyciem, czy nie itp. Analizator semantyczny generuje drzewo składni z adnotacjami jako wyjście.

Generowanie kodu pośredniego

Po analizie semantycznej kompilator generuje kod pośredni kodu źródłowego dla maszyny docelowej. Reprezentuje program dla jakiejś abstrakcyjnej maszyny. Znajduje się pomiędzy językiem wysokiego poziomu a językiem maszynowym. Ten kod pośredni powinien być generowany w taki sposób, aby był łatwiejszy do przetłumaczenia na docelowy kod maszynowy.

Optymalizacja kodu

W następnej fazie następuje optymalizacja kodu pośredniego. Optymalizację można założyć jako coś, co usuwa niepotrzebne linie kodu i porządkuje sekwencję instrukcji w celu przyspieszenia wykonywania programu bez marnowania zasobów (procesor, pamięć).

Generowanie kodu

W tej fazie generator kodu przyjmuje zoptymalizowaną reprezentację kodu pośredniego i mapuje go na docelowy język maszynowy. Generator kodu tłumaczy kod pośredni na sekwencję (ogólnie) kodu maszynowego, który można ponownie zlokalizować. Sekwencja instrukcji kodu maszynowego wykonuje zadanie tak, jak zrobiłby to kod pośredni.

Tabela symboli

Jest to struktura danych utrzymywana we wszystkich fazach kompilatora. Tutaj przechowywane są wszystkie nazwy identyfikatorów wraz z ich typami. Tablica symboli ułatwia kompilatorowi szybkie przeszukiwanie rekordu identyfikatora i pobieranie go. Tabela symboli służy również do zarządzania zakresem.

Analiza leksykalna to pierwsza faza kompilatora. Pobiera zmodyfikowany kod źródłowy z preprocesorów języka, które są zapisane w postaci zdań. Analizator leksykalny dzieli te składnie na serię tokenów, usuwając wszelkie białe znaki lub komentarze w kodzie źródłowym.

Jeśli analizator leksykalny stwierdzi, że token jest nieprawidłowy, generuje błąd. Analizator leksykalny ściśle współpracuje z analizatorem składni. Odczytuje strumienie znaków z kodu źródłowego, sprawdza legalne tokeny i przekazuje dane do analizatora składni, gdy tego wymaga.

Tokeny

Mówi się, że leksemy są sekwencją znaków (alfanumerycznych) w tokenie. Istnieją pewne predefiniowane reguły dla każdego leksemu, które mają być identyfikowane jako ważny token. Reguły te są definiowane przez reguły gramatyczne za pomocą wzorca. Wzorzec wyjaśnia, co może być tokenem, a wzorce te są definiowane za pomocą wyrażeń regularnych.

W języku programowania słowa kluczowe, stałe, identyfikatory, łańcuchy, liczby, operatory i symbole interpunkcyjne mogą być traktowane jako tokeny.

Na przykład w języku C wiersz deklaracji zmiennej

int value = 100;

zawiera tokeny:

int (keyword), value (identifier), = (operator), 100 (constant) and ; (symbol).

Specyfikacje tokenów

Rozumiemy, jak teoria języka przyjmuje następujące terminy:

Alfabety

Dowolny skończony zbiór symboli {0,1} jest zbiorem binarnych alfabetów, {0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F} to zestaw alfabetów szesnastkowych, {az, AZ} to zestaw alfabetów języka angielskiego.

Smyczki

Każda skończona sekwencja alfabetów nazywana jest łańcuchem. Długość ciągu to całkowita liczba wystąpień alfabetów, np. Długość ciągu znaków tutorialspoint wynosi 14 i jest oznaczona przez | tutorialspoint | = 14. Łańcuch nie posiadający alfabetów, tj. Ciąg o zerowej długości jest nazywany łańcuchem pustym i oznaczany jest przez ε (epsilon).

Symbole specjalne

Typowy język wysokiego poziomu zawiera następujące symbole: -

Symbole arytmetyczne Dodawanie (+), odejmowanie (-), modulo (%), mnożenie (*), dzielenie (/)
Interpunkcja Przecinek (,), średnik (;), kropka (.), Strzałka (->)
Zadanie =
Specjalne zadanie + =, / =, * =, - =
Porównanie ==,! =, <, <=,>,> =
Preprocesor #
Specyfikator lokalizacji &
Logiczny &, &&, |, ||,!
Operator zmiany >>, >>>, <<, <<<

Język

Język jest uważany za skończony zbiór ciągów na pewnym skończonym zbiorze alfabetów. Języki komputerowe są traktowane jako zbiory skończone i można na nich wykonywać operacje na zestawach matematycznych. Języki skończone można opisać za pomocą wyrażeń regularnych.

Wyrażenia regularne

Analizator leksykalny musi skanować i identyfikować tylko skończony zbiór poprawnych ciągów znaków / tokenów / leksemów, które należą do używanego języka. Wyszukuje wzorzec zdefiniowany przez reguły języka.

Wyrażenia regularne mają możliwość wyrażania skończonych języków poprzez definiowanie wzorca dla skończonych ciągów symboli. Gramatyka zdefiniowana przez wyrażenia regularne jest znana jakoregular grammar. Język zdefiniowany przez gramatykę regularną jest znany jakoregular language.

Wyrażenie regularne jest ważną notacją przy określaniu wzorców. Każdy wzorzec pasuje do zestawu ciągów, więc wyrażenia regularne służą jako nazwy zestawu ciągów. Tokeny języka programowania można opisać zwykłymi językami. Specyfikacja wyrażeń regularnych jest przykładem definicji rekurencyjnej. Zwykłe języki są łatwe do zrozumienia i mają wydajną implementację.

Istnieje wiele praw algebraicznych, które są przestrzegane przez wyrażenia regularne, których można używać do manipulowania wyrażeniami regularnymi w równoważne formy.

Operacje

Różne operacje na językach to:

  • Związek dwóch języków L i M jest zapisywany jako

    LUM = {s | s jest w L lub s w M}

  • Łączenie dwóch języków L i M jest zapisywane jako

    LM = {st | s jest w L, at jest w M}

  • Zamknięcie Kleene języka L jest zapisane jako

    L * = zero lub więcej występowania języka L.

Notacje

Jeśli r i s są wyrażeniami regularnymi oznaczającymi języki L (r) i L (s), to

  • Union : (r) | (s) jest wyrażeniem regularnym oznaczającym L (r) UL (s)

  • Concatenation : (r) (s) jest wyrażeniem regularnym oznaczającym L (r) L (s)

  • Kleene closure : (r) * jest wyrażeniem regularnym oznaczającym (L (r)) *

  • (r) jest wyrażeniem regularnym oznaczającym L (r)

Pierwszeństwo i łączność

  • *, konkatenacja (.) i | (znak rury) są lewostronne
  • * ma najwyższy priorytet
  • Konkatenacja (.) Ma drugi najwyższy priorytet.
  • | (znak potoku) ma najniższy priorytet ze wszystkich.

Przedstawianie prawidłowych tokenów języka w wyrażeniach regularnych

Jeśli x jest wyrażeniem regularnym, to:

  • x * oznacza zero lub więcej wystąpień x.

    tzn. może generować {e, x, xx, xxx, xxxx,…}

  • x + oznacza jedno lub więcej wystąpień x.

    tzn. może generować {x, xx, xxx, xxxx…} lub xx *

  • x? oznacza co najwyżej jedno wystąpienie x

    tj. może generować {x} lub {e}.

  • [az] to wszystkie małe litery języka angielskiego.

    [AZ] to wszystkie wielkie litery języka angielskiego.

    [0-9] to wszystkie cyfry naturalne używane w matematyce.

Przedstawianie występowania symboli za pomocą wyrażeń regularnych

litera = [a - z] lub [A - Z]

cyfra = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 lub [0-9]

znak = [+ | -]

Reprezentowanie tokenów językowych przy użyciu wyrażeń regularnych

Dziesiętny = (znak) ? (cyfra) +

Identyfikator = (litera) (litera | cyfra) *

Jedynym problemem, jaki pozostał z analizatorem leksykalnym, jest to, jak zweryfikować poprawność wyrażenia regularnego używanego przy określaniu wzorców słów kluczowych języka. Dobrze przyjętym rozwiązaniem jest użycie automatów skończonych do weryfikacji.

Automaty skończone

Automaty skończone to maszyna stanów, która przyjmuje ciąg symboli jako dane wejściowe i odpowiednio zmienia swój stan. Automaty skończone to aparat rozpoznający wyrażenia regularne. Kiedy ciąg wyrażenia regularnego jest wprowadzany do automatów skończonych, zmienia swój stan dla każdego literału. Jeśli łańcuch wejściowy został pomyślnie przetworzony i automat osiągnął swój stan końcowy, jest on akceptowany, tj. O podanym właśnie łańcuchu mówi się, że jest prawidłowym tokenem używanego języka.

Model matematyczny automatów skończonych składa się z:

  • Skończony zbiór stanów (Q)
  • Skończony zbiór symboli wejściowych (Σ)
  • Jeden stan początkowy (q0)
  • Zbiór stanów końcowych (qf)
  • Funkcja przejścia (δ)

Funkcja przejścia (δ) odwzorowuje skończony zbiór stanu (Q) na skończony zbiór symboli wejściowych (Σ), Q × Σ ➔ Q

Konstrukcja automatów skończonych

Niech L (r) będzie językiem regularnym rozpoznawanym przez jakieś automaty skończone (FA).

  • States: Stany FA są reprezentowane przez kółka. Nazwy stanów są zapisane w kółkach.

  • Start state: Stan, w którym automaty się uruchamiają, nazywany jest stanem początkowym. Stan początkowy ma skierowaną w jego stronę strzałkę.

  • Intermediate states: Wszystkie stany pośrednie mają co najmniej dwie strzałki; jeden wskazuje, a drugi wskazuje od nich.

  • Final state: Jeśli wejściowy ciąg został pomyślnie przeanalizowany, oczekuje się, że automaty będą w tym stanie. Stan końcowy jest reprezentowany przez podwójne okręgi. Może mieć dowolną nieparzystą liczbę strzałek wskazujących na niego i parzystą liczbę strzałek wskazujących z niego. Liczba strzał nieparzystych jest o jeden większa niż parzysta, tjodd = even+1.

  • Transition: Przejście z jednego stanu do innego stanu następuje, gdy na wejściu zostanie znaleziony żądany symbol. Po przejściu automaty mogą albo przejść do następnego stanu, albo pozostać w tym samym stanie. Przemieszczanie się z jednego stanu do drugiego jest przedstawiane jako skierowana strzałka, w której strzałki wskazują stan docelowy. Jeśli automaty pozostają w tym samym stanie, rysowana jest strzałka wskazująca ze stanu do samego siebie.

Example: Zakładamy, że FA akceptuje dowolną trzycyfrową wartość binarną kończącą się cyfrą 1. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}

Zasada najdłuższego meczu

Kiedy analizator leksykalny odczytuje kod źródłowy, skanuje literę po literze; a kiedy napotka biały znak, symbol operatora lub symbole specjalne, decyduje, że słowo jest zakończone.

For example:

int intvalue;

Podczas skanowania obu leksemów do „int”, analizator leksykalny nie może określić, czy jest to słowo kluczowe int, czy inicjały wartości identyfikatora int.

Reguła najdłuższego dopasowania stanowi, że skanowany leksem powinien być określany na podstawie najdłuższego dopasowania spośród wszystkich dostępnych tokenów.

Dalej następuje analizator leksykalny rule prioritygdzie zarezerwowane słowo, np. słowo kluczowe języka, ma pierwszeństwo przed wprowadzaniem danych przez użytkownika. Oznacza to, że jeśli analizator leksykalny znajdzie leksem pasujący do dowolnego istniejącego słowa zastrzeżonego, powinien wygenerować błąd.

Analiza składni lub parsowanie to druga faza kompilatora. W tym rozdziale poznamy podstawowe pojęcia używane w konstrukcji parsera.

Widzieliśmy, że analizator leksykalny może identyfikować tokeny za pomocą wyrażeń regularnych i reguł wzorców. Jednak analizator leksykalny nie może sprawdzić składni danego zdania ze względu na ograniczenia wyrażeń regularnych. Wyrażenia regularne nie mogą sprawdzać tokenów równoważących, takich jak nawiasy. Dlatego w tej fazie stosowana jest gramatyka bezkontekstowa (CFG), która jest rozpoznawana przez automaty przesuwające w dół.

Z drugiej strony CFG to nadzbiór gramatyki regularnej, jak pokazano poniżej:

Oznacza to, że każda gramatyka regularna jest również bezkontekstowa, ale istnieją pewne problemy, które wykraczają poza zakres gramatyki regularnej. CFG to narzędzie pomocne w opisywaniu składni języków programowania.

Gramatyka bezkontekstowa

W tej sekcji najpierw zobaczymy definicję gramatyki bezkontekstowej i przedstawimy terminologię używaną w technologii analizowania.

Gramatyka bezkontekstowa składa się z czterech elementów:

  • Zestaw non-terminals(V). Terminale to zmienne składniowe, które oznaczają zestawy łańcuchów. Nieterminale definiują zestawy łańcuchów, które pomagają zdefiniować język generowany przez gramatykę.

  • Zestaw tokenów, znany jako terminal symbols(Σ). Terminale to podstawowe symbole, z których tworzone są łańcuchy.

  • Zestaw productions(P). Produkcje gramatyki określają sposób, w jaki terminale i nieterminale mogą być łączone w łańcuchy. Każda produkcja składa się znon-terminal zwana lewą stroną produkcji, strzałką i sekwencją żetonów i / lub on- terminals, zwana prawą stroną produkcji.

  • Jeden z nieterminali jest oznaczony jako symbol startu (S); skąd zaczyna się produkcja.

Ciągi są wyprowadzane z symbolu początkowego przez wielokrotne zastępowanie nieterminalnego (początkowo symbolu początkowego) prawą stroną produkcji, dla tego nieterminala.

Przykład

Podejmiemy problem języka palindromowego, którego nie da się opisać za pomocą wyrażeń regularnych. To znaczy L = {w | w = w R } nie jest językiem zwykłym. Ale można to opisać za pomocą CFG, jak pokazano poniżej:

G = ( V, Σ, P, S )

Gdzie:

V = { Q, Z, N }
Σ = { 0, 1 }
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }
S = { Q }

Ta gramatyka opisuje język palindromowy, taki jak: 1001, 11100111, 00100, 1010101, 11111 itd.

Analizatory składni

Analizator składni lub parser pobiera dane wejściowe z analizatora leksykalnego w postaci strumieni tokenów. Parser analizuje kod źródłowy (strumień tokenów) pod kątem reguł produkcji, aby wykryć wszelkie błędy w kodzie. Wyjście tej fazy toparse tree.

W ten sposób parser wykonuje dwa zadania, tj. Analizuje kod, szuka błędów i generuje drzewo parsowania jako wynik fazy.

Parsery powinny przeanalizować cały kod, nawet jeśli w programie występują błędy. Parsery używają strategii naprawiania błędów, o których dowiemy się w dalszej części tego rozdziału.

Pochodzenie

Wyprowadzenie jest w zasadzie sekwencją reguł produkcji, aby uzyskać ciąg wejściowy. Podczas analizowania podejmujemy dwie decyzje dotyczące pewnej zdaniowej formy danych wejściowych:

  • Decydowanie o nieterminalu, który ma zostać wymieniony.
  • Decydowanie o zasadzie produkcji, według której nieterminal zostanie zastąpiony.

Aby zdecydować, który nieterminal ma zostać zastąpiony regułą produkcji, możemy mieć dwie opcje.

Wyprowadzenie skrajnie lewe

Jeśli zdaniowa forma wejścia jest skanowana i zastępowana od lewej do prawej, nazywa się to wyprowadzeniem najbardziej z lewej strony. Forma zdań wyprowadzona przez lewe wyprowadzenie nazywa się formą zdaniową po lewej stronie.

Wyprowadzenie najbardziej po prawej

Jeśli zeskanujemy i zastąpimy dane wejściowe regułami produkcji, od prawej do lewej, jest to znane jako wyprowadzenie najbardziej na prawo. Forma zdań wywodząca się z najbardziej prawej wyprowadzenia nazywana jest formą zdaniową po prawej stronie.

Example

Zasady produkcji:

E → E + E
E → E * E
E → id

Ciąg wejściowy: id + id * id

Najbardziej lewe wyprowadzenie to:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Zwróć uwagę, że nieterminalowa skrajna lewa strona jest zawsze przetwarzana jako pierwsza.

Najbardziej prawe wyprowadzenie to:

E → E + E
E → E + E * E
E → E + E * id
E → E + id * id
E → id + id * id

Drzewo analizy

Drzewo parsowania to graficzne przedstawienie wyprowadzenia. Wygodne jest zobaczenie, jak ciągi są wyprowadzane z symbolu początkowego. Symbol początkowy wyprowadzenia staje się korzeniem drzewa parsowania. Zobaczmy to na przykładzie z ostatniego tematu.

Bierzemy skrajne lewe wyprowadzenie a + b * c

Najbardziej lewe wyprowadzenie to:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Krok 1:

E → E * E

Krok 2:

E → E + E * E

Krok 3:

E → id + E * E

Krok 4:

E → id + id * E

Krok 5:

E → id + id * id

W drzewie parsowania:

  • Wszystkie węzły liściowe są terminalami.
  • Wszystkie węzły wewnętrzne nie są terminalami.
  • Przechodzenie w kolejności daje oryginalny ciąg wejściowy.

Drzewo analizy przedstawia asocjatywność i pierwszeństwo operatorów. Najgłębsze poddrzewo jest przeszukiwane jako pierwsze, dlatego operator w tym poddrzewie ma pierwszeństwo przed operatorem, który znajduje się w węzłach nadrzędnych.

Typy analizowania

Analizatory składni kierują się regułami produkcyjnymi zdefiniowanymi za pomocą gramatyki bezkontekstowej. Sposób, w jaki reguły produkcji są wdrażane (wyprowadzanie), dzieli analizowanie na dwa typy: analizowanie odgórne i analizowanie oddolne.

Analiza odgórna

Kiedy parser zaczyna konstruować drzewo parsowania na podstawie symbolu startu, a następnie próbuje przekształcić symbol początkowy na dane wejściowe, nazywa się to analizowaniem odgórnym.

  • Recursive descent parsing: Jest to powszechna forma analizy odgórnej. Nazywa się to rekurencyjnym, ponieważ wykorzystuje procedury rekurencyjne do przetwarzania danych wejściowych. Rekurencyjne analizowanie zejścia cierpi z powodu wycofywania.

  • Backtracking: Oznacza to, że jeśli jedno wyprowadzenie produkcji nie powiedzie się, analizator składni ponownie uruchomi proces przy użyciu innych reguł tej samej produkcji. Ta technika może przetwarzać ciąg wejściowy więcej niż raz, aby określić właściwą produkcję.

Analiza oddolna

Jak sama nazwa wskazuje, analiza oddolna rozpoczyna się od symboli wejściowych i próbuje skonstruować drzewo analizy aż do symbolu początkowego.

Example:

Ciąg wejściowy: a + b * c

Zasady produkcji:

S → E
E → E + T
E → E * T
E → T
T → id

Zacznijmy analizę oddolną

a + b * c

Przeczytaj dane wejściowe i sprawdź, czy jakakolwiek produkcja jest zgodna z danymi wejściowymi:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S

Dwuznaczność

Mówi się, że gramatyka G jest niejednoznaczna, jeśli ma więcej niż jedno drzewo analizy (lewe lub prawe wyprowadzenie) dla co najmniej jednego ciągu.

Example

E → E + E
E → E – E
E → id

Dla ciągu id + id - id, powyższa gramatyka generuje dwa drzewa parsowania:

Mówi się, że język generowany przez niejednoznaczną gramatykę jest inherently ambiguous. Niejednoznaczność gramatyczna nie jest dobra dla konstrukcji kompilatora. Żadna metoda nie może automatycznie wykryć i usunąć niejednoznaczności, ale można ją usunąć przez ponowne napisanie całej gramatyki bez niejasności lub ustawienie i przestrzeganie ograniczeń asocjatywności i pierwszeństwa.

Łączność

Jeśli operand ma operatory po obu stronach, strona, po której operator przyjmuje ten operand, jest określana przez asocjatywność tych operatorów. Jeśli operacja jest lewostronna, operand zostanie pobrany przez lewy operator lub jeśli operacja jest prawostronna, prawy operator zajmie operand.

Example

Operacje takie jak dodawanie, mnożenie, odejmowanie i dzielenie są lewostronne. Jeśli wyrażenie zawiera:

id op id op id

zostanie oceniony jako:

(id op id) op id

Na przykład (id + id) + id

Operacje takie jak potęgowanie są prawostronnie asocjacyjne, tj. Kolejność oceny w tym samym wyrażeniu będzie następująca:

id op (id op id)

Na przykład id ^ (id ^ id)

Precedens

Jeśli dwa różne operatory mają wspólny operand, pierwszeństwo operatorów decyduje, który operand zajmie. Oznacza to, że 2 + 3 * 4 może mieć dwa różne drzewa analizy, jedno odpowiadające (2 + 3) * 4, a drugie odpowiadające 2+ (3 * 4). Ustawiając pierwszeństwo między operatorami, problem ten można łatwo usunąć. Podobnie jak w poprzednim przykładzie, matematycznie * (mnożenie) ma pierwszeństwo przed + (dodawanie), więc wyrażenie 2 + 3 * 4 będzie zawsze interpretowane jako:

2 + (3 * 4)

Te metody zmniejszają prawdopodobieństwo niejednoznaczności w języku lub jego gramatyce.

Rekursja lewostronna

Gramatyka staje się lewostronnie rekurencyjna, jeśli ma jakieś nieterminalne „A”, którego wyprowadzenie zawiera „A” jako skrajny lewy symbol. Gramatyka lewostronna jest uważana za problematyczną dla parserów odgórnych. Parsery odgórne rozpoczynają analizę od symbolu Start, który sam w sobie nie jest terminalem. Tak więc, gdy parser napotyka ten sam nieterminalowy w swoim wyprowadzeniu, trudno jest mu ocenić, kiedy przestać analizować lewy nieterminal i przechodzi w nieskończoną pętlę.

Example:

(1) A => Aα | β

(2) S => Aα | β 
    A => Sd

(1) jest przykładem natychmiastowej lewostronnej rekurencji, gdzie A jest dowolnym symbolem nieterminalnym, a α reprezentuje ciąg znaków nieterminalnych.

(2) jest przykładem rekursji pośredniej lewostronnej.

Parser odgórny najpierw przeanalizuje A, co z kolei da ciąg składający się z samego A, a parser może przejść do pętli na zawsze.

Usunięcie lewostronnej rekursji

Jednym ze sposobów usunięcia rekurencji lewej jest użycie następującej techniki:

Produkcja

A => Aα | β

jest konwertowana na kolejne produkcje

A => βA’
A => αA’ | ε

Nie ma to wpływu na ciągi wywodzące się z gramatyki, ale usuwa natychmiastową lewą rekursję.

Drugą metodą jest użycie następującego algorytmu, który powinien wyeliminować wszystkie bezpośrednie i pośrednie lewe rekursje.

Algorithm
START
Arrange non-terminals in some order like A1, A2, A3,…, An
for each i from 1 to n
{
for each j from 1 to i-1
   {
   replace each production of form Ai⟹Aj
   with Ai ⟹ δ1  | δ2 | δ3 |…|  
   where Aj ⟹ δ1 | δ2|…| δn  are current Aj productions
}
   }
   eliminate immediate left-recursion
END

Example

Zestaw produkcyjny

S => Aα | β 
A => Sd

po zastosowaniu powyższego algorytmu powinno stać się

S => Aα | β 
A => Aαd | βd

a następnie usuń natychmiastową lewą rekursję, używając pierwszej techniki.

A => βdA’
A => αdA’ | ε

Teraz żadna z produkcji nie ma bezpośredniej ani pośredniej rekurencji lewej.

Faktoring lewy

Jeśli więcej niż jedna reguła produkcji gramatyki ma wspólny ciąg przedrostka, wówczas parser odgórny nie może dokonać wyboru, który z produkcji powinien wykonać, aby przeanalizować ciąg w ręku.

Example

Jeśli odgórny parser napotka produkcję taką jak

A ⟹ αβ | α | …

Wtedy nie może określić, którą produkcję należy wykonać, aby przeanalizować ciąg, ponieważ obie produkcje zaczynają się od tego samego terminala (lub nieterminala). Aby usunąć to zamieszanie, używamy techniki zwanej faktoringiem lewostronnym.

Faktoring lewy przekształca gramatykę, aby była użyteczna dla parserów odgórnych. W tej technice tworzymy jedną produkcję dla każdego wspólnego przedrostka, a resztę wyprowadzenia dodajemy w nowych produkcjach.

Example

Powyższe produkcje można zapisać jako

A => αA’
A’=> β |  | …

Teraz parser ma tylko jedną produkcję na prefiks, co ułatwia podejmowanie decyzji.

Zestawy First i Follow

Ważną częścią konstrukcji tablicy parsera jest tworzenie pierwszych i następujących po sobie zestawów. Te zestawy mogą zapewnić rzeczywistą pozycję dowolnego terminala w wyprowadzeniu. Ma to na celu utworzenie tabeli parsowania, w której decyzja o zastąpieniu T [A, t] = α jakąś regułą produkcji.

Pierwszy zestaw

Ten zestaw jest tworzony, aby wiedzieć, jaki symbol terminala jest wyprowadzany na pierwszej pozycji przez nieterminal. Na przykład,

α → t β

Czyli α wyprowadza t (terminal) na pierwszej pozycji. Zatem t ∈ PIERWSZY (α).

Algorytm obliczania pierwszego zbioru

Spójrz na definicję pierwszego zbioru (α):

  • jeśli α jest końcem, to PIERWSZA (α) = {α}.
  • jeśli α jest nieterminalnym i α → ℇ jest produkcją, to PIERWSZA (α) = {ℇ}.
  • jeśli α jest niekońcem i α → 1 2 3… n i każda FIRST () zawiera t, to t jest w FIRST (α).

Pierwszy zbiór można zobaczyć jako: PIERWSZY (α) = {t | α → * t β} ∪ {ℇ | α → * ε}

Śledź Set

Podobnie, obliczamy, który symbol końcowy występuje bezpośrednio po nieterminalnej α w regułach produkcji. Nie bierzemy pod uwagę tego, co może wygenerować nieterminal, ale zamiast tego widzimy, jaki byłby następny symbol terminala, który następuje po produkcji nieterminala.

Algorytm obliczania zbioru Follow:

  • jeśli α jest symbolem początkowym, to FOLLOW () = $

  • jeśli α jest nieterminalnym i ma produkcję α → AB, to FIRST (B) jest w FOLLOW (A) z wyjątkiem ℇ.

  • jeśli α jest nieterminalnym i ma produkcję α → AB, gdzie B ℇ, to FOLLOW (A) jest w FOLLOW (α).

Zbiór następujący można zobaczyć jako: FOLLOW (α) = {t | S * αt *}

Strategie usuwania błędów

Parser powinien być w stanie wykryć i zgłosić każdy błąd w programie. Oczekuje się, że w przypadku napotkania błędu parser powinien być w stanie go obsłużyć i kontynuować analizowanie reszty danych wejściowych. Przeważnie oczekuje się, że parser będzie sprawdzał błędy, ale błędy mogą wystąpić na różnych etapach procesu kompilacji. Program może mieć następujące rodzaje błędów na różnych etapach:

  • Lexical : nazwa jakiegoś identyfikatora wpisanego nieprawidłowo

  • Syntactical : brak średnika lub niezrównoważonego nawiasu

  • Semantical : niezgodne przypisanie wartości

  • Logical : kod nieosiągalny, nieskończona pętla

Istnieją cztery typowe strategie usuwania błędów, które można zaimplementować w parserze, aby radzić sobie z błędami w kodzie.

Tryb paniki

Gdy parser napotka błąd w dowolnym miejscu instrukcji, ignoruje pozostałą część instrukcji, nie przetwarzając danych wejściowych od błędnych danych wejściowych do separatora, takiego jak średnik. Jest to najłatwiejszy sposób naprawy błędów, a także zapobiega tworzeniu nieskończonych pętli przez parser.

Tryb instrukcji

Kiedy parser napotka błąd, próbuje podjąć działania naprawcze, tak aby pozostałe dane wejściowe instrukcji umożliwiały parserowi analizę z wyprzedzeniem. Na przykład wstawienie brakującego średnika, zastąpienie przecinka średnikiem itp. Projektanci parserów muszą tutaj zachować ostrożność, ponieważ jedna błędna poprawka może prowadzić do nieskończonej pętli.

Produkcje błędów

Projektanci kompilatora znają niektóre typowe błędy, które mogą wystąpić w kodzie. Ponadto projektanci mogą tworzyć gramatykę rozszerzoną do wykorzystania jako produkcje, które generują błędne konstrukcje w przypadku napotkania tych błędów.

Globalna korekta

Parser traktuje program w ręku jako całość i próbuje dowiedzieć się, co program ma zrobić, i próbuje znaleźć najbliższe dopasowanie do niego, co jest bezbłędne. Podanie błędnego wejścia (instrukcji) X tworzy drzewo parsowania dla jakiejś najbliższej wolnej od błędów instrukcji Y. Może to pozwolić parserowi na wprowadzenie minimalnych zmian w kodzie źródłowym, ale ze względu na złożoność (czas i przestrzeń) tej strategii, nie została ona jeszcze wdrożona w praktyce.

Abstrakcyjne drzewa składniowe

Reprezentacje drzewa analizy nie są łatwe do przeanalizowania przez kompilator, ponieważ zawierają więcej szczegółów niż jest to faktycznie potrzebne. Jako przykład weźmy następujące drzewo analizy:

Jeśli przyjrzymy się uważnie, stwierdzimy, że większość węzłów liści jest pojedynczymi potomkami ich węzłów nadrzędnych. Informacje te można wyeliminować przed przekazaniem ich do następnej fazy. Ukrywając dodatkowe informacje, możemy uzyskać drzewo, jak pokazano poniżej:

Drzewo abstrakcyjne można przedstawić jako:

AST to ważne struktury danych w kompilatorze zawierające najmniej niepotrzebnych informacji. AST są bardziej zwarte niż drzewo parsowania i mogą być łatwo używane przez kompilator.

Ograniczenia analizatorów składni

Analizatory składni otrzymują dane wejściowe w postaci tokenów z analizatorów leksykalnych. Analizatory leksykalne są odpowiedzialne za ważność tokenu dostarczonego przez analizator składni. Analizatory składni mają następujące wady:

  • nie może określić, czy token jest ważny,
  • nie może określić, czy token został zadeklarowany przed jego użyciem,
  • nie może określić, czy token jest inicjalizowany przed użyciem,
  • nie może określić, czy operacja wykonana na typie tokena jest prawidłowa, czy nie.

Zadania te wykonuje analizator semantyczny, który będziemy badać w ramach analizy semantycznej.

Dowiedzieliśmy się, jak parser konstruuje drzewa parsowania w fazie analizy składni. Zwykłe drzewo parsowania skonstruowane w tej fazie jest generalnie bezużyteczne dla kompilatora, ponieważ nie zawiera żadnych informacji o tym, jak ocenić drzewo. Produkcje gramatyki bezkontekstowej, która tworzy reguły języka, nie uwzględniają sposobu ich interpretacji.

Na przykład

E → E + T

Z powyższą produkcją CFG nie jest związana żadna reguła semantyczna i nie może pomóc w nadaniu sensu produkcji.

Semantyka

Semantyka języka nadaje znaczenie jego konstrukcjom, takim jak tokeny i struktura składni. Semantyka pomaga interpretować symbole, ich typy i ich wzajemne relacje. Analiza semantyczna ocenia, czy struktura składni skonstruowana w programie źródłowym ma jakiekolwiek znaczenie, czy nie.

CFG + semantic rules = Syntax Directed Definitions

Na przykład:

int a = “value”;

nie powinien powodować błędu w fazie analizy leksykalnej i składniowej, ponieważ jest poprawny leksykalnie i strukturalnie, ale powinien generować błąd semantyczny, ponieważ rodzaj przypisania jest inny. Reguły te są wyznaczane przez gramatykę języka i oceniane w analizie semantycznej. W analizie semantycznej należy wykonać następujące zadania:

  • Rozdzielczość zakresu
  • Sprawdzanie typu
  • Sprawdzanie związane z tablicą

Błędy semantyczne

Wspomnieliśmy o niektórych błędach semantycznych, które analizator semantyczny powinien rozpoznać:

  • Niezgodność typów
  • Niezadeklarowana zmienna
  • Niewłaściwe użycie zastrzeżonego identyfikatora.
  • Wielokrotna deklaracja zmiennej w zakresie.
  • Dostęp do zmiennej spoza zakresu.
  • Rzeczywista i formalna niezgodność parametrów.

Gramatyka atrybutów

Gramatyka atrybutów jest specjalną formą gramatyki bezkontekstowej, w której pewne dodatkowe informacje (atrybuty) są dołączane do jednego lub większej liczby nieterminali w celu dostarczenia informacji kontekstowych. Każdy atrybut ma dobrze zdefiniowaną dziedzinę wartości, taką jak liczba całkowita, zmiennoprzecinkowa, znak, ciąg znaków i wyrażenia.

Gramatyka atrybutów jest medium dostarczającym semantykę do gramatyki bezkontekstowej i może pomóc określić składnię i semantykę języka programowania. Gramatyka atrybutów (widziana jako drzewo parsowania) może przekazywać wartości lub informacje między węzłami drzewa.

Example:

E → E + T { E.value = E.value + T.value }

Prawa część CFG zawiera reguły semantyczne, które określają, jak należy interpretować gramatykę. Tutaj wartości nieterminalowe E i T są dodawane do siebie, a wynik jest kopiowany do nieterminalowego E.

Atrybuty semantyczne mogą być przypisane do ich wartości z ich domeny w czasie analizy i oceniane w czasie przypisywania lub warunków. Na podstawie sposobu, w jaki atrybuty uzyskują wartości, można je ogólnie podzielić na dwie kategorie: atrybuty zsyntetyzowane i atrybuty dziedziczone.

Zsyntetyzowane atrybuty

Te atrybuty pobierają wartości z wartości atrybutów ich węzłów podrzędnych. Aby to zilustrować, załóżmy następującą produkcję:

S → ABC

Jeśli S pobiera wartości z węzłów potomnych (A, B, C), to mówi się, że jest to atrybut zsyntetyzowany, ponieważ wartości ABC są syntetyzowane do S.

Podobnie jak w naszym poprzednim przykładzie (E → E + T), węzeł nadrzędny E pobiera wartość ze swojego węzła potomnego. Zsyntetyzowane atrybuty nigdy nie pobierają wartości ze swoich węzłów nadrzędnych ani z żadnych węzłów siostrzanych.

Dziedziczone atrybuty

W przeciwieństwie do atrybutów zsyntetyzowanych, odziedziczone atrybuty mogą przyjmować wartości od rodzica i / lub rodzeństwa. Jak w następnej produkcji,

S → ABC

A może pobrać wartości z S, B i C. B może przyjąć wartości z S, A i C. Podobnie C może przyjąć wartości z S, A i B.

Expansion : Gdy nieterminal jest rozszerzany do terminali zgodnie z regułą gramatyczną

Reduction: Kiedy terminal jest zredukowany do odpowiadającego mu nieterminala zgodnie z regułami gramatycznymi. Drzewa składni są analizowane z góry na dół i od lewej do prawej. Ilekroć następuje redukcja, stosujemy odpowiadające jej reguły semantyczne (akcje).

Analiza semantyczna wykorzystuje tłumaczenia ukierunkowane na składnię do wykonywania powyższych zadań.

Analizator semantyczny otrzymuje AST (Abstract Syntax Tree) z poprzedniego etapu (analiza składni).

Analizator semantyczny dołącza informacje o atrybutach do AST, które są nazywane Attributed AST.

Atrybuty to dwie wartości krotki, <nazwa atrybutu, wartość atrybutu>

Na przykład:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Do każdej produkcji dołączamy regułę semantyczną.

SDT przypisane S.

Jeśli SDT używa tylko zsyntetyzowanych atrybutów, nazywa się to SDT z atrybutem S. Atrybuty te są oceniane za pomocą SDT z przypisanym S, które mają swoje działania semantyczne zapisane po produkcji (prawa strona).

Jak pokazano powyżej, atrybuty w SDT z atrybutem S są oceniane w analizie oddolnej, ponieważ wartości węzłów nadrzędnych zależą od wartości węzłów potomnych.

SDT przypisane L.

Ta forma SDT wykorzystuje zarówno atrybuty zsyntetyzowane, jak i dziedziczone, z zastrzeżeniem niepobierania wartości od właściwego rodzeństwa.

W SDT z atrybutem L, nieterminal może pobierać wartości z węzłów nadrzędnych, podrzędnych i siostrzanych. Jak w następnej produkcji

S → ABC

S może przyjmować wartości z A, B i C (zsyntetyzowane). A może przyjmować wartości tylko z S. B może przyjmować wartości z S i A. C może uzyskać wartości z S, A i B. Żaden nieterminal nie może uzyskać wartości od rodzeństwa po jego prawej stronie.

Atrybuty w L-przypisanych SDT są oceniane metodą analizy najpierw w głąb i od lewej do prawej.

Możemy wywnioskować, że jeśli definicji przypisuje się S, to jest ona również przypisywana L, ponieważ definicja z atrybutem L obejmuje definicje z atrybutem S.

W poprzednim rozdziale zrozumieliśmy podstawowe pojęcia związane z analizowaniem. W tym rozdziale poznamy różne typy dostępnych metod konstrukcji parsera.

Parsowanie można zdefiniować jako odgórne lub oddolne, w zależności od konstrukcji drzewa parsowania.

Analiza odgórna

W poprzednim rozdziale dowiedzieliśmy się, że technika analizy odgórnej analizuje dane wejściowe i zaczyna konstruować drzewo parsowania od węzła głównego, stopniowo przesuwając się w dół do węzłów liści. Poniżej przedstawiono typy analizy odgórnej:

Rekurencyjne analizowanie zejścia

Zejście rekurencyjne to technika analizy zstępującej, która konstruuje drzewo analizy od góry, a dane wejściowe są odczytywane od lewej do prawej. Używa procedur dla każdego terminalu i nieterminala. Ta technika analizowania rekurencyjnie analizuje dane wejściowe, aby utworzyć drzewo analizy, które może wymagać śledzenia wstecznego lub nie. Ale gramatyka z tym związana (jeśli nie zostanie uwzględniona) nie może uniknąć śledzenia wstecznego. Forma analizy zstępującej rekurencyjnej, która nie wymaga śledzenia wstecznego, jest znana jakopredictive parsing.

Ta technika analizowania jest uważana za rekurencyjną, ponieważ wykorzystuje gramatykę bezkontekstową, która ma charakter rekurencyjny.

Śledzenie wstecz

Parsery odgórne zaczynają się od węzła głównego (symbol początkowy) i dopasowują łańcuch wejściowy do reguł produkcji, aby je zastąpić (jeśli są dopasowane). Aby to zrozumieć, weźmy następujący przykład CFG:

S → rXd | rZd
X → oa | ea
Z → ai

Dla ciągu wejściowego: read, odgórny parser, będzie się zachowywał następująco:

Rozpoczyna się literą S od reguł produkcji i dopasowuje swój zysk do lewej litery wejścia, tj. „R”. Pasuje do niego sama produkcja S (S → rXd). Zatem odgórny parser przechodzi do następnej litery wejściowej (tj. „E”). Parser próbuje rozwinąć nieterminalowe „X” i sprawdza jego produkcję od lewej strony (X → oa). Nie pasuje do następnego symbolu wejściowego. Zatem odgórny parser cofa się, aby uzyskać następną regułę produkcji X, (X → ea).

Teraz parser dopasowuje wszystkie wprowadzone litery w uporządkowany sposób. Ciąg jest akceptowany.

Parser predykcyjny

Parser predykcyjny to rekurencyjny parser zstępujący, który ma możliwość przewidywania, która produkcja ma zostać użyta do zastąpienia ciągu wejściowego. Parser predykcyjny nie cierpi z powodu wycofywania.

Aby wykonać swoje zadania, parser predykcyjny używa wskaźnika wyprzedzającego, który wskazuje kolejne symbole wejściowe. Aby parser był wolny od śledzenia wstecznego, parser predykcyjny nakłada pewne ograniczenia na gramatykę i akceptuje tylko klasę gramatyki znaną jako gramatyka LL (k).

Analiza predykcyjna wykorzystuje stos i tabelę analizy do analizowania danych wejściowych i generowania drzewa analizy. Zarówno stos, jak i wejście zawierają symbol końca$aby wskazać, że stos jest pusty, a wejście jest zużywane. Parser odwołuje się do tablicy parsowania, aby podjąć jakąkolwiek decyzję dotyczącą kombinacji elementów wejściowych i stosu.

W parsowaniu rekurencyjnym parser może mieć więcej niż jedną produkcję do wyboru dla jednej instancji danych wejściowych, podczas gdy w parserze predykcyjnym każdy krok ma co najwyżej jedną produkcję do wyboru. Mogą wystąpić przypadki, w których nie ma produkcji pasującej do ciągu wejściowego, co powoduje niepowodzenie procedury analizowania.

LL Parser

Parser LL akceptuje gramatykę LL. Gramatyka LL jest podzbiorem gramatyki bezkontekstowej, ale z pewnymi ograniczeniami, aby uzyskać wersję uproszczoną w celu osiągnięcia łatwej implementacji. Gramatyka LL może być implementowana za pomocą obu algorytmów, mianowicie rekurencyjno-zstępującego lub sterowanego tabelami.

Parser LL jest oznaczony jako LL (k). Pierwsze L w LL (k) analizuje dane wejściowe od lewej do prawej, drugie L w LL (k) oznacza wyprowadzenie najbardziej na lewo, a samo k reprezentuje liczbę wyprzedzeń wyprzedzających. Generalnie k = 1, więc LL (k) można również zapisać jako LL (1).

Algorytm analizy LL

Możemy trzymać się deterministycznego LL (1) dla wyjaśnienia analizatora składni, ponieważ rozmiar tablicy rośnie wykładniczo wraz z wartością k. Po drugie, jeśli dana gramatyka nie jest LL (1), to zwykle nie jest LL (k) dla dowolnego podanego k.

Poniżej podano algorytm parsowania LL (1):

Input: 
string ω 
parsing table M for grammar G
Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol) ω$ in the input buffer

SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
   POP X and advance ip.
	else
   error()
 	endif
else	/* X is non-terminal */
   if M[X,a] = X → Y1, Y2,... Yk    
POP X
PUSH Yk, Yk-1,... Y1 /* Y1 on top */
   Output the production X → Y1, Y2,... Yk 
   else
   error()
   endif
	endif
until X = $	/* empty stack */

Gramatyka G to LL (1), jeśli A-> alfa | b to dwie różne produkcje G:

  • w przypadku braku terminala zarówno alfa, jak i beta wyprowadzają ciągi zaczynające się od a.

  • co najwyżej jeden z alfa i beta może wyprowadzić pusty łańcuch.

  • jeśli beta => t, to alpha nie wyprowadza żadnego łańcucha zaczynającego się od terminala w FOLLOW (A).

Analiza oddolna

Analiza od dołu do góry rozpoczyna się od węzłów liści drzewa i działa w górę, aż dotrze do węzła głównego. Tutaj zaczynamy od zdania, a następnie stosujemy reguły produkcji w odwrotny sposób, aby dotrzeć do symbolu początku. Poniższy obraz przedstawia dostępne parsery oddolne.

Parsowanie Shift-Reduce

Analiza metodą Shift-Redukcja wykorzystuje dwa unikalne kroki do analizy oddolnej. Te kroki są znane jako krok zmiany i krok redukcji.

  • Shift step: Krok przesunięcia odnosi się do przesunięcia wskaźnika wejściowego do następnego symbolu wejściowego, który jest nazywany przesuniętym symbolem. Ten symbol jest kładziony na stosie. Przesunięty symbol jest traktowany jako pojedynczy węzeł drzewa analizy.

  • Reduce step: Kiedy parser znajduje pełną regułę gramatyczną (RHS) i zastępuje ją (LHS), jest to znane jako krok redukcji. Dzieje się tak, gdy wierzchołek stosu zawiera uchwyt. Aby zmniejszyć, na stosie wykonywana jest funkcja POP, która wyskakuje z uchwytu i zastępuje go nieterminalnym symbolem LHS.

LR Parser

Parser LR jest parserem nierekurencyjnym, redukującym przesunięcie i oddolnym. Wykorzystuje szeroką klasę gramatyki bezkontekstowej, co czyni ją najbardziej wydajną techniką analizy składni. Parsery LR są również znane jako parsery LR (k), gdzie L oznacza skanowanie strumienia wejściowego od lewej do prawej; R oznacza konstrukcję wyprowadzenia znajdującego się najbardziej na prawo w odwrotnej kolejności, a k oznacza liczbę symboli wyprzedzających do podejmowania decyzji.

Istnieją trzy powszechnie używane algorytmy do konstruowania parsera LR:

  • SLR (1) - prosty parser LR:
    • Działa na najmniejszej klasie gramatyki
    • Niewielka liczba stanów, stąd bardzo mała tabela
    • Prosta i szybka konstrukcja
  • LR (1) - Parser LR:
    • Działa na pełnym zestawie gramatyki LR (1)
    • Generuje dużą tabelę i dużą liczbę stanów
    • Powolna konstrukcja
  • LALR (1) - Look-Ahead LR Parser:
    • Działa na gramatyce o średniej wielkości
    • Liczba stanów jest taka sama jak w lustrzance (1)

Algorytm analizy LR

Tutaj opisujemy szkieletowy algorytm parsera LR:

token = next_token()
repeat forever
   s = top of stack
   if action[s, token] = “shift si” then
   PUSH token
   PUSH si 
   token = next_token()
else if action[s, tpken] = “reduce A::= β“ then 
   POP 2 * |β| symbols
   s = top of stack
   PUSH A
	PUSH goto[s,A]
else if action[s, token] = “accept” then
	return
	else
   error()

LL kontra LR

LL LR
Wykonuje wyprowadzenie skrajnie lewe. Wykonuje prawe wyprowadzenie w odwrotnej kolejności.
Rozpoczyna się nieterminalem głównym na stosie. Kończy się nieterminalem głównym na stosie.
Kończy się, gdy stos jest pusty. Zaczyna się od pustego stosu.
Używa stosu do określenia tego, czego nadal można się spodziewać. Używa stosu do oznaczania tego, co jest już widoczne.
Buduje drzewo analizy od góry do dołu. Buduje drzewo parsowania od dołu do góry.
Ciągle zdejmuje nieterminal ze stosu i odkłada odpowiednią prawą stronę. Próbuje rozpoznać prawą stronę stosu, wyskakuje ją i odkłada odpowiedni nieterminal.
Rozwija nieterminale. Zmniejsza liczbę nie-terminali.
Odczytuje terminale, gdy zdejmuje jeden ze stosu. Odczytuje terminale, wpychając je na stos.
Zamów przeglądanie drzewa parsowania w przedsprzedaży. Przeglądanie drzewa parsowania po zamówieniu.

Program jako kod źródłowy jest jedynie zbiorem tekstu (kod, instrukcje itp.) I aby go ożywić, wymaga wykonania działań na maszynie docelowej. Program potrzebuje zasobów pamięci do wykonywania instrukcji. Program zawiera nazwy procedur, identyfikatorów itp., Które wymagają odwzorowania na rzeczywistą lokalizację pamięci w czasie wykonywania.

Przez środowisko uruchomieniowe rozumiemy program w trakcie wykonywania. Środowisko wykonawcze to stan maszyny docelowej, który może obejmować biblioteki oprogramowania, zmienne środowiskowe itp. W celu świadczenia usług procesom działającym w systemie.

System wsparcia runtime to pakiet, generowany przeważnie za pomocą samego programu wykonywalnego i ułatwiający komunikację procesu pomiędzy procesem a środowiskiem wykonawczym. Zajmuje się alokacją i cofaniem alokacji pamięci podczas wykonywania programu.

Drzewa aktywacji

Program to sekwencja instrukcji połączonych w szereg procedur. Instrukcje w procedurze są wykonywane sekwencyjnie. Procedura ma ogranicznik początku i końca, a wszystko w niej jest nazywane treścią procedury. Identyfikator procedury i sekwencja skończonych instrukcji wewnątrz niego tworzą treść procedury.

Wykonanie procedury nazywa się jej aktywacją. Rekord aktywacji zawiera wszystkie niezbędne informacje wymagane do wywołania procedury. Rekord aktywacji może zawierać następujące jednostki (w zależności od używanego języka źródłowego).

Tymczasowe Przechowuje tymczasowe i pośrednie wartości wyrażenia.
Dane lokalne Przechowuje lokalne dane wywoływanej procedury.
Stan maszyny Przechowuje stan maszyny, taki jak rejestry, licznik programów itp., Przed wywołaniem procedury.
Control Link Przechowuje adres rekordu aktywacji procedury dzwoniącego.
Łącze dostępu Przechowuje informacje o danych, które są poza zakresem lokalnym.
Rzeczywiste parametry Przechowuje aktualne parametry, tj. Parametry, które służą do wysyłania danych wejściowych do wywoływanej procedury.
Wartość zwracana Przechowuje wartości zwracane.

Za każdym razem, gdy procedura jest wykonywana, jej rekord aktywacji jest przechowywany na stosie, znanym również jako stos kontrolny. Gdy procedura wywołuje inną procedurę, wykonywanie obiektu wywołującego jest zawieszane do momentu zakończenia wykonywania wywoływanej procedury. W tym momencie rekord aktywacji wywoływanej procedury jest przechowywany na stosie.

Zakładamy, że sterowanie programem przepływa sekwencyjnie i gdy wywoływana jest procedura, jej sterowanie jest przekazywane do wywoływanej procedury. Gdy wywoływana procedura jest wykonywana, zwraca sterowanie z powrotem do obiektu wywołującego. Ten typ przepływu sterowania ułatwia przedstawienie serii aktywacji w postaci drzewa, znanego jakoactivation tree.

Aby zrozumieć tę koncepcję, weźmy fragment kodu jako przykład:

. . .
printf(“Enter Your Name: “);
scanf(“%s”, username);
show_data(username);
printf(“Press any key to continue…”);
. . .
int show_data(char *user)
   {
   printf(“Your name is %s”, username);
   return 0;
   }
. . .

Poniżej znajduje się drzewo aktywacji podanego kodu.

Teraz rozumiemy, że procedury są wykonywane w pierwszej kolejności w głąb, więc alokacja stosu jest najlepszą odpowiednią formą przechowywania dla aktywacji procedur.

Alokacja pamięci

Środowisko wykonawcze zarządza wymaganiami dotyczącymi pamięci w czasie wykonywania dla następujących jednostek:

  • Code: Jest znany jako tekstowa część programu, która nie zmienia się w czasie wykonywania. Jego wymagania dotyczące pamięci są znane w czasie kompilacji.

  • Procedures: Ich część tekstowa jest statyczna, ale są wywoływane w losowy sposób. Dlatego do zarządzania wywołaniami procedur i aktywacjami jest używana pamięć stosu.

  • Variables: Zmienne są znane tylko w czasie wykonywania, chyba że są globalne lub stałe. Schemat alokacji pamięci sterty służy do zarządzania alokacją i cofaniem alokacji pamięci dla zmiennych w czasie wykonywania.

Alokacja statyczna

W tym schemacie alokacji dane kompilacji są powiązane ze stałą lokalizacją w pamięci i nie zmieniają się podczas wykonywania programu. Ponieważ wymagania dotyczące pamięci i miejsca przechowywania są znane z góry, pakiet obsługi środowiska wykonawczego do alokacji i cofania alokacji nie jest wymagany.

Alokacja stosu

Wywołania procedur i ich aktywacje są zarządzane za pomocą alokacji pamięci stosu. Działa w metodzie Last-In-First-Out (LIFO) i ta strategia alokacji jest bardzo przydatna w przypadku wywołań procedur rekurencyjnych.

Alokacja sterty

Zmienne lokalne dla procedury są przydzielane i cofane tylko w czasie wykonywania. Alokacja sterty służy do dynamicznego przydzielania pamięci do zmiennych i odbierania jej z powrotem, gdy zmienne nie są już potrzebne.

Z wyjątkiem obszaru pamięci przydzielonego statycznie, zarówno pamięć stosu, jak i sterty mogą rosnąć i kurczyć się dynamicznie i nieoczekiwanie. Dlatego nie można im zapewnić stałej ilości pamięci w systemie.

Jak pokazano na powyższym obrazku, część tekstowa kodu ma przydzieloną stałą ilość pamięci. Pamięć stosu i sterty są rozmieszczone na krańcach całkowitej pamięci przydzielonej programowi. Oba kurczą się i rosną przeciwko sobie.

Przekazywanie parametru

Medium komunikacyjne między procedurami jest znane jako przekazywanie parametrów. Wartości zmiennych z procedury wywołującej są przenoszone do wywoływanej procedury przez jakiś mechanizm. Zanim przejdziesz dalej, najpierw zapoznaj się z podstawowymi terminologiami dotyczącymi wartości w programie.

wartość r

Wartość wyrażenia nazywana jest jego wartością r. Wartość zawarta w jednej zmiennej również staje się wartością r, jeśli pojawia się po prawej stronie operatora przypisania. Wartości-r można zawsze przypisać do jakiejś innej zmiennej.

Wartość l

Lokalizacja pamięci (adres), w której przechowywane jest wyrażenie, nazywana jest wartością l tego wyrażenia. Zawsze pojawia się po lewej stronie operatora przypisania.

Na przykład:

day = 1;
week = day * 7;
month = 1;
year = month * 12;

Z tego przykładu rozumiemy, że stałe wartości, takie jak 1, 7, 12 i zmienne, takie jak dzień, tydzień, miesiąc i rok, mają wartości r. Tylko zmienne mają l-wartości, ponieważ reprezentują również przypisaną im lokalizację pamięci.

Na przykład:

7 = x + y;

jest błędem wartości l, ponieważ stała 7 nie reprezentuje żadnego miejsca w pamięci.

Parametry formalne

Zmienne pobierające informacje przekazane przez procedurę wywołującą nazywane są parametrami formalnymi. Te zmienne są zadeklarowane w definicji wywoływanej funkcji.

Rzeczywiste parametry

Zmienne, których wartości lub adresy są przekazywane do wywoływanej procedury, nazywane są parametrami rzeczywistymi. Te zmienne są określone w wywołaniu funkcji jako argumenty.

Example:

fun_one()
{
   int actual_parameter = 10;
   call fun_two(int actual_parameter);
}
   fun_two(int formal_parameter)
{
   print formal_parameter;
}

Parametry formalne przechowują informacje o rzeczywistym parametrze, w zależności od zastosowanej techniki przekazywania parametrów. Może to być wartość lub adres.

Podaj wartość

W mechanizmie przekazywania wartości procedura wywołująca przekazuje wartość r rzeczywistych parametrów, a kompilator umieszcza ją w rekordzie aktywacji wywoływanej procedury. Następnie parametry formalne przechowują wartości przekazane przez procedurę wywołującą. Jeżeli wartości utrzymywane przez parametry formalne ulegną zmianie, nie powinno to mieć wpływu na parametry rzeczywiste.

Przekaż przez odniesienie

W przejściu przez mechanizm odniesienia wartość l rzeczywistego parametru jest kopiowana do rekordu aktywacji wywoływanej procedury. W ten sposób wywołana procedura ma teraz adres (miejsce w pamięci) aktualnego parametru, a parametr formalny odnosi się do tej samej lokalizacji w pamięci. W związku z tym, jeśli wartość wskazywana przez parametr formalny ulegnie zmianie, wpływ należy zobaczyć na rzeczywisty parametr, ponieważ powinny one również wskazywać na tę samą wartość.

Przejdź przez kopiowanie-przywracanie

Ten mechanizm przekazywania parametrów działa podobnie do „przekazywania przez referencję”, z tą różnicą, że zmiany rzeczywistych parametrów są dokonywane po zakończeniu wywoływanej procedury. Po wywołaniu funkcji wartości rzeczywistych parametrów są kopiowane do rekordu aktywacji wywoływanej procedury. Parametry formalne, jeśli są manipulowane, nie mają wpływu w czasie rzeczywistym na parametry rzeczywiste (w miarę przekazywania l-wartości), ale po zakończeniu wywoływanej procedury wartości l parametrów formalnych są kopiowane do l-wartości parametrów rzeczywistych.

Example:

int y; 
calling_procedure() 
{
   y = 10;     
   copy_restore(y); //l-value of y is passed
   printf y; //prints 99 
}
copy_restore(int x) 
{     
   x = 99; // y still has value 10 (unaffected)
   y = 0; // y is now 0 
}

Po zakończeniu tej funkcji wartość l parametru formalnego x jest kopiowana do rzeczywistego parametru y. Nawet jeśli wartość y zostanie zmieniona przed zakończeniem procedury, wartość l z x jest kopiowana do wartości l z y, dzięki czemu zachowuje się jak wywołanie przez odniesienie.

Być znanym pod imieniem

Języki takie jak Algol zapewniają nowy rodzaj mechanizmu przekazywania parametrów, który działa jak preprocesor w języku C. W mechanizmie przechodzenia przez nazwę nazwa wywoływanej procedury jest zastępowana jej treścią. Przekazywanie nazwy tekstowo zastępuje wyrażenia argumentów w wywołaniu procedury dla odpowiednich parametrów w treści procedury, dzięki czemu może teraz działać na rzeczywistych parametrach, podobnie jak przekazywanie przez odwołanie.

Tablica symboli to ważna struktura danych tworzona i utrzymywana przez kompilatory w celu przechowywania informacji o występowaniu różnych bytów, takich jak nazwy zmiennych, nazwy funkcji, obiekty, klasy, interfejsy itp. Tablica symboli jest używana zarówno przez analizę, jak i syntezę części kompilatora.

Tabela symboli może służyć następującym celom w zależności od używanego języka:

  • Przechowywanie nazw wszystkich podmiotów w uporządkowanej formie w jednym miejscu.

  • Aby sprawdzić, czy zmienna została zadeklarowana.

  • Aby zaimplementować sprawdzanie typów, weryfikując przypisania i wyrażenia w kodzie źródłowym są semantycznie poprawne.

  • Określenie zakresu nazwy (rozdzielczość zakresu).

Tablica symboli to po prostu tablica, która może być liniowa lub tablica mieszająca. Przechowuje wpis dla każdej nazwy w następującym formacie:

<symbol name,  type,  attribute>

Na przykład, jeśli tablica symboli ma przechowywać informacje o następującej deklaracji zmiennej:

static int interest;

to powinien przechowywać wpis taki jak:

<interest, int, static>

Klauzula atrybutu zawiera wpisy związane z nazwą.

Realizacja

Jeśli kompilator ma obsługiwać niewielką ilość danych, wówczas tablicę symboli można zaimplementować jako nieuporządkowaną listę, którą można łatwo zakodować, ale nadaje się tylko do małych tabel. Tablicę symboli można zaimplementować na jeden z następujących sposobów:

  • Lista liniowa (posortowana lub nieposortowana)
  • Drzewo wyszukiwania binarnego
  • Tabela skrótów

Spośród wszystkich, tablice symboli są najczęściej implementowane jako tablice skrótów, w których sam symbol kodu źródłowego jest traktowany jako klucz dla funkcji skrótu, a wartość zwracana jest informacją o symbolu.

Operacje

Tabela symboli, liniowa lub hash, powinna zapewniać następujące operacje.

wstawić()

Ta operacja jest częściej wykorzystywana przez fazę analizy, czyli pierwszą połowę kompilatora, w której identyfikowane są tokeny, a nazwy są przechowywane w tabeli. Ta operacja służy do dodawania informacji w tablicy symboli o unikalnych nazwach występujących w kodzie źródłowym. Format lub struktura, w której przechowywane są nazwy, zależy od używanego kompilatora.

Atrybutem symbolu w kodzie źródłowym są informacje związane z tym symbolem. Te informacje zawierają wartość, stan, zakres i typ symbolu. Funkcja insert () przyjmuje symbol i jego atrybuty jako argumenty i przechowuje informacje w tablicy symboli.

Na przykład:

int a;

powinien zostać przetworzony przez kompilator jako:

insert(a, int);

lookup ()

Operacja lookup () służy do wyszukiwania nazwy w tablicy symboli w celu określenia:

  • jeśli symbol istnieje w tabeli.
  • jeśli jest zadeklarowany przed użyciem.
  • jeśli nazwa jest używana w zakresie.
  • jeśli symbol został zainicjowany.
  • jeśli symbol został zadeklarowany wiele razy.

Format funkcji lookup () różni się w zależności od języka programowania. Podstawowy format powinien pasować do następujących:

lookup(symbol)

Ta metoda zwraca 0 (zero), jeśli symbol nie istnieje w tablicy symboli. Jeśli symbol istnieje w tablicy symboli, zwraca atrybuty przechowywane w tablicy.

Zarządzanie zakresem

Kompilator obsługuje dwa typy tablic symboli: a global symbol table do których można uzyskać dostęp za pomocą wszystkich procedur i scope symbol tables które są tworzone dla każdego zakresu w programie.

Aby określić zakres nazwy, tabele symboli są ułożone w strukturę hierarchiczną, jak pokazano na poniższym przykładzie:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

Powyższy program można przedstawić w hierarchicznej strukturze tablic symboli:

Globalna tablica symboli zawiera nazwy jednej zmiennej globalnej (wartość int) i dwie nazwy procedur, które powinny być dostępne dla wszystkich węzłów potomnych pokazanych powyżej. Nazwy wymienione w tabeli symboli pro_one (i wszystkich jej tabelach podrzędnych) nie są dostępne dla symboli pro_two i jego tabel podrzędnych.

Ta hierarchia struktury danych tablicy symboli jest przechowywana w analizatorze semantycznym i za każdym razem, gdy nazwa musi zostać wyszukana w tablicy symboli, jest przeszukiwana przy użyciu następującego algorytmu:

  • najpierw będzie wyszukiwany symbol w bieżącym zakresie, tj. bieżącej tablicy symboli.

  • jeśli nazwa zostanie znaleziona, wyszukiwanie jest zakończone, w przeciwnym razie będzie przeszukiwane w tabeli symboli nadrzędnych do,

  • znaleziono nazwę lub przeszukano globalną tablicę symboli.

Kod źródłowy można bezpośrednio przetłumaczyć na docelowy kod maszynowy, więc po co w ogóle musimy tłumaczyć kod źródłowy na kod pośredni, który jest następnie tłumaczony na kod docelowy? Zobaczmy, dlaczego potrzebujemy kodu pośredniego.

  • Jeśli kompilator tłumaczy język źródłowy na docelowy język maszynowy bez opcji generowania kodu pośredniego, to dla każdej nowej maszyny wymagany jest pełny natywny kompilator.

  • Kod pośredni eliminuje potrzebę nowego pełnego kompilatora dla każdej unikalnej maszyny, utrzymując część analityczną taką samą dla wszystkich kompilatorów.

  • Druga część kompilatora, synteza, jest zmieniana w zależności od maszyny docelowej.

  • Stosowanie modyfikacji kodu źródłowego w celu poprawy wydajności kodu staje się łatwiejsze dzięki zastosowaniu technik optymalizacji kodu w kodzie pośrednim.

Reprezentacja pośrednia

Kody pośrednie mogą być przedstawiane na różne sposoby i mają swoje własne zalety.

  • High Level IR- Reprezentacja kodu pośredniego wysokiego poziomu jest bardzo zbliżona do samego języka źródłowego. Można je łatwo wygenerować z kodu źródłowego, a my możemy łatwo zastosować modyfikacje kodu w celu zwiększenia wydajności. Ale w przypadku optymalizacji maszyny docelowej jest mniej preferowana.

  • Low Level IR - Ten znajduje się blisko maszyny docelowej, co sprawia, że ​​nadaje się do alokacji rejestrów i pamięci, wyboru zestawu instrukcji itp. Jest dobry do optymalizacji zależnych od maszyny.

Kod pośredni może być specyficzny dla języka (np. Kod bajtowy dla Java) lub niezależny od języka (kod trójadresowy).

Kod trójadresowy

Generator kodu pośredniego otrzymuje dane wejściowe z poprzedniej fazy, analizatora semantycznego, w postaci drzewa składni z adnotacjami. To drzewo składniowe można następnie przekształcić w reprezentację liniową, np. Notację postfiksową. Kod pośredni jest zwykle kodem niezależnym od maszyny. Dlatego generator kodu zakłada, że ​​ma nieograniczoną ilość pamięci (rejestru) do generowania kodu.

Na przykład:

a = b + c * d;

Generator kodu pośredniego spróbuje podzielić to wyrażenie na wyrażenia podrzędne, a następnie wygeneruje odpowiedni kod.

r1 = c * d;
r2 = b + r1;
a = r2

r jest używany jako rejestry w programie docelowym.

Kod z trzema adresami ma co najwyżej trzy lokalizacje adresowe do obliczenia wyrażenia. Kod trójadresowy można przedstawić w dwóch postaciach: poczwórnej i potrójnej.

Czteroosobowe

Każda instrukcja w prezentacji poczwórnej jest podzielona na cztery pola: operator, arg1, arg2 i wynik. Powyższy przykład jest przedstawiony poniżej w formacie poczwórnym:

Op arg 1 arg 2 wynik
* do re r1
+ b r1 r2
+ r2 r1 r3
= r3 za

Potrójne

Każda instrukcja w prezentacji trójek ma trzy pola: op, arg1 i arg2. Wyniki odpowiednich wyrażeń podrzędnych są oznaczone pozycją wyrażenia. Trójki reprezentują podobieństwo z DAG i drzewem składni. Są one równoważne DAG podczas reprezentowania wyrażeń.

Op arg 1 arg 2
* do re
+ b (0)
+ (1) (0)
= (2)

Podczas optymalizacji trzykrotnie borykają się z problemem niezmienności kodu, ponieważ wyniki są pozycyjne, a zmiana kolejności lub pozycji wyrażenia może powodować problemy.

Pośrednie potrójne

Ta reprezentacja jest ulepszeniem w stosunku do reprezentacji potrójnej. Używa wskaźników zamiast pozycji do przechowywania wyników. Umożliwia to optymalizatorom swobodną zmianę pozycji wyrażenia podrzędnego w celu utworzenia zoptymalizowanego kodu.

Deklaracje

Przed użyciem należy zadeklarować zmienną lub procedurę. Deklaracja polega na przydzieleniu miejsca w pamięci oraz wpisaniu typu i nazwy w tablicy symboli. Program można zakodować i zaprojektować z uwzględnieniem struktury maszyny docelowej, ale nie zawsze może być możliwe dokładne przekonwertowanie kodu źródłowego na język docelowy.

Przyjmując cały program jako zbiór procedur i podprocedur, możliwe staje się zadeklarowanie wszystkich nazw jako lokalnych dla procedury. Alokacja pamięci odbywa się w sposób sekwencyjny, a nazwy są przydzielane do pamięci w kolejności zadeklarowanej w programie. Używamy zmiennej offset i ustawiamy ją na zero {offset = 0}, które oznacza adres bazowy.

Źródłowy język programowania i architektura maszyny docelowej mogą różnić się sposobem przechowywania nazw, dlatego używane jest adresowanie względne. Podczas gdy pamięć jest przydzielana pierwszej nazwie, zaczynając od komórki pamięci 0 {offset = 0}, kolejnej nazwie deklarowanej później należy przydzielić pamięć obok pierwszej.

Example:

Weźmy przykład języka programowania C, w którym zmiennej całkowitej są przypisane 2 bajty pamięci, a zmiennej zmiennoprzecinkowej przypisane są 4 bajty pamięci.

int a;
float b;
Allocation process:
{offset = 0}
int a;
id.type = int
id.width = 2
offset = offset + id.width 
{offset = 2}
float b;
   id.type = float
   id.width = 4
   offset = offset + id.width 
{offset = 6}

Aby wprowadzić ten szczegół do tabeli symboli, można użyć procedury enter . Ta metoda może mieć następującą strukturę:

enter(name, type, offset)

Procedura ta powinna stworzyć wpis w tablicy symboli, dla nazwy zmiennej , mając jej typ ustawiony na typ i względne przesunięcie adresu w obszarze danych.

Generację kodu można uznać za ostatnią fazę kompilacji. Dzięki generowaniu kodu pocztowego proces optymalizacji można zastosować w kodzie, ale można to postrzegać jako część samej fazy generowania kodu. Kod wygenerowany przez kompilator jest kodem obiektowym jakiegoś języka programowania niższego poziomu, na przykład asemblera. Widzieliśmy, że kod źródłowy napisany w języku wyższego poziomu jest przekształcany w język niższego poziomu, co daje w wyniku kod obiektowy niższego poziomu, który powinien mieć następujące minimalne właściwości:

  • Powinien zawierać dokładne znaczenie kodu źródłowego.
  • Powinien być wydajny pod względem wykorzystania procesora i zarządzania pamięcią.

Zobaczymy teraz, jak kod pośredni jest przekształcany w docelowy kod obiektowy (w tym przypadku kod asemblera).

Skierowany wykres acykliczny

Skierowany graf acykliczny (DAG) to narzędzie, które przedstawia strukturę podstawowych bloków, pomaga zobaczyć przepływ wartości przepływających między podstawowymi blokami, a także oferuje optymalizację. DAG zapewnia łatwą transformację podstawowych bloków. DAG można zrozumieć tutaj:

  • Węzły liści reprezentują identyfikatory, nazwy lub stałe.

  • Węzły wewnętrzne reprezentują operatorów.

  • Węzły wewnętrzne reprezentują również wyniki wyrażeń lub identyfikatory / nazwy, w których mają być przechowywane lub przypisywane wartości.

Example:

t0 = a + b
t1 = t0 + c
d = t0 + t1

[t 0 = a + b]

[t 1 = t 0 + c]

[d = t 0 + t 1 ]

Optymalizacja wizjera

Ta technika optymalizacji działa lokalnie na kodzie źródłowym, aby przekształcić go w zoptymalizowany kod. Mówiąc lokalnie, mamy na myśli niewielką część dostępnego bloku kodu. Metody te można stosować zarówno do kodów pośrednich, jak i docelowych. Zestaw instrukcji jest analizowany i sprawdzany pod kątem następującej możliwej optymalizacji:

Eliminacja zbędnych instrukcji

Na poziomie kodu źródłowego użytkownik może wykonać następujące czynności:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }
int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }
int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }
int add_ten(int x)
   {
   return x + 10;
   }

Na poziomie kompilacji kompilator wyszukuje instrukcje, które są z natury zbędne. Wielokrotne ładowanie i przechowywanie instrukcji może mieć to samo znaczenie, nawet jeśli niektóre z nich zostaną usunięte. Na przykład:

  • MOV x, R0
  • MOV R0, R1

Możemy usunąć pierwszą instrukcję i przepisać zdanie jako:

MOV x, R1

Nieosiągalny kod

Kod nieosiągalny to część kodu programu, do której nigdy nie uzyskuje się dostępu z powodu konstrukcji programistycznych. Programiści mogli przypadkowo napisać fragment kodu, do którego nigdy nie można dotrzeć.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

W tym segmencie kodu printf Instrukcja nigdy nie zostanie wykonana, ponieważ element sterujący programu wraca, zanim będzie mógł wykonać printf może być usunięty.

Przepływ optymalizacji sterowania

Istnieją przypadki w kodzie, w których sterowanie programem przeskakuje tam iz powrotem bez wykonywania żadnego znaczącego zadania. Te skoki można usunąć. Rozważmy następujący fragment kodu:

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

W tym kodzie etykieta L1 może zostać usunięta, gdy przekazuje sterowanie do L2. Więc zamiast przeskakiwać do L1, a następnie do L2, sterowanie może bezpośrednio dotrzeć do L2, jak pokazano poniżej:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Uproszczenie wyrażeń algebraicznych

Są sytuacje, w których wyrażenia algebraiczne można uprościć. Na przykład wyrażeniea = a + 0 można zastąpić a sama i wyrażenie a = a + 1 można po prostu zastąpić przez INC a.

Redukcja siły

Istnieją operacje, które pochłaniają więcej czasu i miejsca. Ich „siłę” można zmniejszyć, zastępując je innymi operacjami, które zajmują mniej czasu i miejsca, ale dają ten sam efekt.

Na przykład, x * 2 można zastąpić x << 1, która obejmuje tylko jedną zmianę w lewo. Chociaż wyjście a * a i a 2 jest takie samo, implementacja a 2 jest znacznie wydajniejsza.

Dostęp do instrukcji maszyny

Maszyna docelowa może wdrażać bardziej wyrafinowane instrukcje, które mogą znacznie wydajniej wykonywać określone operacje. Jeśli kod docelowy może bezpośrednio uwzględnić te instrukcje, nie tylko poprawi to jakość kodu, ale także zapewni bardziej wydajne wyniki.

Generator kodów

Od generatora kodu oczekuje się zrozumienia środowiska wykonawczego maszyny docelowej i zestawu instrukcji. Generator kodu powinien wziąć pod uwagę następujące rzeczy, aby wygenerować kod:

  • Target language: Generator kodu musi być świadomy charakteru języka docelowego, dla którego kod ma zostać przekształcony. Ten język może ułatwić pewne instrukcje specyficzne dla maszyny, aby pomóc kompilatorowi wygenerować kod w wygodniejszy sposób. Maszyna docelowa może mieć architekturę procesora CISC lub RISC.

  • IR Type: Reprezentacja pośrednia ma różne formy. Może mieć strukturę abstrakcyjnego drzewa składni (AST), odwrotną notację polską lub kod 3-adresowy.

  • Selection of instruction: Generator kodu przyjmuje reprezentację pośrednią jako dane wejściowe i konwertuje (odwzorowuje) ją na zestaw instrukcji maszyny docelowej. Jedna reprezentacja może mieć wiele sposobów (instrukcji), aby ją przekształcić, więc to generator kodu spoczywa na odpowiedzialności za mądry wybór odpowiednich instrukcji.

  • Register allocation: Program ma kilka wartości, które mają być zachowane podczas wykonywania. Architektura maszyny docelowej może nie pozwalać na przechowywanie wszystkich wartości w pamięci procesora lub rejestrach. Generator kodu decyduje, jakie wartości zachować w rejestrach. Decyduje również o rejestrach, które mają być używane do przechowywania tych wartości.

  • Ordering of instructions: W końcu generator kodu decyduje o kolejności, w jakiej instrukcja zostanie wykonana. Tworzy harmonogramy instrukcji ich wykonania.

Deskryptory

Generator kodu musi śledzić zarówno rejestry (dostępność), jak i adresy (lokalizację wartości) podczas generowania kodu. Dla obu z nich używane są następujące dwa deskryptory:

  • Register descriptor: Deskryptor rejestru służy do informowania generatora kodu o dostępności rejestrów. Deskryptor rejestru śledzi wartości przechowywane w każdym rejestrze. Zawsze, gdy podczas generowania kodu wymagany jest nowy rejestr, należy sprawdzić dostępność rejestru przy użyciu tego deskryptora.

  • Address descriptor: Wartości nazw (identyfikatorów) używanych w programie mogą być przechowywane w różnych lokalizacjach podczas wykonywania. Deskryptory adresów służą do śledzenia lokalizacji pamięci, w których przechowywane są wartości identyfikatorów. Te lokalizacje mogą obejmować rejestry procesora, sterty, stosy, pamięć lub kombinację wspomnianych lokalizacji.

Generator kodu aktualizuje oba deskryptory w czasie rzeczywistym. Dla instrukcji load, LD R1, x, generator kodu:

  • aktualizuje deskryptor rejestru R1, który ma wartość x i
  • aktualizuje deskryptor adresu (x), aby pokazać, że jedno wystąpienie x znajduje się w R1.

Generowanie kodu

Bloki podstawowe składają się z sekwencji instrukcji trójadresowych. Generator kodu przyjmuje tę sekwencję instrukcji jako dane wejściowe.

Note: Jeśli wartość nazwy zostanie znaleziona w więcej niż jednym miejscu (rejestr, pamięć podręczna lub pamięć), wartość rejestru będzie miała pierwszeństwo przed pamięcią podręczną i pamięcią główną. Podobnie wartość pamięci podręcznej będzie preferowana w stosunku do pamięci głównej. Pamięć główna nie jest preferowana.

getReg: Generator kodu używa funkcji getReg do określenia stanu dostępnych rejestrów i lokalizacji wartości nazw. getReg działa w następujący sposób:

  • Jeśli zmienna Y jest już w rejestrze R, używa tego rejestru.

  • W przeciwnym razie, jeśli jakiś rejestr R jest dostępny, używa tego rejestru.

  • W przeciwnym razie, jeśli obie powyższe opcje nie są możliwe, wybiera rejestr, który wymaga minimalnej liczby instrukcji ładowania i przechowywania.

Dla instrukcji x = y OP z generator kodu może wykonać następujące czynności. Załóżmy, że L to lokalizacja (najlepiej rejestr), w której ma zostać zapisane wyjście y OP z:

  • Wywołaj funkcję getReg, aby zdecydować o lokalizacji L.

  • Określ bieżącą lokalizację (rejestr lub pamięć) y konsultując się z deskryptorem adresu y. Gdybyy nie jest obecnie zarejestrowany L, a następnie wygeneruj następującą instrukcję, aby skopiować wartość y do L:

    MOV y ', L

    gdzie y’ reprezentuje skopiowaną wartość y.

  • Określ bieżącą lokalizację z używając tej samej metody, co w kroku 2 dla y i wygeneruj następującą instrukcję:

    OP z ', L.

    gdzie z’ reprezentuje skopiowaną wartość z.

  • Teraz L zawiera wartość y OP z, do której ma zostać przypisana x. Tak więc, jeśli L jest rejestrem, zaktualizuj jego deskryptor, aby wskazać, że zawiera on wartośćx. Zaktualizuj deskryptorx aby wskazać, że jest przechowywany w miejscu L.

  • Jeśli yiz nie mają już zastosowania, można je zwrócić systemowi.

Inne konstrukcje kodu, takie jak pętle i instrukcje warunkowe, są przekształcane w język asemblera w sposób generalny.

Optymalizacja to technika transformacji programu, która próbuje ulepszyć kod, sprawiając, że zużywa mniej zasobów (np. Procesor, pamięć) i zapewnia dużą prędkość.

W optymalizacji, ogólne konstrukcje programowania wysokiego poziomu są zastępowane przez bardzo wydajne kody programowania niskiego poziomu. Proces optymalizacji kodu musi przestrzegać trzech zasad podanych poniżej:

  • Kod wyjściowy nie może w żaden sposób zmieniać znaczenia programu.

  • Optymalizacja powinna zwiększyć szybkość programu i jeśli to możliwe, program powinien wymagać mniejszej liczby zasobów.

  • Optymalizacja powinna być szybka i nie powinna opóźniać całego procesu kompilacji.

Wysiłki mające na celu zoptymalizowanie kodu mogą być podejmowane na różnych poziomach kompilacji procesu.

  • Na początku użytkownicy mogą zmienić / przestawić kod lub użyć lepszych algorytmów do napisania kodu.

  • Po wygenerowaniu kodu pośredniego kompilator może zmodyfikować kod pośredni poprzez obliczenia adresu i ulepszenie pętli.

  • Podczas tworzenia docelowego kodu maszynowego kompilator może korzystać z hierarchii pamięci i rejestrów procesora.

Optymalizację można ogólnie podzielić na dwa typy: niezależne od maszyny i zależne od maszyny.

Optymalizacja niezależna od maszyny

W tej optymalizacji kompilator przyjmuje kod pośredni i przekształca część kodu, która nie obejmuje żadnych rejestrów procesora i / lub bezwzględnych lokalizacji pamięci. Na przykład:

do
{
   item = 10;
   value = value + item; 
}while(value<100);

Ten kod polega na powtórnym przypisaniu elementu identyfikatora, który jeśli umieścimy w ten sposób:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

powinien nie tylko zapisywać cykle procesora, ale może być używany na dowolnym procesorze.

Optymalizacja zależna od maszyny

Optymalizacja zależna od maszyny jest wykonywana po wygenerowaniu kodu docelowego i po przekształceniu kodu zgodnie z architekturą maszyny docelowej. Obejmuje rejestry procesora i może mieć raczej bezwzględne odniesienia do pamięci niż odniesienia względne. Optymalizatory zależne od maszyny dokładają wszelkich starań, aby maksymalnie wykorzystać hierarchię pamięci.

Podstawowe bloki

Kody źródłowe zwykle zawierają szereg instrukcji, które są zawsze wykonywane w sekwencji i są uważane za podstawowe bloki kodu. Te podstawowe bloki nie zawierają między sobą żadnych instrukcji skoku, tj. Gdy wykonywana jest pierwsza instrukcja, wszystkie instrukcje w tym samym bloku podstawowym zostaną wykonane w kolejności ich pojawiania się bez utraty kontroli przepływu programu.

Program może mieć różne konstrukcje jako podstawowe bloki, takie jak IF-THEN-ELSE, instrukcje warunkowe SWITCH-CASE i pętle, takie jak DO-WHILE, FOR i REPEAT-UNTIL itp.

Podstawowa identyfikacja bloku

Aby znaleźć podstawowe bloki w programie, możemy użyć następującego algorytmu:

  • Wyszukaj instrukcje nagłówka wszystkich podstawowych bloków, od których zaczyna się podstawowy blok:

    • Pierwsza instrukcja programu.
    • Instrukcje, które są kierowane do dowolnej gałęzi (warunkowe / bezwarunkowe).
    • Instrukcje występujące po każdej instrukcji gałęzi.
  • Instrukcje nagłówkowe i następujące po nich instrukcje tworzą podstawowy blok.

  • Podstawowy blok nie zawiera żadnej instrukcji nagłówka żadnego innego podstawowego bloku.

Podstawowe bloki są ważnymi pojęciami zarówno z punktu widzenia generowania kodu, jak i optymalizacji.

Podstawowe bloki odgrywają ważną rolę w identyfikowaniu zmiennych, które są używane więcej niż raz w jednym bloku podstawowym. Jeśli jakakolwiek zmienna jest używana więcej niż raz, pamięć rejestrów przydzielona tej zmiennej nie musi być opróżniana, chyba że blok zakończy wykonywanie.

Wykres przepływu sterowania

Podstawowe bloki w programie można przedstawić za pomocą grafów sterowania. Wykres przepływu sterowania przedstawia sposób przekazywania sterowania programem między blokami. Jest to przydatne narzędzie, które pomaga w optymalizacji, pomagając w lokalizowaniu niechcianych pętli w programie.

Optymalizacja pętli

Większość programów działa jako pętla w systemie. Konieczna staje się optymalizacja pętli, aby zaoszczędzić cykle procesora i pamięć. Pętle można optymalizować za pomocą następujących technik:

  • Invariant code: Fragment kodu, który znajduje się w pętli i oblicza tę samą wartość w każdej iteracji, nazywany jest kodem niezmiennym w pętli. Ten kod można przenieść z pętli, zapisując go do obliczenia tylko raz, a nie przy każdej iteracji.

  • Induction analysis : Zmienna nazywana jest zmienną indukcyjną, jeśli jej wartość zostanie zmieniona w pętli o wartość niezmienną w pętli.

  • Strength reduction: Istnieją wyrażenia, które zajmują więcej cykli procesora, czasu i pamięci. Wyrażenia te należy zastąpić tańszymi wyrażeniami bez uszczerbku dla wyników wyrażenia. Na przykład mnożenie (x * 2) jest kosztowne pod względem cykli procesora niż (x << 1) i daje ten sam wynik.

Eliminacja martwego kodu

Martwy kod to jedna lub więcej instrukcji kodu, którymi są:

  • Albo nigdy nie stracony, albo nieosiągalny,
  • Lub po wykonaniu ich dane wyjściowe nigdy nie są używane.

Dlatego martwy kod nie odgrywa żadnej roli w działaniu żadnego programu i dlatego można go po prostu wyeliminować.

Częściowo martwy kod

Istnieją pewne instrukcje kodu, których obliczone wartości są używane tylko w określonych okolicznościach, tj. Czasami wartości są używane, a czasami nie. Takie kody są znane jako częściowo martwy kod.

Powyższy wykres przepływu sterowania przedstawia fragment programu, w którym zmienna „a” jest używana do przypisania wyniku wyrażenia „x * y”. Załóżmy, że wartość przypisana do 'a' nigdy nie jest używana wewnątrz pętli. Natychmiast po wyjściu kontrolki z pętli, 'a' przypisywana jest wartość zmiennej 'z', która będzie później używana w programie. Dochodzimy tutaj do wniosku, że kod przypisania „a” nigdy nie jest nigdzie używany, dlatego kwalifikuje się do usunięcia.

Podobnie, powyższy obraz pokazuje, że instrukcja warunkowa jest zawsze fałszywa, co oznacza, że ​​kod napisany w prawdziwym przypadku nigdy nie zostanie wykonany, dlatego można go usunąć.

Częściowa nadmiarowość

Zbędne wyrażenia są obliczane więcej niż raz w ścieżce równoległej, bez żadnych zmian w operandach, podczas gdy wyrażenia częściowo nadmiarowe są obliczane więcej niż raz w ścieżce, bez zmiany operandów. Na przykład,

[zbędne wyrażenie]

[częściowo zbędne wyrażenie]

Kod niezmienny w pętli jest częściowo nadmiarowy i można go wyeliminować za pomocą techniki ruchu kodu.

Innym przykładem częściowo nadmiarowego kodu może być:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Zakładamy, że wartości argumentów (y i z) nie są zmieniane od przypisania zmiennej a do zmiennej c. Tutaj, jeśli warunek jest prawdziwy, to y OP z jest obliczane dwukrotnie, w przeciwnym razie raz. Ruch kodu można wykorzystać do wyeliminowania tej nadmiarowości, jak pokazano poniżej:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Tutaj, czy warunek jest prawdziwy czy fałszywy; y OP z należy obliczyć tylko raz.