为什么 Parsec Choice 运算符似乎取决于解析器的顺序？

Question

我正在尝试解析一种仅由十进制或二进制数字组成的非常简单的语言。例如，这里有一些有效的输入：

#b1
#d1
#b0101
#d1234

我在使用 Parsec 的选择运算符时遇到问题：<|>。根据教程：Write yourself a Scheme in 48 hours:

[The choice operator] tries the first parser, then if it fails, tries the second. If either succeeds, then it returns the value returned by that parser..

但根据我的经验，我发现提供的解析器的顺序很重要。这是我的程序：

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

仔细阅读：

[The choice operator] tries the first parser, then if it fails, tries the second. If either succeeds, then it returns the value returned by that parser..

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

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

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 添加到 <|> 的整个左分支来恢复完美的不确定性。然而，不推荐这样做，因为它会促使程序员编写低效的解析器，这既是因为内存问题，也是因为人们可以轻松编写需要指数数量的回溯才能成功解析的语法。

Answer 2

秒差距有两种"failure"：有消耗输入的失败，也有不消耗输入的失败。为了避免回溯（并因此保持输入超过 necessary/being 通常对垃圾收集器不友好），(<|>) 在消耗输入后立即提交给第一个解析器；因此，如果它的第一个参数消耗输入并失败，则它的第二个解析器永远不会有机会成功。您可以使用 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"

在您的情况下，您需要类似地分解出“#”标记。

为什么 Parsec Choice 运算符似乎取决于解析器的顺序？

Why does it seem that the Parsec Choice operator depends on order of the parsers?

haskell

parsec

正在安装依赖项

正在编译

运行