Parser Combinatorというもの(その2)
このページにはいわゆる解説記事を載せるつもりは無かったのだが、
(たいていは他にもっとうまい説明のページがあるだろうから…)
どうやらこれがそうなってしまいそうである。
もっとまともな解説は
http://sky.zero.ad.jp/~zaa54437/programming/clean/CleanBook/part2/Chap5.html
こちらをどうぞ。(って人のページなんだけどな…)
- 概要
パーザコンビネータはプリミティブパーザと
パーザ同士を組み合わせるコンビネータとからなる。
小さいパーザを組み立てて最終的なパーザを作り上げるのである。
- パーザ
パーザはいろいろなものが考えられるが、
ここでは単純に、文字列を引数にとり、
解析したもの+残りの文字列を返す関数であるとする。
type Parser a = String -> (a,String)
Stringもパラメータ化すると、もっと抽象的になる。
type Parser s a = [s] -> (a,[s])
これだと確定的なパーザであるが、
文法によってはいつも解析が一通りに決まるとは限らない。
そのような文法を解析できるように解析結果として全候補を返すようにする。
type Parser s a = [s] -> [(a,[s])]
これで多分十分である。
- プリミティブパーザ
プリミティブなものとなるパーザを考える。
まず、一文字を解析するパーザ
symbol :: Eq s => s -> Parser s s symbol c (x:xs) | c==x = [(x,xs)] symbol _ _ = []
symbol 'a' とすると'a'という文字を解析するパーザとなる。
Main> (symbol 'a') "abc"
[('a',"bc")]
Main> (symbol 'a') "dab"
[]
このような挙動を示す。
このパーザを一般的にしたもの、
satisfy :: (s -> Bool) -> Parser s s satisfy p (x:xs) | p x = [(x,xs)] satisfy _ _ = []
が考えられる。これを用いるとsymbolは
symbol c = satisfy (==c)
と定義できる。
便利のためにトークン列を解析するパーザ
token :: Eq s => [s] -> Parser s [s] token t ls | t == take n ls = [(t,drop n ls)] | otherwise = [] where n = length t
組み合わせるために使う物として、
常に成功する/失敗するパーザを定義する。
success :: a -> Parser s a success v xs = [(v,xs)] failure :: Parser s a failure _ = []
successは入力を消費せずに与えられたものを解析結果とする。
コンビネータとは自由項を持たない関数というぐらいの意味であるが、
ここではパーザを組み合わせてパーザを組み立てるような関数のことである。
まずは直列化。
infixr 6 <&> (<&>) :: Parser s a -> Parser s b -> Parser s (a,b) p <&> q = \ls -> [((r1,r2),s2) | (r1,s1) <- p ls, (r2,s2) <- q s1]
symbol 'a' <&> symbol 'b' で、abを解析するパーザとなる
Main> (symbol 'a' <&> symbol 'b') "abcde"
[(('a','b'),"cde")]
Main> (symbol 'a' <&> symbol 'b') "adcde"
[]
次に選択。
infixr 4 <|> (<|>) :: Parser s a -> Parser s a -> Parser s a p <|> q ls = p ls ++ q ls
symbol 'a' <|> symbol 'b' でaかbを解析するパーザになる。
Main> (symbol 'a' <|> symbol 'b') "adcde"
[('a',"dcde")]
Main> (symbol 'a' <|> symbol 'b') "bdcde"
[('b',"dcde")]
Main> (symbol 'a' <|> symbol 'b') "dcde"
[]
解析結果はこれまでトークンそのものとか、<&>によって作られたペアとかであったが、
これではやりにくいし何より再帰的なパーザに型が付かない。
そこで、解析結果を変換するようなものを考える。
infixl 5 <@ (<@) :: Parser s a -> (a -> b) -> Parser s b p <@ f = \ls -> [(f r,s) | (r,s) <- p ls]
これを用いて
Main> (satisfy isDigit <@ \d -> ord d - ord '0') "123" [(1,"23")]
このようなものが作れる。
あまり重要ではないが、<&>のバリエーションとして
どちらかの解析結果を捨てるようなものを考えると便利である。
infixr 6 <& (<&) :: Parser s a -> Parser s b -> Parser s a p <& q = p <&> q <@ fst infixr 6 &> (&>) :: Parser s a -> Parser s b -> Parser s b p &> q = p <&> q <@ snd
括弧で囲われた文字を解析するパーザが次のようになる。
Main> (symbol '(' &> satisfy (const True) <& symbol ')') "(a)cde"
[('a',"cde")]
- コンビネータ続き
ここまでで大体のことは出来るのであるが、
利便性を考えてもっと色々なバリエーションを考える。
与えられたパーザの0回以上の出現。
many :: Parser s a -> Parser s [a]
many p = p <&> many p <@ (\(x,xs) -> x:xs)
<|> success []
与えられたパーザの1回以上の出現もつくれる。
many1 :: Parser s a -> Parser s [a] many1 p = p <&> many p <@ \(x,xs) -> x:xs
これを用いると数字のパーザは次のようになる。
natural :: Parser Char Int natural = many1 (satisfy isDigit) <@ read
Main> natural "123abc" [(123,"abc"),(12,"3abc"),(1,"23abc")]
manyが<|>でつながれているので、1文字以上の解析すべてが結果として出てきている。
最初のもの以外は欲しくないので、最初のものだけを
返すようにする物を考える。
first :: Parser s a -> Parser s a first p = take 1 . p
これで解析できる最長のものを返すmanyが作れる。
manyf p = first (many p) many1f p = first (many1 p)
naturalでつかっているのをmany1fに変えると、
Main> natural "123abc" [(123,"abc")]
このようになる。
もうこの辺で正規表現程度ならすべて直接表現できるのであるが、
正規表現やBNFにとらわれる必要は全く無い。
更なるコンビネータを考える。
まず、区切りで区切られたリスト。
listOf :: Parser s a -> Parser s b -> Parser s [a]
listOf p s = p <&> many (s &> p) <@ (\(l,ls) -> l:ls)
<|> success []
カンマで区切られたリストなどが簡単に作れる。
commaSep :: Parser Char a -> Parser Char [a] commaSep p = listOf p (symbol ',')
例、カンマで区切られた数字の和を求めるパーザ
Main> (commaSep natural <@ sum) "123,456,789" [(1368,""),(579,",789"),(123,",456,789"),(0,"123,456,789")]
listOfにて、区切り文字が意味を持つ場合がある。
四則演算などにおける演算子などである。
このような場合について、次のようなものを考えると
式の解析でとても便利である。
chainl :: Parser s a -> Parser s (a->a->a) -> Parser s a chainl p s = p <&> many (s <&> p) <@ (\(e0,l) -> foldl (\x (op,y) -> op x y) e0 l) chainr :: Parser s a -> Parser s (a->a->a) -> Parser s a chainr p s = many (p <&> s) <&> p <@ (\(l,e0) -> foldr (\(x,op) y -> op x y) e0 l)
chainlが左結合、chainrが右結合で解析する。
加減算が次のように書ける。
Main> (chainl natural (symbol '+' <@ const (+) <|> symbol '-' <@ const (-))) "1-2-3+4" [(0,""),(-4,"+4"),(-1,"-3+4"),(1,"-2-3+4")]
- 応用例
先の式にて、演算子の優先順位は1レベルであったが、
多レベルのものも考えられる。
たとえば四則演算なら*/が+-よりも高い順位を持つ。
まず、次の補助関数を定義する。
opr :: String -> (a->a->a) -> Parser Char (a->a->a) opr str f = token str <@ const f choice :: [Parser s a] -> Parser s a choice (x:xs) = foldl (<|>) x xs
四則演算のBNFは
Expr = Term { (+|-) Term }
Term = Fact { (*|/) Fact }
Fact = natural | '(' Expr ')'
このような感じ。
これを元に適当に実装すると、
expr = chainl term (opr "+" (+) <|> opr "-" (-))
term = chainl fact (opr "*" (*) <|> opr "/" div)
fact = natural <|> symbol '(' &> expr <& symbol ')'
このようになる。
演算子の部分をくくりだすと
expr = chainl term $ choice $ map (\(s,f) -> opr s f) add_op
term = chainl fact $ choice $ map (\(s,f) -> opr s f) mul_op
add_op = [("+",(+)),("-",(-))]
mul_op = [("*",(*)),("/",div)]
さらに共通部分をくくりだす。
expr = chainl term (makeOplist add_op) term = chainl fact (makeOplist mul_op) makeOplist = choice . map (\(s,f) -> opr s f)
exprとtermを一行にまとめると
expr = chainl (chainl fact (makeOplist mul_op)) (makeOplist add_op)
これは、foldのパターンである。
よってfoldを使って書き直せる。
expr = foldr (\op f -> chainl f (makeOplist op)) fact [mul_op,add_op]
さらにここからfact及び演算子のリストをパラメータ化すると、
汎用の式解析パーザ生成関数を作ることが出来る。
buildExpr p tbl = foldl (\f op -> chainl f (makeOplist op)) p tbl
十分に汎用化された。これでexprを定義すると
expr = buildExpr fact oprTbl where
oprTbl =
[ [("*",(*)),("/",div)]
, [("+",(+)),("-",(-))] ]
最後の定義に対しては演算子の追加などが非常に簡単である。
- パーザでは無い部分
上で書いてきたパーザは結果を解析候補のリストで返す。
内部的にはともかく、これを外部的には使いにくいのである。
そこで、次のような関数を用意する。
parse :: Parser s a -> [s] -> a parse p = fst . head . p
解析はこのように行う
Main> parse expr "1-(2-3)" 2
- モナディック
パーザコンビネータを見て何かに似ていると思われなかったであろうか?
そう、モナドである。
実際のところ、パーザを要素、bind演算を<&>、
returnをsuccessと考えると、
(<&> の型は Parser s a -> (a -> Parser s b) -> Parser s b に変更)
パーザはモナドとなる。
実際、Haskellの標準的なライブラリについているText.ParserCombinators.Parsecは
モナディックなパーザコンビネータになっている。
(というか、昨日使ったやつ)
ということで、今日はなんだか長くなってきたので
Parsecについては次回。
今回、オリジナル要素はほぼ無しなんだけどな…
