構文木を作る

プログラム言語では文字列をパースしながら言語の構文木を作っていくらしい。そこで、前回の calc.hs を改造して構文木を作らせてみた。

構文木のデータ構造は Expr 型として次のように定義した。

data Expr = Val String
  | Sum [Expr]
  | Product [Expr]
  deriving Show

factor, term, expression の区別はなくひとまとめに Expr 型にしてある。実行例は次のようになる。

*Calc> parseTest expr "(1+2)*(3+4)"
Sum [Product [Sum [Product [Val "1"],Product [Val "2"]],Sum [Product
 [Val "3"],Product [Val "4"]]]]

思っていたのよりノードの数が多すぎる気がするのだが、機械的にやるとこんなものなのだろうか。プログラム言語を作ったことなどないのでよくわからない。とにかく構文木らしきものができたので満足。

プログラムは calc.hs のものとほとんど変わらない。ほぼそのままのプログラムで出力を Int 型から Expr 型に変更できるのが面白い。

ソースコード

ファイル名：calctree.hs

module Calc where

import Text.Parsec

data Expr = Val String
  | Sum [Expr]
  | Product [Expr]
  deriving Show

expr :: Parsec String () Expr
expr = Sum <$> ((:) <$> term <*> many (char '+' *> term))

term :: Parsec String () Expr
term = Product <$> ((:) <$> factor <*> many (char '*' *> factor))

factor :: Parsec String () Expr
factor = (char '(' *> expr <* char ')') <|> (Val <$>
 (many1 digit))

とにかくパーサで構文木を作らせるところまでできた。パターンの作り方、パーサのアクションの記述の仕方、Applicative の使い方、構文木の定義の仕方などが有機的に理解できたような気がする。また、言わばパターンプログラミングとでもいえるような、パターンでプログラムするプログラミングのやり方が面白かった。

構文木の評価

構文木を評価するプログラムは簡単だ。次の eval 関数のプログラムを上のソースプログラムの最後に追加すると構文木を eval 関数で評価することができる。実行例は次のようになる。パーサから構文木を取り出すためには parseTest 関数ではなく、parse 関数を使う。

*Calc> let Right es = parse expr "foo" "(1+2)*(3+4)" in eval es
21

eval 関数のソースは次のようになる。

eval :: Expr -> Int
eval (Val a) = read a :: Int
eval (Sum es) = sum $ map eval es
eval (Product es) = product $ map eval es