1. 回顧

在上一篇文章中，介紹了一個基於解析器組合子實現的詞法/語法解析器，在處理call的時候，由於其右側產生式的第一項便是expr，如果不做處理，普通的遞迴下降解析器將會陷入死迴圈的情況，因此對其進行了右遞迴的轉換，保證解析器可以正常執行。

2. 左遞迴語法的處理

由於右遞迴轉換後的描述相較左遞迴的描述更加複雜且不夠自然，因此本章通過引入GLL演算法的思想，來為遞迴下降的解析器支援左遞迴語法的處理。

2.1 GLL演算法及其思想

GLL演算法通過引入一個graph-structured stack，提供了可以轉移控制流的能力，使其在解析的過程中，可以暫停和恢復，讓解析器在多個點位跳轉切換，從而避免了左遞迴導致的死迴圈，並在生成解析結果後，將其作為左遞迴產生式的結果返回。

2.2 再探continuation

根據2.1節中對GLL演算法的描述，可以看到其引入的graph-structured stack提供了一個和first-class continuation非常相似的操作。上一篇文章中，對於continuation的描述，只是簡短的將其定義為“接下來要做的事情”。本節中，會對continuation進行更加細緻的定義，即“在當前上下文環境中，接下來要做的事情”。對解析器進行continuation化，不僅僅是提供了一種便於組合和異常處理的方式，更關鍵的是，在continuation化之後，解析器的控制流將會被結構化的顯式呈現，使得程式自身可以隨意切換執行點位，甚至可以多次回溯重試。下面，通過一個栗子來演示一下continuation的執行和作用。

2.3 使用continuation在兩個函式間切換

``scheme (define num-gen (lambda (yield) ; 定義了一個無限遞迴的函式, 每次增加1後, 跳出當前控制流 (define infinity-add (lambda (n yield) ; let/cc將當前表示式的continuation繫結到k上 ; 外部在獲取到當前的continuation後, 將下一次需要跳轉的外部continuation傳入 (let ([new-yield (let/cc k (yield(,n ,k)))]) (infinity-add (add1 n) new-yield)))) (infinity-add 1 yield)))

(define num-access (lambda (count) (define num-access-to (lambda (i num-gen) (if (< i count) ; 將當前表示式的continuation傳給num-gen, 使其在數字+1後可以返回該處, ; 同時將獲取下一個數字的continuation一併返回 (match (let/cc k (num-gen k)) [`(,n ,next-num) (printf "~a " n) (num-access-to (add1 i) next-num)]) (newline)))) (num-access-to 0 num-gen)))

; 獲取從1開始的9個數字 (num-access 9) ; 獲取從1開始的5個數字 (num-access 5)

; 執行結果 1 2 3 4 5 6 7 8 9 1 2 3 4 5 `` 上述的栗子中，通過定義num-gen來描述了一個死迴圈的函式，如果沒有continuation將控制流讓出，一旦呼叫該函式，程式則必然會卡死。之後又定義了num-access函式，其通過外部指定的count來有限的獲取num-gen產生的結果。在num-access呼叫num-gen時，其將當前表示式的continuation傳給了num-gen，使得num-gen可以將其內部的數字傳遞到num-access處，同時，也將num-gen接下來的continuation一併傳給了num-access，使其可以重新返回num-gen中，並將新的num-access的conitnuation帶入，使得num-gen可以再次跳轉到num-access處。同時，continuation會包含返回點的上下文環境，新呼叫的(num-access 5)並不會和上一次的(num-access 9)`產生混淆，就如同兩個平行世界一般，只可在自己的世界中穿梭。

2.4 continuation與左遞迴語法

上一節通過一個具體的栗子講述了continuation的運作流程，那麼continuation又如何與左遞迴語法結合呢？答案便是同num-gen一樣，在重複呼叫的時候跳出控制流，在當前位置掛起，使解析器可以進行接下來的匹配，等匹配完成時，再將其作為結果喚醒掛起點，從而使得左遞迴語法可以如期匹配執行。

3. 解析流程的具體分析

在討論了continuation與左遞迴語法之後，本節通過一個具體的簡短示例，來詳細分析continuation如何掛起以及恢復，來實現左遞迴語法的處理。

3.1 示例語法定義

$$ Expr = Expr(Expr) | Num | Var $$ 本節中，定義了一個簡單的語法，表示式可以由識別符號、數字和函式呼叫構成，其中函式呼叫以左遞迴的方式描述。同時，給出一個具體的文字定義："foo(10)(20)(30)"。

3.2 匹配流程的執行

Expr <- (_, "foo(10)(20)(30)") k-1 其中, <-左側的Expr表示本次呼叫的產生式對應的解析器, 右側通過一個二元向量描述當前的匹配結果及剩餘符號流，其最右側的k-1表示以該二元向量作為引數呼叫Expr時解析成功的continuation，為便於分析討論，本慄暫不關心其他異常問題。解析器內部的呼叫以縮排的方式表示。

Expr <- (_, "foo(10)(20)(30)") k-1 Expr(Expr) <- (_, "foo(10)(20)(30)") Expr <- (_, "foo(10)(20)(30)") k-2 通過兩次呼叫，解析器便已經觸及到左遞迴的迴圈，在第3行中，以相同的二元向量呼叫Expr，如果不做處理，解析器則將陷入死迴圈，因此，解析器將需要在此處進行掛起，並認為本次匹配失敗。

Expr <- (_, "foo(10)(20)(30)") k-1 Expr(Expr) <- (_, "foo(10)(20)(30)") Expr <- (_, "foo(10)(20)(30)") k-2 -> failure -> failure Num <- (_, "foo(10)(20)(30)") -> failure Var <- (_, "foo(10)(20)(30)") -> (foo, "(10)(20)(30)") -> (foo, "(10)(20)(30)") 由於遞迴呼叫Expr失敗，則其呼叫者Expr(Expr)也匹配失敗，因此Expr一路向下，分別使用Num和Var進行匹配，最終，Var成功匹配到foo，則最外層的Expr的匹配結果為(foo, "(10)(20)(30)")。在獲取到結果後，此時便可以按順序將其廣播給Expr的continuation，來恢復之前掛起的執行點。

Expr <- (_, "foo(10)(20)(30)") k-1 -> (foo, "(10)(20)(30)") 首先將(foo, "(10)(20)(30)")傳給一開始k-1，即最開始的呼叫，但顯然該結果並不滿足預期，因此需要繼續呼叫之後的k-2。

Expr <- (_, "foo(10)(20)(30)") k-1 Expr(Expr) <- (_, "foo(10)(20)(30)") Expr <- (_, "foo(10)(20)(30)") k-2 -> (foo, "(10)(20)(30)") ( <- (foo, "(10)(20)(30)") -> (foo(, "10)(20)(30)") Expr <- (foo(, "10)(20)(30)") k-3 Expr(Expr) <- (foo(, "10)(20)(30)") Expr <- (foo(, "10)(20)(30)") k-4 -> failure -> failure Num <- (foo(, "10)(20)(30)") -> (foo(10, ")(20)(30)") -> (foo(10, ")(20)(30)") 將(foo, "(10)(20)(30)")傳遞給k-2後，解析器的控制流切換至第二次使用(_, "foo(10)(20)(30)")呼叫Expr的地方，即本次的呼叫返回結果為(foo, "(10)(20)(30)")。之後按順序匹配剩餘的(Expr)部分，解析器會再一次陷入遞迴掛起的狀態，其處理方式與最外側的Expr一致，掛起並執行後續的匹配。在經過Num的匹配後，Expr得到其匹配結果(foo(10, ")(20)(30)")，同樣，開始將結果廣播給本次Expr的continuation，即k-3。

Expr <- (_, "foo(10)(20)(30)") k-1 Expr(Expr) <- (_, "foo(10)(20)(30)") Expr <- (_, "foo(10)(20)(30)") k-2 -> (foo(10), "(20)(30)") ( <- (foo(10), "(20)(30)") -> (foo(10)(, "20)(30)") Expr <- (foo(10)(, "20)(30)") k-5 -> (foo(10)(20, ")(30)") ) <- (foo(10)(20, ")(30)") -> (foo(10)(20), "(30)") -> (foo(10)(20), "(30)") -> (foo(10)(20), "(30)") Expr <- (_, "foo(10)(20)(30)") k-1 Expr(Expr) <- (_, "foo(10)(20)(30)") Expr <- (_, "foo(10)(20)(30)") k-2 -> (foo(10)(20), "(30)") ( <- (foo(10)(20), "(30)") -> (foo(10)(20)(, "30)") Expr <- (foo(10)(20)(, "30)") k-7 Expr(Expr) <- (foo(10)(20)(, "30)") Expr <- (foo(10)(20)(, "30)") k-8 -> failure -> failure Num <- (foo(10)(20)(, "30)") -> (foo(10)(20)(30, ")") -> (foo(10)(20)(30, ")") Expr <- (_, "foo(10)(20)(30)") k-1 Expr(Expr) <- (_, "foo(10)(20)(30)") Expr <- (_, "foo(10)(20)(30)") k-2 -> (foo(10)(20), "(30)") ( <- (foo(10)(20), "(30)") -> (foo(10)(20)(, "30)") Expr <- (foo(10)(20)(, "30)") k-7 -> (foo(10)(20)(30, ")") ) <- (foo(10)(20)(30, ")") -> (foo(10)(20)(30), "") -> (foo(10)(20)(30), "") -> (foo(10)(20)(30), "") 重複數次後，最外層的Expr解析到了(foo(10)(20)(30), "")，將其傳遞給k-1後，符合預期，解析至此完成。

4. 總結

根據上節的示例的具體分析，可以看到continuation是如何在左遞迴語法的解析中工作的，其具有的控制流掛起與恢復能力，可以打破因遞迴導致的死迴圈，下一篇中，將會對之前的解析子組合子進行改造，使其能夠真正的處理左遞迴語法的解析與匹配。

hi, 我是快手電商的Kaso.Lu

快手電商無線技術團隊正在招賢納士🎉🎉🎉! 我們是公司的核心業務線, 這裡雲集了各路高手, 也充滿了機會與挑戰. 伴隨著業務的高速發展, 團隊也在快速擴張. 歡迎各位高手加入我們, 一起創造世界級的電商產品~

熱招崗位: Android/iOS 高階開發, Android/iOS 專家, Java 架構師, 產品經理(電商背景), 測試開發... 大量 HC 等你來呦~

內部推薦請發簡歷至 >>>我們的郵箱: [email protected] <<<, 備註我的花名成功率更高哦~ 😘

基於解析器組合子的語法解析器(中)