48時間でSchemeを書こう/構文解析4

# 参考URL
[48時間でSchemeを書こう/構文解析](https://ja.wikibooks.org/wiki/48%E6%99%82%E9%96%93%E3%81%A7Scheme%E3%82%92%E6%9B%B8%E3%81%93%E3%81%86/%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90)

#ソース
https://github.com/0zawa/scheme_in_48_hours/blob/master/parsing.hs

#List
Listのパーサーを作成します。
ListはLispValのリストです。
LispValにはListも含まれるので再帰的な構造を作ることができます。

パーサー関数は

```hs
parseList :: Parser LispVal
parseList = liftM List $ sepBy parseExpr spaces
```
となります。

spacesはスペース文字をパースする(そしてなにも返さない)関数、
parseExprは文字列をLispValにパースする関数です。
sepByは第二引数のパーサ関数で入力文字列を分割して、
それぞれに対して第一引数のパーサー関数を適用します。

カンマ区切りの数値をパースして、リストにするには

```hs
> parse (sepBy (many digit) (char ',')) "csv" "123,456,789"
Right ["123","456","789"]
```

と書きます。
パーサ関数「char ','」で、入力文字列がカンマの位置で分割されて、
分割されたそれぞれに(many digit)が適用されて、結果
Right ["123","456","789"]
が返却されます。

parseListは１文字以上連続したスペース文字で分割し、
それぞれにparseExpr関数を適用します。
その結果得られたParser [LispVal]にliftMでListコンストラクタを適用して、
Parser List [LispVal]型に変換します。
List [LispVal]はLispVal型なので、
結果戻り値の型はParser LispValになります。

# DottedList
DottedListは

```hs
DottedList [LispVal] LispVal
```
と定義されています。
通常のリストにもう一つLispValが加わっています。

DottedListの入力文字列は「1 2 3 . 4」の様な形式になります。
「.」の前が[LispVal]になり、「.」の後がLispValになります。

DottedListのパーサー関数は

```hs
parseDottedList :: Parser LispVal
parseDottedList = do
    head <- endBy parseExpr spaces
    tail <- char '.' >> spaces >> parseExpr
    return $ DottedList head tail
```

です。

headを取得する処理でListで使われたsepByではなくendByが使われています。

endByをさきほどsepByで使用した例に当てはめてみると、

```hs
> parse (endBy (many digit) (char ',')) "csv" "123,456,789"
Left "csv" (line 1, column 12):
unexpected end of input
expecting digit or ","
```

エラーになりました。
unexpected end of input
expecting digit or ","
とあるので、入力文字列の最後に「,」を加えて"123,456,789,"とすると、

```hs
> parse (endBy (many digit) (char ',')) "csv" "123,456,789,"
Right ["123","456","789"]
```
今度は成功しました。

つまりendByはsepByと異なり、最後に付く文字を基準に分割する
パース関数のようです。

「,」ではなく「;」にすると用途がわかりやすいかもしれません。

```hs
> parse (endBy (many (letter <|> digit <|> (char '='))) (char ';')) "csv" "a=1;b=2;c=3;"
Right ["a=1","b=2","c=3"]
```

DottedListに戻るとheadは各要素の最後にスペースがあるものが入ります。

```hs
head <- endBy parseExpr spaces
```

「1 2 3 . 4」
といった入力文字列を考えると「.」もheadに入りそうですが、
symbolで指定した記号に「.」は含まれていないため、
「.」はparseExprでパースされません。

結果「1 2 3 」がパースされ「. 4」が残ります。

次にtailは

```hs
tail <- char '.' >> spaces >> parseExpr
```
となっています。「>>」演算子は結果を次の関数に渡さない演算子なので
char '.'とspacesでパースした結果は破棄されます。
入力文字列としては「4」が残りこれがparseExprでパースされ
tailに格納されます。

最終的にDottedListコンストラクタでheadとtailを結合して
Parserで包んだLispVal型にして返却します。

```hs
return $ DottedList head tail
```

# Quoted
「構文解析」の最後はQuotedです。
入力文字列は「'a」のようにシングルクオートが先頭に付きます。

パーサーは以下のようになります。

```hs
parseQuoted :: Parser LispVal
parseQuoted = do
   char '\''
   x <- parseExpr
   return $ List [Atom "quote", x]
```
単純に「'」を取り除いて、次に続くLispValをxに格納して
[Atom "quote", x]といった形のリストにして
ListコンストラクタでLispValにしています。

Quotedをどのように使うかは今後詳しくみていきます。

# parseExpr
最後にこれまで個々に作成したパーサーをまとめます。

```hs
parseExpr :: Parser LispVal
parseExpr = parseAtom
        <|> parseString
        <|> parseNumber
        <|> parseQuoted
        <|> do char '('
               x <- try parseList <|> parseDottedList
               char ')'
               return x
```

ここでparseList <|> psrseDottedListの前にtry関数が使われています。
try関数はパースに失敗した場合に、入力を消費せずに
次のパーサ関数に渡します。

例として"#1"を受け付けるパーサと"#2"を受け付けるパーサを
<|>で繋いだパーサに"#2"を渡してみます。
(stringは文字列を受け付けるパーサ関数です。)

```hs
> parse ((string "#1") <|> (string "#2")) "test" "#2"
Left "test" (line 1, column 1):
unexpected "2"
expecting "#1"
```

結果はエラーになりました。
string "#1"で"#"が消費されているため、
string "#2"がパースされないようです。

tryを使って書きなおしてもう一度実行してみます。

```hs
> parse (try (string "#1") <|> (string "#2")) "test" "#2"
Right "#2"
```
今度は成功しました。

以上で「構文解析」終了になります。
引き続き解析後の評価に進んでいきます。