2010年12月25日

ParsecでPL/0の構文解析 - 式の構文解析

(この記事は Haskell Advent Calendar jp 2010 に参加しています)

Haskell のパーサコンビネータライブラリ Parsec を使って PL/0 の構文解析をします. 今回は式を解析して構文木を作るところまでです. 参考文献は Real World HaskellWrite Yourself a Scheme in 48 Hours です.

準備

Parsec モジュールをインポートします. Persec.Token を使えばいろいろ便利になりますが, 今回は省きます.
import Text.ParserCombinators.Parsec hiding(spaces)
import Control.Monad (liftM,liftM2)
-- import Text.ParserCombinators.Parsec.Token

データ構造

test 構文木のデータ構造を作ります. プリティプリントのためにShowクラスのインスタンスを 宣言しています. derivingで自動で導出させていないのは, そうすると表示が冗長になるからです.
data PLTree = Node PLOp PLTree PLTree
            | Leaf PLVal
              deriving(Eq)

data PLOp = Add | Sub | Mul | Div
            deriving(Eq)

data PLVal = Number Int
           | Ident [Char]
           | Bool Bool
             deriving(Eq)

instance Show PLTree where
    show (Node op left right) =
        '(' : show op ++ " " ++ show left ++ " " ++ show right ++ ")"
    show (Leaf val) = show val

instance Show PLOp where
    show Add = "+"
    show Sub = "-"
    show Mul = "*"
    show Div = "/"

instance Show PLVal where
    show (Number x) = show x
    show (Ident x) = x
    show (Bool x) = show x

式パーサ

PL/0のWikipedia記事 のENBFによると,数式は以下のような感じです. 演算子の順位をENBFの段階で表現しているわけですね. []は省略可能,{}は0回以上の繰り返しです.
expression = [ "+"|"-"] term { ("+"|"-") term}.
term = factor {("*"|"/") factor}.
factor = ident | number | "(" expression ")".
この通りに実装すればいいわけですが, その前に数値と名前(関数名と変数名)を解析するパーサを作ります.
number :: Parser PLVal
number = liftM (Number . read) $ many1 digit

ident :: Parser PLVal 
ident = 
  liftM Ident $ liftM2 (:) (firstChars) (many restChars)
    where
      firstChars = letter <|> char '_'
      restChars = letter <|> digit <|> char '_'
ENBFのまま素朴に実装します.
expression :: Parser PLTree
expression = do
  opchar <- optionMaybe $ oneOf "+-"
  liftM (prefix opchar) $ term `chainl1` addop
    where
      prefix (Just '-') = Node Mul (Leaf . Number $ -1)
      prefix _          = id
      addop = do {     char '+'; return $ Node Add }
              <|> do { char '-'; return $ Node Sub }
                         
term :: Parser PLTree
term = factor `chainl1` mulop
    where mulop = do {     char '*'; return $ Node Mul }
                  <|> do { char '/'; return $ Node Div }

factor :: Parser PLTree
factor = 
  (liftM Leaf ident)  <|>
  (liftM Leaf number) <|>
  (braces expression)

実行

うまくいっているようです.
> parse expression "PL/0 Expr" "(1+3)/(-2)"
Right (/ (+ 1 3) (* -1 2))

余談

  • ホワイトスペースの処理が未実装です. Persec.Tokenモジュールのsymbolを 使えばうまく表現できそうです.
  • 「純粋関数型言語で教育用言語を実装する」って ありがちなネタかと思ったけどあまりやってる人がいなくて助かりました.
  • モナドとかよく分かってません. GHC のエラーがなくなるようにすれば, それでも動くものができるので何とかなってます.

続くか未定



kazeula at 22:58│Comments(0)TrackBack(0)Haskell 

トラックバックURL

コメントする

名前
URL
 
  絵文字