Jak podejść do pisania tłumacza od podstaw

Niektórzy mówią, że „wszystko sprowadza się do jedynek i zer” — ale czy naprawdę rozumiemy, jak nasze programy są tłumaczone na te bity?

Zarówno kompilatory, jak i interpretery pobierają nieprzetworzony ciąg znaków reprezentujący program, analizują go i nadają mu sens. Chociaż tłumacze są prostsi z tych dwóch, pisanie nawet bardzo prostego tłumacza (który wykonuje tylko dodawanie i mnożenie) będzie pouczające. Skoncentrujemy się na tym, co łączy kompilatory i interpretery: leksykanie i analizowanie danych wejściowych.

Nakazy i zakazy pisania własnego tłumacza ustnego

Czytelnicy mogą się zastanawiać , co jest nie tak z wyrażeniem regularnym? Wyrażenia regularne mają duże możliwości, ale gramatyki kodu źródłowego nie są wystarczająco proste, aby mogły być przez nie analizowane. Podobnie jak języki specyficzne dla domeny (DSL), a klient może na przykład potrzebować niestandardowego DSL do wyrażeń autoryzacji. Ale nawet bez bezpośredniego zastosowania tej umiejętności, napisanie interpretera znacznie ułatwia docenienie wysiłku kryjącego się za wieloma językami programowania, formatami plików i DSL.

Poprawne ręczne pisanie parserów może być trudne we wszystkich skrajnych przypadkach. Dlatego istnieją popularne narzędzia, takie jak ANTLR, które mogą generować parsery dla wielu popularnych języków programowania. Istnieją również biblioteki zwane kombinatorami parserów , które umożliwiają programistom pisanie parserów bezpośrednio w preferowanych przez nich językach programowania. Przykładami są FastParse dla Scali i Parsec dla Pythona.

Zalecamy, aby w kontekście zawodowym czytelnicy korzystali z takich narzędzi i bibliotek, aby uniknąć ponownego wymyślania koła. Mimo to zrozumienie wyzwań i możliwości pisania interpretera od podstaw pomoże programistom efektywniej wykorzystać takie rozwiązania.

Przegląd komponentów tłumacza

Interpreter to złożony program, więc składa się z wielu etapów:

1. Lekser to część interpretera, która zamienia ciąg znaków (zwykły tekst) w ciąg tokenów.
2. Z kolei parser pobiera sekwencję tokenów i tworzy abstrakcyjne drzewo składni (AST) języka. Reguły, według których działa parser, są zwykle określone przez gramatykę formalną.
3. Interpreter to program, który interpretuje AST źródła programu w locie (bez wcześniejszej kompilacji).

Nie zbudujemy tutaj konkretnego, zintegrowanego tłumacza. Zamiast tego omówimy każdą z tych części i ich wspólne problemy z osobnymi przykładami. Ostatecznie kod użytkownika będzie wyglądał tak:

 val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res")

Po trzech etapach oczekujemy, że kod obliczy wartość końcową i wydrukuje Result is: 19 . Ten samouczek używa Scali, ponieważ jest:

• Bardzo zwięzły, mieszczący dużo kodu na jednym ekranie.
• Zorientowany na ekspresję, bez konieczności stosowania niezainicjowanych/null zmiennych.
• Pisz bezpiecznie dzięki potężnej bibliotece kolekcji, wyliczeniom i klasom przypadków.

W szczególności kod tutaj jest napisany w składni Scala3 z opcjonalnymi nawiasami klamrowymi (składnia podobna do Pythona, oparta na wcięciach). Ale żadne z tych podejść nie jest specyficzne dla Scali , a Scala jest podobna do wielu innych języków: Czytelnicy mogą łatwo przekonwertować te próbki kodu na inne języki. Poza tym przykłady można uruchomić online za pomocą programu Scastie.

Wreszcie sekcje Lexer, Parser i Interpreter mają różne przykładowe gramatyki . Jak pokazuje odpowiednie repozytorium GitHub, zależności w późniejszych przykładach zmieniają się nieznacznie, aby zaimplementować te gramatyki, ale ogólne koncepcje pozostają takie same.

Interpreter Komponent 1: Pisanie leksera

Powiedzmy, że chcemy przetłumaczyć ten ciąg: "123 + 45 true * false1" . Zawiera różne rodzaje tokenów:

• Literały całkowite
• Operator +
• * operator
• true dosłowny
• Identyfikator, false1

W tym przykładzie odstępy między tokenami zostaną pominięte.

Na tym etapie wyrażenia nie muszą mieć sensu; lekser po prostu konwertuje ciąg wejściowy na listę tokenów. (Zadanie „zrozumienia znaczenia tokenów” jest pozostawione parserowi).

Użyjemy tego kodu do reprezentowania tokena:

 case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOF

Każdy token ma typ, reprezentację tekstową i pozycję w oryginalnych danych wejściowych. Stanowisko może pomóc użytkownikom końcowym leksera w debugowaniu.

Token EOF to specjalny token oznaczający koniec wprowadzania. Nie istnieje w tekście źródłowym; używamy go tylko do uproszczenia etapu parsera.

To będzie wyjście naszego leksera:

 Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )

Przyjrzyjmy się realizacji:

 class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toList

Zaczynamy od pustej listy tokenów, następnie przechodzimy przez ciąg i dodajemy tokeny, gdy się pojawią.

Używamy znaku lookahead do określenia typu następnego tokena . Zauważ, że znak wyprzedzający nie zawsze jest najdalszym badanym znakiem. Na podstawie lookahead wiemy, jak wygląda token i używamy currentPos do zeskanowania wszystkich oczekiwanych znaków w bieżącym tokenie, a następnie dodajemy token do listy:

Jeśli lookahead to biały znak, pomijamy go. Żetony jednoliterowe są trywialne; dodajemy je i zwiększamy indeks. W przypadku liczb całkowitych wystarczy zadbać o indeks.

Teraz dochodzimy do czegoś nieco skomplikowanego: identyfikatory kontra literały. Zasada jest taka, że ​​bierzemy jak najdłuższe dopasowanie i sprawdzamy, czy jest dosłowne; jeśli nie, to jest to identyfikator.

Zachowaj ostrożność podczas obsługi operatorów takich jak < i <= . Tam musisz spojrzeć w przód o jeszcze jeden znak i sprawdzić, czy jest to = , zanim dojdziesz do wniosku, że jest to operator <= . W przeciwnym razie to tylko < .

Dzięki temu nasz lekser stworzył listę tokenów.

Interpreter Komponent 2: Pisanie parsera

Musimy nadać pewną strukturę naszym tokenom — nie możemy wiele zrobić z samą listą. Na przykład musimy wiedzieć:

Jakie wyrażenia są zagnieżdżone? Jakie operatory są stosowane w jakiej kolejności? Jakie zasady określania zakresu mają zastosowanie, jeśli w ogóle?

Struktura drzewa wspiera zagnieżdżanie i porządkowanie. Ale najpierw musimy zdefiniować pewne zasady konstruowania drzew. Chcielibyśmy, aby nasz parser był jednoznaczny — zawsze zwracał tę samą strukturę dla danego wejścia.

Zauważ, że następujący parser nie używa poprzedniego przykładu leksera . Ten służy do dodawania liczb, więc jego gramatyka ma tylko dwa tokeny, '+' i NUM :

 expr -> expr '+' expr expr -> NUM

Odpowiednik, używający znaku kreski pionowej ( | ) jako symbolu „lub”, jak w wyrażeniach regularnych, to:

 expr -> expr '+' expr | NUM

Tak czy inaczej, mamy dwie reguły: jedną, która mówi, że możemy zsumować dwa expr , a drugą, która mówi, że expr może być tokenem NUM , co tutaj oznacza nieujemną liczbę całkowitą.

Reguły są zwykle określane za pomocą gramatyki formalnej . Formalna gramatyka składa się z: Samych reguł, jak pokazano powyżej Reguły początkowej (pierwsza określona reguła, zgodnie z konwencją) Dwóch typów symboli definiujących reguły za pomocą: Terminale: „litery” (i inne znaki) naszego języka — nieredukowalne symbole, które tworzą tokeny Nieterminale: konstrukcje pośrednie używane do parsowania (tj. symbole, które można zastąpić)

Tylko nieterminal może znajdować się po lewej stronie reguły; prawa strona może mieć zarówno terminale, jak i nieterminale. W powyższym przykładzie terminalami są '+' i NUM , a jedynym nieterminalem jest expr . Szerszy przykład: w języku Java mamy terminale takie jak 'true' , '+' , Identifier i '[' , a także terminale nieterminalne, takie jak BlockStatements , ClassBody i MethodOrFieldDecl .

Istnieje wiele sposobów na zaimplementowanie tego parsera. Tutaj użyjemy techniki analizowania „zejścia rekurencyjnego”. Jest to najczęstszy typ, ponieważ jest najprostszy do zrozumienia i wdrożenia.

Rekurencyjny parser zstępujący wykorzystuje jedną funkcję dla każdego nieterminala w gramatyce. Zaczyna się od reguły początkowej i stamtąd schodzi (stąd „zejście”), zastanawiając się, którą regułę zastosować w każdej funkcji. Część „rekurencyjna” jest niezbędna, ponieważ możemy zagnieżdżać nieterminale rekurencyjnie! Regexes tego nie potrafią: nie potrafią nawet obsługiwać zrównoważonych nawiasów. Potrzebujemy więc mocniejszego narzędzia.

Parser dla pierwszej reguły wyglądałby mniej więcej tak (pełny kod):

 def expr() = expr() eat('+') expr()

Funkcja eat() sprawdza, czy lookahead pasuje do oczekiwanego tokena, a następnie przesuwa indeks lookahead. Niestety, to jeszcze nie zadziała, ponieważ musimy naprawić pewne problemy z naszą gramatykę.

Niejednoznaczność gramatyczna

Pierwsza sprawa to niejednoznaczność naszej gramatyki, która na pierwszy rzut oka może nie być widoczna:

 expr -> expr '+' expr | NUM

Biorąc pod uwagę dane wejściowe 1 + 2 + 3 , nasz parser może wybrać expr expr wynikowym AST:

Dlatego musimy wprowadzić pewną asymetrię :

 expr -> expr '+' NUM | NUM

Zestaw wyrażeń, które możemy reprezentować za pomocą tej gramatyki, nie zmienił się od czasu jej pierwszej wersji. Tylko teraz jest to jednoznaczne : parser zawsze idzie w lewo. Właśnie tego potrzebowaliśmy!

To sprawia, że ​​nasza operacja + pozostaje asocjacyjna , ale stanie się to widoczne, gdy przejdziemy do sekcji Interpreter.

Reguły lewostronnie rekurencyjne

Niestety powyższa poprawka nie rozwiązuje naszego innego problemu, rekursji lewostronnej:

 def expr() = expr() eat('+') eat(NUM)

Mamy tu nieskończoną rekurencję . Gdybyśmy wkroczyli do tej funkcji, w końcu otrzymalibyśmy błąd przepełnienia stosu. Ale teoria parsowania może pomóc!

Załóżmy, że mamy taką gramatykę, w której alpha może być dowolną sekwencją terminali i nieterminali:

 A -> A alpha | B

Możemy przepisać tę gramatykę jako:

 A -> BA' A' -> alpha A' | epsilon

Tam epsilon to pusty ciąg — nic, żaden token.

Przyjrzyjmy się aktualnej wersji naszej gramatyki:

 expr -> expr '+' NUM | NUM

Zgodnie z opisaną powyżej metodą przepisywania reguł parsowania, gdzie alpha jest naszymi tokenami '+' NUM , nasza gramatyka staje się:

 expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilon

Teraz gramatyka jest w porządku i możemy ją przeanalizować za pomocą rekurencyjnego parsera zstępującego. Zobaczmy, jak taki parser wyglądałby dla tej najnowszej iteracji naszej gramatyki:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head

Tutaj używamy tokena EOF , aby uprościć nasz parser. Zawsze mamy pewność, że na naszej liście jest przynajmniej jeden token, więc nie musimy zajmować się szczególnym przypadkiem pustej listy.

Ponadto, gdybyśmy przełączyli się na lekser strumieniowy, nie mielibyśmy listy w pamięci, ale iterator, więc potrzebujemy znacznika, aby wiedzieć, kiedy dojdziemy do końca danych wejściowych. Gdy dojdziemy do końca, token EOF powinien być ostatnim pozostałym tokenem.

Przeglądając kod, widzimy, że wyrażenie może być tylko liczbą. Jeśli nic nie zostanie, następnym tokenem nie będzie Plus , więc przestaniemy analizować. Ostatnim tokenem będzie EOF i skończymy.

Jeśli ciąg wejściowy ma więcej tokenów, to musiałyby one wyglądać jak + 123 . W tym miejscu wkracza rekursja na exprOpt() !

Generowanie AST

Teraz, gdy pomyślnie przeanalizowaliśmy nasze wyrażenie, trudno jest cokolwiek z nim zrobić w takim stanie, w jakim jest. Moglibyśmy umieścić kilka wywołań zwrotnych w naszym parserze, ale byłoby to bardzo kłopotliwe i nieczytelne. Zamiast tego zwrócimy AST, drzewo reprezentujące wyrażenie wejściowe:

 case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case Epsilon

Przypomina to nasze reguły, używając prostych klas danych.

Nasz parser zwraca teraz użyteczną strukturę danych:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon

Aby zapoznać się z eat() , error() i innymi szczegółami implementacji, zobacz towarzyszące repozytorium GitHub.

Zasady upraszczania

Nasz nieterminal ExprOpt można jeszcze ulepszyć:

 '+' NUM exprOpt | epsilon

Trudno jest rozpoznać wzorzec, który reprezentuje w naszej gramatyce, po prostu patrząc na niego. Okazuje się, że możemy zastąpić tę rekurencję prostszą konstrukcją:

 ('+' NUM)*

Ta konstrukcja oznacza po prostu, że '+' NUM występuje zero lub więcej razy.

Teraz nasza pełna gramatyka wygląda tak:

 expr -> NUM exprOpt* exprOpt -> '+' NUM

A nasz AST wygląda ładniej:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int)

Wynikowy parser ma taką samą długość, ale jest prostszy do zrozumienia i użycia. Wyeliminowaliśmy Epsilon , co sugeruje teraz, że zaczynamy od pustej struktury.

Nie potrzebowaliśmy tutaj nawet klasy ExprOpt . Moglibyśmy po prostu umieścić case class Expr(num: Int, exprOpts: Seq[Int]) lub w formacie gramatycznym NUM ('+' NUM)* . Dlaczego więc tego nie zrobiliśmy?

Weź pod uwagę, że gdybyśmy mieli wiele możliwych operatorów, takich jak - lub * , mielibyśmy taką gramatykę:

 expr -> NUM exprOpt* exprOpt -> [+-*] NUM

W takim przypadku AST potrzebuje następnie ExprOpt , aby dostosować typ operatora:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int)

Zwróć uwagę, że składnia [+-*] w gramatyce oznacza to samo, co w wyrażeniach regularnych: „jeden z tych trzech znaków”. Zobaczymy to wkrótce w akcji.

Interpreter Komponent 3: Pisanie tłumacza

Nasz interpreter użyje naszego leksera i parsera, aby uzyskać AST naszego wyrażenia wejściowego, a następnie oceni to AST w dowolny sposób. W tym przypadku mamy do czynienia z liczbami i chcemy oszacować ich sumę.

W implementacji naszego przykładu interpretera użyjemy tej prostej gramatyki:

 expr -> NUM exprOpt* exprOpt -> [+-] NUM

A to AST:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)

(Omówiliśmy, jak zaimplementować lekser i parser dla podobnych gramatyk, ale wszyscy czytelnicy, którzy utkną, mogą przejrzeć implementacje leksera i parsera dla tej dokładnej gramatyki w repozytorium).

Teraz zobaczymy, jak napisać interpreter dla powyższej gramatyki:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp

Jeśli przeanalizujemy dane wejściowe do AST bez napotkania błędu, jesteśmy pewni, że zawsze będziemy mieć co najmniej jeden NUM . Następnie bierzemy opcjonalne liczby i dodajemy je (lub odejmujemy) od naszego wyniku.

Uwaga z początku dotycząca lewego zespolenia + jest teraz jasna: zaczynamy od skrajnej lewej liczby i dodajemy kolejne, od lewej do prawej. Może się to wydawać nieistotne w przypadku dodawania, ale rozważ odejmowanie: wyrażenie 5 - 2 - 1 jest obliczane jako (5 - 2) - 1 = 3 - 1 = 2 , a nie jako 5 - (2 - 1) = 5 - 1 = 4 !

Ale jeśli chcemy wyjść poza interpretację operatorów plus i minus, musimy zdefiniować inną regułę.

Precedens

Wiemy, jak parsować proste wyrażenie, takie jak 1 + 2 + 3 , ale jeśli chodzi o 2 + 3 * 4 + 5 , mamy mały problem.

Większość ludzi zgadza się z konwencją, że mnożenie ma wyższy priorytet niż dodawanie. Ale parser tego nie wie. Nie możemy po prostu ocenić tego jako ((2 + 3) * 4) + 5 . Zamiast tego chcemy (2 + (3 * 4)) + 5 .

Oznacza to, że najpierw musimy obliczyć mnożenie . Mnożenie musi znajdować się dalej od korzenia AST , aby wymusić jego ocenę przed dodaniem. W tym celu musimy wprowadzić jeszcze jedną warstwę pośredniości.

Naprawianie naiwnej gramatyki od początku do końca

Oto nasza oryginalna gramatyka lewostronnie rekurencyjna, która nie ma żadnych reguł pierwszeństwa:

 expr -> expr '+' expr | expr '*' expr | NUM

Najpierw nadajemy mu zasady pierwszeństwa i usuwamy jego niejednoznaczność :

 expr -> expr '+' term | term term -> term '*' NUM | NUM

Następnie otrzymuje reguły nielewostronnie rekurencyjne :

 expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUM

Rezultatem jest pięknie wyrazisty AST:

 case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)

To pozostawia nam zwięzłą implementację interpretera:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmp

Tak jak poprzednio, idee w wymaganym lekserze i gramatyce zostały omówione wcześniej, ale czytelnicy mogą je znaleźć w repozytorium w razie potrzeby.

Kolejne kroki w pisaniu tłumaczy ustnych

Nie omówiliśmy tego, ale obsługa błędów i raportowanie to kluczowe cechy każdego parsera. Jako programiści wiemy, jak frustrujące może być, gdy kompilator generuje mylące lub wprowadzające w błąd błędy. Jest to obszar, który ma wiele interesujących problemów do rozwiązania, takich jak podawanie poprawnych i precyzyjnych komunikatów o błędach, nie odstraszanie użytkownika większą liczbą komunikatów niż jest to konieczne i wdzięczne odzyskiwanie po błędach. To zależy od programistów, którzy napiszą interpreter lub kompilator, aby zapewnić swoim przyszłym użytkownikom lepsze wrażenia.

Przechodząc przez nasze przykładowe leksery, parsery i interpretery, tylko zarysowaliśmy powierzchnię teorii stojących za kompilatorami i interpreterami, które obejmują takie tematy jak:

• Zakresy i tablice symboli
• Typy statyczne
• Optymalizacja w czasie kompilacji
• Analizatory programów statycznych i linterów
• Formatowanie kodu i ładne drukowanie
• Języki specyficzne dla domeny

Do dalszej lektury polecam te zasoby:

• Wzorce implementacji języka autorstwa Terence'a Parr
• Bezpłatna książka online, Crafting Interpreters , autorstwa Boba Nystroma
• Wprowadzenie do gramatyki i analizowania autorstwa Paula Klint
• Pisanie dobrych komunikatów o błędach kompilatora przez Caleba Meredith
• Notatki z kursu „Tłumaczenie i kompilacja programów” Uniwersytetu East Carolina