あどけない話

インターネットに関する技術的な話など

モナディック・パーサー

ふつうの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,"")]