如何组合多个解析器？

Question

为什么此解析器失败以及如何修复它？

λ> str1 = string "elif "
λ> str2 = string "else "
λ> strs = (,) <$> many str1 <*> optionMaybe str2

λ> parse strs "" "elif elif elif else "
Left (line 1, column 16):
unexpected "s"
expecting "elif "

如何组合 many 解析器和 optionalMaybe 解析器？

Answer 1

问题是 string "elif " 会吃掉 else 中的 el，并且由于它已经消耗了输入，所以它不会回溯而是抱怨意外的 s

最简单的解决方法是允许回溯 try:

str1 = try $ string "elif "

Answer 2

另一个答案显示了使用 try 的简单修复。不过，这确实会带来成本，即引入回溯。在这个答案中，我介绍了另一种没有回溯的解决方案，因此它应该稍微快一点并且使用更少的内存。基本思想是解析共享前缀，然后在我们遇到两者实际不同的部分时分派。所以：

strs = (string "el" *> (elseParser <|> elifParser)) <|> pure ([], Nothing) where
    elseParser = ([], Just "else ") <$ string "se "
    elifParser = liftA2
        (\_ (elifs, elses) -> ("elif ":elifs, elses))
        (string "if ")
        strs

为简单起见，我在结果中使用常量 "else " 和 "elif " 字符串，但这些可以通过一些额外的连接从 string 解析器的部分结果构建.

如何组合多个解析器？

How to combine many parsers?

parsing

haskell

functional-programming

parsec