WHsT

WHsT

WHsT's name is .
Twitter: @xukiro, GitHub: whst

Parsec: try a <|> b 有害论

本文译自: http://blog.ezyang.com/2014/05/parsec-try-a-or-b-considered-harmful/


如果嫌长,请直接看结论:用于回溯的 try 的作用域越小越好,一般把 try 放到对应 parser 的定义内。

你有没有用 Parsec 写过 parser, 但它对不合语法的代码报的错却语焉不详呢?

1
2
3
"test.txt" (line 15, column 7):
unexpected 'A'
expecting end of input

提示的错误位置看上去像是待编译代码中的任意行任意列,而且你确定错误应该源自一大堆 parser combinator 中的某一个。等一下!Parsec却不知怎么认为文件应当结尾。你四处寻找原因终于发现真正的错误实际上处于报告的位置的后面.

我们可能会想,“难怪 Parsec 在错误处理方面的这名声不咋地……”


假设出现了这样的问题,而且要解析的也并非特别怪异的语法,那么产生这类不够详细的错误消息的原因一般是这样:程序员在代码中用很多用于回溯的 try 语句,正是回溯破坏了有用的错误状态。总之,在某个点 parser 若解析失败,它就想向用户报告错误原因,但是一个包围它的 try 语句会迫使 parser 回溯,然后尝试另一种解析方案(实际上没啥希望)。

现在用一个例子印证上面的观点:假设一个 Haskell 程序员用 parse combinator 为 Haskell 的模块导入写一个 parser:

1
2
stmt ::= import qualified A as B
| import A

对 Parsec 内置的 token combinators 稍作了解,写出来的第一个版本可能像这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import Text.Parsec
import qualified Text.Parsec.Token as P
import Text.Parsec.Language (haskellDef)

data Stmt = QualifiedImport String String | Import String
deriving (Show)

pStmt = pQualifiedImport <|> pImport

pQualifiedImport = do
reserved "import"
reserved "qualified"
i <- identifier
reserved "as"
i' <- identifier
return (QualifiedImport i i')

pImport = do
reserved "import"
i <- identifier
return (Import i)

lexer = P.makeTokenParser (haskellDef
{ P.reservedNames = P.reservedNames haskellDef ++ ["qualified", "as"] })
identifier = P.identifier lexer
reserved = P.reserved lexer

parseStmt input = parse (pStmt >> eof) "(unknown)" input

然而,这个 Parser 其实压根儿就解析不了常规的导入语句————它会产生这样的错误消息:

1
2
3
4
*Main> parseStmt "import Foo"
Left "(unknown)" (line 1, column 8):
unexpected "F"
expecting "qualified"

稍微谷歌一下,可以知道 Parsec 默认不回溯。嗯,这不算什么大问题,为啥不往 parser 里面加一个 try 语句呢:

1
pStmt = try pQualifiedImport <|> pImport

这样就能让两个 Parser 都正常运行了。而且从这里,我们为以后用 Parsec 写 parser 得出了一些“经验”:

如果要在多个 parser 分支之间作出选择,但是有的 parser 会消耗输入。那么,在每个分支 parser 前面插一个 try 就 OK, 因为这样能回溯。

不知不觉中,Parsec 的用户就引入了不好的报错方式:

1
2
3
4
*Main> parseStmt "import qualified Foo s B"
Left "(unknown)" (line 1, column 17):
unexpected reserved word "qualified"
expecting letter or digit or "#

呃,等下……上面这个例子中我们希望它提示“有一个未预期的标识符 s”, 因为我们希望得到 as. 但是发现这个错误的时候,Parsec 没有报告出来,而是回溯了,它尝试用 pImport 的规则来匹配,然后再次失败。但这个时候,另一个分支的错误原因却已经永远丢失,不能再显示……

要咋修复这个问题呢?此问题在于,有时候我们程序员知道回溯已经没用了,但是这段代码还是会傻傻地回溯。在这个例子里,一旦解析出了 import qualified, 我们就已经知道这是个 qualified import 语句,就不应该再回溯。那么怎么让 Parsec 理解这个规则?很简单,减少 try 回溯操作的作用域:

1
2
3
4
5
6
7
8
9
10
pStmt = pQualifiedImport <|> pImport

pQualifiedImport = do
try $ do
reserved "import"
reserved "qualified"
i <- identifier
reserved "as"
i' <- identifier
return (QualifiedImport i i')

这里,我把 trypStmt 当中移到了 pQualifiedImport 当中,所以这次只会在读取 import qualified 失败的时候回溯。一旦它读取到了,我们就消耗了这些 token, 并且确定了这是个 qualified import. 这个版本的错误信息就好看些了:

1
2
3
4
*Main> parseStmt "import qualified Foo s F"
Left "(unknown)" (line 1, column 22):
unexpected "s"
expecting "as"

此例要说明的意思在于:用于回溯的 try 的作用域越小越好,一般把 try 放到对应 parser 的定义内。这样就需要用点人类的智慧:你得确定需要多少预读符号(lookahead)才能决定进入一个分支,这通常取决于 Parser 怎么用。还好,大多数语言设计的时候就考虑了这点,因此它们要预读的符号不算太多。而且对于那些我想用 Parsec 的项目,我愿意为此牺牲一点模块性。


如果从另一个角度看这个问题,其实这锅应该由 Parsec 来背:它根本就不该提供一个这样能把错误消息搞得乱七八糟的 API —— 为何不能自动判断要预读的符号呢?尽管传统的 Parser 生成器能够做到这些(而且在我们先前的例子里还能通过避免回溯来提高效率),其实是因为有一些基本的原因决定了 Parsec combinator(以及与之类似的 Monadic parser combinator)不能判断预判符号是什么。这就是很多 Haskell 程序员更倾向于使用高效但却无错误处理的 parser 的原因。

那么为什么要写这篇文章呢?因为还是有不少文献推荐用 Parsec, 而且 Haskell 初学应该不会用 Parsec 实现他们的第一个 parser。最后,如果你想用 Parsec 写一个 parser, 那么你最好还是花点时间来限制回溯————这样你用 Parsec 的时候可能要顺手得多