PEGパーサーを書いてみる

Haskell Monad PEG Parser

PEGで文法を表現してみて、ルールのそれぞれの使い方動きにもなじみが出てきました。

ここで、PEGパーサーをちょっと書いてみたいと思います。PappyやFrisbyのようにO(N)というわけに行くかどうかはわかりませんが…

方針としては、Parsecのまねということで、モナドのインターフェースにあわせて、ステートモナドのパターンを踏襲していきたいと思います。

次に、モナドパーサーの入出力についてみてみたいと思います。まず、パーサーとして、成功のときはパースの結果と、残りの入力文字列を返す必要があります。さらに、PEGパーサーのルールの中では空文字：（）のように成功しても何も出力しないものがあります。つまり、出力型は｢空｣というコンセプトが表現できなくてはいけませんね。それ以外にも順序：(e1,e2,e3,e4)のように複数のパーサーを順次マッチさせた結果を返すときは各パーサーの要素をうまくつなぎ合わせることができると話が単純になりそうです。ということで、ちょっと無駄なような気もするのですが、出力は常にリストになるようにするとして

data Parser i o = Parser { runParser :: \i -> Maybe ([o], i)}

ということにして見ます。パース失敗のときはNothing、成功の場合はJust（[o], i)といった感じで…その辺を指定するべくモナドのインスタンス宣言を書いて見ます：

instance Monad (Parser i) where
　　m >>= f = Parser $ \i ->
　　　　case (runParser m i) of
　　　　　　Nothing -> Nothing
　　　　　　Just (o, i') -> runParse (f o) i'
　　return o = Parse \i -> Just (o, i)

PEGのルールを見てみると、いくつかの種類に分けることができることに気づきます。
まずはパーサーの核というべき単純なパーサーです：

emptyP :: Parser i o
emptyP = Parser $ \i -> Just ([], i)

itemP :: o -> Parser i o
itemP o = Parser $ \is@(i:iss) -> 
　　if (i == 0) then Just ([o], iss)
　　　　else Nothing

ここから先はとりあえずシグネチャだけ押さえていきたいと思います。

そして、それを組み合わせていくコンビネータのうち次の2つを2項演算子として定義します

seqP :: Parser i o -> Parser i o -> Parser i o

orP :: Parser i o -> Parser i o -> Parser i o

そして、単項演算子が

manyP :: Parser i o -> Parser i o

many1P p = p `seqP` (manyP p)

optP :: Parser i o -> Parser i o

最後に、迷ったのがfollowedByPとnotFollowedByPです。これは2項でも単項でもかけるんですが、followedByという意味からすると2項で行く方法もありだと思うのですが、単項でやって見ましたということで：

followedByP :: Parser i o -> Parser i o
notFollowedByP :: Parser i o -> Parser i o

この2つを単項演算子で定義することのメリットは単体で使えることなんですが、まぁ、そんなに重要なことではないかもしれません。さらに、2項で定義したとしても、emptyPを組み合わせれば簡単に単項バージョンと同じように使えます。

これが完成すれば、前回の四則演算のPEGを使って電卓が作れます…
ではでは。