原題 | Left-recursive PEG grammars

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（“Python貓”公眾號(hào)作者）

聲明 | 本翻譯是出于交流學(xué)習(xí)的目的，基于 CC BY-NC-SA 4.0 授權(quán)協(xié)議。為便于閱讀，內(nèi)容略有改動(dòng)。

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

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

假設(shè)有如下的語法規(guī)則：

          
            expr: expr '+' term | term
          
        

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

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

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

傳統(tǒng)的補(bǔ)救措施是重寫語法。在之前的文章中，我已經(jīng)這樣做了。事實(shí)上，上面的語法也能識(shí)別出來，如果我們重寫成這樣：

          
            expr: term '+' expr | term
          
        

但是，如果我們用它生成一個(gè)解析樹，那么解析樹的形狀會(huì)有所不同，這會(huì)導(dǎo)致破壞性的后果，比如當(dāng)我們在語法中添加一個(gè) '-' 運(yùn)算符時(shí)（因?yàn)? a - (b - c) 與 (a - b) - c 不一樣）。

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

          
            expr: term ('+' term)*
          
        

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

但是這仍然存在一些問題：因?yàn)橄? '+' 和 '-' 這樣的運(yùn)算符，基本上是二進(jìn)制的（在 Python 中），當(dāng)我們解析像 a + b + c 這樣的東西時(shí)，我們必須遍歷解析的結(jié)果（基本上是列表['a'，'+'，'b'，'+'，'c'] ），以構(gòu)造一個(gè)左遞歸的解析樹（類似于 [['a'，'+'，'b'] ，'+'，'c'] ）。

原始的左遞歸語法已經(jīng)表訴了所需的關(guān)聯(lián)性，因此，如果我們可以直接以該形式生成解析器，那將會(huì)很好。我們可以！一位粉絲向我指出了一個(gè)很好的技巧，還附帶了一個(gè)數(shù)學(xué)證明，很容易實(shí)現(xiàn)。我會(huì)試著在這里解釋一下。

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

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

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

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

在代碼中，應(yīng)該是這樣：

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

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

我?guī)缀跸胗? sys._getframe() 來實(shí)現(xiàn)它，但有更好的方法：讓我們反轉(zhuǎn)調(diào)用的堆棧！

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

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

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

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

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

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

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

          
            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
            
          
        

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

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

為了做到這點(diǎn)，我們需要一個(gè)單獨(dú)的 @memoize_left_rec 裝飾器，它只用于左遞歸規(guī)則。它通過將保存的值從記憶緩存中取出，充當(dāng)了 oracle_expr() 函數(shù)的角色，并且它包含著一個(gè)循環(huán)調(diào)用，只要每個(gè)新結(jié)果所覆蓋的部分比前一個(gè)長，就反復(fù)地調(diào)用 expr()。

當(dāng)然，因?yàn)橛洃浘彺娣謩e按輸入位置和每個(gè)解析方法來處理緩存，所以它不受回溯或多個(gè)遞歸規(guī)則的影響（例如，在玩具語法中，我一直使用 expr 和 term 都是左遞歸的）。

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

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

所以讓我們堅(jiān)持干，并展示一些真實(shí)的代碼。

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

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

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

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

          
            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 裝飾器在每個(gè)輸入位置記住了前一調(diào)用——在輸入標(biāo)記符的（惰性）數(shù)組的每個(gè)位置，有一個(gè)單獨(dú)的 memo 字典。memoize_wrapper 函數(shù)的前四行與獲取正確的 memo 字典有關(guān)。

這是 @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 。

每當(dāng)你調(diào)用被裝飾的 expr() 函數(shù)時(shí)，裝飾器就會(huì)“攔截”調(diào)用，它會(huì)在當(dāng)前位置查找前一個(gè)調(diào)用。在第一個(gè)調(diào)用處，它會(huì)進(jìn)入 else 分支，在那里它重復(fù)地調(diào)用未裝飾的函數(shù)。當(dāng)未裝飾的函數(shù)調(diào)用 expr() 時(shí)，這當(dāng)然指向了被裝飾的版本，因此這個(gè)遞歸調(diào)用會(huì)再次被截獲。遞歸在這里停止，因?yàn)楝F(xiàn)在 memo 緩存有了命中。

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

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

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

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

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

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

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

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

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

本文內(nèi)容與示例代碼的授權(quán)協(xié)議：CC BY-NC-SA 4.0

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

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

公眾號(hào)【 Python貓 】， 本號(hào)連載優(yōu)質(zhì)的系列文章，有喵星哲學(xué)貓系列、Python進(jìn)階系列、好書推薦系列、技術(shù)寫作、優(yōu)質(zhì)英文推薦與翻譯等等，歡迎關(guān)注哦。