「ふつうのHaskellプログラミング」や 「構文解析結合子」の元ネタは、どうやら「Monadic parsing in Haskell」のようです。(さらに元ネタは Parsec ですかね。)
このオリジナルは、MonadPlus の部分などが古くさいのですが、分りやすいです。というわけで、例題を Parsec 風にアレンジしつつ、勉強してみました。
四則演算式のパーサーを実現することを目標にします。
おまじない
最終的に以下のモジュールが必要になるので、import しておきます。
import Monad import Data.Char
Parser の定義
Parser 型の定義はこうなります。
data Parser a = Parser (String -> [(a,String)])
- 状態を表すために関数を使っている
- 関数を使うと状態が表現できることが分らない人は、先に「状態モナド遊び」を読んで下さい。
- 最初の String が入力で、次の String が消費されずに残った入力です。
- 消費された入力は、何かに加工されて a として返ります。
- Char、String、Int など、何でも返せます。
- 解析のパスは複数あるかもしれないので、返り値がリストになっています。
Parser というラベルと外すと関数が出てきます。これから定義するパーサーを実行するために、parse という関数を定義しておきましょう。
parse (Parser p) = p
一文字にマッチするパーサー
一文字を消費し、その文字を返すパーサー item は、以下のように定義します。
item :: Parser Char item = Parser $ \cs -> case cs of "" -> [] (c:cs') -> [(c,cs')]
動かすとこうなります。
parse item "abc" → [('a',"bc")]
連接と選択
モナディック・パーサーでは、連接と選択をそれぞれ >>= と mplus に割り当てます。
というわけで、P1 → P2 P3 のような連接が出てくると、こう書けます。
p1 = do p2 p3
また、mplus を演算子らしい <|> で表現すると、P1 → P2 | P3 のような選択は、こう書けます。
p1 = p2 <|> p3
>>=の定義
Parser をモナドにしましょう。
instance Monad Parser where return a = Parser $ \cs -> [(a,cs)] p >>= f = Parser $ \cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs]
リスト内包表記がよく分らないという人は、これでも構いません。
p >>= f = Parser $ \cs -> let l = parse p cs ll = map func l in concat ll where func (a,cs') = parse (f a) cs'
>>=を使ってみる
これで、複数のパーサーを合成し、より大きなパーサーを作ることができます。たとえば、2文字にマッチするパーサーは、こう書けます。
p1 = do a <- item b <- item return [a,b]
動かすと、こうなります。
parse p1 "abc" → [("ab","c")]
文字を文字列に加工して返しているのが分りますか？
MonadPlus
item は、どんな文字にもマッチしました。次は、マッチすべき文字を指定できる char というパーサーを作りましょう。
そのためには、mzero が必要なので、Parser を MonadPlus のインスタンスにします。mplus には、後で戻ってきますので、今は読み飛ばして下さい。
instance MonadPlus Parser where mzero = Parser $ \cs -> [] mplus p q = Parser $ \cs -> parse p cs ++ parse q cs
これで、satisfy という関数が定義できます。
satisfy :: (Char -> Bool) -> Parser Char satisfy f = do c <- item if f c then return c else mzero
satisfy を使って、char を定義します。
char :: Char -> Parser Char char c = satisfy (c ==)
'a' にマッチするパーサは、こう書けます。
pa = char 'a'
実行してみましょう。
parse pa "abc" → [('a',"bc")] parse pa "bcd" → []
string と oneOf
Parsec で定義されている string と oneOf 作ってみましょう。
string :: String -> Parser String string "" = return "" string (c:cs) = do char c string cs return $ c:cs oneOf :: String -> Parser Char oneOf cs = satisfy (\c -> elem c cs)
string は do の中で再帰しているので、最初は理解できないかもしれません。大切なのは慣れです。今分らなくても、後から読み返してみて下さい。
string と oneOf を使った例を以下に示します。
ps = string "main" pd = oneOf "0123456789" -- satisfy isDigit でもよい
<|>の定義
mplus は、++ を使って、パスの可能性を全部連結していました。ですから、選択演算子 <|> を単純に mplus とすると、すべての解析パスを返します。
-- p <|> q = p `mplus` q
しかしながらここでは、最初のパスだけが返るように定義してみましょう。
p <|> q = Parser $ \cs -> case parse (p `mplus` q) cs of [] -> [] (x:xs) -> [x]
こんな感じで使います。
pfoo = string "foo" <|> string "bar" <|> string "baz"
実行してみましょう。
parse pfoo "bazx" → [("baz","x")]
ちなみに、Parsec の <|> は、try を使わない限り、消費した文字を元に戻せません。ですので、この例では string "bar" に "ba" が消費されてしまい、string "baz" は "baz" にマッチできません。
parseTest pfoo "barx" → "bar" parseTest pfoo "bazx" → parse error at (line 1, column 1): unexpected "z" expecting "bar"
今回の <|> では、上記のように、<|> だけであれば後戻り可能です。しかし、最初のパスしか採用しないので、>>= が挟まると後戻りできません。
たとえば、"ac" と "abc" の 2 つのパスがある X → a B c, B → ε| b という BNF を考えます。素直にパーサーを書くと、こうなります。
px = do a <- char 'a' b <- pb c <- char 'c' return $ [a] ++ b ++ [c] pb = return [] <|> do b <- char 'b' return [b]
pb の最初が必ず成功してしまうので、"abc" にはマッチできないことが分ります。
parse px "ac" → [("ac","")] parse px "abc" → []
選択演算子 <|> を mplus にしてあげれば、>>= が利用されても、後戻りできるようになります。
-- p <|> q = p `mplus` q parse px "ac" → [("ac","")] parse px "abc" → [("abc","")]
many と many1
選択演算子 <|> があれば、many と many1 を定義できます。
many :: Parser a -> Parser [a] many p = many1 p <|> return [] many1 :: Parser a -> Parser [a] many1 p = do a <- p as <- many p return $ a:as
多重再帰で、もう大変ですね。X-(
many と many1 があれば、パーサーらしいパーサーが書けるようになります。
例として、自然数にマッチし、その値を返す natural を定義してみましょう。
d1 = do x <- oneOf "123456789" return $ ord x - ord '0' d0 = do x <- satisfy isDigit return $ ord x - ord '0' natural = do n <- d1 ns <- many d0 return $ foldl toNum 0 (n:ns) where toNum x y = x * 10 + y
実行するとこうなります。
parse natural "123" → [(123,"")]
文字列ではなく、数値が返っていることに注意して下さい。
実現する式
実現する四則演算式の BNF を以下に示します。
expr → unary expr'
expr' → expr' addop term | term
term → term mulop factor | factor
factor → number | '(' expr ')'
number → {digit}
digit → '0' | '1' | ... | '9'
unary → '+' | '-' | ε
addop → '+' | '-'
mulop → '/' | '*'
expr' と term は、二項演算子が左結合になるように恐怖の左再帰を使っています。これを単純にプログラムにすると、無限ループに陥ります。
chainl1
そこで、左再帰をうまく処理してくれる chainl1 を定義します。
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
chainl1 p op = do a <- p
rest a
where
rest a = do f <- op
b <- p
rest $ f a b
<|> return a
四則演算式のパーサー
準備ができたので、四則演算式のパーサーを定義します。
expr = do op <- unary n <- term `chainl1` addop return $ op n term = factor `chainl1` mulop factor = number <|> do char '(' n <- expr char ')' return n number = do ns <- many1 digit return $ foldl toNum 0 ns where toNum x y = x * 10 + y digit = do x <- satisfy isDigit return $ ord x - ord '0' addop = add <|> subs add = do char '+' return (+) subs = do char '-' return (-) mulop = mul <|> divi mul = do char '*' return (*) divi = do char '/' return div unary = plus <|> minus <|> return id plus = do char '+' return id minus = do char '-' return negate
使ってみましょう。
parse expr "-(1+2)*(3-5)/2" → [(3,"")]
字句解析
上記の四則演算式のパーサーは、余分な空白があると動きません。そこで、字句解析の部品を作り、四則演算式のパーサーから利用するようにします。
入力は、一般にこういう形をしています。
不要 必要 不要 必要 ... 必要 不要
不要な部分は、必要な部分よりも 1 つだけ多いので、2つの流儀が生まれます。
- 必要と不要を組にする。字句解析器は、必要な部分を取り出したら、直後の不要な部分も消費しておく。最初の不要な部分は別の何かで削る。
- 不要と必要を組にする。字句解析器は、まず不要な部分を削り、必要な部分を取り出す。最後の不要な部分は別の何かで削る。
ここでは、最初の方法を採用して、以下のような部品を作ります。
space :: Parser String space = many $ satisfy isSpace token :: Parser a -> Parser a token p = do a <- p space return a symb :: String -> Parser String symb cs = token $ string cs apply :: Parser a -> String -> [(a,String)] apply p = parse $ do {space; p}
完成版
symb と token を使って書き直した四則演算式のパーサーはこうなります。
expr = do op <- unary n <- term `chainl1` addop return $ op n term = factor `chainl1` mulop factor = number <|> do symb "(" n <- expr symb ")" return n number = do ns <- token $ many1 digit return $ foldl toNum 0 ns where toNum x y = x * 10 + y digit = do x <- satisfy isDigit return $ ord x - ord '0' addop = add <|> subs add = do symb "+" return (+) subs = do symb "-" return (-) mulop = mul <|> divi mul = do symb "*" return (*) divi = do symb "/" return div unary = plus <|> minus <|> return id plus = do symb "+" return id minus = do symb "-" return negate
使ってみましょう。
apply expr " -(1 + 2) * (3 -5) / 2 " → [(3,"")]
