原題 | Left-recursive PEG grammars

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（“Python貓”公眾號作者）

聲明 | 本翻譯是出于交流學習的目的，基于 CC BY-NC-SA 4.0 授權協議。為便于閱讀，內容略有改動。

我曾幾次提及左遞歸是一塊絆腳石，是時候去解決它了。基本的問題在于：使用遞歸下降解析器時，左遞歸會因堆棧溢出而導致程序終止。

【這是我的 PEG 系列的第 5 部分。其它文章參見這個目錄】

假設有如下的語法規則：

          
            expr: expr '+' term | term
          
        

如果我們天真地將它翻譯成遞歸下降解析器的片段，會得到如下內容：

          
            def expr():
    if expr() and expect('+') and term():
        return True
    if term():
        return True
    return False
          
        

也就是 expr() 以調用 expr() 開始，后者也以調用 expr() 開始，以此類推……這只能以堆棧溢出而結束，拋出異常 RecursionError 。

傳統的補救措施是重寫語法。在之前的文章中，我已經這樣做了。事實上，上面的語法也能識別出來，如果我們重寫成這樣：

          
            expr: term '+' expr | term
          
        

但是，如果我們用它生成一個解析樹，那么解析樹的形狀會有所不同，這會導致破壞性的后果，比如當我們在語法中添加一個 '-' 運算符時（因為 a - (b - c) 與 (a - b) - c 不一樣）。

這通常可以使用更強大的 PEG 特性來解決，例如分組和迭代，我們可以將上述規則重寫為：

          
            expr: term ('+' term)*
          
        

實際上，這正是 Python 當前語法在 pgen 解析器生成器上的寫法（pgen 與左遞歸規則具有同樣的問題）。

但是這仍然存在一些問題：因為像 '+' 和 '-' 這樣的運算符，基本上是二進制的（在 Python 中），當我們解析像 a + b + c 這樣的東西時，我們必須遍歷解析的結果（基本上是列表['a'，'+'，'b'，'+'，'c'] ），以構造一個左遞歸的解析樹（類似于 [['a'，'+'，'b'] ，'+'，'c'] ）。

原始的左遞歸語法已經表訴了所需的關聯性，因此，如果我們可以直接以該形式生成解析器，那將會很好。我們可以！一位粉絲向我指出了一個很好的技巧，還附帶了一個數學證明，很容易實現。我會試著在這里解釋一下。

讓我們考慮輸入 foo + bar + baz 作為示例。我們想要解析出的解析樹對應于 (foo + bar)+ baz 。這需要對 expr() 進行三次左遞歸調用：一次對應于頂級的“+” 運算符（即第二個）; 一次對應于內部的“+”運算符（即第一個）; 還有一次是選擇第二個備選項（即 term ）。

由于我不善于使用計算機繪制實際的圖表，因此我將在此使用 ASCII 技巧作演示：

          
            expr------------+------+
  |              \      \
expr--+------+   '+'   term
  |    \      \          |
expr   '+'   term        |
  |            |         |
term           |         |
  |            |         |
'foo'        'bar'     'baz'
          
        

我們的想法是希望在 expr() 函數中有一個“oracle”（譯注：預言、神諭，后面就不譯了），它要么告訴我們采用第一個備選項（即遞歸調用 expr()），要么是第二個（即調用 term()）。在第一次調用 expr() 時，“oracle”應該返回 true; 在第二次（遞歸）調用時，它也應該返回 true，但在第三次調用時，它應該返回 false，以便我們可以調用 term()。

在代碼中，應該是這樣：

          
            def expr():
    if oracle() and expr() and expect('+') and term():
        return True
    if term():
        return True
    return False
          
        

我們該怎么寫這樣的“oracle”呢？試試看吧......我們可以嘗試記錄在調用堆棧上的 expr() 的（左遞歸）調用次數，并將其與下面表達式中“+” 運算符的數量進行比較。如果調用堆棧的深度大于運算符的數量，則應該返回 false。

我幾乎想用 sys._getframe() 來實現它，但有更好的方法：讓我們反轉調用的堆棧！

這里的想法是我們從 oracle 返回 false 處調用，并保存結果。這就有了 expr()->term()->'foo' 。（它應該返回初始的 term 的解析樹，即 'foo' 。上面的代碼僅返回 True，但在本系列第二篇文章中，我已經演示了如何返回一個解析樹。）很容易編寫一個 oracle 來實現，它應該在首次調用時就返回 false——不需要檢查堆棧或向前回看。

然后我們再次調用 expr() ，這時 oracle 會返回 true，但是我們不對 expr() 進行左遞歸調用，而是用前一次調用時保存的結果來替換。瞧吶，預期的 '+' 運算符及隨后的 term 也出現了，所以我們將會得到 foo + bar 。

我們重復這個過程，然后事情看起來又很清晰了：這次我們會得到完整表達式的解析樹，并且它是正確的左遞歸（（foo + bar）+ baz ）。

然后我們再次重復該過程，這一次，oracle 返回 true，并且前一次調用時保存的結果可用，沒有下一步的'+' 運算符，并且第一個備選項失效。所以我們嘗試第二個備選項，它會成功，正好找到了初始的 term（'foo'）。與之前的調用相比，這是一個糟糕的結果，所以在這里我們停止并留下最長的解析（即（foo + bar）+ baz ）。

為了將其轉換為實際的工作代碼，我首先要稍微重寫代碼，以將 oracle() 的調用與左遞歸的 expr() 調用相結合。我們稱之為 oracle_expr() 。代碼：

          
            def expr():
    if oracle_expr() and expect('+') and term():
        return True
    if term():
        return True
    return False
          
        

接著，我們將編寫一個實現上述邏輯的裝飾器。它使用了一個全局變量（不用擔心，我稍后會改掉它）。 oracle_expr() 函數將讀取該全局變量，而裝飾器操縱著它：

          
            saved_result = None
def oracle_expr():
    if saved_result is None:
        return False
    return saved_result
def expr_wrapper():
    global saved_result
    saved_result = None
    parsed_length = 0
    while True:
        new_result = expr()
        if not new_result:
            break
        new_parsed_length = 
            
              
        if new_parsed_length <= parsed_length:
            break
        saved_result = new_result
        parsed_length = new_parsed_length
    return saved_result
            
          
        

這過程當然是可悲的，但它展示了代碼的要點，所以讓我們嘗試一下，將它發展成我們可以引以為傲的東西。

決定性的洞察（這是我自己的，雖然我可能不是第一個想到的）是我們可以使用記憶緩存而不是全局變量，將一次調用的結果保存到下一次，然后我們不需要額外的 oracle_expr() 函數——我們可以生成對 expr() 的標準調用，無論它是否處于左遞歸的位置。

為了做到這點，我們需要一個單獨的 @memoize_left_rec 裝飾器，它只用于左遞歸規則。它通過將保存的值從記憶緩存中取出，充當了 oracle_expr() 函數的角色，并且它包含著一個循環調用，只要每個新結果所覆蓋的部分比前一個長，就反復地調用 expr()。

當然，因為記憶緩存分別按輸入位置和每個解析方法來處理緩存，所以它不受回溯或多個遞歸規則的影響（例如，在玩具語法中，我一直使用 expr 和 term 都是左遞歸的）。

我在第 3 篇文章中創建的基礎結構的另一個不錯的屬性是它更容易檢查新結果是否長于舊結果：mark() 方法將索引返回到輸入的標記符數組中，因此我們可以使用它，而非上面的parsed_length 。

我沒有證明為什么這個算法總是有效的，不管這個語法有多瘋狂。那是因為我實際上沒有讀過那個證明。我看到它適用于玩具語法中的 expr 等簡單情況，也適用于更復雜的情況（例如，涉及一個備選項里可選條目背后藏著的左遞歸，或涉及多個規則之間的相互遞歸），但在 Python 的語法中，我能想到的最復雜的情況仍然相當溫和，所以我可以信任于定理和證明它的人。

所以讓我們堅持干，并展示一些真實的代碼。

首先，解析器生成器必須檢測哪些規則是左遞歸的。這是圖論中一個已解決的問題。我不會在這里展示算法，事實上我將進一步簡化工作，并假設語法中唯一的左遞歸規則就是直接左遞歸的，就像我們的玩具語法中的 expr 一樣。然后檢查左遞歸只需要查找以當前規則名稱開頭的備選項。我們可以這樣寫：

          
            def is_left_recursive(rule):
    for alt in rule.alts:
        if alt[0] == rule.name:
            return True
    return False
          
        

現在我們修改解析器生成器，以便對于左遞歸規則，它能生成一個不同的裝飾器。回想一下，在第 3 篇文章中，我們使用 @memoize 修飾了所有的解析方法。我們現在對生成器進行一個小小的修改，對于左遞歸規則，我們替換成 @memoize_left_rec ，然后我們在memoize_left_rec 裝飾器中變魔術。生成器的其余部分和支持代碼無需更改！（然而我不得不在可視化代碼中搗鼓一下。）

作為參考，這里是原始的 @memoize 裝飾器，從第 3 篇中復制而來。請注意，self 是一個Parser 實例，它具有 memo 屬性（用空字典初始化）、mark() 和 reset() 方法，用于獲取和設置 tokenizer 的當前位置：

          
            def memoize(func):
    def memoize_wrapper(self, *args):
        pos = self.mark()
        memo = self.memos.get(pos)
        if memo is None:
            memo = self.memos[pos] = {}
        
        key = (func, args)
        if key in memo:
            res, endpos = memo[key]
            self.reset(endpos)
        else:
            res = func(self, *args)
            endpos = self.mark()
            memo[key] = res, endpos
        return res
    return memoize_wrapper
          
        

@memoize 裝飾器在每個輸入位置記住了前一調用——在輸入標記符的（惰性）數組的每個位置，有一個單獨的 memo 字典。memoize_wrapper 函數的前四行與獲取正確的 memo 字典有關。

這是 @memoize_left_rec 。只有 else 分支與上面的 @memoize 不同：

          
                def memoize_left_rec(func):
    def memoize_left_rec_wrapper(self, *args):
        pos = self.mark()
        memo = self.memos.get(pos)
        if memo is None:
            memo = self.memos[pos] = {}
        key = (func, args)
        if key in memo:
            res, endpos = memo[key]
            self.reset(endpos)
        else:
            # Prime the cache with a failure.
            memo[key] = lastres, lastpos = None, pos
            # Loop until no longer parse is obtained.
            while True:
                self.reset(pos)
                res = func(self, *args)
                endpos = self.mark()
                if endpos <= lastpos:
                    break
                memo[key] = lastres, lastpos = res, endpos
            res = lastres
            self.reset(lastpos)
        return res
    return memoize_left_rec_wrapper
          
        

它很可能有助于顯示生成的 expr() 方法，因此我們可以跟蹤裝飾器和裝飾方法之間的流程：

          
                @memoize_left_rec 
    def expr(self):
        pos = self.mark()
        if ((expr := self.expr()) and
            self.expect('+') and
            (term := self.term())):
            return Node('expr', [expr, term])
        self.reset(pos)
        if term := self.term():
            return Node('term', [term])
        self.reset(pos)
        return None
          
        

讓我們試著解析 foo + bar + baz 。

每當你調用被裝飾的 expr() 函數時，裝飾器就會“攔截”調用，它會在當前位置查找前一個調用。在第一個調用處，它會進入 else 分支，在那里它重復地調用未裝飾的函數。當未裝飾的函數調用 expr() 時，這當然指向了被裝飾的版本，因此這個遞歸調用會再次被截獲。遞歸在這里停止，因為現在 memo 緩存有了命中。

接下來呢？初始的緩存值來自這行：

          
                        # Prime the cache with a failure.
            memo[key] = lastres, lastpos = None, pos
          
        

這使得被裝飾的 expr() 返回 None，在那 expr() 里的第一個 if 會失敗（在 expr := self.expr() ）。所以我們繼續到第二個 if，它成功識別了一個 term（在我們的例子中是 ‘foo’），expr 返回一個 Node 實例。它返回到了哪里？到了裝飾器里的 while 循環。這新的結果會更新 memo 緩存（那個 node 實例），然后開始下一個迭代。

再次調用未裝飾的 expr()，這次截獲的遞歸調用返回新緩存的 Node 實例（一個 term）。這是成功的，調用繼續到 expect('+')。這再次成功，然后我們現在處于第一個“+” 操作符。在此之后，我們要查找一個 term，也成功了（找到 'bar'）。

所以對于空的 expr()，目前已識別出 foo + bar ，回到 while 循環，還會經歷相同的過程：用新的（更長的）結果來更新 memo 緩存，并開啟下一輪迭代。

游戲再次上演。被截獲的遞歸 expr() 調用再次從緩存中檢索新的結果（這次是 foo + bar），我們期望并找到另一個 ‘+’（第二個）和另一個 term（‘baz’）。我們構造一個 Node 表示 (foo + bar) + baz ，并返回給 while 循環，后者將它填充進 memo 緩存，并再次迭代。

但下一次事情會有所不同。有了新的結果，我們查找另一個 '+' ，但沒有找到！所以這個expr() 調用會回到它的第二個備選項，并返回一個可憐的 term。當走到 while 循環時，它失望地發現這個結果比最后一個短，就中斷了，將更長的結果（（foo + bar）+ baz ）返回給原始調用，就是初始化了外部 expr() 調用的地方（例如，一個 statement() 調用——此處未展示）。

到此，今天的故事結束了：我們已經成功地在 PEG（-ish）解析器中馴服了左遞歸。至于下周，我打算論述在語法中添加“動作”（actions），這樣我們就可以為一個給定的備選項的解析方法，自定義它返回的結果（而不是總要返回一個 Node 實例）。

如果你想使用代碼，請參閱GitHub倉庫。（我還為左遞歸添加了可視化代碼，但我并不特別滿意，所以不打算在這里給出鏈接。）

本文內容與示例代碼的授權協議：CC BY-NC-SA 4.0

作者簡介： Guido van Rossum，Python 的創造者，一直是“終身仁慈獨裁者”，直到 2018 年 7 月 12 日退位。目前，他是新的最高決策層的五位成員之一，依然活躍在社區中。本文出自他在 Medium 開博客所寫的解析器系列，該系列仍在連載中，每周日更新。

譯者簡介： 豌豆花下貓，生于廣東畢業于武大，現為蘇漂程序員，有一些極客思維，也有一些人文情懷，有一些溫度，還有一些態度。公眾號：「Python貓」（python_cat）。

公眾號【 Python貓 】， 本號連載優質的系列文章，有喵星哲學貓系列、Python進階系列、好書推薦系列、技術寫作、優質英文推薦與翻譯等等，歡迎關注哦。