在 48 小時內編寫你自己的 Scheme/解析
我們將使用 Parsec 庫。要安裝它，你需要 cabal-install，它由 cabal 命令呼叫。
在 Debian/Ubuntu 上：sudo apt-get install cabal-install。或者，你可以使用 ghcup，它適用於許多平臺。
安裝 cabal-install 後，讓我們建立一個專案
$ cabal update
$ mkdir myProject
$ cd myProject
$ cabal init
現在編輯 myProject.cabal，使 parsec 列在 build-depends 列表中，除了 base 之外。
現在，可以使用 cabal run 執行專案
Building executable 'myProject' for myProject-0.1.0.0.. [1 of 1] Compiling Main ( app/Main.hs ) Linking myProject-0.1.0.0/x/myProject/build/myProject/myProject ... Hello, Haskell!
最後一行是程式的輸出。
現在，讓我們嘗試編寫一個非常簡單的解析器。
首先，將這些行新增到 app/Main.hs 的匯入部分（由 cabal init 生成）
import Text.ParserCombinators.Parsec hiding (spaces)
import System.Environment
這使 Parsec 庫函式對我們可用，除了 spaces 函式，它的名稱與我們稍後將定義的函式衝突。
現在，我們將定義一個解析器，它識別 Scheme 識別符號中允許的符號之一
symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"
這是另一個單子示例：在這種情況下，隱藏的“額外資訊”是關於輸入流中位置的所有資訊，回溯記錄，第一個和跟隨集等等。Parsec 為我們處理所有這些。我們只需要使用 Parsec 庫函式 oneOf，它將識別傳遞給它的字串中的任何一個字元。Parsec 提供了許多預構建的解析器：例如，letter 和 digit 是庫函式。正如你將要看到的，你可以將原始解析器組合成更復雜的產生式。
讓我們定義一個函式來呼叫我們的解析器並處理任何可能的錯誤
readExpr :: String -> String
readExpr input = case parse symbol "lisp" input of
Left err -> "No match: " ++ show err
Right val -> "Found value"
從型別簽名中可以看出，readExpr 是一個從 String 到 String 的函式（->）。我們命名引數為 input，並將其與上面定義的 symbol 解析器一起傳遞給 Parsec 函式 parse。parse 的第二個引數是輸入的名稱。它用於錯誤訊息。
parse 可以返回解析的值或錯誤，因此我們需要處理錯誤情況。遵循典型的 Haskell 慣例，Parsec 返回一個 Either 資料型別，使用 Left 建構函式表示錯誤，使用 Right 建構函式表示正常值。
我們使用 case...of 結構將 parse 的結果與這些備選方案匹配。如果我們得到一個 Left 值（錯誤），那麼我們將錯誤本身繫結到 err 並返回“無匹配”和錯誤的字串表示。如果我們得到一個 Right 值，我們將它繫結到 val，忽略它，並返回字串“找到值”。
case...of 結構是模式匹配的一個例子，我們將在 後面 更詳細地看到。
最後，我們需要修改主函式以呼叫 readExpr 並列印結果
main :: IO ()
main = do
(expr:_) <- getArgs
putStrLn (readExpr expr)
要編譯和執行它，可以在“可執行目標”之後指定命令列引數，該“可執行目標”是專案腳手架在第一節中使用 init 呼叫生成的。例如
$ cabal run myProject $ Found value $ cabal run myProject a No match: "lisp" (line 1, column 1): unexpected "a"
接下來，我們將對我們的解析器進行一系列改進，使其能夠識別越來越複雜的表示式。如果在符號之前有空白，當前解析器會卡住
$ cabal run myProject " %" No match: "lisp" (line 1, column 1): unexpected " "
讓我們修復它，以便忽略空白。
首先，讓我們定義一個解析器，它識別任意數量的空白字元。順便說一下，這就是我們在匯入 Parsec 時包含 hiding (spaces) 子句的原因：該庫中已經有一個 spaces 函式，但它不能完全滿足我們的需求。（事實上，還有一個名為 lexeme 的解析器，它完全滿足我們的需求，但出於教學目的我們將忽略它。）
spaces :: Parser ()
spaces = skipMany1 space
正如函式可以傳遞給函式一樣，操作也可以傳遞給操作。這裡我們將 Parser 操作 space 傳遞給 Parser 操作 skipMany1，以獲取一個能夠識別一個或多個空格的 Parser。
現在，讓我們編輯我們的解析函式，使其使用這個新的解析器
readExpr input = case parse (spaces >> symbol) "lisp" input of
Left err -> "No match: " ++ show err
Right val -> "Found value"
我們在第二課中簡要介紹了 >>（“繫結”）運算子，在那裡我們提到它是在幕後用來組合 do 塊的各行的。這裡，我們顯式地使用它來組合我們的空白和符號解析器。但是，繫結在 Parser 和 IO 單子中具有完全不同的語義。在 Parser 單子中，繫結意味著“嘗試匹配第一個解析器，然後嘗試使用剩餘的輸入匹配第二個解析器，如果任何一個失敗則失敗”。一般來說，繫結在不同的單子中會產生截然不同的效果；它旨在作為一種構建計算的通用方式，因此需要足夠通用以適應所有不同型別的計算。閱讀單子的文件以準確瞭解它的作用。
編譯並執行這段程式碼。請注意，由於我們根據 skipMany1 定義了 spaces，它將不再識別一個普通的單個字元。相反，你必須在符號前加上一些空白。我們很快就會看到這如何有用
$ cabal run myProject " %" Found value $ cabal run myProject % No match: "lisp" (line 1, column 1): unexpected "%" expecting space $ cabal run myProject " abc" No match: "lisp" (line 1, column 4): unexpected "a" expecting space
現在，解析器並沒有真正做太多事情——它只是告訴我們給定的字串是否可以識別。一般來說，我們希望從解析器中獲得更多東西：我們希望它們將輸入轉換為一個數據結構，我們可以輕鬆地遍歷它。在本節中，我們將學習如何定義資料型別，以及如何修改解析器，使其返回此資料型別。
首先，我們需要定義一個數據型別，它可以儲存任何 Lisp 值
data LispVal = Atom String
| List [LispVal]
| DottedList [LispVal] LispVal
| Number Integer
| String String
| Bool Bool
這是一個代數資料型別的例子：它定義了 LispVal 型別變數可以儲存的一組可能的值。每個備選方案（稱為建構函式，用 | 分隔）都包含一個建構函式的標籤以及建構函式可以儲存的資料型別。在這個例子中，一個 LispVal 可以是
- 一個
Atom，它儲存一個字串，命名原子 - 一個
List，它儲存其他 LispVal 的列表（Haskell 列表用方括號表示）；也稱為適當列表 - 一個
DottedList，表示 Scheme 形式(a b . c)；也稱為不適當列表。它儲存除了最後一個元素之外的所有元素，然後將最後一個元素儲存為另一個欄位 - 一個
Number，包含一個 Haskell 整數 - 一個
String，包含一個 Haskell 字串 - 一個
Bool，包含一個 Haskell 布林值
建構函式和型別具有不同的名稱空間，因此你可以同時擁有名為 String 的建構函式和名為 String 的型別。型別和建構函式標籤始終以大寫字母開頭。
接下來，讓我們新增幾個解析函式，以建立這些型別的值。字串是一個雙引號，後面跟著任意數量的非引號字元，最後是一個閉合的引號
parseString :: Parser LispVal
parseString = do
char '"'
x <- many (noneOf "\"")
char '"'
return $ String x
我們又回到了使用 do 語法而不是 >> 運算子。這是因為我們將檢索解析的值（由 many(noneOf "\"") 返回），並對其進行操作，同時插入一些其他解析操作。一般來說，如果操作不返回值，則使用 >>，如果要將該值立即傳遞給下一個操作，則使用 >>=，否則使用 do 語法。
一旦我們完成了解析並從 many 函式中獲得了 Haskell 字串，我們就使用 String 建構函式（來自我們的 LispVal 資料型別）將其轉換為 LispVal。代數資料型別中的每個建構函式也像一個函式一樣，可以將它的引數轉換為其型別的值。它還可以用作可以在模式匹配表示式左側使用的模式；我們在 第 3.1 課 中看到了一個例子，當時我們將解析器結果與 Either 資料型別中的兩個建構函式匹配。
然後，我們應用內建函式 return 將我們的 LispVal 提升到 Parser 單子中。請記住，do 塊的每一行都必須具有相同的型別，但我們字串建構函式的結果只是一個普通的 LispVal。return 讓我們將它包裝在一個 Parser 操作中，該操作不消耗任何輸入，而是將其作為內部值返回。因此，整個 parseString 操作將具有 Parser LispVal 型別。
$ 運算子是中綴函式應用：它與 return (String x) 相同，但 $ 是右結合且優先順序低，可以讓我們消除一些括號。由於 $ 是一個運算子，因此您可以對它執行任何通常對函式執行的操作：傳遞它，部分應用它等等。在這方面，它的功能類似於 Lisp 函式 apply。
現在讓我們繼續討論 Scheme 變數。一個 原子 是一個字母或符號，後面可以跟任意數量的字母、數字或符號。
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 組合器，選擇運算子 <|>。它嘗試第一個解析器，如果失敗，則嘗試第二個解析器。如果任何一個成功，則它返回該解析器返回的值。第一個解析器必須在消耗任何輸入之前失敗：我們將在後面看到如何實現回溯。
一旦我們讀取了第一個字元和原子的其餘部分，我們需要將它們放在一起。 "let" 語句定義了一個新變數 atom。我們使用列表 cons 運算子 : 來實現這一點。我們也可以使用連線運算子 ++，例如 [first] ++ rest；回想一下，first 只是一個字元，因此我們透過在它周圍加上方括號將其轉換為單元素列表。
然後，我們使用一個 case 表示式來確定要建立和返回哪個 LispVal，並根據 true 和 false 的文字字串進行匹配。下劃線 _ 替代項是一個可讀性技巧：case 塊一直持續到 _ case（或任何導致整個 case 表示式失敗的 case），將 _ 視為一個 萬用字元。因此，如果程式碼繼續執行到 _ case，它總是匹配，並返回 atom 的值。
最後，我們建立了另一個解析器，用於數字。這展示了處理單子值的另一種方法。
parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit
從後向前讀最容易，因為函式應用（$）和函式組合（.）都與右側關聯。parsec 組合器 many1 匹配一個或多個其引數，因此在這裡我們匹配一個或多個數字。我們想從結果字串中構造一個數字 LispVal，但我們有一些型別不匹配。首先，我們使用內建函式 read 將該字串轉換為數字。然後，我們將結果傳遞給 Number 以獲得 LispVal。函式組合運算子 . 建立一個函式，該函式應用其右引數，然後將結果傳遞給左引數，因此我們使用它來組合這兩個函式應用。
不幸的是，many1 digit 的結果實際上是一個 Parser String，因此我們的組合 Number . read 仍然無法對它進行操作。我們需要一種方法來告訴它只對單子內部的值進行操作，從而返回一個 Parser LispVal。標準函式 liftM 正好可以做到這一點，因此我們將 liftM 應用於我們的 Number . read 函式，然後將該結果應用於我們的解析器。
我們還必須在程式的最上面匯入 Monad 模組，以便能夠訪問 liftM
import Control.Monad
這種程式設計風格——高度依賴函式組合、函式應用和將函式傳遞給函式——在 Haskell 程式碼中非常常見。它通常可以讓您在一行程式碼中表達非常複雜的演算法，將中間步驟分解成其他函式，這些函式可以以各種方式組合。不幸的是，這意味著您通常必須從右到左閱讀 Haskell 程式碼，並仔細跟蹤型別。我們將在本教程的其餘部分中看到更多示例，因此希望您能夠對此感到非常熟悉。
讓我們建立一個解析器，它可以接受字串、數字或原子。
parseExpr :: Parser LispVal
parseExpr = parseAtom
<|> parseString
<|> parseNumber
並編輯 readExpr 以呼叫我們的新解析器。
readExpr :: String -> String
readExpr input = case parse parseExpr "lisp" input of
Left err -> "No match: " ++ show err
Right _ -> "Found value"
編譯並執行這段程式碼，您會注意到它接受任何數字、字串或符號，但不接受其他字串。
$ cabal run myProject "\"this is a string\""
Found value
$ cabal run myProject 25
Found value
$ cabal run myProject symbol
Found value
$ cabal run myProject (symbol)
bash: syntax error near unexpected token `symbol'
$ cabal run myProject "(symbol)"
No match: "lisp" (line 1, column 1):
unexpected "("
expecting letter, "\"" or digit
| 練習 |
|---|
|
接下來，我們向直譯器新增幾個解析器操作。從 Lisp 著名的帶括號的列表開始。
parseList :: Parser LispVal
parseList = liftM List $ sepBy parseExpr spaces
它的工作原理類似於 parseNumber，首先解析一系列用空格分隔的表示式（sepBy parseExpr spaces），然後在 Parser 單子中對它應用 List 建構函式。還要注意，我們可以將 parseExpr 傳遞給 sepBy，即使它是我們自己編寫的操作。
帶點列表解析器稍微複雜一些，但仍然只使用我們已經熟悉的概念。
parseDottedList :: Parser LispVal
parseDottedList = do
head <- endBy parseExpr spaces
tail <- char '.' >> spaces >> parseExpr
return $ DottedList head tail
請注意，我們如何使用 >> 將一系列 Parser 操作串聯在一起，然後在 do 語句的右側使用整個序列。表示式 char '.' >> spaces 返回一個 Parser ()，然後將它與 parseExpr 組合得到一個 Parser LispVal，這正是我們對 do 塊需要的型別。
接下來，讓我們新增對 Scheme 單引號語法糖的支援。
parseQuoted :: Parser LispVal
parseQuoted = do
char '\''
x <- parseExpr
return $ List [Atom "quote", x]
其中大部分都是相當熟悉的：它讀取一個單引號字元，讀取一個表示式並將其繫結到 x，然後返回 (quote x)，以使用 Scheme 符號。Atom 建構函式的工作原理類似於普通函式：您將要封裝的字串傳遞給它，它會返回一個 LispVal。您可以對這個 LispVal 執行任何您通常可以執行的操作，例如將其放入列表中。
最後，編輯我們對 parseExpr 的定義以包含我們的新解析器。
parseExpr :: Parser LispVal
parseExpr = parseAtom
<|> parseString
<|> parseNumber
<|> parseQuoted
<|> do char '('
x <- try parseList <|> parseDottedList
char ')'
return x
這說明了 Parsec 的最後一個特性：回溯。parseList 和 parseDottedList 識別到點為止的相同字串；這打破了選擇替代項在失敗之前不能消耗任何輸入的要求。try 組合器嘗試執行指定的解析器，但如果失敗，它將回溯到前一個狀態。這使您可以在選擇替代項中使用它，而不會干擾其他替代項。
編譯並執行這段程式碼。
$ cabal run myProject "(a test)" Found value $ cabal run myProject "(a (nested) test)" Found value $ cabal run myProject "(a (dotted . list) test)" Found value $ cabal run myProject "(a '(quoted (dotted . list)) test)" Found value $ cabal run myProject "(a '(imbalanced parens)" No match: "lisp" (line 1, column 24): unexpected end of input expecting space or ")"
請注意，透過在解析器中引用 parseExpr，我們可以將它們巢狀任意深度。因此，我們只用幾個定義就得到了一個完整的 Lisp 閱讀器。這就是遞迴的力量。
| 練習 |
|---|
|