Software is all about logic. Programowanie zyskało reputację dziedziny, która jest ciężka w matematyce i szalonych równaniach. A Informatyka wydaje się być sednem tego nieporozumienia.

oczywiście, jest trochę matematyki i są pewne formuły – ale żaden z nas nie musi mieć doktoratów z rachunku różniczkowego, abyśmy mogli zrozumieć, jak działają nasze maszyny! W rzeczywistości wiele zasad i paradygmatów, których uczymy się podczas pisania kodu, to te same zasady i paradygmaty, które odnoszą się do złożonych pojęć z dziedziny informatyki. Czasami te idee wywodzą się z informatyki, a my nigdy o tym nie wiedzieliśmy.

niezależnie od tego, jakiego języka programowania używamy, kiedy większość z nas pisze nasz kod, staramy się zamknąć różne rzeczy w klasy, obiekty lub metody, celowo oddzielając różne części naszego kodu. Innymi słowy, wiemy, że ogólnie rzecz biorąc dobrze jest podzielić nasz kod tak, aby jedna klasa, obiekt lub metoda zajmowała się tylko jedną rzeczą i była za nią odpowiedzialna. Jeśli tego nie zrobimy, rzeczy mogą się bardzo poplątać i splecione w bałagan sieci. Czasami zdarza się to nadal, nawet przy rozdzielaniu obaw.

jak się okazuje, nawet wewnętrzne działanie naszych komputerów podąża za bardzo podobnymi paradygmatami projektowania. Na przykład nasz kompilator ma różne części do niego, a każda część jest odpowiedzialna za obsługę jednej konkretnej części procesu kompilacji. Napotkaliśmy trochę tego w zeszłym tygodniu, kiedy dowiedzieliśmy się o parserze, który jest odpowiedzialny za tworzenie drzew parsowania. Ale parser nie może być zadane ze wszystkim.

parser potrzebuje pomocy od swoich kumpli, a w końcu nadszedł czas, aby dowiedzieć się, kim są!

Kiedy ostatnio dowiedzieliśmy się o parsowaniu, zagłębiliśmy się w gramatykę, składnię i sposób, w jaki kompilator reaguje i reaguje na te rzeczy w języku programowania. Ale nigdy tak naprawdę nie podkreśliliśmy, czym dokładnie jest kompilator! Gdy wejdziemy w wewnętrzne funkcjonowanie procesu kompilacji, będziemy się dużo uczyć o projektowaniu kompilatorów, więc ważne jest, abyśmy zrozumieli, o czym dokładnie mówimy.

Kompilatory mogą wydawać się trochę przerażające, ale ich praca nie jest zbyt skomplikowana, aby zrozumieć — szczególnie, gdy rozbijamy różne części kompilatora na części o wielkości ugryzienia.

ale najpierw zacznijmy od najprostszej możliwej definicji. Kompilator to program, który odczytuje nasz kod (lub dowolny kod, w dowolnym języku programowania) i tłumaczy go na inny język.

ogólnie rzecz biorąc, kompilator jest w stanie przetłumaczyć Kod tylko z języka wysokiego poziomu na język niższego poziomu. Języki niższego poziomu, na które kompilator tłumaczy Kod, są często określane jako kod złożeniowy, kod maszynowy lub kod obiektowy. Warto wspomnieć, że większość programistów tak naprawdę nie zajmuje się ani nie pisze żadnego kodu maszynowego; raczej polegamy na kompilatorze, aby wziął nasze programy i przetłumaczył je na kod maszynowy, który jest tym, co nasz komputer będzie działał jako program wykonywalny.

możemy myśleć o kompilatorach jako pośredniku między nami, programistami i naszymi komputerami, które mogą uruchamiać tylko programy wykonywalne w językach niższego poziomu.

kompilator wykonuje pracę tłumaczenia tego, co chcemy zrobić w sposób zrozumiały i wykonywalny dla naszych maszyn.

bez kompilatora bylibyśmy zmuszeni do komunikowania się z naszymi komputerami poprzez pisanie kodu maszynowego, który jest niesamowicie nieczytelny i trudny do rozszyfrowania. Dla ludzkiego oka kod maszynowy często wygląda jak zbiór zer i jedynek-to wszystko jest binarne, pamiętasz? – co sprawia, że bardzo trudno jest czytać, pisać i debugować. Kompilator abstrahował kod maszynowy dla nas jako programistów, ponieważ bardzo ułatwiał nam nie myślenie o kodzie maszynowym i pisanie programów przy użyciu znacznie bardziej eleganckich, przejrzystych i łatwych do odczytania języków.

w ciągu najbliższych kilku tygodni będziemy rozpakowywać coraz więcej informacji o tajemniczym kompilatorze, co, miejmy nadzieję, sprawi, że będzie on mniej zagadkowy. Ale na razie wróćmy do pytania: Jakie są najprostsze możliwe Części kompilatora?

każdy kompilator, bez względu na to, jak może być zaprojektowany, ma różne fazy. Te fazy pozwalają nam odróżnić unikalne części kompilatora.

napotkaliśmy już jedną z faz naszych przygód kompilacyjnych, kiedy niedawno dowiedzieliśmy się o drzewach parserów i parserów. Wiemy, że parsowanie jest procesem podejmowania niektórych danych wejściowych i budowania drzewa parsowania z niego, który jest czasami określany jako akt parsowania. Jak się okazuje, praca parsingu jest specyficzna dla fazy procesu kompilacji zwanej analizą składniową.

jednak, parser nie tylko zbudować drzewo parse z powietrza. Ma jakąś pomoc! Przypomnijmy, że parser otrzymuje kilka tokenów (zwanych również terminalami) i buduje drzewo parsowania z tych tokenów. Ale skąd bierze te żetony? Na szczęście parser nie musi pracować w próżni; zamiast tego ma jakąś pomoc.

to prowadzi nas do kolejnej fazy procesu kompilacji, poprzedzającej fazę analizy składniowej: fazę analizy leksykalnej.

termin „leksykalny” odnosi się do znaczenia słowa w oderwaniu od zdania go zawierającego, niezależnie od jego kontekstu gramatycznego. Jeśli spróbujemy odgadnąć nasze własne znaczenie oparte wyłącznie na tej definicji, możemy założyć, że faza analizy leksykalnej ma związek z poszczególnymi słowami/terminami w samym programie, a nie ma nic wspólnego z gramatyką lub znaczeniem zdania, które zawiera słowa.

Faza analizy leksykalnej jest pierwszym krokiem w procesie kompilacji. Nie zna ani nie dba o gramatykę zdania lub znaczenie tekstu lub programu; wszystko, co wie, to znaczenie samych słów.

Analiza leksykalna musi nastąpić, zanim jakikolwiek kod z programu źródłowego może zostać przetworzony. Zanim zostanie odczytany przez parser, program musi najpierw zostać zeskanowany, podzielony i pogrupowany w określony sposób.

Kiedy w zeszłym tygodniu zaczęliśmy analizować fazę analizy składniowej, dowiedzieliśmy się, że drzewo parse jest budowane przez przyglądanie się poszczególnym częściom zdania i dzielenie wyrażeń na prostsze części. Jednak w fazie analizy leksykalnej kompilator nie zna ani nie ma dostępu do tych „poszczególnych części”. Raczej musi najpierw je zidentyfikować i znaleźć, a następnie wykonać pracę dzielenia tekstu na poszczególne części.

na przykład, gdy czytamy zdanie z Szekspira, takie jak To sleep, perchance to dream., wiemy, że spacje i interpunkcja dzielą „słowa” zdania. Jest to, oczywiście, ponieważ zostaliśmy przeszkoleni, aby czytać zdanie, ” lex ” go, i analizować go dla gramatyki.

ale dla kompilatora to samo zdanie może wyglądać tak przy pierwszym czytaniu: Tosleepperhachancetodream. Kiedy czytamy to zdanie, trochę trudniej jest nam określić, czym są prawdziwe „słowa”! Jestem pewien, że nasz kompilator czuje to samo.

jak nasza maszyna radzi sobie z tym problemem? Podczas analizy leksykalnej procesu kompilacji, zawsze robi dwie ważne rzeczy: skanuje kod, a następnie go ocenia.

praca skanowania i ewaluacji może być czasami połączona w JEDEN program, lub mogą to być dwa oddzielne programy, które zależą od siebie; tak naprawdę jest to tylko kwestia tego, jak zaprojektowano dowolny kompilator. Program w kompilatorze, który jest odpowiedzialny za wykonywanie pracy skanowania i ewaluacji, jest często określany jako lexer lub tokenizer, a cała Faza analizy leksykalnej jest czasami nazywana procesem lexowania lub tokenizacji.

do skanowania, ewentualnie do czytania

pierwszym z dwóch podstawowych etapów analizy leksykalnej jest skanowanie. Możemy myśleć o skanowaniu jako o pracy „czytania” tekstu wejściowego. Pamiętaj, że ten tekst wejściowy może być ciągiem znaków, zdaniem, wyrażeniem, a nawet całym programem! To naprawdę nie ma znaczenia, ponieważ w tej fazie procesu jest to tylko gigantyczna plama postaci, która jeszcze nic nie znaczy i jest jednym ciągłym kawałkiem.

spójrzmy na przykład, aby zobaczyć, jak dokładnie to się dzieje. Użyjemy naszego oryginalnego zdania, To sleep, perchance to dream., które jest naszym tekstem źródłowym lub kodem źródłowym. Dla naszego kompilatora ten tekst źródłowy zostanie odczytany jako tekst wejściowy, który wygląda jak Tosleep,perchancetodream., który jest tylko ciągiem znaków, który nie został jeszcze rozszyfrowany.

pierwszą rzeczą, którą nasz kompilator musi zrobić, to podzielić ten blob tekstu na najmniejsze możliwe Części, co znacznie ułatwi identyfikację słów w blobie tekstu.

najprostszym sposobem na zanurzenie się w gigantycznym kawałku tekstu jest czytanie go powoli i systematycznie, jeden znak na raz. I to jest dokładnie to, co robi kompilator.

często proces skanowania jest obsługiwany przez oddzielny program o nazwie skaner, którego jedynym zadaniem jest czytanie pliku źródłowego / tekstu, jeden znak na raz. Dla naszego skanera nie ma znaczenia, jak duży jest nasz tekst; wszystko, co zobaczy ,gdy „przeczyta” nasz plik, to jeden znak na raz.

oto jak nasze Szekspirowskie zdanie zostanie odczytane przez nasz skaner:

zauważymy, żeTo sleep, perchance to dream. został podzielony na poszczególne znaki przez nasz skaner. Co więcej, nawet spacje między wyrazami są traktowane jak znaki, podobnie jak interpunkcja w naszym zdaniu. Na końcu tej sekwencji znajduje się również znak, który jest szczególnie interesujący: eof. Jest to znak „koniec pliku” i jest podobny do tabspace I newline. Ponieważ nasz tekst źródłowy jest tylko jednym zdaniem, Kiedy nasz skaner dociera do końca pliku (w tym przypadku do końca zdania), odczytuje koniec pliku i traktuje go jako znak.

tak więc, w rzeczywistości, kiedy nasz skaner odczytał nasz tekst wejściowy, zinterpretował go jako pojedyncze znaki, co skutkowało tym:.

teraz, gdy nasz skaner przeczytał i podzielił nasz tekst źródłowy na najmniejsze możliwe Części, będzie miał znacznie łatwiejszy czas na rozgryzienie „słów” w naszym zdaniu.

następnie skaner musi przyjrzeć się jego rozdzielonym znakom w kolejności i określić, które znaki są częściami słowa, a które nie. Dla każdego czytanego znaku skaner zaznacza linię I pozycję, w której ten znak został znaleziony w tekście źródłowym.

pokazany tutaj obraz ilustruje ten proces dla naszego Szekspirowskiego zdania. Widzimy, że nasz skaner zaznacza linię I kolumnę dla każdego znaku w naszym zdaniu. Możemy myśleć o reprezentacji linii i kolumn jako macierzy lub tablicy znaków.

przypomnij sobie, że ponieważ nasz plik ma tylko jedną pojedynczą linię, wszystko żyje w linii0. Jednak, gdy przechodzimy przez zdanie, kolumna każdego znaku zwiększa się. Warto również wspomnieć, że ponieważ nasz skaner odczytuje spacesnewlineseof, a wszystkie znaki interpunkcyjne pojawiają się również w naszej tabeli znaków!

Po zeskanowaniu i oznaczeniu tekstu źródłowego nasz kompilator jest gotowy do przekształcenia tych znaków w słowa. Ponieważ skaner nie tylko wie, gdzie znajdują się spacesnewlines I eof w pliku, ale także gdzie mieszkają w stosunku do innych znaków otaczających je, może przeskanować te znaki i podzielić je na poszczególne łańcuchy znaków w razie potrzeby.

w naszym przykładzie skaner spojrzy na znakiT, następnieo, a następniespace. Gdy znajdzie spację, podzieli To na własne słowo — najprostszą możliwą kombinację znaków, zanim skaner napotka spację.

jest to podobna historia dla następnego słowa, które znajdzie, czyli sleep. Jednak w tym scenariuszu odczytuje s-l-e-e-p, a następnie odczytuje ,, znak interpunkcyjny. Ponieważ przecinek ten jest otoczony znakiem (p) I space po obu stronach, przecinek jest sam w sobie uważany za „słowo”.

zarówno słowosleep, jak i znak interpunkcyjny, nazywane są leksemami, które są podłańcuchami tekstu źródłowego. Leksem jest grupowanie najmniejszych możliwych sekwencji znaków w naszym kodzie źródłowym. Leksemy pliku źródłowego są uważane za pojedyncze „słowa” samego pliku. Gdy nasz skaner zakończy odczytywanie pojedynczych znaków naszego pliku, zwróci zestaw lexemów, które wyglądają tak: .

zauważ, jak nasz skaner pobrał kropkę tekstu, której początkowo nie mógł odczytać, i zaczął skanować go raz na znak, jednocześnie czytając i zaznaczając zawartość. Następnie zaczął dzielić łańcuch na najmniejsze możliwe leksemy, używając spacji i interpunkcji między znakami jako ograniczników.

jednak pomimo całej tej pracy, na tym etapie analizy leksykalnej nasz skaner nic nie wie o tych słowach. Oczywiście, to podzielić tekst na słowa o różnych kształtach i rozmiarach, ale jeśli chodzi o to, co te słowa są skaner nie ma pojęcia! Słowa mogą być literalnym ciągiem, albo mogą być znakiem interpunkcyjnym, albo mogą być czymś zupełnie innym!

skaner nie wie nic o samych słowach, ani o tym, jaki jest ich „typ”. Po prostu wie, gdzie słowa kończą się i zaczynają w samym tekście.

w ten sposób Rozpoczynamy drugą fazę analizy leksykalnej: ewaluację. Gdy zeskanujemy nasz tekst i podzielimy kod źródłowy na poszczególne jednostki leksemu, musimy ocenić słowa, które skaner nam zwrócił i dowiedzieć się, z jakimi rodzajami słów mamy do czynienia — w szczególności musimy szukać ważnych słów, które znaczą coś specjalnego w języku, który próbujemy skompilować.

ocenianie ważnych części

Po zakończeniu skanowania naszego tekstu źródłowego i zidentyfikowaniu naszych leksemów, będziemy musieli coś zrobić z naszym leksem „słowa”. Jest to etap oceny analizy leksykalnej, który jest często określany w projektowaniu kompilatorów jako proces lexingu lub tokenizacji naszych danych wejściowych.

Kiedy oceniamy nasz zeskanowany kod, wszystko, co tak naprawdę robimy, to przyglądamy się bliżej każdemu leksemowi wygenerowanemu przez nasz skaner. Nasz kompilator będzie musiał przyjrzeć się każdemu słowu lexeme i zdecydować, jakie to jest słowo. Proces określania, jakiego rodzaju leksem jest każde „słowo” w naszym tekście, polega na tym, jak nasz kompilator zamienia każdy pojedynczy leksem w token, tokenizując w ten sposób nasz łańcuch wejściowy.

Po raz pierwszy zetknęliśmy się z tokenami, gdy uczyliśmy się o drzewach parsowania. Tokeny są specjalnymi symbolami, które znajdują się w centrum każdego języka programowania. Tokeny ,takie jak(, ), +, -, if, else, then, pomagają kompilatorowi zrozumieć, jak różne części wyrażenia i różne elementy odnoszą się do siebie. Parser, który jest centralnym elementem fazy analizy składniowej, polega na skądś odbieraniu tokenów, a następnie zamienia je w drzewo parsowania.

cóż, zgadnij co? W końcu rozgryzliśmy „gdzieś”! Jak się okazuje, tokeny wysyłane do parsera są generowane w fazie analizy leksykalnej przez tokenizer, zwany także lexerem.

więc jak dokładnie wygląda token? Token jest dość prosty i zwykle jest reprezentowany jako para, składająca się z nazwy tokena i pewnej wartości (która jest opcjonalna).

na przykład, jeśli tokenizujemy nasz Szekspirowski ciąg znaków, otrzymamy tokeny, które będą głównie literałami i separatorami. Możemy przedstawić leksem "dream” jako token w ten sposób: <string literal, "dream">. W podobny sposób możemy przedstawić leksem . jako token, <separator, .>.

zauważymy, że każdy z tych tokenów w ogóle nie modyfikuje leksemu — po prostu dodaje do niego dodatkowe informacje. Token jest leksem lub jednostką leksykalną o większej szczegółowości; konkretnie, dodany szczegół mówi nam, z jaką kategorią tokenu (jakiego rodzaju „słowem”) mamy do czynienia.

teraz, gdy tokenizowaliśmy nasze Szekspirowskie zdanie, widzimy, że nie ma aż tak dużej różnorodności typów tokenów w naszym pliku źródłowym. Nasze zdanie miało tylko ciągi znaków i interpunkcję – ale to tylko wierzchołek symbolicznej góry lodowej! Istnieje wiele innych rodzajów „słów”, które leksem można podzielić na.

tabela pokazana tutaj ilustruje niektóre z najczęstszych tokenów, które nasz kompilator widziałby podczas czytania pliku źródłowego w prawie każdym języku programowania. Widzieliśmy przykłady literals, które mogą być dowolnym ciągiem znaków, liczbą lub wartością logiczną/logiczną, a także separators, które są dowolnym rodzajem interpunkcji, w tym nawiasami ({}) I nawiasami (()).

However, there are also keywords, which are terms that are reserved in the language (such as ifvarwhilereturn), as well as operators, which operate on arguments and return some value ( +-x/). Możemy również napotkać leksemy, które mogą być tokenizowane jako identifiers, które zwykle są nazwami zmiennych lub rzeczami napisanymi przez użytkownika/programistę w celu odniesienia się do czegoś innego, a także , które mogą być komentarzami liniowymi lub blokującymi napisanymi przez użytkownika.

nasze oryginalne zdanie pokazało nam tylko dwa przykłady tokenów. Przepiszmy nasze zdanie, aby zamiast tego przeczytać: var toSleep = "to dream";. Jak nasz kompilator może lex tej wersji Szekspira?

tutaj zobaczymy, że mamy większą różnorodność tokenów. Mamy keyword w var, gdzie deklarujemy zmienną, i identifiertoSleep, co jest sposobem, w jaki nazwiemy naszą zmienną lub odwołujemy się do przyszłej wartości. Następnie jest nasz=, który jestoperator token, po którym następuje literal"to dream". Nasza instrukcja kończy się separatorem;, wskazującym koniec wiersza i rozdzielającym spacje.

ważne jest, aby pamiętać o procesie tokenizacji, że nie tokenizujemy żadnych białych spacji (spacje, nowe linie, tabulatory, koniec linii itp.), ani przekazywanie go do parsera. Pamiętaj, że tylko tokeny są przekazywane parserowi i trafiają do drzewa parsowania.

warto również wspomnieć, że różne języki będą miały różne znaki, które stanowią spację. Na przykład w niektórych sytuacjach język programowania Python używa wcięć — w tym tabulatorów i spacji — w celu wskazania, jak zmienia się zakres funkcji. Tak więc tokenizer kompilatora Pythona musi być świadomy faktu, że w pewnych sytuacjach tab lub space faktycznie musi być tokenizowany jako słowo, ponieważ faktycznie musi być przekazany do parsera!

lexer vs skaner.

ten aspekt tokenizera jest dobrym sposobem na kontrastowanie tego, jak lexer / tokenizer różni się od skanera. Podczas gdy skaner jest ignorantem i wie tylko, jak podzielić tekst na mniejsze możliwe Części (jego „słowa”), lexer/tokenizer jest znacznie bardziej świadomy i dokładniejszy w porównaniu.

tokenizer musi znać zawiłości i specyfikacje języka, który jest kompilowany. Jeślitabs są ważne, musi to wiedzieć; jeślinewlines może mieć pewne znaczenie w kompilowanym języku, tokenizer musi być świadomy tych szczegółów. Z drugiej strony skaner nie wie nawet, jakie są słowa, które dzieli, a tym bardziej, co oznaczają.

skaner kompilatora jest znacznie bardziej zależny od języka, podczas gdy tokenizer musi być z definicji specyficzny dla danego języka.

te dwie części procesu analizy leksykalnej idą w parze i są kluczowe dla pierwszej fazy procesu kompilacji. Oczywiście różne Kompilatory są projektowane na własne, unikalne sposoby. Niektóre Kompilatory wykonują krok skanowania i tokenizacji w jednym procesie i jako pojedynczy program, podczas gdy inne podzielą je na różne klasy, w takim przypadku tokenizer wywoła klasę skanera po uruchomieniu.

w obu przypadkach etap analizy leksykalnej jest bardzo ważny dla kompilacji, ponieważ faza analizy składniowej bezpośrednio od niej zależy. I chociaż każda część kompilatora ma swoje specyficzne role, opiera się na sobie nawzajem i jest od siebie zależna — tak jak zawsze robią to dobrzy przyjaciele.

zasoby

ponieważ istnieje wiele różnych sposobów pisania i projektowania kompilatora, istnieje również wiele różnych sposobów ich nauczania. Jeśli wykonasz wystarczająco dużo badań nad podstawami kompilacji, staje się jasne, że niektóre wyjaśnienia są o wiele bardziej szczegółowe niż inne, co może lub nie może być pomocne. Jeśli chcesz dowiedzieć się więcej, poniżej znajdują się różne zasoby na temat kompilatorów — ze szczególnym uwzględnieniem fazy analizy leksykalnej.

1. Rozdział 4 — Tworzenie interpreterów, Robert Nystrom
2. Budowa kompilatora, profesor Allan Gottlieb
3. podstawy kompilatora, profesor James Alan Farrell
4. pisanie języka programowania — Lexer, Andy Balaam
5. uwagi na temat pracy parserów i kompilatorów, Stephen Raymond Ferg
6. Jaka jest różnica między tokenem a leksem?, StackOverflow