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

語言: CN / TW / HK

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一路向下,分別使用NumVar進行匹配,最終,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-3 -> (foo(10, ")(20)(30)") ) <- (foo(10, ")(20)(30)") -> (foo(10), "(20)(30)") -> (foo(10), "(20)(30)") -> (foo(10), "(20)(30)") 解析器從k-3恢復後,經過後續的一路匹配,可以成功解析到第二行的Expr(Expr)的結果,其結果同樣作為第一行的Expr,之後,再次廣播結果給continuation,首先是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-5 Expr(Expr) <- (foo(10)(, "20)(30)") Expr <- (foo(10)(, "20)(30)") k-6 -> failure -> failure Num <- (foo(10)(, "20)(30)") -> (foo(10)(20, ")(30)") -> (foo(10)(20, ")(30)") 之後的調用與上述相同,Expr解析到(foo(10)(20, ")(30)")的結果後,執行切換到k-5處。

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] <<<, 備註我的花名成功率更高哦~ 😘