Linux中國

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

207 views0
By
Share

早上醒來的時候，我就在想：「為什麼我們學習一個新技能這麼難？」

我不認為那是因為它很難。我認為原因可能在於我們花了太多的時間，而這件難事需要有豐富的閱歷和足夠的知識，然而我們要把這樣的知識轉換成技能所用的練習時間又不夠。

拿游泳來說，你可以花上幾天時間來閱讀很多有關游泳的書籍，花幾個小時和資深的游泳者和教練交流，觀看所有可以獲得的訓練視頻，但你第一次跳進水池的時候，仍然會像一個石頭那樣沉入水中，

要點在於：你認為自己有多了解那件事都無關緊要 —— 你得通過練習把知識變成技能。為了幫你練習，我把訓練放在了這個系列的 第一部分 和 第二部分 了。當然，你會在今後的文章中看到更多練習，我保證 ：)

好，讓我們開始今天的學習。

到現在為止，你已經知道了怎樣解釋像 「7 + 3」 或者 「12 - 9」 這樣的兩個整數相加減的算術表達式。今天我要說的是怎麼解析（識別）、解釋有多個數字相加減的算術表達式，比如 「7 - 3 + 2 - 1」。

文中的這個算術表達式可以用下面的這個語法圖表示：

什麼是 語法圖 syntax diagram ？ 語法圖 是對一門編程語言中的語法規則進行圖像化的表示。基本上，一個語法圖就能告訴你哪些語句可以在程序中出現，哪些不能出現。

語法圖很容易讀懂：按照箭頭指向的路徑。某些路徑表示的是判斷，有些表示的是循環。

你可以按照以下的方式讀上面的語法圖：一個 term 後面可以是加號或者減號，接著可以是另一個 term，這個 term 後面又可以是一個加號或者減號，後面又是一個 term，如此循環。從字面上你就能讀懂這個圖片了。或許你會奇怪，「term」 是什麼、對於本文來說，「term」 就是個整數。

語法圖有兩個主要的作用：

  • 它們用圖形的方式表示一個編程語言的特性（語法）。
  • 它們可以用來幫你寫出解析器 —— 你可以根據下列簡單規則把圖片轉換成代碼。

你已經知道，識別出記號流中的片語的過程就叫做 解析。解釋器或者編譯器執行這個任務的部分叫做 解析器。解析也稱為 語法分析，並且解析器這個名字很合適，你猜的對，就是 語法分析器。

根據上面的語法圖，下面這些表達式都是合法的：

  • 3
  • 3 + 4
  • 7 - 3 + 2 - 1

因為算術表達式的語法規則在不同的編程語言裡面是很相近的，我們可以用 Python shell 來「測試」語法圖。打開 Python shell，運行下面的代碼：

>>> 3
3
>>> 3 + 4
7
>>> 7 - 3 + 2 - 1
5

意料之中。

表達式 「3 + 」 不是一個有效的數學表達式，根據語法圖，加號後面必須要有個 term （整數），否則就是語法錯誤。然後，自己在 Python shell 裡面運行：

>>> 3 +
  File "<stdin>", line 1
    3 +
      ^
SyntaxError: invalid syntax

能用 Python shell 來做這樣的測試非常棒，讓我們把上面的語法圖轉換成代碼，用我們自己的解釋器來測試，怎麼樣？

從之前的文章里（第一部分 和 第二部分）你知道 expr 方法包含了我們的解析器和解釋器。再說一遍，解析器僅僅識別出結構，確保它與某些特性對應，而解釋器實際上是在解析器成功識別（解析）特性之後，就立即對表達式進行評估。

以下代碼片段顯示了對應於圖表的解析器代碼。語法圖裡面的矩形方框（term）變成了 term 方法，用於解析整數，expr 方法和語法圖的流程一致：

def term(self):
    self.eat(INTEGER)

def expr(self):
    # 把當前標記設為從輸入中拿到的第一個標記
    self.current_token = self.get_next_token()

    self.term()
    while self.current_token.type in (PLUS, MINUS):
        token = self.current_token
        if token.type == PLUS:
            self.eat(PLUS)
            self.term()
        elif token.type == MINUS:
            self.eat(MINUS)
            self.term()

你能看到 expr 首先調用了 term 方法。然後 expr 方法裡面的 while 循環可以執行 0 或多次。在循環裡面解析器基於標記做出判斷（是加號還是減號）。花一些時間，你就知道，上述代碼確實是遵循著語法圖的算術表達式流程。

解析器並不解釋任何東西：如果它識別出了一個表達式，它就靜默著，如果沒有識別出來，就會拋出一個語法錯誤。改一下 expr 方法，加入解釋器的代碼：

def term(self):
    """Return an INTEGER token value"""
    token = self.current_token
    self.eat(INTEGER)
    return token.value

def expr(self):
    """Parser / Interpreter """
    # 將輸入中的第一個標記設置成當前標記
    self.current_token = self.get_next_token()

    result = self.term()
    while self.current_token.type in (PLUS, MINUS):
        token = self.current_token
        if token.type == PLUS:
            self.eat(PLUS)
            result = result + self.term()
        elif token.type == MINUS:
            self.eat(MINUS)
            result = result - self.term()

    return result

因為解釋器需要評估一個表達式， term 方法被改成返回一個整型值，expr 方法被改成在合適的地方執行加法或減法操作，並返回解釋的結果。儘管代碼很直白，我建議花點時間去理解它。

進行下一步，看看完整的解釋器代碼，好不？

這是新版計算器的源代碼，它可以處理包含有任意多個加法和減法運算的有效的數學表達式。

# 標記類型
#
# EOF （end-of-file 文件末尾）標記是用來表示所有輸入都解析完成
INTEGER, PLUS, MINUS, EOF = &apos;INTEGER&apos;, &apos;PLUS&apos;, &apos;MINUS&apos;, &apos;EOF&apos;

class Token(object):
    def __init__(self, type, value):
        # token 類型: INTEGER, PLUS, MINUS, or EOF
        self.type = type
        # token 值: 非負整數值, &apos;+&apos;, &apos;-&apos;, 或無
        self.value = value

    def __str__(self):
        """String representation of the class instance.

        Examples:
            Token(INTEGER, 3)
            Token(PLUS, &apos;+&apos;)
        """
        return &apos;Token({type}, {value})&apos;.format(
            type=self.type,
            value=repr(self.value)
        )

    def __repr__(self):
        return self.__str__()

class Interpreter(object):
    def __init__(self, text):
        # 客戶端字元輸入， 例如. "3 + 5", "12 - 5", 
        self.text = text
        # self.pos is an index into self.text
        self.pos = 0
        # 當前標記實例
        self.current_token = None
        self.current_char = self.text[self.pos]

    ##########################################################
    # Lexer code                                             #
    ##########################################################
    def error(self):
        raise Exception(&apos;Invalid syntax&apos;)

    def advance(self):
        """Advance the `pos` pointer and set the `current_char` variable."""
        self.pos += 1
        if self.pos > len(self.text) - 1:
            self.current_char = None  # Indicates end of input
        else:
            self.current_char = self.text[self.pos]

    def skip_whitespace(self):
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def integer(self):
        """Return a (multidigit) integer consumed from the input."""
        result = &apos;&apos;
        while self.current_char is not None and self.current_char.isdigit():
            result += self.current_char
            self.advance()
        return int(result)

    def get_next_token(self):
        """Lexical analyzer (also known as scanner or tokenizer)

        This method is responsible for breaking a sentence
        apart into tokens. One token at a time.
        """
        while self.current_char is not None:

            if self.current_char.isspace():
                self.skip_whitespace()
                continue

            if self.current_char.isdigit():
                return Token(INTEGER, self.integer())

            if self.current_char == &apos;+&apos;:
                self.advance()
                return Token(PLUS, &apos;+&apos;)

            if self.current_char == &apos;-&apos;:
                self.advance()
                return Token(MINUS, &apos;-&apos;)

            self.error()

        return Token(EOF, None)

    ##########################################################
    # Parser / Interpreter code                              #
    ##########################################################
    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 term(self):
        """Return an INTEGER token value."""
        token = self.current_token
        self.eat(INTEGER)
        return token.value

    def expr(self):
        """Arithmetic expression parser / interpreter."""
        # 將輸入中的第一個標記設置成當前標記
        self.current_token = self.get_next_token()

        result = self.term()
        while self.current_token.type in (PLUS, MINUS):
            token = self.current_token
            if token.type == PLUS:
                self.eat(PLUS)
                result = result + self.term()
            elif token.type == MINUS:
                self.eat(MINUS)
                result = result - self.term()

        return result

def main():
    while True:
        try:
            # To run under Python3 replace &apos;raw_input&apos; call
            # 要在 Python3 下運行，請把 『raw_input』 的調用換成 『input』
            text = raw_input(&apos;calc> &apos;)
        except EOFError:
            break
        if not text:
            continue
        interpreter = Interpreter(text)
        result = interpreter.expr()
        print(result)

if __name__ == &apos;__main__&apos;:
    main()

把上面的代碼保存到 calc3.py 文件中，或者直接從 GitHub 上下載。試著運行它。看看它能不能處理我之前給你看過的語法圖裡面派生出的數學表達式。

這是我在自己的筆記本上運行的示例：

$ python calc3.py
calc> 3
3
calc> 7 - 4
3
calc> 10 + 5
15
calc> 7 - 3 + 2 - 1
5
calc> 10 + 1 + 2 - 3 + 4 + 6 - 15
5
calc> 3 +
Traceback (most recent call last):
  File "calc3.py", line 147, in <module>
    main()
  File "calc3.py", line 142, in main
    result = interpreter.expr()
  File "calc3.py", line 123, in expr
    result = result + self.term()
  File "calc3.py", line 110, in term
    self.eat(INTEGER)
  File "calc3.py", line 105, in eat
    self.error()
  File "calc3.py", line 45, in error
    raise Exception(&apos;Invalid syntax&apos;)
Exception: Invalid syntax

記得我在文章開始時提過的練習嗎：它們在這兒，我保證過的：)

  • 畫出只包含乘法和除法的數學表達式的語法圖，比如 「7 4 / 2 3」。認真點，拿只鋼筆或鉛筆，試著畫一個。 修改計算器的源代碼，解釋只包含乘法和除法的數學表達式。比如 「7 4 / 2 3」。
  • 從頭寫一個可以處理像 「7 - 3 + 2 - 1」 這樣的數學表達式的解釋器。用你熟悉的編程語言，不看示例代碼自己思考著寫出代碼。做的時候要想一想這裡面包含的組件：一個詞法分析器，讀取輸入並轉換成標記流，一個解析器，從詞法分析器提供的記號流中獲取，並且嘗試識別流中的結構，一個解釋器，在解析器成功解析（識別）有效的數學表達式後產生結果。把這些要點串起來。花一點時間把你獲得的知識變成一個可以運行的數學表達式的解釋器。

檢驗你的理解：

  1. 什麼是語法圖？
  2. 什麼是語法分析？
  3. 什麼是語法分析器？

嘿，看！你看完了所有內容。感謝你們堅持到今天，而且沒有忘記練習。:) 下次我會帶著新的文章回來，盡請期待。

via: https://ruslanspivak.com/lsbasi-part3/

作者：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中國