请解释这个秒差距排列解析器的行为

Question

为什么这个Parsec permutation parser不解析b？

p :: Parser (String, String)
p = permute (pair
              <$?> ("", pa)
              <|?> ("", pb))
  where pair a b = (a, b)

pa :: Parser String
pa = do
  char 'x'
  many1 (char 'a')

pb :: Parser String
pb = do
  many1 (char 'b')

λ> parseTest p "xaabb"
("aa","bb")               -- expected result, good
λ> parseTest p "aabb"
("","")                   -- why "" for b?

解析器 pa 通过 <$?> 配置为可选，所以我不明白为什么它的失败会影响 b 的解析。我可以将其更改为 optional (char 'x') 以获得预期的行为，但我不明白为什么。

pa :: Parser String
pa = do
  optional (char 'x')
  many1 (char 'a')

pb :: Parser String
pb = do
  optional (char 'x')
  many1 (char 'b')

λ> parseTest p "xaaxbb"
parse error at (line 1, column 2):
unexpected "a"
expecting "b"
λ> parseTest p "xbbxaa"
("aa","bb")

当我们有相同的共享前缀 "x" 时如何支持两种输入顺序？

我也不明白使用可选 "x" 对解析行为的影响：

pb :: Parser String
pb = do
  try px -- with this try x remains unconsumed and "aa" gets parsed
         -- without this try x is consumed, but "aa" isn't parsed even though "x" is optional anyway
  many1 (char 'b')

px :: Parser Char
px = do
  optional (char 'x')
  char 'x' <?> "second x"

λ> parseTest p "xaaxbb"            -- without try on px
parse error at (line 1, column 2):
unexpected "a"
expecting second x
λ> parseTest p "xaaxbb"            -- with try on px
("aa","")

Answer 1

Why does this Parsec permutation parser not parse b?

因为 'a' 不是解析器 pa 或解析器 pb 的有效第一个字符。

How can both input orderings be supported when we have identical shared prefix "x"?

共享前缀必须从语法中排除；或以牺牲性能为代价插入回溯点（使用try）。

Answer 2

为什么 parseTest p "aabb" 给出 ("","")

排列解析器尝试去除其组成解析器可以解析的给定字符串前缀的前面（在本例中为 pa 和 pb）。在这里，它将尝试将 pa 和 pb 应用到 "aabb" 并且在这两种情况下都失败了 - 它甚至从来没有尝试解析 "bb".

为什么 pa 和 pb 不能都以 optional (char 'x')

开头

正在查看 permute, you'll see it uses choice, which in turn relies on (<|>)。正如 (<|>) 的文档所说，

This combinator implements choice. The parser p <|> q first applies p. If it succeeds, the value of p is returned. If p fails without consuming any input, parser q is tried. This combinator is defined equal to the mplus member of the MonadPlus class and the (<|>) member of Alternative.

The parser is called predictive since q is only tried when parser p didn't consume any input (i.e.. the look ahead is 1). This non-backtracking behaviour allows for both an efficient implementation of the parser combinators and the generation of good error messages.

所以当你做类似 parseTest p "xbb" 的事情时，pa 不会立即失败（它会消耗 'x'）然后整个事情都会失败，因为它无法回溯。

如何使共享前缀起作用？

正如丹尼尔所建议的，最好分解出你的语法。或者，您可以使用 try:

The parser try p behaves like parser p, except that it pretends that it hasn't consumed any input when an error occurs

根据我们之前谈到的 (<|>)，你应该把 try 放在 optional (char 'x').

的前面