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

- [第一回：ごりごり編](https://qiita.com/sgmryk/items/18e0a4c72130b2a54986)
- [第二回：Stateモナド編](https://qiita.com/sgmryk/items/dfb0666f44020f4f5e6b)
- 第三回：パーサコンビネータ編←いまここ
- [最終回：Operationalモナド編](https://qiita.com/sgmryk/items/a2931e077f6c170d5f62)

# パーサコンビネータとは
以下の記事がパーサコンビネータの仕組みをわかりやすく解説してくれています。
[Haskell 構文解析 超入門](https://qiita.com/7shi/items/b8c741e78a96ea2c10fe)

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

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

```hs
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型を以下のように拡張する案もあります。

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

# 動作確認
```hs
> 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!」のコードがうまく変換できました。

```hs
> parseTest parseBF "+>hoge+[fuga]-<-"
< [Inc,Next,Inc,Loop [],Dec,Prev,Dec]
```
コメントがあってもうまく無視してくれています。

```hs
> parseTest parseBF "[+>+[+++]-<-"
< parse error at (line 1, column 13):
< unexpected end of input
< expecting "+", "-", ">", "<", ".", ",", "[" or "]"
```
ループの閉じ括弧がたりない場合はちゃんとエラーになってくれます。

```hs
parseTest parseBF "+>+[+++]-]<-"
[Inc,Next,Inc,Loop [Inc,Inc,Inc],Dec]
```
閉じ括弧が多い場合は、途中までしかパースしてくれません。
`many`は失敗するまでパースした結果が返るためです。

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

```hs
> parseTest (catMaybes <$> manyTill bf eof) "+>+[+++]-]<-"
< parse error at (line 1, column 10):
< unexpected ']'
< expecting end of input, "+", "-", ">", "<", ".", "," or "["
```
うまくエラーになりました。

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

```hs
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(ドメイン固有言語)化することに挑戦します。