歡迎光臨
每天分享高質量文章

讓我們做個簡單的直譯器(三) | Linux 中國

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


致謝
編譯自 | https://ruslanspivak.com/lsbasi-part3/ 
 作者 | Ruslan Spivak
 譯者 | 周家未 (BriFuture) ? ? ? 共計翻譯:21 篇 貢獻時間:611 天

早上醒來的時候,我就在想:“為什麼我們學習一個新技能這麼難?”

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

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

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

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

到現在為止,你已經知道了怎樣解釋像 “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,執行下麵的程式碼:

  1. >>> 3

  2. 3

  3. >>> 3 + 4

  4. 7

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

  6. 5

意料之中。

運算式 “3 + ” 不是一個有效的數學運算式,根據語法圖,加號後面必須要有個 term (整數),否則就是語法錯誤。然後,自己在 Python shell 裡面執行:

  1. >>> 3 +

  2.  File "", line 1

  3.    3 +

  4.      ^

  5. SyntaxError: invalid syntax

能用 Python shell 來做這樣的測試非常棒,讓我們把上面的語法圖轉換成程式碼,用我們自己的直譯器來測試,怎麼樣?

從之前的文章裡(第一部分[1] 和 第二部分[2])你知道 expr 方法包含了我們的解析器和直譯器。再說一遍,解析器僅僅識別出結構,確保它與某些特性對應,而直譯器實際上是在解析器成功識別(解析)特性之後,就立即對運算式進行評估。

以下程式碼片段顯示了對應於圖表的解析器程式碼。語法圖裡面的矩形方框(term)變成了 term 方法,用於解析整數,expr 方法和語法圖的流程一致:

  1. def term(self):

  2.    self.eat(INTEGER)

  3. def expr(self):

  4.    # 把當前標記設為從輸入中拿到的第一個標記

  5.    self.current_token = self.get_next_token()

  6.    self.term()

  7.    while self.current_token.type in (PLUS, MINUS):

  8.        token = self.current_token

  9.        if token.type == PLUS:

  10.            self.eat(PLUS)

  11.            self.term()

  12.        elif token.type == MINUS:

  13.            self.eat(MINUS)

  14.            self.term()

你能看到 expr 首先呼叫了 term 方法。然後 expr 方法裡面的 while 迴圈可以執行 0 或多次。在迴圈裡面解析器基於標記做出判斷(是加號還是減號)。花一些時間,你就知道,上述程式碼確實是遵循著語法圖的算術運算式流程。

解析器並不解釋任何東西:如果它識別出了一個運算式,它就靜默著,如果沒有識別出來,就會丟擲一個語法錯誤。改一下 expr 方法,加入直譯器的程式碼:

  1. def term(self):

  2.    """Return an INTEGER token value"""

  3.    token = self.current_token

  4.    self.eat(INTEGER)

  5.    return token.value

  6. def expr(self):

  7.    """Parser / Interpreter """

  8.    # 將輸入中的第一個標記設定成當前標記

  9.    self.current_token = self.get_next_token()

  10.    result = self.term()

  11.    while self.current_token.type in (PLUS, MINUS):

  12.        token = self.current_token

  13.        if token.type == PLUS:

  14.            self.eat(PLUS)

  15.            result = result + self.term()

  16.        elif token.type == MINUS:

  17.            self.eat(MINUS)

  18.            result = result - self.term()

  19.    return result

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

進行下一步,看看完整的直譯器程式碼,好不?

這是新版計算器的原始碼,它可以處理包含有任意多個加法和減法運算的有效的數學運算式。

  1. # 標記型別

  2. #

  3. # EOF end-of-file 檔案末尾)標記是用來表示所有輸入都解析完成

  4. INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'

  5. class Token(object):

  6.    def __init__(self, type, value):

  7.        # token 型別: INTEGER, PLUS, MINUS, or EOF

  8.        self.type = type

  9.        # token 值: 非負整數值, '+', '-', 或無

  10.        self.value = value

  11.    def __str__(self):

  12.        """String representation of the class instance.

  13.        Examples:

  14.            Token(INTEGER, 3)

  15.            Token(PLUS, '+')

  16.        """

  17.        return 'Token({type}, {value})'.format(

  18.            type=self.type,

  19.            value=repr(self.value)

  20.        )

  21.    def __repr__(self):

  22.        return self.__str__()

  23. class Interpreter(object):

  24.    def __init__(self, text):

  25.        # 客戶端字元輸入, 例如. "3 + 5", "12 - 5",

  26.        self.text = text

  27.        # self.pos is an index into self.text

  28.        self.pos = 0

  29.        # 當前標記實體

  30.        self.current_token = None

  31.        self.current_char = self.text[self.pos]

  32.    ##########################################################

  33.    # Lexer code                                             #

  34.    ##########################################################

  35.    def error(self):

  36.        raise Exception('Invalid syntax')

  37.    def advance(self):

  38.        """Advance the `pos` pointer and set the `current_char` variable."""

  39.        self.pos += 1

  40.        if self.pos > len(self.text) - 1:

  41.            self.current_char = None  # Indicates end of input

  42.        else:

  43.            self.current_char = self.text[self.pos]

  44.    def skip_whitespace(self):

  45.        while self.current_char is not None and self.current_char.isspace():

  46.            self.advance()

  47.    def integer(self):

  48.        """Return a (multidigit) integer consumed from the input."""

  49.        result = ''

  50.        while self.current_char is not None and self.current_char.isdigit():

  51.            result += self.current_char

  52.            self.advance()

  53.        return int(result)

  54.    def get_next_token(self):

  55.        """Lexical analyzer (also known as scanner or tokenizer)

  56.        This method is responsible for breaking a sentence

  57.        apart into tokens. One token at a time.

  58.        """

  59.        while self.current_char is not None:

  60.            if self.current_char.isspace():

  61.                self.skip_whitespace()

  62.                continue

  63.            if self.current_char.isdigit():

  64.                return Token(INTEGER, self.integer())

  65.            if self.current_char == '+':

  66.                self.advance()

  67.                return Token(PLUS, '+')

  68.            if self.current_char == '-':

  69.                self.advance()

  70.                return Token(MINUS, '-')

  71.            self.error()

  72.        return Token(EOF, None)

  73.    ##########################################################

  74.    # Parser / Interpreter code                              #

  75.    ##########################################################

  76.    def eat(self, token_type):

  77.        # 將當前的標記型別與傳入的標記型別作比較,如果他們相匹配,就

  78.        # eat 掉當前的標記並將下一個標記賦給 self.current_token

  79.        # 否則丟擲一個異常

  80.        if self.current_token.type == token_type:

  81.            self.current_token = self.get_next_token()

  82.        else:

  83.            self.error()

  84.    def term(self):

  85.        """Return an INTEGER token value."""

  86.        token = self.current_token

  87.        self.eat(INTEGER)

  88.        return token.value

  89.    def expr(self):

  90.        """Arithmetic expression parser / interpreter."""

  91.        # 將輸入中的第一個標記設定成當前標記

  92.        self.current_token = self.get_next_token()

  93.        result = self.term()

  94.        while self.current_token.type in (PLUS, MINUS):

  95.            token = self.current_token

  96.            if token.type == PLUS:

  97.                self.eat(PLUS)

  98.                result = result + self.term()

  99.            elif token.type == MINUS:

  100.                self.eat(MINUS)

  101.                result = result - self.term()

  102.        return result

  103. def main():

  104.    while True:

  105.        try:

  106.            # To run under Python3 replace 'raw_input' call

  107.            # 要在 Python3 下執行,請把 raw_input 的呼叫換成 input

  108.            text = raw_input('calc> ')

  109.        except EOFError:

  110.            break

  111.        if not text:

  112.            continue

  113.        interpreter = Interpreter(text)

  114.        result = interpreter.expr()

  115.        print(result)

  116. if __name__ == '__main__':

  117.    main()

把上面的程式碼儲存到 calc3.py 檔案中,或者直接從 GitHub[3] 上下載。試著執行它。看看它能不能處理我之前給你看過的語法圖裡面派生出的數學運算式。

這是我在自己的筆記本上執行的示例:

  1. $ python calc3.py

  2. calc> 3

  3. 3

  4. calc> 7 - 4

  5. 3

  6. calc> 10 + 5

  7. 15

  8. calc> 7 - 3 + 2 - 1

  9. 5

  10. calc> 10 + 1 + 2 - 3 + 4 + 6 - 15

  11. 5

  12. calc> 3 +

  13. Traceback (most recent call last):

  14.  File "calc3.py", line 147, in <module>

  15.    main()

  16.  File "calc3.py", line 142, in main

  17.    result = interpreter.expr()

  18.  File "calc3.py", line 123, in expr

  19.    result = result + self.term()

  20.  File "calc3.py", line 110, in term

  21.    self.eat(INTEGER)

  22.  File "calc3.py", line 105, in eat

  23.    self.error()

  24.  File "calc3.py", line 45, in error

  25.    raise Exception('Invalid syntax')

  26. Exception: Invalid syntax

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

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

檢驗你的理解:

☉ 什麼是語法圖?
☉ 什麼是語法分析?
☉ 什麼是語法分析器?

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


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

作者:Ruslan Spivak[5] 譯者:BriFuture 校對:wxy

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

贊(0)

分享創造快樂

© 2024 知識星球   網站地圖