標籤：

讓我們做個簡單的解釋器（一）

04-01

「如果你不知道編譯器是怎麼工作的，那你就不知道電腦是怎麼工作的。如果你不能百分百確定，那就是不知道它們是如何工作的。」 --Steve Yegge

就是這樣。想一想。你是萌新還是一個資深的軟體開發者實際上都無關緊要：如果你不知道編譯器compiler和解釋器interpreter是怎麼工作的，那麼你就不知道電腦是怎麼工作的。就這麼簡單。

所以，你知道編譯器和解釋器是怎麼工作的嗎？我是說，你百分百確定自己知道他們怎麼工作嗎？如果不知道。

或者如果你不知道但你非常想要了解它。

不用擔心。如果你能堅持跟著這個系列做下去，和我一起構建一個解釋器和編譯器，最後你將會知道他們是怎麼工作的。並且你會變成一個自信滿滿的快樂的人。至少我希望如此。

為什麼要學習編譯器和解釋器？有三點理由。

  1. 要寫出一個解釋器或編譯器，你需要有很多的專業知識，並能融會貫通。寫一個解釋器或編譯器能幫你加強這些能力，成為一個更厲害的軟體開發者。而且，你要學的技能對編寫軟體非常有用，而不是僅僅局限於解釋器或編譯器。
  2. 你確實想要了解電腦是怎麼工作的。通常解釋器和編譯器看上去很魔幻。你或許不習慣這種魔力。你會想去揭開構建解釋器和編譯器那層神秘的面紗，了解它們的原理，把事情做好。
  3. 你想要創建自己的編程語言或者特定領域的語言。如果你創建了一個，你還要為它創建一個解釋器或者編譯器。最近，興起了對新的編程語言的興趣。你能看到幾乎每天都有一門新的編程語言橫空出世：Elixir，Go，Rust，還有很多。

好，但什麼是解釋器和編譯器？

解釋器 和 編譯器 的任務是把用高級語言寫的源程序翻譯成其他的格式。很奇怪，是不是？忍一忍，稍後你會在這個系列學到到底把源程序翻譯成什麼東西。

這時你可能會奇怪解釋器和編譯器之間有什麼區別。為了實現這個系列的目的，我們規定一下，如果有個翻譯器把源程序翻譯成機器語言，那它就是 編譯器。如果一個翻譯器可以處理並執行源程序，卻不用把它翻譯器機器語言，那它就是 解釋器。直觀上它看起來像這樣：

我希望你現在確信你很想學習構建一個編譯器和解釋器。你期望在這個教程里學習解釋器的哪些知識呢？

你看這樣如何。你和我一起為 Pascal 語言的一個大子集做一個簡單的解釋器。在這個系列結束的時候你能做出一個可以運行的 Pascal 解釋器和一個像 Python 的 pdb 那樣的源代碼級別的調試器。

你或許會問，為什麼是 Pascal？一方面，它不是我為了這個系列而提出的一個虛構的語言：它是真實存在的一門編程語言，有很多重要的語言結構。有些陳舊但有用的計算機書籍使用 Pascal 編程語言作為示例（我知道對於選擇一門語言來構建解釋器，這個理由並不令人信服，但我認為學一門非主流的語言也不錯 :））。

這有個 Pascal 中的階乘函數示例，你將能用自己的解釋器解釋代碼，還能夠用可交互的源碼級調試器進行調試，你可以這樣創造：

program factorial;function factorial(n: integer): longint;begin if n = 0 then factorial := 1 else factorial := n * factorial(n - 1);end;var n: integer;begin for n := 0 to 16 do writeln(n, ! = , factorial(n));end.

這個 Pascal 解釋器的實現語言會使用 Python，但你也可以用其他任何語言，因為這裡展示的思想不依賴任何特殊的實現語言。好，讓我們開始幹活。準備好了，出發！

你會從編寫一個簡單的算術表達式解析器，也就是常說的計算器，開始學習解釋器和編譯器。今天的目標非常簡單：讓你的計算器能處理兩個個位數相加，比如 3+5。下面是你的計算器的源代碼——不好意思，是解釋器：

# 標記類型## EOF （end-of-file 文件末尾）標記是用來表示所有輸入都解析完成INTEGER, PLUS, EOF = INTEGER, PLUS, EOFclass Token(object): def __init__(self, type, value): # token 類型: INTEGER, PLUS, MINUS, or EOF self.type = type # token 值: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, 或 None self.value = value def __str__(self): """String representation of the class instance. Examples: Token(INTEGER, 3) Token(PLUS +) """ return Token({type}, {value}).format( type=self.type, value=repr(self.value) ) def __repr__(self): return self.__str__()class Interpreter(object): def __init__(self, text): # 用戶輸入字元串, 例如 "3+5" self.text = text # self.pos 是 self.text 的索引 self.pos = 0 # 當前標記實例 self.current_token = None def error(self): raise Exception(Error parsing input) def get_next_token(self): """詞法分析器（也說成掃描器或者標記器） 該方法負責把一個句子分成若干個標記。每次處理一個標記 """ text = self.text # self.pos 索引到達了 self.text 的末尾嗎？ # 如果到了，就返回 EOF 標記，因為沒有更多的 # 能轉換成標記的輸入了 if self.pos > len(text) - 1: return Token(EOF, None) # 從 self.pos 位置獲取當前的字元， # 基於單個字元判斷要生成哪種標記 current_char = text[self.pos] # 如果字元是一個數字，就把他轉換成一個整數，生成一個 INTEGER # 標記，累加 self.pos 索引，指向數字後面的下一個字元， # 並返回 INTEGER 標記 if current_char.isdigit(): token = Token(INTEGER, int(current_char)) self.pos += 1 return token if current_char == +: token = Token(PLUS, current_char) self.pos += 1 return token self.error() def eat(self, token_type): # 將當前的標記類型與傳入的標記類型作比較，如果他們相匹配，就 # 「eat」 掉當前的標記並將下一個標記賦給 self.current_token， # 否則拋出一個異常 if self.current_token.type == token_type: self.current_token = self.get_next_token() else: self.error() def expr(self): """expr -> INTEGER PLUS INTEGER""" # 將輸入中的第一個標記設置成當前標記 self.current_token = self.get_next_token() # 我們期望當前標記是個位數。 left = self.current_token self.eat(INTEGER) # 期望當前標記是 『+』 號 op = self.current_token self.eat(PLUS) # 我們期望當前標記是個位數。 right = self.current_token self.eat(INTEGER) # 上述操作完成後，self.current_token 被設成 EOF 標記 # 這時成功找到 INTEGER PLUS INTEGER 標記序列 # 這個方法就可以返回兩個整數相加的結果了， # 即高效的解釋了用戶輸入 result = left.value + right.value return resultdef main(): while True: try: # 要在 Python3 下運行，請把 『raw_input』 換成 『input』 text = raw_input(calc> ) except EOFError: break if not text: continue interpreter = Interpreter(text) result = interpreter.expr() print(result)if __name__ == __main__: main()

把上面的代碼保存到 calc1.py 文件，或者直接從 GitHub 上下載。在你深入研究代碼前，在命令行裡面運行它看看效果。試一試！這是我筆記本上的示例會話（如果你想在 Python3 下運行，你要把 raw_input 換成 input）：

$ python calc1.pycalc> 3+47calc> 3+58calc> 3+912calc>

要讓你的簡易計算器正常工作，不拋出異常，你的輸入要遵守以下幾個規則：

  • 只允許輸入個位數
  • 此時支持的唯一一個運算符是加法
  • 輸入中不允許有任何的空格符號

要讓計算器變得簡單，這些限制非常必要。不用擔心，你很快就會讓它變得很複雜。

好，現在讓我們深入它，看看解釋器是怎麼工作，它是怎麼評估出算術表達式的。

當你在命令行中輸入一個表達式 3+5，解釋器就獲得了字元串 「3+5」。為了讓解釋器能夠真正理解要用這個字元串做什麼，它首先要把輸入 「3+5」 分到叫做 token（標記）的容器里。標記token 是一個擁有類型和值的對象。比如說，對字元 「3」 而言，標記的類型是 INTEGER 整數，對應的值是 3。

把輸入字元串分成標記的過程叫詞法分析lexical analysis。因此解釋器的需要做的第一步是讀取輸入字元，並將其轉換成標記流。解釋器中的這一部分叫做詞法分析器lexical analyzer，或者簡短點叫 lexer。你也可以給它起別的名字，諸如掃描器scanner或者標記器tokenizer。它們指的都是同一個東西：解釋器或編譯器中將輸入字元轉換成標記流的那部分。

Interpreter 類中的 get_next_token 方法就是詞法分析器。每次調用它的時候，你都能從傳入解釋器的輸入字元中獲得創建的下一個標記。仔細看看這個方法，看看它是如何完成把字元轉換成標記的任務的。輸入被存在可變文本中，它保存了輸入的字元串和關於該字元串的索引（把字元串想像成字元數組）。pos 開始時設為 0，指向字元 『3』。這個方法一開始檢查字元是不是數字，如果是，就將 pos加 1，並返回一個 INTEGER 類型的標記實例，並把字元 『3』 的值設為整數，也就是整數 3：

現在 pos 指向文本中的 『+』 號。下次調用這個方法的時候，它會測試 pos 位置的字元是不是個數字，然後檢測下一個字元是不是個加號，就是這樣。結果這個方法把 pos 加 1，返回一個新創建的標記，類型是 PLUS，值為 『+』。

pos 現在指向字元 『5』。當你再調用 get_next_token 方法時，該方法會檢查這是不是個數字，就是這樣，然後它把 pos 加 1，返回一個新的 INTEGER 標記，該標記的值被設為整數 5：

因為 pos 索引現在到了字元串 「3+5」 的末尾，你每次調用 get_next_token 方法時，它將會返回 EOF 標記：

自己試一試，看看計算器里的詞法分析器的運行：

>>> from calc1 import Interpreter>>>>>> interpreter = Interpreter(3+5)>>> interpreter.get_next_token()Token(INTEGER, 3)>>>>>> interpreter.get_next_token()Token(PLUS, +)>>>>>> interpreter.get_next_token()Token(INTEGER, 5)>>>>>> interpreter.get_next_token()Token(EOF, None)>>>

既然你的解釋器能夠從輸入字元中獲取標記流，解釋器需要對它做點什麼：它需要在詞法分析器 get_next_token 中獲取的標記流中找出相應的結構。你的解釋器應該能夠找到流中的結構：INTEGER -> PLUS -> INTEGER。就是這樣，它嘗試找出標記的序列：整數後面要跟著加號，加號後面要跟著整數。

負責找出並解釋結構的方法就是 expr。該方法檢驗標記序列確實與期望的標記序列是對應的，比如 INTEGER -> PLUS -> INTEGER。成功確認了這個結構後，就會生成加號左右兩邊的標記的值相加的結果，這樣就成功解釋你輸入到解釋器中的算術表達式了。

expr 方法用了一個助手方法 eat 來檢驗傳入的標記類型是否與當前的標記類型相匹配。在匹配到傳入的標記類型後，eat 方法會獲取下一個標記，並將其賦給 current_token 變數，然後高效地 「吃掉」 當前匹配的標記，並將標記流的虛擬指針向後移動。如果標記流的結構與期望的 INTEGER -> PLUS -> INTEGER 標記序列不對應，eat 方法就拋出一個異常。

讓我們回顧下解釋器做了什麼來對算術表達式進行評估的：

  • 解釋器接受輸入字元串，比如說 「3+5」
  • 解釋器調用 expr 方法，在詞法分析器 get_next_token 返回的標記流中找出結構。這個結構就是 INTEGER -> PLUS -> INTEGER 這樣的格式。在確認了格式後，它就通過把兩個整型標記相加來解釋輸入，因為此時對於解釋器來說很清楚，它要做的就是把兩個整數 3 和 5 進行相加。

恭喜。你剛剛學習了怎麼構建自己的第一個解釋器！

現在是時候做練習了。

看了這篇文章，你肯定覺得不夠，是嗎？好，準備好做這些練習：

  1. 修改代碼，允許輸入多位數，比如 「12+3」
  2. 添加一個方法忽略空格符，讓你的計算器能夠處理帶有空白的輸入，比如 「12 + 3」
  3. 修改代碼，用 『-』 號而非 『+』 號去執行減法比如 「7-5」

檢驗你的理解

  1. 什麼是解釋器？
  2. 什麼是編譯器
  3. 解釋器和編譯器有什麼差別？
  4. 什麼是標記?
  5. 將輸入分隔成若干個標記的過程叫什麼？
  6. 解釋器中進行詞法分析的部分叫什麼？
  7. 解釋器或編譯器中進行詞法分析的部分有哪些其他的常見名字？

在結束本文前，我衷心希望你能留下學習解釋器和編譯器的承諾。並且現在就開始做。不要把它留到以後。不要拖延。如果你已經看完了本文，就開始吧。如果已經仔細看完了但是還沒做什麼練習 —— 現在就開始做吧。如果已經開始做練習了，那就把剩下的做完。你懂得。而且你知道嗎？簽下承諾書，今天就開始學習解釋器和編譯器！

本人， ______，身體健全，思想正常，在此承諾從今天開始學習解釋器和編譯器，直到我百分百了解它們是怎麼工作的！

簽字人:

日期:

簽字，寫上日期，把它放在你每天都能看到的地方，確保你能堅守承諾。謹記你的承諾：

「承諾就是，你說自己會去做的事，在你說完就一直陪著你的東西。」 —— Darren Hardy

好，今天的就結束了。這個系列的下一篇文章里，你將會擴展自己的計算器，讓它能夠處理更複雜的算術表達式。敬請期待。

via: ruslanspivak.com/lsbasi

作者：Ruslan Spivak 譯者：BriFuture 校對：wxy

本文由 LCTT 原創編譯，Linux中國 榮譽推出


推薦閱讀：

※用python實現一個簡易的lisp解釋器--解釋器基本結構的實現(5)
※一起寫一個解釋器（2）---看，兔子！
※用python實現一個簡易的lisp解釋器--默認操作符的實現(6)
※一晚上糊出一個語言「後端」

TAG:解釋器 | 編程語言 |