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

Haskell

文脈自由文法(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にするとPEGになる
-- a ... 今回は構文解析の正否のみに興味があるので () にする。

-- 演算子の説明
-- A >> B ... 構文要素の連接を表す。
-- A `mplus` B ... 構文要素の選択を表す。

-- CFG/PEG共通 : 指定した1文字を読む。
readChar :: MonadPlus m => Char -> StateT String m ()
readChar ch = do
  (ch0:str) <- get
  guard $ ch0 == ch
  put str

-- CFG/PEG共通 : 文字列の終端か検査する。
eof :: MonadPlus m => StateT String m ()
eof = do
  [] <- get
  return ()

-- 文法その1
-- S -> A $
-- A -> "a" A "a" | "a"
a :: MonadPlus m => StateT String m ()
a = (readChar 'a' >> a >> readChar 'a')
    `mplus` readChar 'a'

grammar1 :: MonadPlus m => StateT String m ()
grammar1 = a >> eof


-- 文法その2
-- S -> B $
-- B -> "a" B "a" | "b" B "b" | ""
b :: MonadPlus m => StateT String m ()
b = (readChar 'a' >> b >> readChar 'a')
    `mplus` (readChar 'b' >> b >> readChar 'b')
    `mplus` return ()

grammar2 :: MonadPlus m => StateT String m ()
grammar2 = b >> eof


-- 文法を(左再帰的でない)CFGとして検査する
checkCFG :: StateT String [] () -> String -> Bool
checkCFG grammar str = runStateT grammar str /= []

-- 文法をPEGとして検査する
checkPEG :: StateT String Maybe () -> String -> Bool
checkPEG grammar str = runStateT grammar str /= Nothing


main :: IO ()
main = do
  forM_ [
      "",
      "a",
      "aa",
      "aaa",
      "aaaa",
      "aaaaa",
      "aaaaaa",
      "aaaaaaa"
    ] (\str -> do
      putStrLn $ "checkCFG grammar1 " ++ show str ++ " = " ++ show (checkCFG grammar1 str)
      putStrLn $ "checkPEG grammar1 " ++ show str ++ " = " ++ show (checkPEG grammar1 str)
    )
  forM_ [
      "aa",
      "abba",
      "bbbbbb",
      "baaaab"
    ] (\str -> do
      putStrLn $ "checkCFG grammar2 " ++ show str ++ " = " ++ show (checkCFG grammar2 str)
      putStrLn $ "checkPEG grammar2 " ++ show str ++ " = " ++ show (checkPEG grammar2 str)
    )

実行結果

checkCFG grammar1 "" = False
checkPEG grammar1 "" = False
checkCFG grammar1 "a" = True
checkPEG grammar1 "a" = True
checkCFG grammar1 "aa" = False
checkPEG grammar1 "aa" = False
checkCFG grammar1 "aaa" = True
checkPEG grammar1 "aaa" = True
checkCFG grammar1 "aaaa" = False
checkPEG grammar1 "aaaa" = False
checkCFG grammar1 "aaaaa" = True
checkPEG grammar1 "aaaaa" = False
checkCFG grammar1 "aaaaaa" = False
checkPEG grammar1 "aaaaaa" = False
checkCFG grammar1 "aaaaaaa" = True
checkPEG grammar1 "aaaaaaa" = True
checkCFG grammar2 "aa" = True
checkPEG grammar2 "aa" = True
checkCFG grammar2 "abba" = True
checkPEG grammar2 "abba" = True
checkCFG grammar2 "bbbbbb" = True
checkPEG grammar2 "bbbbbb" = True
checkCFG grammar2 "baaaab" = True
checkPEG grammar2 "baaaab" = False

文法の例として挙げたもの

S -> A
A -> "a" A "a"
A -> "a"

このCFGは奇数個のaからなる文字列を受理する。

S <- A
A <- "a" A "a"
   / "a"

このPEGは(2の冪-1)個のaからなる文字列を受理する。

S -> B
B -> "a" B "a"
B -> "b" B "b"
B -> ε

このCFGはaとbからなる偶数文字の回文を受理する。

S <- B
B <- "a" B "a"
   / "b" B "b"
   / ε

このPEGはよくわからないが回文でも受理しない場合がある。(上の実行結果を見よ。)