问：

解析器中的 Parsec <|> 选择，错误抛出但不会转到下一个解析器（1 个答案）

8年前关闭。

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

#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 解析器被激活，最终失败，因为预期的下一个字符是而不是。似乎应该发生某种回溯，我不知道。#bd

感谢您的帮助！

哈斯克尔 ·帕塞克

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

例如

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

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

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

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

或求助于，try

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

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

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"

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

上一个：变基后手动合并的拉取请求在 Github 上不会显示为已合并

下一个：如何在Web测试用例中访问客户端请求使用的Symfony服务？

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

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

安装依赖项

编译

跑

评论

评论