Write Yourself a Scheme in 48 Hours/Parsing

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

一个简单的解析器

现在，让我们试着写一个非常简单的解析器。我们会用到Parsec库。（如果你还没有安装的话，可以通过Haskell平台下载或者直接使用它的源代码。根据你的编译器的版本，选择对应的代码包并编译它。在Ubuntu系统上的话，直接运行命令sudo apt-get install cabal-install;cabal update;cabal install parsec来安装）

添加一行到导入模块的部分：

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

这样我们就可以使用Parsec库中的函数了，除了一个等下会和我们自己定义的函数名冲突的spaces函数。

现在让我们定义一个能够识别出Scheme中允许的符号的解析器：

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

这又是一个Monad的例子：在这里，被隐藏的“额外信息”包括在输入流中的位置，回溯记录以及First和Follow集等。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的解析器一起传递给parse函数。传递的第二个参数是我们给输入定义的名称，这会在显示错误信息的时候用到。parse会返回一个被解析的返回值或者一个错误，因此我们是需要处理错误情况的。根据标准的Haskell编程规约，Parsec返回一个Either类型，用他得Left构造器表示错误并且用Right构造器来表示普通的值。

我们使用一个case...of的语句来对parse的各种可能的返回值进行匹配。如果我们得到一个Left值（错误），那我们就把这个error绑定给变量err然后在开头加上字符串“No match ”然后返回。如果我们得到一个Right值，我们把它绑定给val，然后无视它并返回一个“Found value”字符串。

我们可以看到使用case...of来进行模式匹配的例子，之后我们会继续看到很多类似的做法的。

最后，我们需要修改我们的main函数来调用readExpr并且打印出结果：

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

为了编译并运行程序，需要在命令行指定--make参数，否则就会爆出链接错误。举个栗子：

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

空格

接下来，我们会对我们的解析器添加一系列改动来使它能够渐渐识别出我们给出的更加复杂的表达式。现在的解析器在遇到空白的时候就会卡住了：

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

让我们来修正这个问题，并且忽略掉输入中的空格符。

首先，我们定义一个能够辨认出任意数量空格的解析器。顺便，这也是我们之前在导入Parsec模块的时候添加了hiding (spaces)的原因：模块中已经有一个spaces
函数了，但却不大符合我们的要求。（不过有一个叫做lexeme的解析器完全符合我们的要求，不过出于教学目的，我们暂时先无视它。）

spaces :: Parser ()
spaces = skipMany1 space

就像函数一样，操作也能传递给其他操作。在这里我们把Parser操作space 传递给Parser操作skipMany1，来获取到一个能够解析一个或者多个空格的解析器。

现在，我们来编辑一下我们的解析函数：

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

我们在第二课里简单看过一点关于>>("bind")操作符的内容，并且提到我们是把它放在do代码块中的每行的行尾来起到连接作用的。这里，我们显式的使用它来将我们的空格解析器和之前的符合解析器组合起来。然而，相比IO Monad绑定在Parser中有着完全不同的语义。
对于Parser Monad来说，绑定意味着“尝试匹配第一个解析器，然后用剩下的输入尝试匹配第二个，如果任意一次匹配失败的话，就返回失败”。总的来说，绑定在具体的Monad中会起到不同的效果；它被用作一种通用的组织计算的方式，所以能够适应各种不同的情况。你可以阅读对应的文档来判断出它到底会干什么。

编译并且运行代码。请注意我们这里的spaces函数是基于skipMany1定义的，他不会再像之前那样能够识别出单个的字符。因此你必须放一些空格在输入字符的前面。看下现在代码是如何运作的：

$ 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

返回值

现在，我们的解析器还并不能做些什么---它仅仅是告诉我们一个给定的字符串是否能够被识别。现在，我们想让它能够做更多的事情：我们希望它能够将输入的字符串转换成一个特定的数据结构并让我们可以容易的遍历它。在这一节，我们将学习如何定义一个数据类型，并且修改我们的解析器让它能够返回该数据类型。

首先，我们来定义一个包含所有各种Lisp值得数据类型：

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

这是一个代数数据类型的例子：它定义了一组LispVal类型的变量可能存储的值。每一个可能性（通过“|”符号分割的构造器）包含了一个代表构造器的标识符和这个构造器能够接受的一系列数据类型。在这里，一个LispVal可能是：

  1. Atom。存储了一个用来命名它的字符串
  2. List。其中存储了一组其他LispVal（Haskell列表用方括号表示），也被称为Proper List。
  3. DottedList。对应Scheme中的(a b . c)形式。也被称作Improper List。存储了除最后一个元素以外的所有元素，然后再把最后一个元素额外存储起来。
  4. Number。包含一个Haskell数字。
  5. String。包含一个Haskell字符串。
  6. Bool。包含一个Haskell布尔值。

构造器和类型使用的是不同的命名空间，所以你同时将一个类型名和构造器都定义成String，并没有问题。唯一要注意的是，它们都需要以大写字母开头。

接下来，我们来添加一些解析函数来返回对应的不同类型。一个字符串总是一个以双引号开头，然后接着一串不包含双引号的字符，最终以另一个双引号结束：

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

我们再次使用do表达式而不是>>操作符来组织代码。只是因为我们需要获取解析得到的值（many (noneOf "\\"")的返回值）并且同时使用一些其他的解析操作。总的来说，对于不返回值得操作，使用>>符号，对于你需要立刻将返回的值传递到下一个操作的情况，使用>>=，其余的情况则用do代码块比较好。

当我们完成解析并从many函数中获取Haskell字符串时，我们调用了String构造器（LispVal数据类型）来把它转化成一个LispVal类型的值。每一个在代数数据类型中的构造器都能够像函数一样将传递给它的参数转化成它对应的类型。构造器还能够在模式匹配中作为左手边的匹配表达式进行使用；我们会在第三课里尝试将解析器返回的结果分别用Either类型的两种构造器进行匹配。

接着我们使用内置的return函数将我们的LispVal值lift成一个Parser Monad。注意，do代码块中的每行都必须有同样的类型，然而由于我们的String构造器的返回结果是LispVal类型，因此我们要利用return帮助将它风中成一个Parser操作并且在不消费任何输入的情况下直接将内部的值进行返回。这样我们的整个parserString操作就能够得到Parser LispVal类型的返回值了。

$符号是一个中缀函数呼叫符：它和我们直接使用return (String x)的作用一样，但是$是右结合的，并且运行的优先级较低，这样让我们能够省略掉一些原来需要写得括号。由于$是一个操作符，你可以像使用函数那样使用它做任何事情：传递它，部分调用等。在这个方面，它和Lisp中的apply函数功能一致。

现在继续来看Scheme的变量。一个atom是一个字母或者符号，跟着若干个字母，数字或者符号：

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的组合符，选择符<|>。它会让我们首先尝试第一个解析器，如果它失败了，然后尝试第二个。如果任意一个成功了，那就会返回成功解析出得值。第一个解析器必须在它消费掉任何输入前失败返回：我们待会儿来看看如何用它来实现回溯。

一旦我们读到第一个字符和并成功读完剩下的部分，我们需要把它们放在一起组成一个atom。let声明定义了一个新的变量atom。我们使用列表连接符:来连接它们。和:相对应的，我们使用连接符++像这样来连接列表[first]++rest；first只是一个字符，我们可以用方括号包围它来将它转换成一个单元素的列表。

然后我们使用一个case表达式来尝试将字符串匹配成true和false，从而判断到底是应该创建和返回哪种LispVal类型。下划线符号\是一个可读性的技巧：目标会不断尝试匹配case块中的值直到遇到\（或者在此之前就因为某些异常失败了从而导致整个匹配失败）并作为一个通配符返回。因此如果代码运行到_条件下，它总是会匹配并且返回一个atom值。

最后，我们再为数字创建一个解析器。这里会展示更多的方法来处理monadic值：

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

从右往左看会让你很容易理解这个表达式，因为函数呼叫符($)和函数组合符(.)函数都是右结合的。结合器many1会匹配目标的一个或者多个传递给它的参数，这里我们会匹配到一个或者多个数字。我们会用返回的字符串来构建出一个数字的LispVal类型，不过这里我们貌似有一些类型上的匹配问题。因此首先，我们用内建的read函数来将字符串转化为数字。然后我们再把数字传递给Number构造器得到一个LispVal类型的值。我们用函数组合符创建出一个将右边参数的调用结果传递给左边参数的函数，因此我们就这样将两个函数调用结合起来了。

不幸的是，many1 digit的返回值是一个Parser String，所以我们的经过结合的Number . Read函数仍然不能直接对它进行操作。我们需要一种告诉它只操作Monad里的值的方法，然后再把处理后的结果返回给Parser LispVal。而标准库中的liftM函数刚好能帮助我呢，所以我们对我们的函数Number . Read使用liftM，然后把结果对Parser进行调用。

我们需要在程序顶部导入Monad模块来使用liftM函数：

import Control.Monad

这种不断进行函数组合，函数调用和函数传递的编程风格在Haskell代码中是非常常见的。这会让你能够在一行中表达出非常复杂的逻辑，并把中间的阶段分解成其它可以用各种方式结合起来的函数。不幸的是，这表明你需要常常从右向左阅读Haskell代码并且注意跟踪它们的类型。在后面的教程中我们会看到更多的例子，所以你应该会马上能适应这种方式。

创建一个能够接受字符串，数字或是Atom的解析器：

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"

编译并运行代码，你就能发现它接受任意的数字，字符串或者符号并且能够拒绝其他的情况了：

$ 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

习题

  1. 重写parseNumber函数，不允许使用liftM，尝试
    1. 使用do代码块
    2. 显式的运用>>=操作符来进行连接
  2. 我们的字符串并不太符合R5RS规范，因为它们不支持在字符串里使用转义之后的引号。修改parseString函数让\”表示一个引号字符而不是整个字符串的结束。你可能需要用一个新的解析器操作来替换noneOf “\””从而让它能接受非引号字符或者一个转义符号之后的引号字符。
  3. 修改程序，让它支持\\n \\r \\t \\\\\\\\以及其它你希望转义的字符。
  4. 修改parseNumber让它提供Scheme标准中对不同进制的支持。readOct和readHex函数或许会对你很有用。
  5. 给LispVal增加一个字符构造器，然后为R5RS标准中定义的字符创造一个解析器。
  6. 给LispVal增加一个浮点数构造器来支持R5RS中的小数相关的语法。参考Haskell中的readFloat函数。
  7. 增加数据类型和解析器从而支持Scheme中的full numeric tower。Haskell已经有内建类型来表示其中的部分内容，你可以通过Prelude模块确认。至于其它，你可以通过定义复合类型的方法来表示它们。例如，一个分数可以用分子和分母表示而一个复数可以用实部和虚部来表示（每一部分都是一个实数）。

递归解析：列表和引号

接下来，给我们的解释器添加更多的解析器。从Lisp的知名括号列表开始：

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

和parserNumber类似的，首先解析一系列由空格分隔开的表达式（sepBy parseExpr spaces），然后在Parser Monad内部调用构造符将它们组成一个List。注意我们能够把parseExpr直接传递给sepBy，尽管它是一个我们自己写的操作。

dotted-list的解析器稍微会复杂一点，不过仍然只是需要使用我们已经熟悉的概念：

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代码块中需要的类型一致。

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和parseDottedLis直到某个特定的位置都能够识别出相同的字符串；这打破了一个选择不能在出错前消费任何输入的前提。而try连接器试图运行某个的解析器，但是如果解析失败了，它会回滚到上一个状态。这让你在不影响其它分支的前提下对目标进行各种操作。

编译然后运行：

$ 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代码了。这就是递归的威力。

习题

  1. 添加backquote语法糖的支持：Scheme标准详述了它应该怎样展开成（quasiquote/unquote）。
  2. 添加vectors的支持。你可以使用Haskell的内置实现Array
    ，但是它使用起来可能会有些问题。严格说，一个vector应该有常数时间的索引和更新操作，但是事实上直接的更新操作在一个纯函数式语言里是很难实现的。你可能在看过该系列教程的后面的章节后会对如何实现它有更好的想法。
  3. 如果不用try组合符的话，你需要将目标从左边开始分解并在接下来调用parseExpr解析器自身。最后需要用一个解析器对字符串进行匹配，它要么是空要么是一个点符号加上一个单元素的表达式。这里把这个有趣的练习留给你：把它们的返回值组合成一个要么是List要么是DottedList的Either类型：你也许需要把判断逻辑分解到另外一个辅助函数里。
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,324评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,303评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,192评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,555评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,569评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,566评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,927评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,583评论 0赞 257
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,827评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2赞 320
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,365评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,941评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2赞 342

推荐阅读更多精彩内容