構文木を作る

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

Prelude> :l calctree.hs
[1 of 1] Compiling Calc ( calctree.hs, interpreted )
Ok, modules loaded: Calc.
*Calc> let (Right x) = parse expr "" "(1+2)*3" in putStrLn $ drawTree $ x
+
|
`- *
....|
....+- +
.....|.. |
.....| ..+- *
.....|.. |.. |
.....|.. |.. `- 1
.....|.. |
.....|... `- *
.....|....... |
.....|....... `- 2
.....|
.....`- 3

思っていたのよりノードの数が多すぎる気がするのだが、機械的にやるとこんなものなのだろうか。プログラム言語を作ったことなどないのでよくわからない。とにかく構文木らしきものができたので満足。プログラムは calc.hs のものとほとんど変わらない。そんなに手を入れなくても出力を Int 型から Tree a 型に変更できるのが面白い。

ソースコード

ファイル名：calctree.hs

module Calc where
import Text.Parsec
import Data.Tree

expr :: Parsec String () (Tree String)
expr = (\y -> Node "+" y) <$> ((:) <$> term <*> many (char '+' *> term))

term :: Parsec String () (Tree String)
term = (\y -> Node "*" y) <$> ((:) <$> factor <*> many (char '*' *>
 factor))

factor :: Parsec String () (Tree String)
factor = (char '(' *> expr <* char ')') <|> ((\x -> Node x []) <$>
 many1 digit)

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