Brainf*ckインタプリタをつくりながら学ぶHaskell（第三回：パーサコンビネータ編）

• 第一回：ごりごり編
• 第二回：Stateモナド編
• 第三回：パーサコンビネータ編←いまここ
• 最終回：Operationalモナド編

パーサコンビネータとは

以下の記事がパーサコンビネータの仕組みをわかりやすく解説してくれています。
Haskell 構文解析 超入門

BF型のパーサを作る

文字列をBF型に変換するパーサをつくります。

data BF = Inc | Dec | Next | Prev | PutC | GetC | Loop [BF] deriving Show

bf :: Stream s Identity Char => Parsec s u BF
bf = choice [
  Inc  <$ char '+',
  Dec  <$ char '-',
  Next <$ char '>',
  Prev <$ char '<',
  PutC <$ char '.',
  GetC <$ char ',',
  Loop <$> between (char '[') (char ']') (many bf)
  ]

単純に定義すると上記のようなパーサになります。
choiceは配列の先頭パーサから順番に評価して、失敗したら次のパーサを評価します。
(<$) :: Functor f => a -> f b -> f aはFunctorの演算子です。
たとえば、Inc <$ char '+'は、'+'という文字をIncにパースします。

Loopは、'['と']'の間に0個以上のBFに変換可能な文字があればパース成功です。

上記を見ると、前回までgetLoopStringなどを使って[]内の文字列を取り出していたのに対して、思ったとおりの定義を与えるだけで変換処理ができる形になっていると思います。

コメントを処理する

上記で定義したbfでは、文字列内にコメント(+-<>.,[]以外の文字)があると、パースに失敗してしまいます。
そこで、コメントが処理できるように修正したいと思います。

bf :: Stream s Identity Char =>  Parsec s u (Maybe BF)
bf = choice [
  Nothing   <$ noneOf "+-<>.,[]",
  Just Inc  <$ char '+',
  Just Dec  <$ char '-',
  Just Next <$ char '>',
  Just Prev <$ char '<',
  Just PutC <$ char '.',
  Just GetC <$ char ',',
  Just . Loop <$> between (char '[') (char ']') parseBF
  ]

parseBF :: Stream s Identity Char => Parsec s u [BF]
parseBF = catMaybes <$> many bf

コメントはBF型ではないため、そのままでは型が違ってしまいchoiceの配列内に加えることができません。
そこでMaybeをつかって型を揃えてあげます。

+-<>.,[]以外の文字はコメントなのでBF型に変換できないためNothingを返します。
先程定義したBFのコードに変換できるものはJustにくるみます。

parseBFはcatMaybes :: [Maybe a] -> [a]を使うことでコメント(=Nothing)を削除してMaybeを外しています。

※MaybeをつかわずにBF型を以下のように拡張する案もあります。

data BF = Inc | Dec | Next | Prev | PutC | GetC | Loop [BF] | Comment String deriving Show

動作確認

> parseTest parseBF "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+."
< [Inc,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Loop [Next,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Next,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Next,Inc,Inc,Inc,Inc,Inc,Prev,Prev,Prev,Dec],Next,PutC,Next,Inc,Inc,PutC,Inc,Inc,Inc,Inc,Inc,Inc,Inc,PutC,PutC,Inc,Inc,Inc,PutC,Next,Dec,PutC,Dec,Dec,Dec,Dec,Dec,Dec,Dec,Dec,Dec,Dec,Dec,Dec,PutC,Prev,Inc,Inc,Inc,Inc,Inc,Inc,Inc,Inc,PutC,Dec,Dec,Dec,Dec,Dec,Dec,Dec,Dec,PutC,Inc,Inc,Inc,PutC,Dec,Dec,Dec,Dec,Dec,Dec,PutC,Dec,Dec,Dec,Dec,Dec,Dec,Dec,Dec,PutC,Next,Inc,PutC]

「Hello, world!」のコードがうまく変換できました。

> parseTest parseBF "+>hoge+[fuga]-<-"
< [Inc,Next,Inc,Loop [],Dec,Prev,Dec]

コメントがあってもうまく無視してくれています。

> parseTest parseBF "[+>+[+++]-<-"
< parse error at (line 1, column 13):
< unexpected end of input
< expecting "+", "-", ">", "<", ".", ",", "[" or "]"

ループの閉じ括弧がたりない場合はちゃんとエラーになってくれます。

parseTest parseBF "+>+[+++]-]<-"
[Inc,Next,Inc,Loop [Inc,Inc,Inc],Dec]

閉じ括弧が多い場合は、途中までしかパースしてくれません。
manyは失敗するまでパースした結果が返るためです。

最後までパースさせたいので、manyTillを使います。

> parseTest (catMaybes <$> manyTill bf eof) "+>+[+++]-]<-"
< parse error at (line 1, column 10):
< unexpected ']'
< expecting end of input, "+", "-", ">", "<", ".", "," or "["

うまくエラーになりました。

完成

動作確認でうまくいかなかった部分を修正して最終的にこうなりました。
どういったパース処理がおこなわれているかが見た目でわかりやすいと思います。

bf :: Stream s Identity Char =>  Parsec s u (Maybe BF)
bf = choice [
  Nothing   <$ noneOf "+-<>.,[]",
  Just Inc  <$ char '+',
  Just Dec  <$ char '-',
  Just Next <$ char '>',
  Just Prev <$ char '<',
  Just PutC <$ char '.',
  Just GetC <$ char ',',
  Just . Loop <$> between (char '[') (char ']') (catMaybes <$> many bf)
  ]

parseBF :: Stream s Identity Char => Parsec s u [BF]
parseBF = catMaybes <$> manyTill bf eof

次回

Freeモナド、CoYonedaをつかってBrainf*ckをDSL(ドメイン固有言語)化することに挑戦します。