Linux中國

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

241 views0
By
Share

就是這樣。想一想。你是萌新還是一個資深的軟體開發者實際上都無關緊要：如果你不知道 編譯器 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', 'EOF'

class 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 result

def 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.py
calc> 3+4
7
calc> 3+5
8
calc> 3+9
12
calc>

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

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

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

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

當你在命令行中輸入一個表達式 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: https://ruslanspivak.com/lsbasi-part1/

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

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

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive

對這篇文章感覺如何？

太棒了
0
不錯
0
愛死了
0
不太好
0
感覺很糟
0
雨落清風。心向陽
    Previous
    Next

    You may also like

    Leave a reply

    您的電子郵箱地址不會被公開。 必填項已用 * 標註

    此站點使用Akismet來減少垃圾評論。了解我們如何處理您的評論數據。

    More in:Linux中國