Parsec 式の定義 buildExpressionParser

Parsec の勉強もやっと式のパースを行えるところまでやってきた。Parsec で式を定義するのには便利な関数 buildExpressionParser がある。この関数は、Text.ParserCombinators.Parsec.Expr モジュールに定義されている。式の定義を考える前に、まず一般的な EBNF 記法による式の文法の定義を見てみよう。

expr ::= expr '+' term | term
term ::= term '*' factor | factor
factor ::= '(' expre ') | digit+
digit ::= '0' | '1' | ... | '9'

これを見ると、*の演算は+の演算より優先度が高く、またこの演算が左結合型であることを左再帰で表している。この EBNF 記法をそのまま Parsec のコンビネータで表現するのは面倒なので、式の演算をテーブルに定義しておけばそれを元に式の定義を作ってしまうのが、buildExpressionParser 関数だ。

buildExpressionParser 関数は二つの引数を取る。一つは演算の規則を定義したテーブルのリスト。もう一つは factor(要素) を定義したパーサ関数だ。演算の左結合、右結合はテーブルに定義し、演算の優先度はテーブルのリスト内での前後関係で定義する。

buildExpressionParser 関数を使って0以上の整数の四則演算をする計算機プログラム expr.hs は次のようになる。

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr

expr :: Parser Integer
expr = buildExpressionParser table factor
      <?> "expression"

table = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
        ,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
        ]
      where
        op s f assoc
          = Infix (do{ string s; return f}) assoc

factor = do{ char '('
           ; x <- expr
           ; char ')'
           ; return x
           }
        <|> number
        <?> "simple expression"

number :: Parser Integer
number = do{ ds <- many1 digit
           ; return (read ds)
           }
        <?> "number"

実行例:
Hugs> :e expr.hs
Hugs> :l expr.hs
Main> parseTest expr "1+2*3"
7

このプログラムでは数と演算子の間にスペースを置くと正しく動作しないが、やっと、式の演算ができるところまでたどり着いた。
[PR]
by tnomura9 | 2009-09-30 19:00 | Haskell | Comments(0)
<< Parsec 字句解析プログラ... Parsec ユーザ定義のエラ... >>