Budowa kompilatora

From Obrona

Revision as of 09:07, 23 October 2008

BUDOWA KOMPILATORA

Wprowadzenie

Jedną z metod wykorzystania komputerów jest pisanie programów w językach programowania. Narzędzia komputerowe służące do przetworzenia tekstu napisanego w języku programowania (programu) to translatory. Translatory tłumaczą kod programu do postaci wykonywanej przez komputer, lub nadającej się do przetworzenia przez inny program. Przykładem tych pierwszych są translatory popularnych języków programowania, takich jak C, które tłumaczą kod w języku programowania do kodu maszynowego, wykonywalnego przez procesor komputera. Przykładem tych drugich mogą być translatory języków skryptowych, na przykład sh. Te z kolei, zamieniają treść skryptu na sekwencję poleceń wykonywanych przez system operacyjny.

Translatory można podzielić na kompilatory i interpretery. Te pierwsze dokonują jednorazowego tłumaczenia kodu, który jest następnie wykonywany, lub przetwarzany niezależnie od kompilatora, przykładem jest kompilator języka C. Przykładem interpretera jest interpreter sh, który analizuje kod na bieżąco i wykonuje polecenia. Kod interpretowany wymaga każdorazowo do uruchomienia interpretera, w tym przypadku powłoki sh. Programy interpretowane są przeważnie wolniejsze od kompilowanych. Często jednak prościej jest je pisać i odnajdywać w nich błędy.


Zalety:
a) kompilatory
§ program wynikowy wykonuje się szybciej
§ do wykonania programu wynikowego nie jest potrzebny kompilator
b) interpretery
§ łatwość zmian programu
§ mniejsza zajętość pamięci zewnętrznej (tylko tekst źródłowy)
§ możliwość pracy konwersacyjnej (zatrzymanie wykonania, zmiana warto ci zmiennych, kontynuacja wykonania)

Budowa kompilatora

Skaner
Podstawowymi celami analizatora leksykalnego - skanera, są :
§ Sprawdzenie czy tekst napisany w języku komputerowym nie zawiera niedozwolonych znaków (i ich ewentualne usunięcie). W większości języków komputerowych dozwolone jest użycie wszystkich znaków ASCII
§ Pogrupowanie znaków w jednostki leksykalne - tokeny ; przez token rozumie się przeważnie grupę znaków odseparowaną od pozostałych białymi znakami (spacja, tabulator, cr)
§ Rozpoznanie tokenów, wyróżnienie słów kluczowych, operatorów, łańcuchów znakowych
§ Stworzenie tablicy tokenów, przechowującej tokeny i informacje o nich
Skaner przekazuje rozpoznawane tokeny do parsera, który wykorzystuje również tablicę tokenów do późniejszego modyfikowania ich wartości.
Skaner jest najprostszą częścią translatora. W niektórych, prostszych, przypadkach może mieć postać kilkunastolinijkowej procedury w języku C.

Parser
Parser analizuje tekst napisany w języku i dokonuje jego rozbioru gramatycznego. Równocześnie sprawdzana jest poprawność gramatyczna. Aby to było możliwe, parser przechowuje definicję gramatyki języka. W trakcie rozbioru gramatycznego tworzone są dodatkowe tablice, które umożliwiają dalszą obróbkę tekstu programu przez generator kodu.

Gramatyka formalna generacyjna jest jedną z metod definiowania języka. Składa się ona z :
§ alfabetu nieterminalnego (zbioru symboli metajęzyka)
§ alfabetu terminalnego
§ skończonego zbioru reguł produkcji
§ symbolu początkowego gramatyki
Gramatyki dzielą się na różne klasy w związku z ich konstrukcją i własnościami. Z tymi klasami wiąże się odpowiednia konstrukcja skanera.

Notacja BNF

Jest to najczęściej stosowana notacja, służąca do zapisywania gramatyk. Gramatyka bezkontekstowa zapisana w tej notacji ma postać szeregu wyrażeń, z których każde składa się z symbolu nieterminalnego ujętego w znaki < >, symbolu produkcji ::= i następującego po nim (po prawej stronie) skończonego ciągu symboli nieterminalnych i terminalnych. Symbol nieterminalny, który jest po lewej stronie symbolu produkcji, może się również powtarzać po jego prawej stronie, umożliwia to definiowanie reguł rekursywnych. Poniżej przedstawiono prosty przykład gramatyki bezkontekstowej, zapisanej w notacji BNF, generującej liczby binarne :
<liczba_binarna> ::= <liczba_binarna> <cyfra> <liczba_binarna> ::= <cyfra> <cyfra>  ::= 0 | 1 Gramatyka ta ma więc postać ogólną: G = { N, V, P, S } Gramatyka N = { <liczba_binarna>, <cyfra> } Alfabet nieterminalny V = { 0, 1 } Alfabet terminalny P = { <liczba_binarna> ::= <liczba_binarna> <cyfra> ;

     <liczba_binarna> ::= <cyfra> ;
     <cyfra>          ::= { 0 | 1 }  Zbiór regół produkcji

Kompilator jest programem wykonującym konwersję kodu źródłowego (przeważnie programów napisanych w języku wysokiego poziomu) do postaci zrozumiałej dla komputera (kodu wynikowego).
Proces ten zwany kompilacją składa się z trzech części:
· Analiza leksykalna
Polega na czytaniu kolejnych znaków instrukcji i rozpoznawaniu znaczników danego języka. Znacznikami są wszystkie ciągi znaków zdefiniowane w tablicy kodów znaczników (np. słowa kluczowe, operatory arytmetyczne itd.)
Część kompilatora przeprowadzająca analizę leksykalną nazywa się „Skanerem”
Wynikiem działania skanera jest ciąg liczb całkowitych reprezentujących kolejne znaczniki występujące w kodzie programu, lub zgłoszenie błędu. Przyczyną wystąpienia błędu na ty etapie kompilacji jest napotkanie na znacznik nie spełniający zasad leksykalnych (np. rozpoczynający się cyfrą, gdy jest to niedozwolone).
· Analiza syntaktyczna
Polega na rozpoznawaniu poszczególnych konstrukcji języka zgodnie z jego gramatyką. Gramatyka języka zbudowana jest z listy definicji kolejnych konstrukcji języka. Rozróżnia się dwa podejścia analizy syntaktycznej:
- Od szczegółu do ogółu ( np. metoda poprzedzania znaczników )

- Od ogółu do szczegółu ( np. metoda zejść rekursywnych )

Część kompilatora przeprowadzająca analizę syntaktyczną nazywa się „Parserem” Wynikiem działania parsera jest program w postaci ciągu definicji syntaktycznych danego języka. · Generacja kodu
Ta część kompilatora na podstawie danych wejściowych (ciągu konstrukcji syntaktycznych) wykonuje odpowiednie procedury, których wynikiem jest odpowiedni kod w postaci instrukcji języka maszynowego (zrozumiałego dla komputera).
Generacja kodu może być wykonywana w sposób bezpośredni lub z wykorzystaniem języka pośredniego.
Na tym etapie kompilacji możliwe jest dokonanie optymalizacji kodu wynikowego (pod względem : minimalnego czasu działania, minimalnego rozmiaru kodu itp.)