Linux中國

讓我們做個簡單的解釋器(一)

就是這樣。想一想。你是萌新還是一個資深的軟體開發者實際上都無關緊要:如果你不知道 編譯器 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
雨落清風。心向陽

    You may also like

    Leave a reply

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

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

    More in:Linux中國