# 練習 33：解析器 > 原文：[Exercise 33: Parsers](https://learncodethehardway.org/more-python-book/ex33.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 想象一下，你將獲得一個巨大的數字列表，你必須將其輸入到電子表格中。一開始，這個巨大的列表只是一個空格分隔的原始數據流。你的大腦會自動在空格處拆分數字流并創建數字。你的大腦像掃描器一樣。然后，你將獲取每個數字，并將其輸入到具有含義的行和列中。你的大腦像一個解析器，通過獲取扁平的數字（記號），并將它們變成一個更有意義的行和列的二維網格。你遵循的規則，什么數字進入什么行什么列，是你的“語法”，解析器的工作就是像你對于電子表格那樣使用語法。 我們再來看一下練習 32 中的微型 Python 代碼，再從三個不同的角度討論解析器： ```py def hello(x, y): print(x + y) hello(10, 20) ``` 當你查看這個代碼時，你看到什么？我看到一棵樹，類似于我們之前創建的`BSTree`或`TSTree`。你看到樹了嗎？我們從這個文件的最上方開始，學習如何將字符轉換為樹。 首先，當我們加載一個`.py`文件時，它只是一個“字符”流 - 實際上是字節，但 Python 使用Unicode，所以必須處理字符。這些字符在一行中，毫無結構，掃描器的任務是增加第一層次的意義。掃描器通過使用正則表達式，從字符串流中提取意義，創建記號列表。我們已經將一個字符列表轉換為一個記號列表，但看看`def hello(x,y):`函數。這是一個函數，里面有代碼塊。這意味著某種形式的“包含”或“東西里面的東西”的結構。 一個很容易表示包含的方式是用一棵樹。我們可以使用表格，像你的電子表格一樣，但它并不像樹那么容易。接下來看看`hello(x, y)`部分。我們有一個`NAME(hello)`記號，但是我們要抓取`(...)`部分的內容，并且知道它在括號內。再次，我們可以使用一個樹，我們將`(...)`部分中的`x, y`部分“嵌套” 為樹的子節點或分支。最終，我們就擁有了一棵樹，從這個 Python 代碼的根開始，并且每個代碼塊，`print`，函數定義和函數調用都是根的分支，它們也有子分支，以此類推。 為什么我們這樣做？我們需要基于其語法，知道 Python 代碼的結構，以便我們稍后分析。如果我們不將記號的線性列表轉換成樹結構，那么我們不知道函數，代碼塊，分支或表達式的邊界在哪里。我們必須以“直線”方式在飛行中確定邊界，這不容易使其可靠。很多早期的糟糕語言是直線語言，我們現在知道了他們不必須是這樣。我們可以使用解析器構建樹結構。 解析器的任務是從掃描器中獲取記號列表，并將其翻譯成更有意義的語法樹。你可以認為解析器是，對記號流應用另一個正則表達式。掃描器的正則表達式將大量字符放入記號中。解析器的“正則表達式”將這些記號放在盒子里面，它里面有盒子，以此類推，直到記號不再是線性的。 解析器也為這些盒子添加了含義。解析器將簡單地刪除`()`括號記號，并為可能的`Function`類創建一個特殊的`parameters`列表。它會刪除冒號，無用的空格，逗號，任何沒有真正意義的記號，并將其轉換為更易于處理的嵌套結構。最后的結果可能看起來像，上面的示例代碼的偽造樹： ``` * root * Function - name = hello - parameters = x, y - code: * Call - name = print - parameters = * Expression - Add - a = x - b = y * Call - name = hello - parameters = 10, 20 ``` ## 遞歸下降解析 有幾種已建立的方法，可以為這種語法創建解析器，但最簡單的方法稱為遞歸下降解析器（RDP）。我實際上在我《笨辦法學 Python》練習 49 中講解了這個話題。你創建了一個簡單的 RDP 解析器來處理你的小游戲語言，你甚至不了解它。在本練習中，我將對如何編寫 RDP 解析器進行更正式的描述，然后讓你使用我們上面的 Python 小代碼片段來嘗試它。 RDP 使用多個相互遞歸的函數調用，它實現了給定語法的樹形結構。RDP 解析器的代碼看起來像你正在處理的實際語法，只要遵循一些規則，它們就很容易編寫。RDP 解析器的兩個缺點是：它們可能不是非常有效，并且通常需要手動編寫它們，因此它們的錯誤比生成的解析器更多。對于 RDP 解析器可以解析的東西，還有一些理論上的限制，但是由于你手動編寫它們，你通常可以解決很多限制。 為了編寫一個 RDP 解析器，你需要使用三個主要操作，來處理掃描器的記號： > `peek` > 如果下一個記號能夠匹配，返回它，但是不從流中移除。 > `match` > 匹配下一個記號，并且從流中移除。 > `skip` > 由于不需要下個記號，跳過它，將其從流中移除。 你會注意到，這些是我在練習 33 中讓你為掃描器創建的三個操作，這就是為什么。你需要他們來實現一個 RDP 解析器。 你可以使用這三個函數來編寫語法解析函數，從掃描器中獲取記號。這個練習的一個簡短的例子是，解析這個簡單的函數： ```py def function_definition(tokens): skip(tokens) # discard def name = match(tokens, 'NAME') match(tokens, 'LPAREN') params = parameters(tokens) match(tokens, 'RPAREN') match(tokens, 'COLON') return {'type': 'FUNCDEF', 'name': name, 'params': params} ``` 你可以看到我只是接受記號并使用`match`和`skip`處理它們。你還會注意到我有一個`parameters`函數，它是“遞歸下降解析器”的“遞歸”部分。當它需要為函數解析參數時，`function_definition`會調用`parameters`。 ## BNF 語法 嘗試從頭開始編寫一個 RDP 解析器是沒有某種形式的語法規范的，有點棘手。你還記得當我要求你將單個正則表達式轉換成 FSM 嗎？這很難嗎？它需要更多的代碼，不只是正則表達式中的幾個字符。當你為這個練習編寫 RDP 解析器時，你將會做類似的事情，因此它有助于使用一種語言，它是“語法的正則表達式”。 最常見的“語法的正則表達式”被稱為 Backus–Naur Form（BNF），以創作者 John Backus 和 Peter Naur 命名。BNF 描述了所需的記號，以及這些記號如何重復來形成語言的語法。BNF 還使用與正則表達式相同的符號，所以`*`，`+`和`?`有相似的含義。 對于這個練習，我將使用 <https://tools.ietf.org/html/rfc5234> 上面的 IETF 增強 BNF 語法，來規定上面的微型 Python 代碼段的語法。ABNF 運算符大部分與正則表達式相同，只是由于某種奇怪的原因，它們在要重復的東西之前放置重復符號。除此之外，請閱讀規范，并嘗試弄清楚下面的意思： ``` root = *(funccal / funcdef) funcdef = DEF name LPAREN params RPAREN COLON body funccall = name LPAREN params RPAREN params = expression *(COMMA expression) expression = name / plus / integer plus = expression PLUS expression PLUS = "+" LPAREN = "(" RPAREN = ")" COLON = ":" COMMA = "," DEF = "def" ``` 讓我們僅僅查看`funcdef `那一行，并將其與`function_definition` Python 代碼比較，匹配每一個部分： `funcdef =` 我們使用`def function_definition(tokens)`來復制，并且它是我們的語法的這個部分的開始。 `DEF` 它在語法中規定了`DEF = "def"`，并且在 Python 代碼中，我們使用`skip(tokens)`跳過了它。 `name` 我需要它，所以我使用`name = match(tokens, 'NAME')`匹配它。我使用 CAPITALS 的約定，在 BNF 中表示我會跳過的東西。 `LPAREN` 我假設我收到了一個`def`，但是現在我打算確保有一個`(`，所以我要匹配它。但是我使用`match(tokens, 'LPAREN')`來忽略結果。它就像“需要但是忽略”。 `params` 在 BNF 中我將`params`定義為了新的“語法產生式”，或者“語法規則”。意思是在我的 Python 代碼中，我需要一個新的函數。這個函數中，我可以使用`params = parameters(tokens)`來調用那個函數。之后我定義了`parameters`函數來為函數處理逗號分隔的參數。 `RPAREN` 同樣我需要但是去掉了它，使用`match(tokens, 'RPAREN')`。 `COLON` 同樣，我去掉了匹配`match(tokens, 'COLON')`。 `body` 我這里實際上跳過了函數體，因為 Python 的縮進語法對于這個例子太難了。你不需要在練習中處理這個例子，除非你喜歡它。 這基本上是，你如何讀取 ABNF 規范，并將其系統地轉換為代碼。你從根開始，將每個語法產生式實現為一個函數，并讓掃描器處理簡單的記號（我用`CAPITAL`（大寫）字母表示）。 ## 簡單的示例黑魔法解析器 這是我快速 Hack 出來的 RDP 解析器，你可以使用它，作為你的更正式和簡潔的解析器的基礎。 ```py from scanner import * from pprint import pprint def root(tokens): """root = *(funccal / funcdef)""" first = peek(tokens) if first == 'DEF': return function_definition(tokens) elif first == 'NAME': name = match(tokens, 'NAME') second = peek(tokens) if second == 'LPAREN': return function_call(tokens, name) else: assert False, "Not a FUNCDEF or FUNCCALL" def function_definition(tokens): """ funcdef = DEF name LPAREN params RPAREN COLON body I ignore body for this example 'cause that's hard. I mean, so you can learn how to do it. """ skip(tokens) # discard def name = match(tokens, 'NAME') match(tokens, 'LPAREN') params = parameters(tokens) match(tokens, 'RPAREN') match(tokens, 'COLON') return {'type': 'FUNCDEF', 'name': name, 'params': params} def parameters(tokens): """params = expression *(COMMA expression)""" params = [] start = peek(tokens) while start != 'RPAREN': params.append(expression(tokens)) start = peek(tokens) if start != 'RPAREN': assert match(tokens, 'COMMA') return params def function_call(tokens, name): """funccall = name LPAREN params RPAREN""" match(tokens, 'LPAREN') params = parameters(tokens) match(tokens, 'RPAREN') return {'type': 'FUNCCALL', 'name': name, 'params': params} def expression(tokens): """expression = name / plus / integer""" start = peek(tokens) if start == 'NAME': name = match(tokens, 'NAME') if peek(tokens) == 'PLUS': return plus(tokens, name) else: return name elif start == 'INTEGER': number = match(tokens, 'INTEGER') if peek(tokens) == 'PLUS': return plus(tokens, number) else: return number else: assert False, "Syntax error %r" % start def plus(tokens, left): """plus = expression PLUS expression""" match(tokens, 'PLUS') right = expression(tokens) return {'type': 'PLUS', 'left': left, 'right': right} def main(tokens): results = [] while tokens: results.append(root(tokens)) return results parsed = main(scan(code)) pprint(parsed) ``` 你會注意到，我正在使用我寫的`scanner`模塊，擁有我的`match`，`peek`，`skip`和`scan`函數。我使用`from scanner import *`，僅使這個例子更容易理解。你應該使用你的`Scanner`類。 你會注意到，我把這個小解析器的 ABNF 放在每個函數的文檔注釋中。這有助于我編寫每個解析器代碼，稍后可以用于錯誤報告。在嘗試挑戰練習之前，你應該研究此解析器，甚至可能作為“代碼大師副本”。 ## 挑戰練習 你的下一個挑戰是，將你的 `Scanner`類與新編寫的`Parser`類組合在一起，你可以派生并重新實現使我這里的簡單的解析器。你的基礎`Parser`類應該能夠： + 接受一個`Scanner`對象并執行自身。你可以假設任何默認函數是語法的起始。 + 擁有錯誤處理代碼，比我簡單的`assert`用法更好。 你應該實現`PunyPythonPython`，它可以解析這個微型 Python 語言，并執行以下操作： + 不是僅僅產生`dicts`的列表，你應該為每個語法生產式的結果創建類。這些類之后成為列表中的對象。 + 這些類只需要存儲被解析的記號，但是要準備做更多事情。 + 你只需要解析這個微型語言，但你應該嘗試解決“Python 縮進”問題。你可能需要秀阿貴掃描器，使其更智能，才能在行的開頭匹配`INDENT`空白字符，并在其他位置忽略它。你還需要跟蹤如何多少縮進了多少，同時也記錄零縮進，所以你可以“壓縮”代碼塊。 一個泛用的測試套件涉及到，將這個微型 python 的更多樣本交給解析器，但現在只需要得到一個小文件來解析。嘗試在測試中獲得良好的覆蓋率，并盡可能多地發現錯誤。 ## 研究性學習 這個練習相當龐大，所以只需要完成。花點時間，一次做一點點。我強烈建議學習我這里的小型樣本，直到你完全弄清楚，并打印正在處理的關鍵位置的記號。 ## 深入學習 查看 David Beazley 的 [SLY 解析器生成器](http://sly.readthedocs.io/en/latest/)，以便讓你的計算機為你生成你的解析器和掃描器（也稱為分詞器）。隨意嘗試用 SLY 重復此練習來進行比較。