PEG

PEG モドキを Haskell で。データ構造を定義した。Show のインスタンスにする部分は省略。

data PExp nt = Eps -- epsilon
          | AtomT String -- Terminal symbol
          | AtomNT nt -- Non-Terminal symbol
          | PExp nt :. PExp nt -- e1 e2
          | PExp nt :/ PExp nt -- e1 / e2
          | Opt (PExp nt) -- e?
          | ZeroOrMore (PExp nt) -- e*
          | OneOrMore (PExp nt) -- e+
          | And (PExp nt) -- &e
          | Not (PExp nt) -- !e
          deriving Eq

data Rule nt = nt :<- (PExp nt) deriving Eq
data Grammer nt = Grammer [Rule nt] deriving Show

そして以下のようにサンプルのグラマーを定義してやる。

pp (Grammer rs) = mapM_ (putStrLn . show) rs

data NT01 = Underscore | Digit | LowerCase | UpperCase | Identifier 
          deriving (Eq, Show)  

g01 :: Grammer NT01
g01 = Grammer [ underScore, digit, lowerCase, upperCase, identifier ]
  where
    underScore = Underscore :<- AtomT "_"
    digit = Digit :<- e
      where f n = [intToDigit n]
            e = foldl1 (:/) $ map (AtomT . f) [0..9]
    lowerCase = LowerCase :<- foldl1 (:/) [AtomT [x] | x <- ['a'..'z']]
    upperCase = UpperCase :<- foldl1 (:/) [AtomT [x] | x <- ['A'..'Z']]
    identifier = Identifier :<- 
                 ((AtomNT LowerCase :/ AtomNT UpperCase :/ AtomNT Underscore) :. 
                  (Opt (AtomNT LowerCase :/ AtomNT UpperCase :/ AtomNT Underscore :/ AtomNT Digit)))

そうすると以下のように出力される。

Main> pp g01
Underscore <- _
Digit <- 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9
LowerCase <- a / b / c / d / e / f / g / h / i / j / k / l / m / n / o / p / q / r / s / t / u / v / w / x / y / z
UpperCase <- A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / Z
Identifier <- ( LowerCase / UpperCase / Underscore ) ( ( LowerCase / UpperCase / Underscore / Digit )? )
Main>