Aktualności

…uf, wszystko działa jak należy.

Ale tak właściwie, co się stało? Skąd komputer, po przeczytaniu Twojego skomplikowanego kodu, dokładnie wie, co zrobić? I kim jest Mark? Na część z tych pytań postaram się tutaj odpowiedzieć.

Uwaga - niniejszy artykuł w żadnym wypadku nie wyczerpuje tematu, jakim jest analiza składniowa, oraz przedstawia tylko jedno z wielu podejść, jakie można obrać. Koncepty tu przedstawione są jednak dosyć uniwersalne. Nie jest to również poradnik, jak zbudować swój własny parser, choć przewinie się trochę kodu tu i ówdzie. Jest to część pierwsza z dwóch. Do omówienia jest dużo, a więc zaczynajmy.

Bez względu na to, czy mówimy o języku interpretowanym, kompilowanym, czy czymś pomiędzy - każdy język na początku przechodzi przez proces analizy leksykalnej oraz składniowej. Jest to sposób, w który nasz interpreter lub kompilator stara się zrozumieć (nie wykonać!) napisany przez nas kod, transformując go do postaci bardziej jemu przyjaznej.

Wszystko zaczyna się od lexera, zwanego też często tokenizerem. Jest to narzędzie przyjmujące na wejściu sekwencję znaków (w naszym przypadku jest to kod źródłowy naszego programu), przeprowadzające analizę leksykalną, a na końcu dostarczające wynik w postaci zbioru tokenów. Prościej mówiąc - można to porównać do konstruowania słów ze zbioru następujących po sobie liter: widząc „Ala ma kota” nasz mózg automatycznie konwertuje te 9 liter na 3 słowa – „Ala”, „ma”, „kota”. W przypadku języków programowania wygląda to bardzo podobnie.

Obrazek jest lekko uproszczony dla przejrzystości. W rzeczywistości większość tokenów nosi trochę więcej informacji. Każdy token posiada swój typ - wyróżniamy takie jak „identifier” (z ang. identyfikator zmiennej), „literal” (z ang. literał łańcuchowy lub liczbowy) czy tokeny słów kluczowych jak „return”, „if” itp.

Aby lexer potrafił przekształcić tekst do tokenów, musi mieć zdefiniowane coś takiego jak lexemes (z ang. leksema) oraz patterns (z ang. wzory).

Leksemą nazywamy sekwencję znaków pasującą do pewnego wzoru. Ta leksema definiuje potem token. Jako przykład: możemy zdefiniować, że każda sekwencja znaków zaczynająca i kończąca się cudzysłowem jest leksemą definiującą token typu „string literal”, każda sekwencja znaków formująca słowo „return” jest leksemą dla tokenu typu „keyword” itd.

Powyższy format tokenów dobrze ilustruje pracę lexera, lecz jest zbyt ogólny dla języków programowania, przez co utrudniałby później pracę parserowi. Jako przykład: grupowanie wszystkich słów kluczowych nie ma zbytnio sensu. Dużo ważniejszą informacją jest fakt, że słowo kluczowe to „return” lub „while”, niż fakt przynależności do tej grupy. Jednocześnie jednak pewne leksema powinny być zgrupowane (literały, nazwy zmiennych) pod jednym typem.

Implementacja takiego lexera jest mocno zależna od składni analizowanego języka i poziomu jego skomplikowania. Na rynku są dostępne generatory lexerów, lexery ogólnego przeznaczenia oraz lexery dopasowane do jednego konkretnego języka. Napisanie własnego analizatora nie jest przesadnie skomplikowanym zadaniem. Algorytm dla prostej składni mógłby wyglądać następująco:

• Dla każdego znaku w kodzie:
  o jeśli znak jest spacją lub nową linią – pomiń,
  o jeśli znak jest jednym z . , : ; { } [ ] ( ) ~:
    > dodaj go do listy tokenów,
  o jeśli znak jest literą:
    > utwórz łańcuch ze wszystkich następujących liter i dodaj go do listy tokenów,
  o jeśli znak jest cudzysłowem:
    > utwórz łańcuch ze wszystkich następujących znaków aż do zamykającego cudzysłowu i dodaj go do listy tokenów,
  o jeśli znak jest cyfrą:
    > utwórz łańcuch ze wszystkich następujących cyfr i dodaj go do listy tokenów,
  o jeśli znak jest jednym z = + - * & | / < > ! % ^:
    > utwórz łańcuch ze wszystkich następujących znaków będących jednym z = + - * & | / < > ! % ^ i dodaj go do listy tokenów,
  o jeśli znak nie spełnił żadnego z powyższych warunków:
    > wyświetl błąd informujący o nieznanym znaku,
    > (alternatywnie dodaj go do listy tokenów jako nieznany token i pozwól później parserowi wyświetlić błąd).

Jest to bardzo prosty, podatny na błędy algorytm, lecz powinien dać sobie radę z mniej skomplikowanymi kawałkami kodu.

No dobrze, ale co dalej? Posiadamy zestaw tokenów, ale jest to nadal jedynie tylko zestaw tokenów. Nosi on informacje o tym, co się znajduje w programie, ale nie jak go wykonać.

Do akcji wkracza wspominany wcześniej parser, który szerzej jest opisany w następnym artykule [LINK].