原文。
https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/Parsing

一個簡單的解析器

現(xiàn)在，讓我們試著寫一個非常簡單的解析器。我們會用到Parsec庫。（如果你還沒有安裝的話，可以通過Haskell平臺下載或者直接使用它的源代碼。根據(jù)你的編譯器的版本，選擇對應(yīng)的代碼包并編譯它。在Ubuntu系統(tǒng)上的話，直接運(yùn)行命令sudo apt-get install cabal-install;cabal update;cabal install parsec來安裝）

添加一行到導(dǎo)入模塊的部分：

import Text.ParserCombinators.Parsec hiding (spaces)
import  System.Environment

這樣我們就可以使用Parsec庫中的函數(shù)了，除了一個等下會和我們自己定義的函數(shù)名沖突的spaces函數(shù)。

現(xiàn)在讓我們定義一個能夠識別出Scheme中允許的符號的解析器：

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

這又是一個Monad的例子：在這里，被隱藏的“額外信息”包括在輸入流中的位置，回溯記錄以及First和Follow集等。Parsec會替我們解決這個問題。而我們只需要去調(diào)用Parsec庫中的函數(shù)oneOf，它就會替我們將傳遞給它的字符串中的任意一個識別出來。Parsec庫提供了一些內(nèi)置的解析器：例如letter和digit函數(shù)。正如你將看到的，你可以將基本的函數(shù)組合成更加復(fù)雜的解析器。

讓我們定義一個調(diào)用解析器并且處理可能的錯誤的函數(shù)：

readExpr :: String -> String
readExpr input = case parse symbol "lisp" input of 
    Left err -> "No match: " ++ show err 
    Right val -> "Found value"

正如你從類型簽名看到的一樣，readExpr是一個將String轉(zhuǎn)化成String的函數(shù)（->）。我們把傳入的參數(shù)命名為input，然后把它和我們之前定義的名叫symbol的解析器一起傳遞給parse函數(shù)。傳遞的第二個參數(shù)是我們給輸入定義的名稱，這會在顯示錯誤信息的時候用到。parse會返回一個被解析的返回值或者一個錯誤，因此我們是需要處理錯誤情況的。根據(jù)標(biāo)準(zhǔn)的Haskell編程規(guī)約，Parsec返回一個Either類型，用他得Left構(gòu)造器表示錯誤并且用Right構(gòu)造器來表示普通的值。

我們使用一個case...of的語句來對parse的各種可能的返回值進(jìn)行匹配。如果我們得到一個Left值（錯誤），那我們就把這個error綁定給變量err然后在開頭加上字符串“No match ”然后返回。如果我們得到一個Right值，我們把它綁定給val，然后無視它并返回一個“Found value”字符串。

我們可以看到使用case...of來進(jìn)行模式匹配的例子，之后我們會繼續(xù)看到很多類似的做法的。

最后，我們需要修改我們的main函數(shù)來調(diào)用readExpr并且打印出結(jié)果：

main :: IO ()
main = do 
    (expr:_) <- getArgs 
    putStrLn (readExpr expr)

為了編譯并運(yùn)行程序，需要在命令行指定--make參數(shù)，否則就會爆出鏈接錯誤。舉個栗子：

$ ghc --make -o simple_parser listing3.1.hs
$ ./simple_parser $
Found value
$ ./simple_parser a
No match: "lisp" (line 1, column 1):
unexpected "a"

空格

接下來，我們會對我們的解析器添加一系列改動來使它能夠漸漸識別出我們給出的更加復(fù)雜的表達(dá)式?，F(xiàn)在的解析器在遇到空白的時候就會卡住了：

$ ./simple_parser "   %"
No match: "lisp" (line 1, column 1):
unexpected " "

讓我們來修正這個問題，并且忽略掉輸入中的空格符。

首先，我們定義一個能夠辨認(rèn)出任意數(shù)量空格的解析器。順便，這也是我們之前在導(dǎo)入Parsec模塊的時候添加了hiding (spaces)的原因：模塊中已經(jīng)有一個spaces
函數(shù)了，但卻不大符合我們的要求。（不過有一個叫做lexeme的解析器完全符合我們的要求，不過出于教學(xué)目的，我們暫時先無視它。）

spaces :: Parser ()
spaces = skipMany1 space

就像函數(shù)一樣，操作也能傳遞給其他操作。在這里我們把Parser操作space 傳遞給Parser操作skipMany1，來獲取到一個能夠解析一個或者多個空格的解析器。

現(xiàn)在，我們來編輯一下我們的解析函數(shù)：

readExpr input = case parse (spaces >> symbol) "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found value"

我們在第二課里簡單看過一點(diǎn)關(guān)于>>("bind")操作符的內(nèi)容，并且提到我們是把它放在do代碼塊中的每行的行尾來起到連接作用的。這里，我們顯式的使用它來將我們的空格解析器和之前的符合解析器組合起來。然而，相比IO Monad綁定在Parser中有著完全不同的語義。
對于Parser Monad來說，綁定意味著“嘗試匹配第一個解析器，然后用剩下的輸入嘗試匹配第二個，如果任意一次匹配失敗的話，就返回失敗”?？偟膩碚f，綁定在具體的Monad中會起到不同的效果；它被用作一種通用的組織計算的方式，所以能夠適應(yīng)各種不同的情況。你可以閱讀對應(yīng)的文檔來判斷出它到底會干什么。

編譯并且運(yùn)行代碼。請注意我們這里的spaces函數(shù)是基于skipMany1定義的，他不會再像之前那樣能夠識別出單個的字符。因此你必須放一些空格在輸入字符的前面?？聪卢F(xiàn)在代碼是如何運(yùn)作的：

$ ghc -package parsec -o simple_parser [../code/listing3.2.hs listing3.2.hs]
$ ./simple_parser "   %"
Found value
$ ./simple_parser %
No match: "lisp" (line 1, column 1):
unexpected "%"
expecting space
$ ./simple_parser "   abc"
No match: "lisp" (line 1, column 4):
unexpected "a"
expecting space 

返回值

現(xiàn)在，我們的解析器還并不能做些什么---它僅僅是告訴我們一個給定的字符串是否能夠被識別?，F(xiàn)在，我們想讓它能夠做更多的事情：我們希望它能夠?qū)⑤斎氲淖址D(zhuǎn)換成一個特定的數(shù)據(jù)結(jié)構(gòu)并讓我們可以容易的遍歷它。在這一節(jié)，我們將學(xué)習(xí)如何定義一個數(shù)據(jù)類型，并且修改我們的解析器讓它能夠返回該數(shù)據(jù)類型。

首先，我們來定義一個包含所有各種Lisp值得數(shù)據(jù)類型：

data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | String String
             | Bool Bool

這是一個代數(shù)數(shù)據(jù)類型的例子：它定義了一組LispVal類型的變量可能存儲的值。每一個可能性（通過“|”符號分割的構(gòu)造器）包含了一個代表構(gòu)造器的標(biāo)識符和這個構(gòu)造器能夠接受的一系列數(shù)據(jù)類型。在這里，一個LispVal可能是：

1. Atom。存儲了一個用來命名它的字符串
2. List。其中存儲了一組其他LispVal（Haskell列表用方括號表示），也被稱為Proper List。
3. DottedList。對應(yīng)Scheme中的(a b . c)形式。也被稱作Improper List。存儲了除最后一個元素以外的所有元素，然后再把最后一個元素額外存儲起來。
4. Number。包含一個Haskell數(shù)字。
5. String。包含一個Haskell字符串。
6. Bool。包含一個Haskell布爾值。

構(gòu)造器和類型使用的是不同的命名空間，所以你同時將一個類型名和構(gòu)造器都定義成String，并沒有問題。唯一要注意的是，它們都需要以大寫字母開頭。

接下來，我們來添加一些解析函數(shù)來返回對應(yīng)的不同類型。一個字符串總是一個以雙引號開頭，然后接著一串不包含雙引號的字符，最終以另一個雙引號結(jié)束：

parseString :: Parser LispVal
parseString = do
                char '"'
                x <- many (noneOf "\\"")
                char '"'
                return $ String x

我們再次使用do表達(dá)式而不是>>操作符來組織代碼。只是因?yàn)槲覀冃枰@取解析得到的值（many (noneOf "\\"")的返回值）并且同時使用一些其他的解析操作?？偟膩碚f，對于不返回值得操作，使用>>符號，對于你需要立刻將返回的值傳遞到下一個操作的情況，使用>>=，其余的情況則用do代碼塊比較好。

當(dāng)我們完成解析并從many函數(shù)中獲取Haskell字符串時，我們調(diào)用了String構(gòu)造器（LispVal數(shù)據(jù)類型）來把它轉(zhuǎn)化成一個LispVal類型的值。每一個在代數(shù)數(shù)據(jù)類型中的構(gòu)造器都能夠像函數(shù)一樣將傳遞給它的參數(shù)轉(zhuǎn)化成它對應(yīng)的類型。構(gòu)造器還能夠在模式匹配中作為左手邊的匹配表達(dá)式進(jìn)行使用；我們會在第三課里嘗試將解析器返回的結(jié)果分別用Either類型的兩種構(gòu)造器進(jìn)行匹配。

接著我們使用內(nèi)置的return函數(shù)將我們的LispVal值lift成一個Parser Monad。注意，do代碼塊中的每行都必須有同樣的類型，然而由于我們的String構(gòu)造器的返回結(jié)果是LispVal類型，因此我們要利用return幫助將它風(fēng)中成一個Parser操作并且在不消費(fèi)任何輸入的情況下直接將內(nèi)部的值進(jìn)行返回。這樣我們的整個parserString操作就能夠得到Parser LispVal類型的返回值了。

$符號是一個中綴函數(shù)呼叫符：它和我們直接使用return (String x)的作用一樣，但是$是右結(jié)合的，并且運(yùn)行的優(yōu)先級較低，這樣讓我們能夠省略掉一些原來需要寫得括號。由于$是一個操作符，你可以像使用函數(shù)那樣使用它做任何事情：傳遞它，部分調(diào)用等。在這個方面，它和Lisp中的apply函數(shù)功能一致。

現(xiàn)在繼續(xù)來看Scheme的變量。一個atom是一個字母或者符號，跟著若干個字母，數(shù)字或者符號：

parseAtom :: Parser LispVal
parseAtom = do 
              first <- letter <|> symbol
              rest <- many (letter <|> digit <|> symbol)
              let atom = first:rest
              return $ case atom of 
                         "#t" -> Bool True
                         "#f" -> Bool False
                         _    -> Atom atom

這里我們來看下另一個Parsec的組合符，選擇符<|>。它會讓我們首先嘗試第一個解析器，如果它失敗了，然后嘗試第二個。如果任意一個成功了，那就會返回成功解析出得值。第一個解析器必須在它消費(fèi)掉任何輸入前失敗返回：我們待會兒來看看如何用它來實(shí)現(xiàn)回溯。

一旦我們讀到第一個字符和并成功讀完剩下的部分，我們需要把它們放在一起組成一個atom。let聲明定義了一個新的變量atom。我們使用列表連接符:來連接它們。和:相對應(yīng)的，我們使用連接符++像這樣來連接列表[first]++rest；first只是一個字符，我們可以用方括號包圍它來將它轉(zhuǎn)換成一個單元素的列表。

然后我們使用一個case表達(dá)式來嘗試將字符串匹配成true和false，從而判斷到底是應(yīng)該創(chuàng)建和返回哪種LispVal類型。下劃線符號\是一個可讀性的技巧：目標(biāo)會不斷嘗試匹配case塊中的值直到遇到\（或者在此之前就因?yàn)槟承┊惓Ｊ×藦亩鴮?dǎo)致整個匹配失?。┎⒆鳛橐粋€通配符返回。因此如果代碼運(yùn)行到_條件下，它總是會匹配并且返回一個atom值。

最后，我們再為數(shù)字創(chuàng)建一個解析器。這里會展示更多的方法來處理monadic值：

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

從右往左看會讓你很容易理解這個表達(dá)式，因?yàn)楹瘮?shù)呼叫符($)和函數(shù)組合符(.)函數(shù)都是右結(jié)合的。結(jié)合器many1會匹配目標(biāo)的一個或者多個傳遞給它的參數(shù)，這里我們會匹配到一個或者多個數(shù)字。我們會用返回的字符串來構(gòu)建出一個數(shù)字的LispVal類型，不過這里我們貌似有一些類型上的匹配問題。因此首先，我們用內(nèi)建的read函數(shù)來將字符串轉(zhuǎn)化為數(shù)字。然后我們再把數(shù)字傳遞給Number構(gòu)造器得到一個LispVal類型的值。我們用函數(shù)組合符創(chuàng)建出一個將右邊參數(shù)的調(diào)用結(jié)果傳遞給左邊參數(shù)的函數(shù)，因此我們就這樣將兩個函數(shù)調(diào)用結(jié)合起來了。

不幸的是，many1 digit的返回值是一個Parser String，所以我們的經(jīng)過結(jié)合的Number . Read函數(shù)仍然不能直接對它進(jìn)行操作。我們需要一種告訴它只操作Monad里的值的方法，然后再把處理后的結(jié)果返回給Parser LispVal。而標(biāo)準(zhǔn)庫中的liftM函數(shù)剛好能幫助我呢，所以我們對我們的函數(shù)Number . Read使用liftM，然后把結(jié)果對Parser進(jìn)行調(diào)用。

我們需要在程序頂部導(dǎo)入Monad模塊來使用liftM函數(shù)：

import Control.Monad

這種不斷進(jìn)行函數(shù)組合，函數(shù)調(diào)用和函數(shù)傳遞的編程風(fēng)格在Haskell代碼中是非常常見的。這會讓你能夠在一行中表達(dá)出非常復(fù)雜的邏輯，并把中間的階段分解成其它可以用各種方式結(jié)合起來的函數(shù)。不幸的是，這表明你需要常常從右向左閱讀Haskell代碼并且注意跟蹤它們的類型。在后面的教程中我們會看到更多的例子，所以你應(yīng)該會馬上能適應(yīng)這種方式。

創(chuàng)建一個能夠接受字符串，數(shù)字或是Atom的解析器：

parseExpr :: Parser LispVal
parseExpr = parseAtom
         <|> parseString
         <|> parseNumber

編輯readExpr函數(shù)讓它調(diào)用我們的新解析器：

readExpr :: String -> String
readExpr input = case parse parseExpr "lisp" input of
    Left err -> "No match: " ++ show err
    Right _ -> "Found value"

編譯并運(yùn)行代碼，你就能發(fā)現(xiàn)它接受任意的數(shù)字，字符串或者符號并且能夠拒絕其他的情況了：

$ ghc -package parsec -o simple_parser [.../code/listing3.3.hs listing3.3.hs]
$ ./simple_parser "\\"this is a string\\""
Found value
$ ./simple_parser 25
Found value
$ ./simple_parser symbol
Found value
$ ./simple_parser (symbol)
bash: syntax error near unexpected token `symbol'
$ ./simple_parser "(symbol)"
No match: "lisp" (line 1, column 1):
unexpected "("
expecting letter, "\\"" or digit

習(xí)題

1. 重寫parseNumber函數(shù)，不允許使用liftM，嘗試
   1. 使用do代碼塊
   2. 顯式的運(yùn)用>>=操作符來進(jìn)行連接
2. 我們的字符串并不太符合R5RS規(guī)范，因?yàn)樗鼈儾恢С衷谧址锸褂棉D(zhuǎn)義之后的引號。修改parseString函數(shù)讓\”表示一個引號字符而不是整個字符串的結(jié)束。你可能需要用一個新的解析器操作來替換noneOf “\””從而讓它能接受非引號字符或者一個轉(zhuǎn)義符號之后的引號字符。
3. 修改程序，讓它支持\\n \\r \\t \\\\\\\\以及其它你希望轉(zhuǎn)義的字符。
4. 修改parseNumber讓它提供Scheme標(biāo)準(zhǔn)中對不同進(jìn)制的支持。readOct和readHex函數(shù)或許會對你很有用。
5. 給LispVal增加一個字符構(gòu)造器，然后為R5RS標(biāo)準(zhǔn)中定義的字符創(chuàng)造一個解析器。
6. 給LispVal增加一個浮點(diǎn)數(shù)構(gòu)造器來支持R5RS中的小數(shù)相關(guān)的語法。參考Haskell中的readFloat函數(shù)。
7. 增加數(shù)據(jù)類型和解析器從而支持Scheme中的full numeric tower。Haskell已經(jīng)有內(nèi)建類型來表示其中的部分內(nèi)容，你可以通過Prelude模塊確認(rèn)。至于其它，你可以通過定義復(fù)合類型的方法來表示它們。例如，一個分?jǐn)?shù)可以用分子和分母表示而一個復(fù)數(shù)可以用實(shí)部和虛部來表示（每一部分都是一個實(shí)數(shù)）。

遞歸解析：列表和引號

接下來，給我們的解釋器添加更多的解析器。從Lisp的知名括號列表開始：

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

和parserNumber類似的，首先解析一系列由空格分隔開的表達(dá)式（sepBy parseExpr spaces），然后在Parser Monad內(nèi)部調(diào)用構(gòu)造符將它們組成一個List。注意我們能夠把parseExpr直接傳遞給sepBy，盡管它是一個我們自己寫的操作。

dotted-list的解析器稍微會復(fù)雜一點(diǎn)，不過仍然只是需要使用我們已經(jīng)熟悉的概念：

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

注意我們是怎么使用>>把一系列的Parser操作連接起來并且do代碼塊中運(yùn)用它的。表達(dá)式char '.' >> spaces返回一個Parser()，然后通過與parseExpr結(jié)合產(chǎn)生一個Parser LispVal類型，完全和我們在do代碼塊中需要的類型一致。

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

大部分都是我們已經(jīng)熟悉了的內(nèi)容了：這段程序讀取一個單個的引號字符，讀取一個表達(dá)式然后把它綁定給x，然后返回(quote x)，來表達(dá)一個Scheme符號。Atom構(gòu)造器就像一個普通函數(shù)一樣：你傳遞一個需要封裝的字符串給它，然后它返回給你一個LispVal類型的值。你可以對這個LispVal做任何你一般情況下能做的事情，比如把它放入一個列表里。

最后，編輯parseExpr函數(shù)來把我們的新解析器添加進(jìn)去：

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

這里演示了最后一個Parsec的功能：回溯。parseList和parseDottedLis直到某個特定的位置都能夠識別出相同的字符串；這打破了一個選擇不能在出錯前消費(fèi)任何輸入的前提。而try連接器試圖運(yùn)行某個的解析器，但是如果解析失敗了，它會回滾到上一個狀態(tài)。這讓你在不影響其它分支的前提下對目標(biāo)進(jìn)行各種操作。

編譯然后運(yùn)行：

$ ghc -package parsec -o simple_parser [../code/listing3.4.hs listing3.4.hs]
$ ./simple_parser "(a test)"
Found value
$ ./simple_parser "(a (nested) test)"
Found value
$ ./simple_parser "(a (dotted . list) test)"
Found value
$ ./simple_parser "(a '(quoted (dotted . list)) test)"
Found value
$ ./simple_parser "(a '(imbalanced parens)"
No match: "lisp" (line 1, column 24):
unexpected end of input
expecting space or ")"

注意我們可以在parseExpr里任意深入的嵌套我們的解析器。這樣，我們通過一些簡單的定義就能夠完全的讓程序閱讀Lisp代碼了。這就是遞歸的威力。

習(xí)題

1. 添加backquote語法糖的支持：Scheme標(biāo)準(zhǔn)詳述了它應(yīng)該怎樣展開成（quasiquote/unquote）。
2. 添加vectors的支持。你可以使用Haskell的內(nèi)置實(shí)現(xiàn)Array
   ，但是它使用起來可能會有些問題。嚴(yán)格說，一個vector應(yīng)該有常數(shù)時間的索引和更新操作，但是事實(shí)上直接的更新操作在一個純函數(shù)式語言里是很難實(shí)現(xiàn)的。你可能在看過該系列教程的后面的章節(jié)后會對如何實(shí)現(xiàn)它有更好的想法。
3. 如果不用try組合符的話，你需要將目標(biāo)從左邊開始分解并在接下來調(diào)用parseExpr解析器自身。最后需要用一個解析器對字符串進(jìn)行匹配，它要么是空要么是一個點(diǎn)符號加上一個單元素的表達(dá)式。這里把這個有趣的練習(xí)留給你：把它們的返回值組合成一個要么是List要么是DottedList的Either類型：你也許需要把判斷邏輯分解到另外一個輔助函數(shù)里。