在 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 阅读器。这就是递归的力量。
| 练习 |
|---|
|