如何從頭開始編寫解釋器

有人說“一切都歸結為 1 和 0”——但我們真的了解我們的程序是如何被翻譯成這些位的嗎？

編譯器和解釋器都採用表示程序的原始字符串，對其進行解析並理解它。 雖然解釋器是兩者中更簡單的，但即使是編寫一個非常簡單的解釋器（只做加法和乘法）也會很有啟發性。 我們將關注編譯器和解釋器的共同點：詞法分析和解析輸入。

編寫自己的解釋器的注意事項

讀者可能想知道正則表達式有什麼問題？ 正則表達式功能強大，但源代碼語法不夠簡單，無法被它們解析。 域特定語言 (DSL) 也不是，例如，客戶端可能需要自定義 DSL 用於授權表達式。 但即使不直接應用這項技能，編寫解釋器也可以更容易地理解許多編程語言、文件格式和 DSL 背後的努力。

對於涉及的所有邊緣情況，手動正確編寫解析器可能具有挑戰性。 這就是為什麼有一些流行的工具，比如 ANTLR，可以為許多流行的編程語言生成解析器。 還有一些稱為解析器組合器的庫，使開發人員能夠直接用他們喜歡的編程語言編寫解析器。 示例包括用於 Scala 的 FastParse 和用於 Python 的 Parsec。

我們建議，在專業背景下，讀者使用此類工具和庫來避免重新發明輪子。 儘管如此，了解從頭開始編寫解釋器的挑戰和可能性將有助於開發人員更有效地利用這些解決方案。

解釋器組件概述

解釋器是一個複雜的程序，所以它有多個階段：

1. 詞法分析器是解釋器的一部分，它將字符序列（純文本）轉換為標記序列。
2. 解析器依次接受一系列標記並生成語言的抽象語法樹 (AST)。 解析器操作的規則通常由形式文法指定。
3. 解釋器是一個即時解釋程序源代碼的 AST（無需先編譯）的程序。

我們不會在這裡構建一個特定的、集成的解釋器。 相反，我們將通過單獨的示例來探索這些部分及其常見問題。 最後，用戶代碼將如下所示：

 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")

在這三個階段之後，我們希望這段代碼計算出最終值並打印Result is: 19 。 本教程碰巧使用了 Scala，因為它是：

• 非常簡潔，在一個屏幕上可以容納很多代碼。
• 面向表達式，不需要未初始化/空變量。
• 類型安全，具有強大的集合庫、枚舉和案例類。

具體來說，這裡的代碼是用 Scala3 可選大括號語法（一種類似 Python、基於縮進的語法）編寫的。 但是這些方法都不是 Scala 特有的，而且 Scala 與許多其他語言相似：讀者會發現將這些代碼示例轉換為其他語言很簡單。 除此之外，這些示例可以使用 Scastie 在線運行。

最後，Lexer、Parser 和 Interpreter 部分有不同的示例語法。 正如相應的 GitHub 存儲庫所示，後面的示例中的依賴項略有變化以實現這些語法，但總體概念保持不變。

解釋器組件 1：編寫 Lexer

假設我們要對這個字符串進行 lex： "123 + 45 true * false1" 。 它包含不同類型的令牌：

• 整數文字
• A +運算符
• *運算符
• true的字面意思
• 標識符， false1

在此示例中將跳過標記之間的空格。

在這個階段，表達不必有意義； 詞法分析器只是將輸入字符串轉換為標記列表。 （“理解標記”的工作留給解析器。）

我們將使用此代碼來表示一個令牌：

 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

每個標記在原始輸入中都有一個類型、文本表示和位置。 該職位可以幫助詞法分析器的最終用戶進行調試。

EOF標記是標記輸入結束的特殊標記。 它在源文本中不存在； 我們只用它來簡化解析器階段。

這將是我們詞法分析器的輸出：

 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) )

讓我們檢查一下實現：

 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

我們從一個空的標記列表開始，然後遍歷字符串並在標記出現時添加它們。

我們使用前瞻字符來決定下一個標記的類型。 請注意，前瞻字符並不總是被檢查的最前面的字符。 基於前瞻，我們知道令牌的樣子，並使用currentPos掃描當前令牌中的所有預期字符，然後將令牌添加到列表中：

如果前瞻是空白，我們跳過它。 單字母標記是微不足道的； 我們添加它們並增加索引。 對於整數，我們只需要處理索引。

現在我們得到了一些複雜的東西：標識符與文字。 規則是我們取最長的匹配並檢查它是否是文字； 如果不是，它是一個標識符。

處理<和<=等運算符時要小心。 在那裡，您必須再看一個字符，看看它是否是= ，然後才能斷定它是<=運算符。 否則，它只是一個< 。

這樣，我們的詞法分析器就生成了一個標記列表。

解釋器組件 2：編寫解析器

我們必須為我們的代幣賦予一些結構——我們不能僅靠一個列表來做很多事情。 例如，我們需要知道：

哪些表達式是嵌套的？ 哪些運算符以什麼順序應用？ 哪些範圍規則適用（如果有）？

樹結構支持嵌套和排序。 但首先，我們必須定義一些構造樹的規則。 我們希望我們的解析器是明確的——總是為給定的輸入返回相同的結構。

請注意，以下解析器不使用前面的詞法分析器示例。 這個是加數字的，所以它的語法只有兩個標記， '+'和NUM ：

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

一個等價的，使用管道字符 ( | ) 作為正則表達式中的“或”符號，是：

 expr -> expr '+' expr | NUM

無論哪種方式，我們都有兩條規則：一條說我們可以對兩個expr求和，另一條說expr可以是一個NUM標記，這意味著一個非負整數。

規則通常用正式文法指定。 正式語法包括： 規則本身，如上所示 起始規則（根據約定指定的第一條規則） 定義規則的兩種類型的符號： 終端：我們語言的“字母”（和其他字符）——構成記號的不可約符號非終結符：用於解析的中間結構（即可以替換的符號）

只有非終結符可以在規則的左側； 右邊可以有終端和非終端。 在上面的示例中，終結符是'+'和NUM ，唯一的非終結符是expr 。 舉個更廣泛的例子，在 Java 語言中，我們有諸如'true' 、 '+' 、 Identifier和'['類的終結符，以及諸如BlockStatements 、 ClassBody和MethodOrFieldDecl類的非終結符。

有很多方法可以實現這個解析器。 在這裡，我們將使用“遞歸下降”解析技術。 它是最常見的類型，因為它最容易理解和實現。

遞歸下降解析器對語法中的每個非終結符使用一個函數。 它從起始規則開始，然後從那裡向下（因此是“下降”），確定在每個函數中應用哪個規則。 “遞歸”部分至關重要，因為我們可以遞歸地嵌套非終結符！ 正則表達式無法做到這一點：它們甚至無法處理平衡括號。 所以我們需要一個更強大的工具。

第一條規則的解析器看起來像這樣（完整代碼）：

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

eat()函數檢查前瞻是否與預期的標記匹配，然後移動前瞻索引。 不幸的是，這還行不通，因為我們需要解決一些語法問題。

語法歧義

第一個問題是我們語法的歧義，乍一看可能並不明顯：

 expr -> expr '+' expr | NUM

給定輸入1 + 2 + 3 ，我們的解析器可以選擇在結果 AST 中首先計算左expr或右expr ：

這就是為什麼我們需要引入一些不對稱性：

 expr -> expr '+' NUM | NUM

自第一個版本以來，我們可以用這個語法表示的表達式集沒有改變。 只是現在它是明確的：解析器總是向左走。 正是我們需要的！

這使我們的+操作左關聯，但是當我們到達解釋器部分時，這將變得明顯。

左遞歸規則

不幸的是，上面的修復並沒有解決我們的另一個問題，左遞歸：

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

我們這裡有無限遞歸。 如果我們進入這個函數，我們最終會得到一個堆棧溢出錯誤。 但是解析理論可以提供幫助！

假設我們有這樣的語法，其中alpha可以是任何終結符和非終結符序列：

 A -> A alpha | B

我們可以將這個語法重寫為：

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

在那裡， epsilon是一個空字符串——什麼都沒有，沒有標記。

讓我們看看我們語法的當前版本：

 expr -> expr '+' NUM | NUM

按照上面詳述的重寫解析規則的方法， alpha是我們'+' NUM個標記，我們的語法變為：

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

現在語法沒問題了，我們可以用遞歸下降解析器來解析它。 讓我們看看這樣的解析器如何查找我們語法的最新迭代：

 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

這裡我們使用EOF標記來簡化我們的解析器。 我們總是確定我們的列表中至少有一個標記，因此我們不需要處理空列表的特殊情況。

此外，如果我們切換到流式詞法分析器，我們將不會有一個內存列表，而是一個迭代器，所以我們需要一個標記來知道我們何時到達輸入的末尾。 當我們走到最後時， EOF令牌應該是剩下的最後一個令牌。

瀏覽代碼，我們可以看到表達式可以只是一個數字。 如果什麼都沒有，下一個標記就不會是Plus ，所以我們將停止解析。 最後一個標記是EOF ，我們就完成了。

如果輸入字符串有更多標記，那麼這些標記必須看起來像+ 123 。 這就是exprOpt()上的遞歸開始的地方！

生成 AST

現在我們成功地解析了我們的表達式，很難按原樣做任何事情。 我們可以在解析器中放置一些回調，但這會非常麻煩且不可讀。 相反，我們將返回一個 AST，一個表示輸入表達式的樹：

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

這類似於我們的規則，使用簡單的數據類。

我們的解析器現在返回一個有用的數據結構：

 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

對於eat() 、 error()和其他實現細節，請參閱隨附的 GitHub 存儲庫。

簡化規則

我們的ExprOpt非終結符仍然可以改進：

 '+' NUM exprOpt | epsilon

僅僅通過觀察很難識別它在我們的語法中所代表的模式。 事實證明，我們可以用一個更簡單的結構來替換這個遞歸：

 ('+' NUM)*

這個結構只是意味著'+' NUM出現零次或多次。

現在我們的完整語法如下所示：

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

我們的 AST 看起來更好：

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

生成的解析器長度相同，但更易於理解和使用。 我們已經消除了Epsilon ，現在從一個空結構開始就暗示了這一點。

我們在這裡甚至不需要ExprOpt類。 我們可以只輸入case class Expr(num: Int, exprOpts: Seq[Int]) ，或者語法格式NUM ('+' NUM)* 。 那我們為什麼不呢？

考慮一下，如果我們有多個可能的運算符，比如-或* ，那麼我們會有這樣的語法：

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

在這種情況下，AST 需要ExprOpt來適應運算符類型：

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

請注意，語法中的[+-*]語法與正則表達式中的含義相同：“這三個字符之一”。 我們很快就會看到這一點。

解釋器組件 3：編寫解釋器

我們的解釋器將使用我們的詞法分析器和解析器來獲取我們輸入表達式的 AST，然後以我們想要的任何方式評估該 AST。 在這種情況下，我們正在處理數字，並且我們想要評估它們的總和。

在我們的解釋器示例的實現中，我們將使用這個簡單的語法：

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

而這個 AST：

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

（我們已經介紹瞭如何為類似的語法實現詞法分析器和解析器，但任何陷入困境的讀者都可以在 repo 中仔細閱讀詞法分析器和解析器的實現，以了解這種精確的語法。）

現在我們將看到如何為上述語法編寫解釋器：

 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

如果我們將輸入解析為 AST 而沒有遇到錯誤，那麼我們確信我們將始終至少有一個NUM 。 然後我們取可選數字並將它們添加到我們的結果中（或從中減去它們）。

從一開始關於+的左結合性的註釋現在很清楚了：我們從最左邊的數字開始，然後從左到右添加其他數字。 這對於加法似乎並不重要，但考慮減法：表達式5 - 2 - 1被計算為(5 - 2) - 1 = 3 - 1 = 2而不是5 - (2 - 1) = 5 - 1 = 4 ！

但是如果我們想超越解釋加號和減號運算符，還有另一個規則需要定義。

優先級

我們知道如何解析像1 + 2 + 3這樣的簡單表達式，但是當涉及到2 + 3 * 4 + 5時，我們遇到了一些問題。

大多數人都同意乘法優先於加法的約定。 但是解析器不知道這一點。 我們不能只將其評估為((2 + 3) * 4) + 5 。 相反，我們想要(2 + (3 * 4)) + 5 。

這意味著我們需要先計算乘法。 乘法需要遠離 AST 的根，以強制在加法之前對其進行評估。 為此，我們需要引入另一層間接。

從頭到尾修復一個幼稚的語法

這是我們最初的左遞歸文法，它沒有優先規則：

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

首先，我們給它一個優先規則並消除它的歧義：

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

然後它得到非左遞歸規則：

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

結果是一個表現精美的 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)

這給我們留下了一個簡潔的解釋器實現：

 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

和以前一樣，必要的詞法分析器和語法中的想法在前面已經介紹過，但是如果需要，讀者可以在 repo 中找到它們。

編寫口譯員的下一步

我們沒有介紹這一點，但錯誤處理和報告是任何解析器的關鍵特性。 作為開發人員，我們知道當編譯器產生令人困惑或誤導的錯誤時會多麼令人沮喪。 這是一個需要解決許多有趣問題的領域，例如提供正確和準確的錯誤消息，不要以不必要的消息來阻止用戶，以及從錯誤中優雅地恢復。 由開發人員編寫解釋器或編譯器來確保他們未來的用戶有更好的體驗。

在瀏覽我們的示例詞法分析器、解析器和解釋器時，我們只觸及了編譯器和解釋器背後的理論的皮毛，它們涵蓋了以下主題：

• 範圍和符號表
• 靜態類型
• 編譯時優化
• 靜態程序分析器和 linter
• 代碼格式化和漂亮的打印
• 特定領域的語言

為了進一步閱讀，我推薦以下資源：

• Terence Parr 的語言實現模式
• Bob Nystrom的免費在線書籍Crafting Interpreters
• Paul Klint語法和解析簡介
• Caleb Meredith編寫好的編譯器錯誤消息
• 東卡羅來納大學《程序翻譯與編譯》課程筆記