为什么看起来Parsec Choice运算符依赖于解析器的顺序？

Question

我试图解析一个非常简单的语言,只包含十进制或二进制数字.例如,以下是一些有效的输入:

#b1
#d1
#b0101
#d1234

我使用Parsec的选择运算符时遇到问题:<|>.根据教程:在48小时内为自己写一个方案:

[选择运算符]尝试第一个解析器,如果失败,则尝试第二个.如果成功,则返回该解析器返回的值.

但根据我的经验,我发现解析器的顺序很重要.这是我的计划:

import System.Environment
import Text.ParserCombinators.Parsec

main :: IO ()
main = do
  (x:_) <- getArgs 
  putStrLn ( "Hello, " ++ readExp x)

bin :: Parser String
bin = do string "#b"
         x <- many( oneOf "01")
         return x

dec :: Parser String
dec = do string "#d"
         x <- many( oneOf "0123456789")
         return x

-- Why does order matter here?
parseExp = (bin <|> dec) 

readExp :: String -> String
readExp input = case parse parseExp "test" input of
                      Left error -> "Error: " ++ show error
                      Right val  -> "Found val" ++ show val 

以下是我运行程序的方法:

安装依赖项

$ cabal sandbox init
$ cabal install parsec

编译

$ cabal exec ghc Main

跑

$ ./Main "#d1"
Hello, Error: "test" (line 1, column 1):
unexpected "d"
expecting "#b"

$ ./Main "#b1"
Hello, Found val"1"

如果我按如下方式更改解析器的顺序:

parseExp = (dec <|> bin) 

然后只检测到二进制数,程序无法识别十进制数.

通过我已经执行的测试,我发现这个问题只发生在其中一个解析器已经开始解析输入时,例如,如果#找到一个散列字符,则bin解析器被激活,最终失败,因为预期的下一个字符是b和否d.似乎应该会发生某种应该发生的回溯,我不知道.

感谢帮助!

Answer 1

Parsec有两种"失败":存在消耗输入的故障,而没有消耗输入的故障.为了避免回溯(因此保持输入超过必要的时间/通常对垃圾收集器不友好),(<|>)一旦消耗输入就提交给第一个解析器; 因此,如果它的第一个参数消耗输入并失败,它的第二个解析器永远不会有机会成功.您可以使用以下方式显式请求回溯行为try:

Text.Parsec> parse (string "ab" <|> string "ac") "" "ac"
Left (line 1, column 1):
unexpected "c"
expecting "ab"
Text.Parsec> parse (try (string "ab") <|> string "ac") "" "ac"
Right "ac"

不幸的是,try有一些令人讨厌的性能损失,这意味着如果你想要一个高性能的解析器,你将不得不重构一下你的语法.我会这样用上面的解析器:

Text.Parsec> parse (char 'a' >> (("ab" <$ char 'b') <|> ("ac" <$ char 'c'))) "" "ac"
Right "ac"

在您的情况下,您需要同样分解"#"标记.

Answer 2

仔细读：

[选择运算符] 尝试第一个解析器，如果失败，则尝试第二个解析器。如果其中一个成功，那么它返回该解析器返回的值。

这意味着首先尝试第一个解析器，如果成功，则根本不会尝试第二个解析器！这意味着第一个解析器具有更高的优先级，因此<|>通常是不可交换的。

可以使用一些总是成功的解析器来制作一个简单的反例，例如

dummy :: Parser Bool
dummy = return True <|> return False

上面等价于return True：因为第一个成功，所以第二个无关紧要。

最重要的是，parsec 被设计为在第一个分支成功消耗一些输入后尽早提交。这种设计为了效率而牺牲了完美的不确定性。否则，parsec 通常需要将所有正在解析的文件保留在内存中，因为如果发生解析错误，则需要尝试一些新的替代方案。

例如，

p = (char 'a' >> char 'b' >> ...) <|>
    (char 'a' >> char 'c' >> ...)

不会像人们预期的那样工作。一旦'a'第一个分支成功使用，parsec 就会对其进行提交。这意味着如果'c'遵循，那么第一个分支将失败，但尝试第二个分支为时已晚。整个解析器根本就失败了。

为了解决这个问题，可以分解出公共前缀，例如

p = char 'a' >> ( (char 'b' >> ...) <|> (char 'c' >> ...) )

或求助于try,

p = (try (char 'a' >> char 'b') >> ...) <|>
    (char 'a' >> char 'c' >> ...)

try基本上告诉 parsec 在整个解析器try成功之前不要提交到分支。如果滥用，它可能会导致 parsec 将文件的大部分内容保留在内存中，但用户至少对此有一些控制权。try理论上，完美的非确定性可以通过始终添加到 的整个左分支来恢复<|>。然而，不建议这样做，因为它会促使程序员编写低效的解析器，这既是因为内存问题，也是因为人们可以轻松地编写需要指数数量的回溯才能成功解析的语法。