文脈自由文法(CFG)と解析表現文法(PEG)をHaskellのモナドで説明する話 - 簡潔なQ

文脈自由文法(Context Free Grammar) と 解析表現文法(Parsing Expression Grammar) は記法が似ているものの、その性質は大きく異なっている。しかし、以下のようにHaskellのモナドを用いて、左再帰的でない文脈自由文法をそのままパーサーコンビネーターとして変換すると、PEGはList monadをMaybe monadとして置き換えたものとして説明できる。 -- CFGとPEGの関係を List vs. Maybe として説明するサンプル import Control.Monad import Control.Monad.State -- 型の説明 : StateT String m a -- StateT String ... 構文解析の残りの文字列を記憶している。 -- m ... 正否をあらわす。ListにするとCFG, Maybeにする