chainl
左再帰のparserを返すコンビネータ
左結合になる
右結合にしたければ
chainr を使えばいいよくある
Expr + Expr + Expr のような連続する二項演算子をパースするparserを作成できるchainl
chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a chainl1
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a 第1引数
Parser a 型的には普通のParsecのparserだな
第2引数
Parser (a -> a -> a) 演算子を消化して二分木を合成する関数を返すパーサを
内部実装の解説
左再帰の除去をするためにchainlを実装していく
全然理解していない
抽象化がすごいので理解したい
実装例
以下の例は、書き換え前は右結合で、書き換え後は左結合になっているので、例としてはあまり良くない
hs- add ::= term | term ('+' add | "-" add)
-- 書き換え前
add :: Parser Expr
add = do
t <- spaces *> term
spaces
*> (Add t <$> (char '+' *> spaces *> add))
<|> (Sub t <$> (char '-' *> spaces *> add))
<|> pure t
-- 書き換え
add :: Parser Expr
add = term `chainl1` addop
addop :: Parser (Expr -> Expr -> Expr)
addop = Add <$ char '+' <|> Sub <$ char '-'実際にループを使ったものとchainlを使ったものを比較している記事はこれを参考
参考
実装例など、わかりやすい