言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella

OMeta の電卓を parsec で作る。

さて、http://jarrett.cs.ucla.edu/ometa-js/#OMeta_Tutorial にある OMeta の電卓の例をそのまま parsec で作ってみます。OMeta は言語に必要な処理を、文字解析に留まらず出来るだけ OMeta で行うのが売りです。また逆に parsec はパーサ特有の処理を、特別な言語を使わず Haskell だけで行うのが売りです。真逆で面白いので、OMeta と parsec を対比させる事で両者の特徴を浮き上がらせてみます。

module Main where
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Pos( updatePosChar, updatePosString )

run :: Show a => Parser a -> String -> IO()
run p input = out (parse p "error" input)
    where out (Right x) = print x
          out (Left err) = print err

ここでは左再帰を多用するので、先ほどの数字を解析するやつを復習します。

numValue :: Parser Int
numValue = numValue' 0

numValue' :: Int -> Parser Int
numValue' n = digit >>= \d ->
                let ds = n * 10 + (fromEnum d - fromEnum '0')
                in numValue' ds <|> return ds

あまりに醜いので読まなくて良いです。。。。Persec には many という関数が用意されていて、それで左再帰(を右再帰に変換した物) を処理出来るのですが、なぜそれを使わなかったかと言うと、many の結果がリスト決め打ちなのが気にくわなかったのです。何とか他に方法が無い物かと悩んで、引数を余分に一つ受け取る many を作れば良いと気がつきました。

manyl :: (a -> Parser a) -> a -> Parser a
manyl f z = (f z  >>= \x -> manyl f x) <|> return z

これを使うと非常にすっきり書けます。manyl は foldl のように振る舞う many です。digValue digValue* のようなクリーネスターとして使います。

digValue :: Num a => Parser a
digValue = digit >>= \d -> return (fromIntegral (fromEnum d - fromEnum '0'))

number :: Num a => Parser a
number = digValue >>= \z -> manyl (\x -> digValue >>= \y -> return (x * 10 + y)) z

わざわざ数値の解析にここまで周到な準備をしたのは、一般的な左再帰に対応するためででした。これで準備万端、電卓のインタプリタを作ります。

add, mul, prim, expr :: Fractional a => Parser a

add = mul >>= manyl (\x -> (char '+' >> mul >>= \y -> return (x + y))
                       <|> (char '-' >> mul >>= \y -> return (x - y)))

mul = prim >>= manyl (\x -> (char '*' >> prim >>= \y -> return (x * y))
                        <|> (char '/' >> prim >>= \y -> return (x / y)))

prim = (char '(' >> expr >>= \x -> char ')' >> return x)
    <|> number

expr = add

-- Main> run expr "(3+4)*6"
-- 42.0

次に、OMeta の例に従って中置を前置に変えてみます。

data Op = Mul | Div | Add | Sub deriving Show

data Expr a = Expr Op (Expr a) (Expr a) | Val a
instance Show a => Show (Expr a) where
    showsPrec p (Val x) = shows x
    showsPrec p (Expr op x y) = showChar '(' . shows op . showChar ' ' . shows x . showChar ' ' . shows y . showString ")"

addExpr, mulExpr, primExpr, exprExpr :: Num a => Parser (Expr a)

addExpr = mulExpr >>= manyl (\x -> (char '+' >> mulExpr >>= \y -> return (Expr Add x y))
                               <|> (char '-' >> mulExpr >>= \y -> return (Expr Sub x y)))

mulExpr = primExpr >>= manyl (\x -> (char '*' >> primExpr >>= \y -> return (Expr Mul x y))
                                <|> (char '/' >> primExpr >>= \y -> return (Expr Div x y)))

primExpr = (char '(' >> exprExpr >>= \x -> char ')' >> return x)
       <|> (number >>= \n -> return (Val n))
        
exprExpr = addExpr

-- Main> run exprExpr "(3+4)*6"
-- (Mul (Add 3 4) 6)

このあとザクッと実行する話を書きますが、疲れたので休憩。

参考