Haskell: Harrothチュートリアルを読みながら実装したForthパーサ
Pugsの勉強をしようと考えている方は、以下のリソースを読むと面白いかもしれません。
Harrothチュートリアルでは、Forthというプログラミング言語のパーサをHaskellで実装しながら、パーサについての理解が深められるように書かれています。しかし残念な点が2点あります。第一に、説明で出てくるコードと実際のソースコードに若干の違いがあり、読者の理解を妨げていることです。*1第二に、パーサの核になる部分のコードが欠落していることです。よく書けているチュートリアルなだけに、本当に残念でした。
あと少しのピースがあれば、完成しそうだったので、代わりにそのピースを作ってみました。何回も試行錯誤してパーサが完成した時は、本当に感動しました。
そのパーサのコードは以下の通りです。
% vim MyForth.hs
{-
MyForth - An Implementation of Forth using Haskell (parser only)
This code is based on the Harroth tutorial. You can find that tutorial:
http://www.perlcabal.org/~nothingmuch/harrorth/doc/
* Usage
% ghci MyForth.hs
*MyForth> parseTest forthProgram "2 foo : bar 4 blah ; ding"
[Push 2,Invoke "foo",NewWord "bar" [Push 4,Invoke "blah"],Invoke "ding"]
-}
module MyForth where
import Text.ParserCombinators.Parsec
-- AST
type Forth = [Exp]
data Exp
= Push Literal
| Invoke Word
| NewWord Word Forth
deriving Show
type Literal = Integer
type Word = String
-- Parser
forthProgram :: Parser Forth
forthProgram = do
ast <- forth
eof
return ast
forth :: Parser Forth
forth = sepEndBy forthExp sep
forthExp :: Parser Exp
forthExp = do {lit <- literal; return $ lit}
<|> do {nw <- newWord; return $ nw}
<|> do {w <- word ; return $ w}
literal :: Parser Exp
literal = do
lit <- many1 digit
return $ Push (read lit)
newWord :: Parser Exp
newWord = do
char ':'
maybeSep
name <- wordName
sep
body <- forth
maybeSep
char ';'
return $ NewWord name body
word :: Parser Exp
word = do
name <- wordName
return $ Invoke name
wordName :: Parser String
wordName = do
name <- many1 letter
return name
sep :: Parser ()
sep = skipMany1 space
maybeSep :: Parser ()
maybeSep = skipMany space一番困ったのは、forthExp関数の定義がどこにも書かれていなかったことです。ヒントになったのは、以下の説明とParsecのマニュアルです。それらを読んで何とか復元できました。
`forthExp` is of type `Parser Exp`, meaning that it returns `Exp`s in the parser monad. Recall that an `Exp` is either a definition of a word, a literal, or a word. `forthExp` uses Parsec's `<|>` operator to denote alternatives.
http://www.perlcabal.org/~nothingmuch/harrorth/doc/03.kwid より
ghciで実行してやると、きちんと動作していることがわかります。ちなみにparseTest関数はパーサをテストするための関数で、Parsecで定義されています。
% ghci MyForth.hs *MyForth> parseTest forthProgram "2 foo : bar 4 blah ; ding" [Push 2,Invoke "foo",NewWord "bar" [Push 4,Invoke "blah"],Invoke "ding"]
少しずつですが、Haskellの感覚がわかってきたような気がします。頑張るぞ。
