数式のLL構文解析

以前から数式処理をやってみたいと思っていたので、その下準備として構文解析を適当に書いてみました。完成に至るまで二転三転しましたが…。
それにしてもこういうコード片だとHaskellは大活躍ですね。Haskellすごい。

import Data.Char

-- 以下から引用。標準のreadは失敗するとエラーを投げる。
-- http://d.hatena.ne.jp/sshi/20060630/p2
read' :: (Read a) => String -> Maybe a
read' s = case [x | (x,t) <- reads s, ("","") <- lex t] of
    [x] -> Just x
    _ -> Nothing


-- 式表現
data Expr = Const Integer | Symbol String
    | Add Expr Expr | Mul Expr Expr | Power Expr Expr
        deriving Show

showExpr :: Expr -> String
showExpr (Const x) = show x
showExpr (Symbol x) = x
showExpr (Add x y) = "(" ++ showExpr x ++ " + " ++ showExpr y ++ ")"
showExpr (Mul x y) = "(" ++ showExpr x ++ " * " ++ showExpr y ++ ")"
showExpr (Power x y) = showExpr x ++ "^" ++ showExpr y


-- 構文解析
term, power, factor, expression :: [String] -> (Expr, [String])

term ("(":is) = let (e, (")":is')) = expression is in (e, is')
term (i:is) = case read' i of
    Just x -> (Const x, is)
    Nothing -> (Symbol i, is)

power = pow . term 
    where
        pow (e, "^":is) = let (e', is') = power is in (Power e e', is')
        pow x = x

factor = fac . power
    where
        fac (e, "*":is) = let (e', is') = power is in fac ((Mul e e'), is')
        fac (e, "/":is) = let (e', is') = power is in fac ((Mul e (Power e' (Const $ -1))), is')
        fac x = x

expression = exp . factor
    where
        exp (e, "+":is) = let (e', is') = factor is in exp ((Add e e'), is')
        exp (e, "-":is) = let (e', is') = factor is in exp ((Add e (Mul (Const $ -1) e')), is')
        exp x = x


-- 字句解析
lexer :: String -> [String]
lexer [] = []
lexer (x:xs)
    | isAlpha x = wordWhile (\x -> isAlpha x && isDigit x)
    | isDigit x = wordWhile isDigit
    | isSpace x = lexer xs
    | isAscii x = [x] : lexer xs
        where wordWhile p = (x : takeWhile p xs) : (lexer $ dropWhile p xs)


-- 構文解析 + 字句解析
parse = fst . expression . lexer

実行結果

> parse "a+b+c"
Add (Add (Symbol "a") (Symbol "b")) (Symbol "c")

> showExpr $ parse "1*2+3/4"
"((1 * 2) + (3 * 4^-1))"

> showExpr $ parse "a*y^2-b/c*y+1"
"(((a * y^2) + (-1 * ((b * c^-1) * y))) + 1)"

減算と除算はそれぞれ乗算と累乗に直してあります。Subとかを作るのは簡単にできます。
LL法のパーサを実装すると、必ず左再帰の問題が発生しますね。
wikipedia:左再帰
今回作ったパーサは、左再帰を回避しつつ、左結合の構文木が作られるように配慮してあります。左結合の演算子(+, *)では、再帰呼び出しの中で、引数に呼び出し元の情報を溜め込んでいくのがポイントです。以下にBNFも置いておきます。

expression = factor expression'
expression' = + factor expression' | - factor expression' | ε
factor = power factor'
factor' = * power factor' | / power factor' | ε
power = term power'
power' = ^ power' | ε
term = Const | Symbol | ( expression )

実行速度は遅いと思いますが、こういうコードで速度が要求される場面もあまりないでしょう。もっといい方法あったら教えてください。