使用 parsec 處理左遞歸

（題圖來自 @後綴自動機·張

在給之前寫的 Lisp 解釋器之前套上表達式語法時，遇到這樣幾條文法

Apply 是許多編程語言中屢見不鮮的函數調用形式。顯然，non-terminal Apply 的派生最左端會進入 Factor，之後又會回到 Apply 。教科書式的左遞歸。

龍書中告訴我們，左遞歸可以通過提取出一個產生式來消除。

對於

在所有不以 A 開頭的 A 的派生 beta 後加入非終結符 A，然後 A 派生出 alpha，即可消除左遞歸。

道理都懂，但是怎麼寫代碼呢？

parsec 的代碼的一個特點是可以很直觀的將文法和返回的結果對應。我們按照最開始的有左遞歸的文法可以很容易的寫出這樣的組合子

parseFactor = spaces >> value >>= v -> return v where parenExpr = between (char () (char )) parseExpr value = choice [ parseNumber, try parseFunCall, -- lots of parsers... parenExpr ]parseExpr = -- based on `Text.Parsec.Expr`theComma = spaces >> char ,parseApply :: Parser ExprparseApply = do fun <- parseExpr spaces args <- between (char () (char )) $ sepBy parseExpr theComma return $ Apply fun args

原文法中的每一個非終結符都可以對應到相應的 parser ，相應的 parser 進行適當的處理返回 AST 的節點。一切都那麼井然有序，除了它會陷入無窮的遞歸然後電腦被不會爆棧的 Haskell 撐爆內存。

然而進行消除左遞歸後的文法中，A 的意義是不明的，不能對應到 AST 中的某個節點；甚至 A 本身意義也是不明的。這種情況下，我們就需要進行一些特殊的間接處理讓 parser 能返回正確的結果。

把原來的文法的左遞歸消除。

第一條產生式很好表達，和之前只是避免了直接派生 Apply

parseFactor = spaces >> nonTerminal <|> parenExpr where split = many splitter parenExpr = between (char () (char )) parseExpr nonTerminal = choice [ parseString, parseNumber, parenExpr, -- lots of parsers... ]

接下來需要處理第二條和第三條。顯然，這兩條規則對應的 AST 節點有兩種，普通的 Factor 或 Apply 。我們可以把這兩條規則視為一個整體的過程：在 parse 出一個 Factor 之後，嘗試 char ( ，滿足則繼續，不滿足則直接返回之前的 Factor 。

parseFactorOrApply = do factor <- parseFactor rest fun where rest x = (do args <- between (char () (char )) $ sepBy parseExpr theComma rest pos . Expr pos $ Apply x args) <|> return x

成功完成任務。

parsec 自帶的組合子中的 chainr1 也是使用的類似方法處理左遞歸，它的功能是構造右結合的雙目操作符的表達式的解析。

chainr1 :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m (a -> a -> a) -> ParsecT s u m achainr1 p op = scan where scan = do{ x <- p; rest x } rest x = do{ f <- op ; y <- scan ; return (f x y) } <|> return x

推薦閱讀：