Aktualnie „na rynku” dostępnych jest kilkaset języków programowania (większość z nich raczej niszowa) i w przyszłości pojawi się ich pewnie jeszcze kilka. Uczyć się każdego z nich zwyczajnie nie ma sensu, ale pracując jako programista dobrze jest mieć świadomość jak wygląda ogólny mechanizm działania poszczególnych grup języków. Na szczęście nie musimy znać kilkuset definicji – języki programowanie z reguły dzielą się na te określane mianem interpretowanych lub kompilowanych.

Na co dzień tworzymy nasze programy korzystając z wysokopoziomowych języków, które są kompletnie niezrozumiałe dla maszyn (dla nas też nie zawsze 😑). Program napisany za pomocą takiego języka nazywany jest kodem źródłowym. Potrzebny jest jednak jeszcze inny program, który przetłumaczy ciąg instrukcji kodu źródłowego na kod maszynowy. Tutaj właśnie do gry wchodzi kompilator lub interpreter. W tym artykule będę chciał skupić się na sposobie działania kompilatora, ale najpierw wyjaśnię pokrótce czym różni się jeden od drugiego.

Dla zachowania bardziej praktycznego podejścia, poszczególne fazy kompilatora opiszę w oparciu o zasady działania kompilatora przeznaczonego dla języka Swift.

 

Kompilator vs interpreter

 

W dużym skrócie kompilator skanuje na początku cały kod źródłowy, generując ostatecznie na jego podstawie kod maszynowy, który zostaje umieszczony w pliku wykonywalnym. Plik ten następnie może zostać uruchomiony w celu wykonania programu. Interpreter jest bardziej bezpośredni i „od ręki” wykonuje nasz program, przekształcając instrukcje w konkretne wyniki.

W przypadku kompilatora tworzone są obiekty pośrednie, ponieważ proces kompilacji jest wieloetapowy (o czym przekonacie się niebawem) i bierze pod uwagę dodatkową optymalizację naszego kodu. Analiza całego kodu źródłowego wymaga odrobiny czasu i zasobów, natomiast w zamian otrzymujemy szybsze wykonanie programu.

Interpreter analizuje instrukcje „w locie”, więc potrzebuje mniej czasu na analizę kodu. W rezultacie jednak wykonanie samego programu jest wolniejsze niż w przypadku kompilacji. Dodatkowo, interpreter nie tworzy plików pośrednich, co pozwala zaoszczędzić trochę zasobów urządzenia.

Nie będzie pewnie dla Was wielkim zaskoczeniem jeżeli napiszę, że języki programowanie korzystające z interpretera określane są mianem „interpretowanych”, natomiast te korzystające z kompilatora określa się jako „kompilowane”. Przykładem pierwszych są na przykład Ruby lub Python, natomiast do tych drugich możemy zaliczyć Swifta, C++, czy też Javę.

Należy natomiast zwrócić uwagę na fakt, że łatka przypięta do danego języka określa jedynie najbardziej powszechny sposób w jaki jest on obsługiwany. W rzeczywistości dany język może posiadać zarówno implementację dla kompilatora jak i interpretera. Przykładem takich języków są Haskell oraz Scala.

 

Jak działa kompilator?

 

Skoro różnice mamy już wyjaśnione to możemy skupić się samym kompilatorze 🧐. Wiemy już, że przekształca on wysokopoziomowy kod do postaci niskopoziomowej zrozumiałej dla konkretnej maszyny (na przykład telefonu komórkowego). W przypadku Javy, kod zostanie przetłumaczony najpierw to wersji pośredniej (Java Bytecode), która zostanie następnie wykonany przez Java Virtual Machine. Swift natomiast będzie tłumaczył kod do Swift Intermediate Language, który zostanie dodatkowo zoptymalizowany. Na jego podstawie zostanie wygenerowany kod LLVM IR, a w ostatniej fazie kod maszynowy.

Tutaj macie taką bardzo ogólną wizualizację:

Działanie kompilatora można podzielić na dwie fazy – front end oraz back end (nie mylić z aplikacjami webowymi).

 

Front end

W fazie tej kompilator sprawdza, czy w kodzie nie ma błędów składniowych, czy dana zmienna została zadeklarowana przed jej użyciem, jaki typ został jej przypisany. Jest to etap, na którym działanie kompilatora jest najbardziej widoczne dla użytkownika. Błędy wyświetlane przez IDE są generowane właśnie przez front end.

Na tym etapie tworzona jest również struktura określana jako Symbol Table, która zwiera informacje o wszystkich symbolach dostępnych w kodzie. Jeżeli kompilator nie napotka żadnych błędów to na podstawie kodu źródłowego zostanie utworzona „pośrednia” wersja kodu, która zostanie przekazana do fazy back end’u.

W przypadku Swift’a za front end odpowiada Clang.

Back end

W tej fazie na podstawie kodu „pośredniego” oraz symbol table generowany jest ostatecznie kod maszynowy. W przypadku Swift’a za back end odpowiada LLVM (to nie jest skrót, ale nazwa własna).

Każda z operacji wykonywanych zarówno w fazie front end jak i back end tworzy określoną strukturę danych, która przekazywana jest do następnego korku. Poszczególne etapy można podzielić na lexical analysis, syntax analysis, semantic analysis, intermediate code generation (front end) oraz code optimization, code generation (back end).

Mała wizualizacja:

 

Lexical Analysis

 

Pierwszy etap pracy kompilatora. W jej trakcie dzieli on kod źródłowy na fragmenty określane jako lexems, a następnie na ich podstawie generuje sekwencję tokenów.

Lexem jest unikalnym cięgiem znaków, który może zostać wyodrębniony z kodu źródłowego. Przykładem może być właściwie wszystko z czego korzystamy podczas pisania kodu – znaki takie jak dwukropki, nawiasy, instrukcje while, if, for, nazwy zmiennych itd.

Token natomiast jest obiektem, który opisuje lexem. Zwiera informacje o tym czy dany lexem jest na przykład słowem kluczowym, czy też tylko nazwą zmiennej. Dodatkowo przechowuje on informacje o położeniu lexem w kodzie źródłowym (wiersz / kolumna).

Jeżeli kompilator napotka na ciąg znaków, z których nie będzie potrafił utworzyć tokena, to zwróci błąd, który za pomocą IDE zostanie wyświetlony użytkownikowi. Jednak ewentualne błędy składniowe generowane są dopiero w następnym kroku. Tutaj chodzi bardziej o użycie niedozwolonych znaków. Na przykład użycie „ą” w nazwie zmiennej.

 

Syntax Analysis

 

Na tym etapie kompilator korzysta z sekwencji tokenów utworzonej w poprzednim kroku. Wykorzystuje je do wygenerowania struktury nazywanej Abstract Syntax Tree (AST). AST prezentuje logiczną strukturę programu:

To na tym etapie kod źródłowy jest sprawdzany pod kątem błędów składniowych. Jeżeli zapomnicie zamknąć nawias po instrukcji „if” kompilator właśnie w tej chwili Wam o tym przypomni.

W przypadku Swift’a za etap ten odpowiada parser skrywający się w bibliotece lib/Parse, który został napisany w języku C++. Zawiera on wbudowany lexer, który odpowiada jednocześnie za wykonanie fazy Lexical Analysis. Jeżeli chcecie sprawdzić sobie jak dokładnie wygląda jego implementacja to możecie zrobić to pod tym adresem.

 

Semantic Analysis

 

Wykorzystując AST utworzone podczas Syntax Analysis, kompilator sprawdzi, czy nasz kod spełnia wymogi określone przez dany język programowania. Ten etap również podzielony został na pewne kroki.

Jednym z nich jest type checking. Kompilator sprawdzi na przykład, czy do poszczególnych zmiennych zostały przypisane odpowiednie typy danych. Jeżeli będziecie próbowali przypisać wartość Boolean do zmiennej typu String, to oczywiście kompilator zgłosi odpowiedni błąd.

Type inference (dobrze znane użytkownikom Swift’a) będzie odpowiadało za przypisanie właściwego typu danych do zmiennych, w których typ ten nie został bezpośrednio zdefiniowany. Jeżeli kompilator zdoła we własnym zakresie określić jaki typ danych został wykorzystany, to przy odpowiednim węźle (node) w strukturze AST doda odpowiednią informację. Oczywiście nie wszystkie języki wspierają tę funkcję. Jeżeli chcecie sprawdzić, w których językach zostało zastosowane type inference to możecie zajrzeć na stronę wiki.

Jak już wcześniej wspomniałem, kompilator przechowuje dane o wszystkich symbolach występujących w kodzie źródłowym w strukturze Symbol Table. Na jej podstawie w fazie określanej jako symbol managment, kompilator jest w stanie określić, czy w kodzie źródłowym nie występują na przykład dwie zmienne o tej samej nazwie, czy dana zmienna jest dostępna w ramach określonego kontekstu, itd.

Efektem końcowym fazy Semantic Analysis jest struktura określana jako Annotated AST lub Type-checked AST, a także wspomniana już tablica symboli. Semantic analysis dla Swift’a zostało zaimplementowane w bibliotece lib/Sema.

 

 

Intermediate Code Generation

 

W fazie generacji kodu pośredniego, kompilator wykorzysta Annotated AST do utworzenia kodu niezależnego od platformy. W przypadku Swift’a na tym etapie tworzony jest wysokopoziomowy kod w języku określanym jako Swift Intermediate Language. Przeznaczony jest on dalszej analizy oraz optymalizacji. Jego implementację możecie znaleźć w tym miejscu –  lib/SILGen. Jeżeli chcecie poczytać więcej o jego designie to możecie zrobić to w tym miejscu.

Zanim jednak SIL przejdzie do fazy optymalizacji, to za pomocą biblioteki określanej jako SIL Guaranteed Transformations (lib/SILOptimizer/Mandatory), wykonywana jest dodatkowa analiza kodu programu.

 

Optimization

 

Faza optymalizacji jest zwykle pierwszą fazą back endu. W jej trakcie kompilator korzysta z różnych metod, aby poprawić wydajność naszego kodu. Może to być na przykład mechanizm zwany function inlining lub generic specialization, o których możecie przeczytać więcej w tym wpisie. Tak będzie prezentował się przykład z wykorzystaniem function inlining:

Optymalizacja ma na oczywiście na celu przyśpieszenie operacji wykonywanych przez naszą aplikację, jak również potencjalnie zmniejszenie jej rozmiarów, poprzez eliminowanie zbędnego kodu (jak w powyższym przykładzie).

Implementacja Swift’a przewiduje wykorzystanie na tym etapie kilku bibliotek, które zajmą się m.in optymalizacjami związanymi z Automatic Reference Counting. Znaleźć możecie je pod tymi adresami:  lib/Analysis, lib/ARC, lib/LoopTransforms, lib/Transforms.

 

Code Generation

 

Wielki finał. Kompilator korzysta z intermediate code, aby utworzyć kod niskopoziomy.

Zoptymalizowany już na tym etapie SIL zostaje przekształcony do formy LLVM IR. Jest to kolejna forma kodu pośredniego, tym razem jednak w wersji niskopoziomej podobnej do assemblera. Tak będzie wyglądał przykładowy fragment:

LLVM (kompilator Swift’a, nie język) wykonuje dodatkową optymalizację, a następnie generuje kod maszynowy (najczęściej w postaci wykonywalnego pliku binarnego). Bibliotekę odpowiedzialną za utworzenie LLVM IR może znaleźć tutaj – lib/IRGen.

 

Słowo na drogę

 

Jak sami widzicie jest tego całkiem sporo, ale moim zdaniem nie ma większego sensu uczenie się tego na pamięć. Warto pamiętać, że proces kompilacji składa się z kilku, ściśle powiązanych ze sobą etapów. A jak pojawi się konieczność skorzystania z tej wiedzy to można zawsze zajrzeć do dokumentacji. Nie ma się co oszukiwać – w codziennej pracy wiedza ta będzie raczej rzadko wykorzystywana. No chyba, że akurat pracujecie nad rozwojem danego języka 😝. Do następnego 😉.

 

Link do obrazka tytułowego.


 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *