Łagodne wprowadzenie do kompilatorów. Część 1: analiza leksykalna i skaner

Moja podróż do świata kompilatorów zaczęła się, gdy próbowałem rozgryźć, jak właściwie działa kompilacja AOT w Angularze, która opiera się na statycznej analizie kodu. Po pewnym czasie debugowania odkryłem, że w dużym stopniu polega ona na kompilatorze TypeScript, więc rozpoczęła się wyprawa mająca na celu jego inżynierię wstecz. Co ciekawe, większość kompilatorów jest zaimplementowana na tych samych zasadach, znanych wspólnie jako teoria kompilatorów. Dobre opanowanie tej teorii jest nieodzowne, gdy próbuje się zrozumieć wnętrze kompilatora.

Ten artykuł jest pierwszym z serii, która podsumuje wszystko, czego się nauczyłem podczas inżynierii wstecz kompilatora TypeScript. Opiszę tu koncepcje ważne dla zrozumienia pierwszego etapu każdego kompilatora — analizy leksykalnej. Artykuł zawiera absolutne minimum teorii i formalizmu, a mimo to wyszedł głównie teoretyczny. W ostatnim rozdziale pokazuję, jak zaimplementowany jest skaner TypeScript, i podaję odpowiednie odnośniki.

Gramatyka TypeScriptu opiera się na specyfikacji ECMAScript (JavaScript) i mam nadzieję, że zaciekawi Cię to na tyle, byś poszedł za odnośnikami z artykułu i zapoznał się ze specyfikacją. Jeśli to zrobisz, powinieneś być w stanie rozumieć gramatykę i poznawać składnię nadchodzących funkcji JavaScriptu długo przed tym, zanim wyjaśnią je na MDN. Jeśli dotrwasz do końca artykułu, możesz się sprawdzić, próbując zrozumieć składnię dekoratorów opisaną w specyfikacji dekoratorów.

Artykuł jest dość długi i dlatego nie jest przewidziany do przeczytania w jednym podejściu. Czytaj go po trochu i daj koncepcjom czas, by się ułożyły w głowie. Jeśli zawsze chciałeś nauczyć się czytać specyfikację ECMAScript albo zrozumieć, jak działa kompilator (skaner), ten artykuł jest dla Ciebie.

Główne etapy

Kompilatory to programy komputerowe, które tłumaczą program napisany w jednym języku na program w innym języku. Kompilator musi najpierw zrozumieć program w języku źródłowym, który przyjmuje na wejściu, a następnie odwzorować jego funkcjonalność na program w języku docelowym. Z powodu odmiennej natury tych dwóch zadań sensowne jest podzielenie funkcjonalności kompilatora na dwa duże bloki: front-end i back-end. Głównym celem pierwszego jest zrozumienie programu w języku źródłowym, drugi zaś koncentruje się na przekształceniu go w program w języku docelowym.

Każdy blok składa się z sekwencji kilku faz, gdzie każdy etap bierze wejście z etapu poprzedniego, modyfikuje je, tworzy własną reprezentację programu źródłowego i przekazuje ją do następnej fazy. Front-end obejmuje trzy główne etapy zwane analizą leksykalną, składniową i semantyczną. Pierwsza faza bierze kod źródłowy jako strumień znaków i wyodrębnia poszczególne słowa (tokeny), takie jak nazwy zmiennych, słowa kluczowe i znaki interpunkcyjne. Druga faza ustala poprawność organizacji składniowej programu i buduje abstrakcyjne drzewo składniowe (AST). Analiza semantyczna sprawdza, czy AST przestrzega reguł języka (sprawdzanie typów, rozwiązywanie nazw).

Ten artykuł dotyczy pierwszego etapu — analizy leksykalnej — oraz jej głównego bohatera, czyli skanera, zwanego też rozpoznawaczem (recognizer).

Języki formalne i gramatyka

Zanim przejdziemy do implementacji skanera, warto powiedzieć trochę o językach naturalnych i formalnych oraz ich gramatykach. Języki naturalne, jak angielski czy francuski, służą głównie do komunikacji i rozwinęły się w sposób naturalny. Języki formalne są natomiast projektowane przez ludzi do konkretnych zastosowań — języki programowania, by wyrażać obliczenia, notacja matematyczna, by oznaczać relacje między liczbami itd.

Zarówno języki naturalne, jak i formalne można opisać gramatyką. Gramatyka to zbiór reguł opisujących, jak składać sekwencje symboli — znaków, słów (tokenów) czy zdań (instrukcji) — które są poprawne zgodnie ze składnią języka. Gramatyka języków naturalnych jest niewiarygodnie złożona i odkrywana drogą badań empirycznych. Z drugiej strony gramatyka języków formalnych (gramatyka formalna) jest zwykle całkiem prosta i definiowana tak, jak nam potrzebne. W zależności od tego, dla jakiego rodzaju symboli chcemy definiować reguły, możemy wyróżnić kilka typów gramatyki.

Gramatyka leksykalna opisuje strukturę słownika języka, czyli każdy token (słowo), którego można w tym języku użyć. Na przykład w JavaScripcie zarówno \, jak i d należą do alfabetu języka, ale gramatyka nie definiuje żadnej reguły, w której \, po którym od razu następuje d, mógłby zostać rozpoznany jako poprawny token poza literałem wyrażenia regularnego, więc jeśli wykonasz taki kod \d, dostaniesz błąd składni o niepoprawnym tokenie:

\d
Uncaught SyntaxError: Invalid or unexpected token

Gramatyka składniowa definiuje strukturę języka, czyli sposób, w jaki tokeny (słowa) mogą być ułożone, by formować instrukcje (zdania). Na przykład gramatyka leksykalna JavaScriptu definiuje dwa tokeny, var i const, ale nie ma reguły mówiącej, że po var może następować const, więc jeśli wykonasz poniższy kod, dostaniesz błąd składni o nieoczekiwanym tokenie:

var const
Uncaught SyntaxError: Unexpected token const

Zgodnie z gramatyką składniową ECMAScript to strukturalnie niedozwolona instrukcja, więc kompilator nie oczekuje, że token const będzie następował po tokenie var w instrukcji, którą napisaliśmy wyżej. Zauważ też różnicę między unexpected (nieoczekiwany) a invalid (niepoprawny) w komunikatach błędów.

Analiza leksykalna

Analiza leksykalna to pierwszy etap trzyczęściowego procesu, którego kompilator używa, by zrozumieć program wejściowy. Rolą analizy leksykalnej jest podzielenie kodu źródłowego programu na podłańcuchy zwane tokenami i sklasyfikowanie każdego tokenu według jego roli (klasy tokenu). Program wykonujący tę analizę nazywa się skanerem lub analizatorem leksykalnym. Czyta on strumień znaków i łączy je w tokeny, korzystając z reguł zdefiniowanych przez gramatykę leksykalną, którą nazywa się też specyfikacją leksykalną. Jeśli nie ma reguł definiujących daną sekwencję znaków, skaner zgłasza błąd. Dokładnie to stało się z naszym przykładowym łańcuchem \d, który dał błąd składni Invalid or unexpected token.

Każdemu rozpoznanemu tokenowi skaner przypisuje kategorię składniową na podstawie gramatyki. Lista kategorii, czyli klas tokenów, dla ECMAScript jest całkiem obszerna i zawiera między innymi takie klasy jak Identifier, NumericLiteral i StringLiteral oraz różne słowa kluczowe, np. ConstKeyword, LetKeyword i IfKeyword.

Zwykle więc wyjściem etapu analizy leksykalnej jest sekwencja tokenów, gdzie każdy token ma powiązaną klasę i podłańcuch, zwykle nazywany leksemem:

{class: SyntaxKind.ConstKeyword, lexeme: 'const'}

Jeśli jesteś ciekawy, jakie tokeny definiuje ECMAScript, sprawdź wyliczenie SyntaxKind (do komentarza // Parse tree nodes) w implementacji TypeScriptu.

Analizator leksykalny można zaimplementować tak, by przeskanował cały program źródłowy i wyprodukował pełną sekwencję tokenów, albo tak, by skanował stopniowo i rozpoznawał jeden token na raz. Skaner, który zamienia cały program źródłowy w tablicę tokenów przed uruchomieniem parsera, jest raczej rzadkością, bo bez potrzeby zużywa pamięć. Dlatego skanery zwykle implementuje się tak, by produkowały tokeny tylko na żądanie parsera — tak jest też ze skanerem TypeScriptu. Skaner TS jest interesujący jeszcze pod innym względem. Składnia JavaScriptu definiuje kilka konstrukcji językowych, np. wyrażenia regularne i literały szablonowe, które wprowadzają niejednoznaczność przy parsowaniu, tak że skaner może rozpoznać różne zbiory tokenów w zależności od kontekstu parsowania. Ponieważ ten kontekst parsowania jest ustalany przez parser przy żądaniu tokenu, skaner TS można w pewnym sensie nazwać sterowanym przez parser. Wyjaśnię tę zawiłość języka w sekcji o wielu symbolach docelowych.

Definiowanie tokenów

Weźmy znany przypadek deklarowania zmiennej w JavaScripcie, by pokazać, jak działają reguły gramatyki. W JavaScripcie możemy zadeklarować zmienną deklaracją const w ten sposób:

const v = 3

Załóżmy dla uproszczenia, że wartością inicjalizującą może być tylko literał numeryczny. Patrząc na kod źródłowy, wyraźnie widzisz słowo const deklarujące zmienną v, operator przypisania = oraz literał numeryczny 3 użyty jako wartość inicjalizująca zmiennej. Nic dziwnego, że skaner widzi to inaczej. Ponieważ ECMAScript definiuje źródło programu za pomocą symboli Unicode, kompilator widzi następującą sekwencję punktów kodowych:

c   o    n    s    t        v        =       3
99, 111, 110, 115, 116, 32, 118, 32, 61, 32, 51

Teraz jego zadaniem jest podzielić wyrażenie na tokeny i skategoryzować je, tak że powstaje następująca lista tokenów:

{class: SyntaxKind.ConstKeyword, lexeme: 'const'}
{class: SyntaxKind.Identifier, lexeme: 'v'}
{class: SyntaxKind.EqualsToken, lexeme: '='}
{class: SyntaxKind.NumericLiteral, lexeme: '3'}

A gdybyśmy zamiast const mieli let, pierwszym tokenem byłoby SyntaxKind.LetKeyword. Gdy token zostanie rozpoznany, skaner zapisuje jego wartość (leksem) we właściwości tokenValue, do której można się dostać metodą getTokenValue.

Gramatyka regularna

ECMAScript definiuje reguły rozpoznawania wejścia z symboli Unicode jako tokenów za pomocą gramatyki regularnej. Zgodnie z klasyfikacją gramatyk Chomsky’ego gramatyka regularna jest typem najbardziej restrykcyjnym, o najmniejszej sile wyrazu. Nadaje się tylko do opisywania tego, jak można konstruować tokeny, ale nie da się jej użyć do opisania struktury zdania. Jednak więcej ograniczeń na gramatykę sprawia, że łatwiej ją opisać i sparsować. A skoro w tym rozdziale zajmujemy się definiowaniem i parsowaniem tokenów, to jest to gramatyka idealna.

W następnym artykule z serii zapoznamy się z gramatyką bezkontekstową (typ 2). Ten typ gramatyki dopuszcza konstrukcje rekurencyjne i służy do definiowania struktury programu (instrukcji). Pozostałe dwie kategorie gramatyk z klasyfikacji Chomsky’ego — gramatyki nieograniczone i kontekstowe — są potężniejsze niż typ 2 i 3, ale są znacznie mniej użyteczne, bo nie potrafimy stworzyć dla nich efektywnych parserów.

Warto zauważyć, że większość materiałów dydaktycznych nie używa gramatyki regularnej przy wyjaśnianiu skanerów, a zamiast tego definiuje specyfikację leksykalną za pomocą wyrażeń regularnych. Jednak skoro ECMAScript używa do tego celu gramatyki regularnej, właśnie na niej będę wyjaśniać w tym artykule.

Poznajemy gramatykę

Spróbujmy teraz zobaczyć, jak można skonstruować gramatykę i reguły, które pomagają TypeScriptowi zidentyfikować listę tokenów pokazaną powyżej. Oto ona jeszcze raz — musimy zdefiniować reguły rozpoznawania każdego tokenu w tej instrukcji:

const v = 3
{class: SyntaxKind.ConstKeyword, lexeme: 'const'}
{class: SyntaxKind.Identifier, lexeme: 'v'}
{class: SyntaxKind.EqualsToken, lexeme: '='}
{class: SyntaxKind.NumericLiteral, lexeme: '3'}

Każdą regułę w gramatyce definiuje się za pomocą produkcji. Produkcja to reguła zamiany, określająca możliwe podstawienia, które można rekurencyjnie wykonywać, by generować nowe sekwencje symboli. W JavaScripcie możemy zadeklarować zmienną tokenem const albo let, więc dla symbolu Keyword możemy zdefiniować taką regułę:

Keyword ::
    const
    let

Reguła dla symbolu Keyword ma dwie produkcje (reguły produkcji), mówiące, że symbol Keyword może zostać zastąpiony łańcuchem const albo let. Keyword jest sztuczną zmienną zwaną symbolem nieterminalnym, co oznacza, że ma produkcje i może być zastępowany (proces zamian na nim się nie kończy). Zamiany zwykle nazywa się wyprowadzeniami (derivations). Produkcje const i let, które ma ten symbol, nazywa się terminalami, bo nie mają one żadnych wyprowadzeń. Symbole terminalne, które nie mają żadnych produkcji, to właśnie te łańcuchy, które można znaleźć w programie źródłowym. Sztuczne symbole nieterminalne służą w gramatyce jedynie do definiowania reguł zamian i nigdy nie są rozpoznawane w programie źródłowym jako poprawne tokeny. ECMAScript definiuje wiele innych produkcji dla symbolu nieterminalnego Keyword, takich jak: if, else, for, do, while, function, class itd.

Do definiowania gramatyki ECMAScript używa następującej, dowolnie przyjętej formy:

non_terminal_symbol ::
  symbol1 symbol2  (reguła produkcji 1: Symbol1, po którym idzie Symbol2)
  symbol3 symbol4  (reguła produkcji 2: Symbol3, po którym idzie Symbol4)

Symbol po lewej stronie :: nazywa się lewą stroną, a symbol po prawej — prawą stroną. W gramatykach regularnych i bezkontekstowych po lewej stronie reguły produkcji może stać tylko symbol nieterminalny. Prawa strona może zawierać zarówno terminale, jak i nieterminale, jednak gramatyka regularna jest ograniczona do tego, by mieć albo:

  • tylko terminale,
  • albo terminale i jeden nieterminal, który zawsze stoi na początku (lewostronnie liniowa) albo zawsze na końcu (prawostronnie liniowa):
non_terminal_symbol ::
  terminal_symbol
non_terminal_symbol ::
  terminal_symbol non_terminal_symbol   (prawostronnie liniowa)
non_terminal_symbol ::
  non_terminal_symbol terminal_symbol   (lewostronnie liniowa)

Gramatyka bezkontekstowa jest luźniejsza i dopuszcza dowolną liczbę terminali i nieterminali po prawej stronie. Zarówno GR, jak i GBK mogą mieć dowolną liczbę alternatyw (produkcji) dla każdego symbolu po lewej stronie:

non_terminal_symbol ::
  reguła produkcji 1
  reguła produkcji 2
  ...
  reguła produkcji n

Istnieją też inne notacje gramatyk, np. postać Backusa–Naura (BNF), która używa takiej składni:

nonterminal_symbol ::= symbol1 | symbol2

więc nasza reguła gramatyki dla Keyword byłaby zapisana jako:

Keyword ::= const | let

Inne alternatywne notacje zamieniają ::= na ->, więc reguła wygląda tak:

Keyword -> const | let

Pod tym względem ECMAScript używa własnego, dowolnie przyjętego formatu wyjaśnionego wyżej. Szczegóły notacji gramatyki opisane są w sekcji Grammar Notation i mocno zachęcam do jej przeczytania. Oto kilka istotnych fragmentów:

Symbole terminalne …pokazane są czcionką o stałej szerokości, symbole nieterminalne pokazane są kursywą… Jedna lub więcej alternatywnych prawych stron dla nieterminala następuje w kolejnych wierszach… Definicję nieterminala wprowadza nazwa nieterminala, po której następuje jeden lub więcej dwukropków. ECMAScript używa podwójnego dwukropka do oznaczenia gramatyki leksykalnej i pojedynczego dla gramatyki składniowej.

Stosowanie reguł produkcji

Regułę produkcji stosuje się do symbolu, zamieniając jedno wystąpienie lewej strony tej reguły na jej prawą stronę. Brzmi to nieco rozwlekle, więc spójrzmy na przykład. Załóżmy, że chcesz zdefiniować język słów zastrzeżonych. Gramatyka takiego języka zacznie się od symbolu nieterminalnego ReservedWord. ECMAScript definiuje dla niego następujące produkcje:

ReservedWord ::
  Keyword
  FutureReservedWord
  NullLiteral
  BooleanLiteral

ograniczmy się jednak na razie tylko do Keyword:

ReservedWord ::
  Keyword

Wcześniej zdefiniowaliśmy gramatykę dla Keyword tak:

Keyword ::
    const
    let

Zatem zamieniając najpierw ReservedWord na Keyword, a potem Keyword na jego produkcje, możemy skończyć z językiem, który ma dwa słowa — const i let. Taki język nazwalibyśmy skończonym, bo może zawierać najwyżej 2 różne łańcuchy. Wszystkie istniejące języki są nieskończone, bo liczba kombinacji, jakie mogą zawierać, jest potencjalnie nieskończona. Wkrótce zobaczymy, dlaczego tak się dzieje, gdy przyjrzymy się gramatyce identyfikatora.

W naszej gramatyce powyżej ReservedWord nazywa się symbolem startowym, bo to od tego symbolu zaczęliśmy generować łańcuchy. Gramatyka ECMAScript definiuje wiele symboli startowych i nazywa je symbolami docelowymi (goal symbols). Wyjaśnię dalej w artykule, dlaczego jest to potrzebne.

Proces, który pozwolił nam wyjść od symbolu startowego ReservedWord i dojść do łańcucha const albo let, nazywa się wyprowadzeniem (derivation). Wyprowadzenie łańcucha dla gramatyki to sekwencja zastosowań reguł gramatyki, która przekształca symbol startowy w ten łańcuch. Wyprowadzenie dowodzi, że łańcuch należy do języka tej gramatyki. Na przykład wiemy, że const jest poprawnym wyrażeniem, bo ReservedWord można rozwinąć w Keyword, a każdy Keyword można rozwinąć w łańcuch const albo let.

Rekurencyjna natura gramatyki

Rekurencyjną naturę gramatyki można pokazać na nazwach zmiennych, zwykle nazywanych w kontekście kompilatorów identyfikatorami. Jak już wiesz, w naszym przykładzie const v = 3 nazwa zmiennej v jest rozpoznawana jako Identifier. Identifier zdefiniowany jest w ECMAScript jako:

Identifier ::
    IdentifierName but not ReservedWord

To w zasadzie mówi nam, że słowa zastrzeżone są podzbiorem IdentifierName, więc reguły rozpoznawania nazw identyfikatorów i słów zastrzeżonych są takie same. Oznacza to, że gdy skaner rozpozna IdentifierName, powinien oznaczyć go jako Identifier, o ile nie jest to słowo zastrzeżone; w przeciwnym razie przypisywana jest mu odpowiednia klasa z kategorii ReservedWord. Dokładnie to robi kompilator TypeScript w funkcji getIdentifierToken. Lista słów zastrzeżonych składa się głównie ze słów kluczowych jak const, let, if, else, for itd., które widzieliśmy powyżej, plus literały null, true i false.

Jak więc można zdefiniować gramatykę dla IdentifierName? Prawdopodobnie wiesz, że pewne znaki, np. cyfry, nie mogą wystąpić na początku nazwy zmiennej, podczas gdy sama nazwa może zawierać znacznie szerszy zbiór znaków, włącznie z cyframi. Trzeba więc oddzielić to, od czego nazwa może się zaczynać, od tego, czym może być kontynuowana. Z tego powodu gramatykę należy zdefiniować za pomocą dwóch symboli nieterminalnych w sekwencji:

IdentifierName ::
    IdentifierStart IdentifierPart

Istotne jest, że zarówno IdentifierStart, jak i IdentifierPart oznaczają jeden znak ze zbioru punktów kodowych Unicode używanych na odpowiednich pozycjach nazwy identyfikatora. Nie będę tu wchodzić w szczegóły, ale jeśli jesteś ciekawy, przeczytaj Valid JavaScript variable names in ECMAScript 5. A ponieważ zarówno IdentifierStart, jak i IdentifierPart rozwijają się do jednego znaku ze zdefiniowanych alfabetów, powyższa definicja mówi, że każda nazwa IdentifierName ma długość dwóch znaków. A tego nie chcemy. Jeśli zajrzysz do gramatyki ECMAScript, zobaczysz następującą definicję:

IdentifierName ::
    IdentifierStart
    IdentifierName IdentifierPart

Rozłóżmy to. Pierwsza produkcja mówi, że nazwa identyfikatora może mieć długość jednego znaku ze zbioru znaków zdefiniowanego przez IdentifierStart. Jeśli wyprowadzisz drugą produkcję rekurencyjnie kilka razy, zobaczysz, że może rozwinąć się w dowolnie dużą liczbę znaków, zaczynając od IdentifierStart i kontynuując przez IdentifierPart:

IdentifierStart IdentifierPart IdentifierPart … IdentifierPart

To właśnie przypadek, w którym rekurencja okazuje się przydatna. Zamieniając rekurencyjnie IdentifierName na drugą produkcję IdentifierName IdentifierPart, możemy dopasować łańcuch dowolnej długości.

Ciekawostką jest, że niektóre notacje gramatyk wprowadzają niestandardowe operatory powtórzenia, jak * albo {…}, co dałoby taką gramatykę:

IdentifierName ::
    IdentifierStart IdentifierPart*
IdentifierName ::
    IdentifierStart {IdentifierPart}

Znaczenie znaków białych

Dla niektórych części gramatyki znaki białe odgrywają ważną rolę, pomagając skanerowi odróżnić jeden token od drugiego. Przyjrzyjmy się takiemu kodowi i wynikającym z niego tokenom:

newObject
{class: SyntaxKind.Identifier, lexeme: 'newObject'}

Tutaj newObject otrzymuje kategorię Identifier. Dzieje się to przez rekurencyjne wyprowadzanie produkcji IdentifierPart, jak widzieliśmy powyżej, a ponieważ każdy znak w słowie newObject należy do zbioru znaków zdefiniowanego dla symbolu IdentifierPart, skaner rozpoznaje cały łańcuch jako jeden pojedynczy token. Oto inny przykład:

new Object
{class: SyntaxKind.NewKeyword, lexeme: 'new'}
{class: SyntaxKind.Identifier, lexeme: 'Object'}

Teraz, choć znaki są te same, są parsowane jako dwa oddzielne tokeny z powodu obecności spacji. Skaner potrafi rozdzielić tokeny, bo wyprowadzając produkcje IdentifierPart, nie uznaje spacji za poprawny znak dla IdentifierPart i produkuje token IdentifierName z leksemem new o długości 3 znaków. Następnie szuka tokenu new na listach słów kluczowych i oznacza go jako NewKeyword (to wyszukiwanie wyjaśnię później).

W innych sytuacjach rozdzielić tokeny pomagają znaki takie jak (, których nie można użyć jako IdentifierPart:

if(s=3){...}
IfKeyword OpenParenToken ...

Znaki białe są też wymienione jako oddzielna klasa tokenów dla symbolu docelowego InputElementDiv:

InputElementDiv::
    WhiteSpace
    LineTerminator
    ...

Definiowanie reguł dla operatorów przypisania i literałów liczbowych

Pokazałem, jak definiuje się gramatykę dla słowa kluczowego const i identyfikatora v. Teraz zostało tylko zdefiniować reguły dla znaku równości i liczby 3:

ConstToken Identifier = 3

Znak równości to to, czym w JavaScripcie przypisujemy wartość do zmiennej. Istnieje wiele innych operatorów przypisania i wszystkie są wygodnie zgrupowane pod symbolem AssignmentOperator:

AssignmentOperator : one of
    *= /= %= += -= <<= >>= >>>= &= ^= |= **=

I ostatni element — liczba 3. W JavaScripcie liczby można zapisywać w wielu postaciach: literał dziesiętny z częścią ułamkową 1.58, literały binarne 0b11 czy szesnastkowe 0x11, postać wykładnicza 5e2 itd. Sensownie jest zgrupować to wszystko pod symbolem NumericLiteral:

NumericLiteral::
  DecimalLiteral
  BinaryIntegerLiteral
  OctalIntegerLiteral
  HexIntegerLiteral

To wszystko są symbole nieterminalne. Możesz kliknąć odnośniki, by prześledzić produkcje każdego nieterminala aż do symboli terminalnych.

Wiele symboli docelowych

Badając proces wyprowadzania, dowiedzieliśmy się, że zaczyna się on od symbolu docelowego (startowego). I tu gramatyka leksykalna ECMAScript staje się skomplikowana, bo definiuje kilka symboli docelowych. Rozważ następujący fragment kodu:

/foo/g

Jeśli skaner ECMAScript zacznie wyprowadzać poniższą instrukcję, używając głównego symbolu docelowego (startowego) InputElementDiv o następujących regułach produkcji:

InputElementDiv ::
    WhiteSpace
    LineTerminator
    Comment
    CommonToken
    DivPunctuator
    RightBracePunctuator

rozpozna następujący strumień tokenów:

/             foo            /             g
DivPunctuator IdentifierName DivPunctuator IdentifierName

Jednak jeśli programowałeś w JS wystarczająco długo, musisz wiedzieć, że /foo/g reprezentuje literał wyrażenia regularnego. Powinien więc zostać rozpoznany jako jeden token RegularExpressionLiteral za pomocą następującej reguły gramatyki:

RegularExpressionLiteral ::
    / RegularExpressionBody / RegularExpressionFlags

Podstawowy symbol docelowy InputElementDiv nie ma żadnych wyprowadzeń, które mogłyby doprowadzić skaner do symbolu RegularExpressionLiteral. Musimy więc zdefiniować nowy symbol docelowy InputElementRegExp z produkcją dla literału wyrażenia regularnego:

InputElementRegExp ::
    WhiteSpace
    ...
    RegularExpressionLiteral

Używając tego symbolu docelowego, skaner poprawnie rozpozna /foo/g jako RegularExpressionLiteral. Ale teraz możesz zapytać: skąd skaner wie, którego symbolu docelowego użyć przy parsowaniu tokenu? Jak wspomniałem wcześniej w artykule, symbol docelowy (kontekst) ustalany jest przez parser. Parser żąda od skanera tokenów jeden po drugim i jeśli bieżący kontekst parsowania dopuszcza użycie symbolu docelowego InputElementRegExp, parser prosi skaner o rozpoznawanie tokenów przy użyciu tego symbolu docelowego.

Na przykład załóżmy, że parser aktualnie parsuje PrimaryExpression, który ma następującą gramatykę:

PrimaryExpression :
    this
    IdentifierLiteral
    …
    RegularExpressionLiteral

Gramatyka mówi, że literał wyrażenia regularnego może być wyprowadzony z wyrażenia pierwotnego, więc parser definiuje symbol docelowy InputElementRegExp dla skanera. Kompilator TypeScript jest zaimplementowany tak, by ponownie skanować bieżący token, jeśli wykryje, że bieżący kontekst dopuszcza symbole docelowe inne niż główny InputElementDiv. ECMAScript definiuje jeszcze kilka innych symboli docelowych — by dowiedzieć się o nich więcej, zobacz tę świetną odpowiedź na StackOverflow.

Wyrażenia regularne

Czasem gramatykę leksykalną określa się za pomocą operatora powtórzenia zamiast rekurencji. Na przykład tak gramatyka Javy 8 definiuje symbol IdentifierChars, który jest odpowiednikiem symbolu IdentifierName z rekurencyjnymi produkcjami w ECMAScript:

IdentifierChars:
    JavaLetter {JavaLetterOrDigit}
JavaLetter:
    any Unicode character that is a "Java letter"
JavaLetterOrDigit:
    any Unicode character that is a "Java letter-or-digit"

Nawiasy klamrowe wokół JavaLetterOrDigit to notacja powtórzenia, jak wyjaśniono w dokumencie gramatyki:

Składnia {x} po prawej stronie produkcji oznacza zero lub więcej wystąpień x.

Ten sposób określania gramatyki ma szczególną własność: podstawiając za każdy nieterminal (poza korzeniowym) jego prawą stronę, można ją zredukować do jednej produkcji dla korzenia, z samymi terminalami po prawej stronie. Takie zredukowane wyrażenie da się potem łatwo przekształcić w wyrażenie regularne (regex). Na przykład dla IdentifierChars mielibyśmy następujące:

[range of Java letter][range of Java letter-or-digit]*

Używanie operatora powtórzenia w regułach gramatyki regularnej zamiast struktur rekurencyjnych nie jest konwencjonalne. Jeśli gramatyka jest określona standardową notacją ze strukturami rekurencyjnymi, mechaniczne przekształcenie gramatyki w wyrażenia regularne nie jest trywialne: najpierw trzeba przekształcić gramatykę w niedeterministyczny automat skończony (NFA, wyjaśniony niżej), a potem NFA w wyrażenia regularne. Często jednak znacznie łatwiej jest wymyślić równoważne wyrażenie regularne, stosując „logiczne myślenie”.

Zarówno gramatyka regularna, jak i wyrażenie regularne mogą opisywać sekwencję znaków pobranych ze stałego zbioru i można ich używać wymiennie. Z tego powodu wyrażenia regularne rutynowo służą do określania specyfikacji leksykalnej zamiast gramatyki regularnej. Tak jest na przykład w generatorach analizatorów leksykalnych (skanerów), takich jak Flex.

Automat skończony

Poza gramatyką regularną i wyrażeniami regularnymi istnieje jeszcze jeden sposób określania specyfikacji leksykalnej — automaty skończone (FA). Wszystkie one to po prostu trzy różne formalizmy robiące zasadniczo to samo — rozpoznające zbiory znaków. Podstawowym powodem, dla którego mamy trzy sposoby robienia tego samego, jest to, że powstawały niezależnie. FA daje jednak najlepszy model mentalny do opisania implementacji skanera i właśnie do tego go użyjemy.

Automat można wyjaśnić za pomocą algorytmu rozpoznającego słowa znak po znaku. Załóżmy, że chcemy rozpoznać token const. Musimy napisać kod, który sprawdza c, po którym idzie o, po którym n, i tak dalej, aż dojdziemy do ostatniego znaku t. Jeśli przedstawimy każdy krok programu jako diagram przejść, otrzymamy następujące stany.

diagram przejść DFA rozpoznającego słowo kluczowe const

Każdy automat ma stany, przedstawione na diagramie jako okręgi. W tym artykule będę mówić tylko o automacie, który ma skończoną liczbę stanów (stąd automat skończony). Ostatni stan, oznaczony podwójną linią, nazywa się stanem akceptującym. Automat może mieć dowolną liczbę stanów akceptujących. Jeśli po przeczytaniu wejścia automat kończy w stanie akceptującym, wejście jest rozpoznane jako poprawna sekwencja znaków.

Istnieją dwa typy automatów skończonych — deterministyczny (DFA) i niedeterministyczny (NFA). Największa różnica między nimi polega na tym, że w DFA każde wejście jednoznacznie wyznacza stan, do którego przejść (stąd „deterministyczny”). Natomiast w NFA niektóre wejścia mogą dopuszczać wybór stanu wynikowego (stąd „niedeterministyczny”).

diagram porównania NFA i DFA

Ponadto DFA może zmienić stan tylko po przeczytaniu wejścia, ale NFA można skonstruować tak, by mógł przejść do jakiegoś nowego stanu w ogóle bez czytania wejścia. Istnieją algorytmy przekształcania jednego typu FA w drugi. NFA i DFA są równoważne w sile wyrazu, a każdy DFA jest szczególnym przypadkiem NFA.

Czasem skaner może wpaść w sytuację niejednoznaczną. Wiemy, że każdy z operatorów =, /=, *=, += jest rozpoznawany jako poprawny token, ale skąd skaner wie, czy rozpoznać łańcuch += jako jeden token +=, czy jako token +, po którym idzie token =? Tego rodzaju niejednoznaczność rozwiązuje się regułą wygrywa najdłuższe dopasowanie, więc łańcuch += jest rozpoznawany jako jeden token, interpretowany w czasie wykonania jako operator przypisania z dodawaniem.

Implementowanie DFA

DFA można zaimplementować jako skaner tablicowy albo pisany ręcznie. Skanery tablicowe zwykle generowane są przez specjalizowane narzędzia jak Flex. Ponieważ w DFA każde wejście jednoznacznie wyznacza stan przejścia i nigdy nie ma nawrotów, DFA jest preferowanym modelem implementacji w generowanych skanerach. Zwykły przebieg polega na przekształceniu specyfikacji leksykalnej (gramatyki regularnej albo wyrażenia regularnego) w NFA, a potem NFA w DFA.

przebieg: specyfikacja leksykalna → NFA → DFA → implementacja

Jednak większość kompilatorów komercyjnych i open-source używa skanerów pisanych ręcznie. Taki skaner jest szybszy od generowanego, bo podczas implementacji można usunąć pewien narzut, który w generowanym skanerze jest konieczny. Taki właśnie typ skanera zaimplementowano w kompilatorze TypeScript. Przy pisaniu skanera ręcznie zwykle nie ma potrzeby jawnego przekształcania gramatyki/regexu w DFA, bo algorytm skanowania da się zaimplementować ręcznie wprost ze specyfikacji leksykalnej. Taka ręczna implementacja w naturalny sposób kończy jako działająca niczym DFA.

Zarówno skanery tablicowe, jak i ręczne działają podobnie, emulując DFA. Wielokrotnie czytają następny znak na wejściu i emulują przejście DFA wywołane tym znakiem. Po przeczytaniu wejścia skaner sprawdza, czy istnieją możliwe przejścia dla tego wejścia. Jeśli przejście zostanie znalezione, następuje po nim i skaner znajduje się w nowym stanie. Jeśli nie ma dostępnych przejść, skaner sprawdza, czy bieżący stan jest stanem akceptującym. Jeśli tak, skaner rozpoznaje słowo i zwraca leksem oraz jego kategorię składniową procedurze wywołującej. W przeciwnym razie skaner ustala, czy po drodze do bieżącego stanu przechodził przez stan akceptujący. Jeśli napotkał stan akceptujący, skaner cofa swój stan wewnętrzny (bieżącą pozycję znaku) do tego punktu i zgłasza sukces. W przeciwnym razie zgłasza błąd.

Implementacja skanera w TypeScripcie

Implementację skanera TypeScript można zobaczyć w pliku scanner.ts. Główna logika, która emuluje DFA przez czytanie wejścia i przechodzenie do następnego stanu, zaimplementowana jest w metodzie scan. Sedno implementacji to nieskończona pętla while, która sprawdza znak wejściowy, obsługuje wszystkie możliwe przejścia z tego znaku, ustawia bieżącą pozycję i zwraca klasę tokenu, jeśli został rozpoznany:

const pos;
while (true) {
    tokenPos = pos;
    if (pos >= end) {
        return token = SyntaxKind.EndOfFileToken;
    }
    let ch = text.charCodeAt(pos);
    switch(ch) {
        case CharacterCodes.exclamation:
            ...
            pos++;
            return token = SyntaxKind.ExclamationToken;
        case CharacterCodes.openParen:
            ...
            pos++;
            return token = SyntaxKind.OpenParenToken;
        ...

Ponieważ emuluje DFA, skaner nigdy nie robi nawrotów.

Spójrzmy na przykład. ECMAScript definiuje między innymi następujące odrębne znaki interpunkcyjne:

Punctuator ::
    !  !=  !==  -  --  -=

Tę regułę można łatwo przekształcić w wyrażenia regularne:

/!==|!=|!|--|-=|-/
DFA dla znaków interpunkcyjnych: !, !=, !==, -, --, -=

Zauważ, że wszystkie stany z wyjątkiem stanu startowego są stanami akceptującymi. Dokładnie to mówią nam gramatyka i wyrażenie regularne.

TypeScript implementuje powyższy DFA następująco:

case CharacterCodes.exclamation:
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        if (text.charCodeAt(pos + 2) === CharacterCodes.equals) {
            pos += 3;
            return token = SyntaxKind.ExclamationEqualsEqualsToken;
        }
        pos += 2
        return token = SyntaxKind.ExclamationEqualsToken;
    }
    pos++;
    return token = SyntaxKind.ExclamationToken;
case CharacterCodes.plus:
    if (text.charCodeAt(pos + 1) === CharacterCodes.plus) {
        pos += 2;
        return token = SyntaxKind.PlusPlusToken;
    }
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        pos += 2
        return token = SyntaxKind.PlusEqualsToken;
    }
    pos++;
    return token = SyntaxKind.PlusToken;

Jak widać z implementacji TS i z DFA, skaner próbuje dopasować najdłuższy możliwy łańcuch.

Obsługa słów kluczowych

Widzieliśmy już, że ECMAScript definiuje słowa kluczowe jak const, let, if we własnej kategorii Keyword. Jednym sposobem ich rozpoznawania byłoby zdefiniowanie dla nich jawnego wyrażenia regularnego i wygenerowanie odpowiednich ścieżek dla DFA. Jednak ponieważ słowa kluczowe są podzbiorem wszystkich identyfikatorów, jak definiuje gramatyka:

Identifier:
    IdentifierName but not ReservedWord

istnieje alternatywna strategia — klasyfikować słowa kluczowe jako identyfikatory i sprawdzać, czy identyfikator jest słowem kluczowym, czy nie. Dokładnie takie podejście stosuje skaner TypeScriptu. Trzyma wszystkie słowa kluczowe wraz z innymi tokenami literałowymi w mapie textToToken i gdy identyfikator zostanie rozpoznany, używa tej mapy, by uzyskać poprawną klasę tokenu, która może być słowem kluczowym, ale nie musi:

default:
    if (isIdentifierStart(ch, languageVersion)) {
        pos++;
        while (isIdentifierPart(ch = text.charCodeAt(pos))) pos++;
        tokenValue = text.substring(tokenPos, pos);
        return token = getIdentifierToken();
    }

function getIdentifierToken(): SyntaxKind {
    if (...) {
        return token = textToToken.get(tokenValue);
    }
    return token = SyntaxKind.Identifier;
}

Chcesz dowiedzieć się więcej?

Piszę właśnie drugą część, która bada teorię gramatyk bezkontekstowych, budowę AST i algorytmy implementacji parsera. Ta druga część pokaże, jak zaimplementowany jest parser TypeScript i jakich algorytmów używa.

Oto też kilka bardzo dobrych źródeł, które polecam, by uzyskać więcej informacji o tematach, które tu wyjaśniłem:

  • Stanford CS143 (Compilers)
  • Engineering: A Compiler