参考URL

ソース

List

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

パーサー関数は

parseList :: Parser LispVal
parseList = liftM List $ sepBy parseExpr spaces

となります。

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

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

> 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は

DottedList [LispVal] LispVal

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

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

DottedListのパーサー関数は

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

です。

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

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

> 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,"とすると、

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

今度は成功しました。

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

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

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

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

head <- endBy parseExpr spaces

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

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

次にtailは

tail <- char '.' >> spaces >> parseExpr

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

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

return $ DottedList head tail

Quoted

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

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

parseQuoted :: Parser LispVal
parseQuoted = do
   char '\''
   x <- parseExpr
   return $ List [Atom "quote", x]

単純に「'」を取り除いて、次に続くLispValをxに格納して
[Atom "quote", x]といった形のリストにして
ListコンストラクタでLispValにしています。

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

parseExpr

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

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は文字列を受け付けるパーサ関数です。)

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

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

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

> parse (try (string "#1") <|> (string "#2")) "test" "#2"
Right "#2"