phorth---（その1.1）AST+Parser

Harrorthを適当にいじった結果なんとなく雰囲気が分かったので，好きなようにHarrothを真似て作ってみます．

文法を（いい加減に）考える

forthの文法では，何かのコード片に名前をつけるのは

:NAME <code>;

とします．:（コロン）の後，;（セミコロン）の前の空白は無視されます．またansiのforth仕様書（のドラフト）を眺めると，各種の命令が大文字だったり数字記号交じりだったりします．

個人的に大文字オンリーの名前や数字や記号が入り込んだものはちょっといやなのと，:と;で挟み込んで名前をつけるのも好きではないので，ばっさり整理してしまいます．必要ならあとで整理しましょう．

• 何かの操作や計算を行うものを「オペレータ」（operator）と呼ぶ
• オペレータの操作対象を「オペランド」（operand）と呼ぶ
• オペレータはスタックからオペランドを取得し，結果をスタックにプッシュする
• オペレータは次の正規表現で表記される文字列とする：[a-z]+|==|\[|\]

とりあえず，これくらいを決めておきます．

また，コード片に名前をつける文法をPostScriptと同じに次のようにします．以降，コード片を「ブロック」と呼ぶことにします．

/name { <code> } def

これによって，に名前nameをつけることにします．defは名前付けのためのオペレータとします．/nameと「/」をつけることで「名前」であることを明示します．

いわゆる「リテラル」は整数だけとします．

ASTを考える

Harrorth--のASTを書き換えます．

type AST = [Exp]
data Exp = Push Literal | Invoke Word deriving Show
type Literal = Integer
type Word = String

でした．Expは「定義」のために拡張します．

type AST = [Exp]
data Exp =   Push Literal
           | Invoke Word 
           | NewWord Name AST
           deriving Show                        
type Literal = Integer
type Word    = String
type Name    = String

新しく「定義」を行うために，データコンストラクタNewWordを用意し，名前とブロック内のコードに対応するASTをおきます．こうして

1 2 /a { 3 4 add } def

とすることで，

[Push 1,
 Push 2,
 NewWord "a" 
         [Push 3,
          Push 4,
          Invoke "add"
         ]
]

というASTができあがることを目指します．

パーサ（ほとんど同じ）

まずはほとんど同じなので，Harroth--のものを流用します．ここで，phorthProgの最初の空白の読み飛ばしskipMany spaceをパーサphorthの方に移します．これで「前後の空白」をスキップできます．

phorthProg::Parser AST
phorthProg = do ast <- phorth
                eof
                return ast

phorth::Parser AST
phorth =  do skipMany space
             sepEndBy1 phorthExp (skipMany1 space)

phorthExp::Parser Exp
phorthExp = literal <|> word <|> newWord

literal::Parser Exp
literal = (many1 digit) >>= \x ->return (Push (read x))

word::Parser Exp
word = many1 letter >>= \x ->return (Invoke x)

ただし，今度は新しいオペレータの定義ために，newWord::Parser Expを追加します．

newWord::Parser Exp
newWord =do char '/'
            name <- many1 letter
            skipMany space
            char '{'
            ast <- phorth
            char '}'
            skipMany space
            string "def"
            return $ NewWord name ast

とりあえずまとめます．

{--
phorth.hs 
--}
import Text.ParserCombinators.Parsec

-- AST
type AST = [Exp]
data Exp =   Push Literal
           | Invoke Word 
           | NewWord Name AST
           deriving Show
type Literal = Integer
type Word = String
type Name = String

-- Parser
phorthProg::Parser AST
phorthProg = do -- skipMany space
                ast <- phorth
                eof
                return ast

phorth::Parser AST
phorth = do skipMany space
            sepEndBy1 phorthExp (skipMany1 space)

phorthExp::Parser Exp
phorthExp = literal <|> word <|> newWord

literal::Parser Exp
literal = (many1 digit) >>= \x ->return (Push (read x))

word::Parser Exp
word = many1 letter >>= \x ->return (Invoke x)

newWord::Parser Exp
newWord =do char '/'
            name <- many1 letter
            skipMany space
            char '{'
            ast <- phorth
            char '}'
            skipMany space
            string "def"
            return $ NewWord name ast

このコードで

ghci
GHCi, version 6.8.3: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> :l phorth.hs
[1 of 1] Compiling Main             ( phorth.hs, interpreted )
Ok, modules loaded: Main.
*Main> parseTest phorthProg " 1 2 /a { 3 4 add } def"
Loading package parsec-2.1.0.1 ... linking ... done.
[Push 1,Push 2,NewWord "a" [Push 3,Push 4,Invoke "add"]]

となります．これは期待したものです．仕様的にはかなりアレなのですが，とりあえずそのまま．