Python 3.9 中的 PEG 語法分析演算法
0 題外話
若文章有后續更新，可以在我的博客上看到，
pre 視頻在這里，
1 PEG: Parsing Expression Grammar
1.1 定義
1.1.1 語法
形式上，一個決議表達文法由以下部分組成：
- 一個有限的非終結符的集合 \(N\)
- 一個有限的終結符的集合 \(\Sigma\)，和 \(N\) 沒有交集
- 一個有限的決議規則的集合 \(P\)
- 一個被稱作開始運算式的決議運算式 \(e_s\)
1.1.2 語意
PEG 與 CFG 最關鍵的不同是，PEG 的選擇運算子是有序的，如果第一個選項匹配成功，則忽略第二個（以及之后的）選項，因此 PEG 的有序選擇是不可交換的，
1.2 解釋
決議表達文法里每一個非終結符本質上表示遞回下降決議器里面的一個決議函式，其對應的決議運算式展示了這個函式包含的代碼內容，
從原理上來說，每一個決議函式接受一個輸入字串作為引數，回傳其中一個結果：
- 成功，函式可能向前移動或者消耗一個或多個輸入字串的字符
- 失敗，不消耗字符
序列運算子 \(e_1e_2\) 首先呼叫 \(e_1\)，如果 \(e_1\) 成功，接著對 \(e_1\) 消耗盛夏得輸入字串呼叫 \(e_2\)，最后回傳結果，如果 \(e_1\) 或者 \(e_2\) 失敗，那么序列運算式 \(e_1e_2\) 失敗，
選擇運算子 \(e_1/e_2\) 首先呼叫 \(e_1\)，如果 \(e_1\) 成功，立刻回傳結果，否則如果 \(e_1\) 失敗，選擇運算子回溯到輸入字串匹配 \(e_1\) 的原始位置，呼叫 \(e_2\)，最后回傳 \(e_2\) 結果，
與背景關系無關文法和正則運算式不同的是，在 PEG 里這些運算子總是執行貪婪的行為，那就是消耗盡可能多的輸入，而且絕對不回溯，正則運算式一開始執行貪婪匹配，但是如果整個正則運算式失敗后，會回退并嘗試短一些的匹配，
1.3 決議器
1.3.1 實作
所有的決議表達文法都能夠被轉化為遞回下降決議器，由于 PEG 提供了理論上不受限制的向前檢查能力，所以最終得到的決議器是可以避免最壞情況下指數級時間復雜度的，通過保存增量決議步驟的結果和確保每一個決議函式在同一個輸入位置只被呼叫一次，就可以把任意決議表達文法轉化成一個 Packrat Parser，可以實作線性時間復雜度決議，代價是占用大量的空間，
1.3.2 細談 Packrat Parser
Packrat Parser 是一種結構上類似遞回下降決議器的語法決議器，區別是決議程序中，它記下所有互相遞回呼叫的函式的中間結果，因為保存了這些資訊，Packrat Parser 擁有以線性時間復雜度決議多數背景關系無關文法和所有決議表達文法的能力，類似的東西讓我想起蔣炎巖老師在 ICS 實驗課上講到過的漢諾塔問題，當時他展示了如何不用遞回解決漢諾塔，用的就是直接對堆疊的操作，當然可能真實原理差了很多，但是同樣是處理遞回問題的一些小小的震撼，因此在這提一嘴，
2 PEG 與 LL (1)
2.1 預測 vs. 回溯
我們知道，Cpython 3.8 以前采用的都是一個叫 pgen 的分析器，它基于的是 LL (1) 分析演算法，而 LL (1) 分析器是一種預測型分析器，即每次可以"預見"往后數 1 個的 token，來確定使用哪條規則展開，這個程序是在實際遞回呼叫之前的，因此可以保證決議函式不會被重復呼叫，并且任意輸入都能在線性時間內完成，那么既然有這么大的時間優勢，LL (1) 演算法必然也會存在一定的局限性，那就是它對文法的要求很高，即很多背景關系無關文法是沒有辦法用 LL (1) 等預測型演算法決議的，比如有不能含有左遞回、必須"left-factoring"等限制條件，
2.2 pgen 的問題
這里列舉了一些 Rossum 要更改 parser 的原因，其中可能并非完全與 LL (1) 自身的性質相關，只是想對 CPython 性能的進一步提升有所幫助，
2.2.1 復雜的 AST 決議
當下的決議器（pgen）中，AST 生成程序和生成樹的特定形狀有著巨大的耦合性，這使得生成 AST 的代碼特別復雜，因為很多的行為和選擇是隱式的，例如，AST 生成代碼根據給定的決議節點中存在的子節點的數量，來知道產生規則的哪些選擇，這使得代碼難以遵循，因為這個屬性與語法檔案沒有直接關系，而是受到實作細節的影響，因此，相當數量的 AST 生成代碼需要處理檢查和推理它所收到的決議樹的特定形狀，
2.2.2 中間生成樹
這個問題在于創建一個決議樹或具體語法樹的中間程序，然后將其轉換為抽象語法樹，雖然 CST 的構建在決議器和編譯器管道中非常常見，但在 CPython 中，這個中間的 CST 并沒有被其他東西使用（它只是被決議器模塊間接地暴露出來，而且 CST 生產中的一小部分代碼在模塊中被重復使用，這令人驚訝），更糟糕的是：整個樹被保存在記憶體中，保留了許多由具有單個子節點的鏈組成的分支，這已被證明會消耗相當多的記憶體，不得不在語法和 AST 之間產生一個中間結果，這件事情是我們不希望看到的，并且它還使得 AST 生成步驟更加復雜，無疑給維護增加了相當大的負擔，
3 PEG parser 給 Python 帶來了什么
3.1 支持左遞回
我們知道，PEG 文法本身是不支持左遞回的，但是當使用的是 Packrat Parser 的時候，就能通過一些改進做到這一點，那么這是如何做到的呢？這篇論文里給出了詳細證明，我在這里稍作解釋，下面展示的這個方法展示了如何做到中間結果的存盤，即將 (R, P) 這對 map 存入 memo table，只要 memo table 中存在這個記錄，就直接回傳結果，一定不會再進行語法分析，從而保證了時間復雜度是線性的，
首先需要搞清楚的是本身不能支持左遞回的原因，假設 Apply-Rule(expr, 0) 是對 expr 這條輸入字串的分析，其中 0 是當前處理字符的位置，考慮將“1-2-3”輸入下面這個規則：
expr : expr '-' num # 1
| num # 2
這里比較災難的一點是，當執行 Apply-Rule(expr, 0) 時，先會去查找 Memo(expr, 0)，即用來保存中間結果的 memo table，當然此時表還是空的，因此結果會是 null，這時接著使用 1 進行匹配，進入了一個無限遞回的程序，因為只有當匹配 1 的結果是失敗時才會進行 2 的匹配，這是由 peg 分析器的特性所決定的，
要能夠支持左遞回，一個簡單點的辦法是在進入 rule 之前先預存一個 fail 的結果，如上圖所示，當首次執行 Apply-Rule(expr, 0) 時，向 memo table 中加入 FAIL，接著進入 Eval(R.body)，此時由于先前存入的 FAIL，使得能夠知道規則 1 匹配不成功，于是進入規則 2，故能消耗掉“1”，剩下“-2-3”，
考慮一下剛剛對 expr 在位置 0 進行的操作：
- parser 的當前位置更新到了 1
- parser 的 memo table 中將 (expr, 0) 更新為 (expr->num->1, 1)
上述行為我們稱為seed parse，實際上當我們有了這個 seed，parser 就能接著往下進行，這個程序就變為了迭代，論文中把這個迭代程序稱為growing the seed，十分生動形象，而剩下需要做的就是分辨出什么時候是左遞回，來讓 memo 記錄下來即可，文章中抽象了一個Grow-LR方法，只要遇到的是遞回，就呼叫這個方法得到最終結果，
上述這些是直接遞回問題，非直接的遞回就不在這里贅述了，感興趣可以閱讀一下原文，
回到 python 上，python 使用的 peg parser 不僅能夠實作簡單的左遞回規則，還有如下非直接左遞回：
rule1: rule2 | 'a'
rule2: rule3 | 'b'
rule3: rule1 | 'c'
以及“隱藏左遞回”：
rule: 'optional'? rule '@' some_other_rule
3.2 Grammar Actions
為了避免掩蓋語法和 AST 生成之間的關系的中間步驟，提議的 PEG 決議器允許通過語法動作直接為規則生成 AST 節點，語法動作是特定于語言的運算式，當語法規則被成功決議時就會被評估，這些運算式可以用 Python 或 C 語言撰寫，這取決于決議器生成器的預期輸出，這意味著如果想用 Python 和 C 語言生成一個決議器，應該寫兩個語法檔案，每個檔案都有一組不同的動作，除了上述動作外，兩個檔案中的其他內容保持一致，作為一個帶有 Python 動作的語法的例子，決議器生成器中決議語法檔案的部分是從帶有 Python 動作的元語法檔案中引匯出來的，這些動作在決議后生成語法樹，
在為 Python 提出的新的 PEG 語法的具體情況下，有了動作就可以直接描述 AST 是如何在語法本身中組成的，使其更加清晰和可維護，這個 AST 的生成程序是通過使用一些輔助函式來支持的，這些函式將常見的 AST 物件操作和其他一些與語法沒有直接關系的必要操作分解出來，
4 Reference
Construction of LL(1) Parsing Table - GeeksforGeeks
Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (mit.edu)
thesis.pdf (mit.edu)
pepm08.pdf (ucla.edu)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/542678.html
標籤：Python