了解百万秒差距中的许多内容

Question

我正在尝试了解 Haskell 的 Megaparsec 库中

many

的行为。我本以为

many

当其输入解析器失败时返回一个空列表，但事实似乎并非如此。

特别是，我对以下最少的代码感到困惑：

import Text.Megaparsec (Parsec, many, parseTest)
import Text.Megaparsec.Char (string)
import Data.Void

test :: Parsec Void String [String] -> String -> IO ()
test = parseTest

main = do
    test (many (string "a" >> string "b")) "ac" -- error
    test (many (string "a" <> string "b")) "ac" -- error
    test (many (string "ab")) "ac" -- []

其输出如下：

1:2:
  |
1 | ac
  |  ^
unexpected 'c'
expecting 'b'
1:2:
  |
1 | ac
  |  ^
unexpected 'c'
expecting 'b'
[]

我不明白为什么前两个测试失败而第三个测试失败。

Answer 1

解析器

string "a" >> string "b"

和

string "a" <> string "b"

解析的内容没有区别，只是解析成功时返回的内容不同（第一个为

"b"

，第二个为

"ab"

），所以这并不奇怪前两种情况的行为相同（即都失败）。

它们失败的原因是解析器

many p

运行解析器

p

直到失败。如果

p

的失败不会消耗输入，则

many p

会成功，并返回解析器

p

在失败之前成功运行的结果列表。如果

p

的失败消耗了输入 ，则

many p

会失败，其“原因”与解析器

p

最终失败相同。

当解析器

string "a" >> string "b"

在输入

"ac"

上运行时，

string "a"

解析器成功解析

"a"

，然后

string "b"

解析器无法解析

"c"

，而不消耗输入。这会导致整个解析器

string "a" >> string "b"

失败，并消耗输入（

string "a"

消耗的输入，即使导致失败

string "b"

的解析本身没有消耗任何输入）。

将它们放在一起，

many (string "a" >> string "b")

运行解析器

string "a" >> string "b"

直到失败，这发生在第一个应用程序上，原因是解析器

string "b"

期望一个

"b"

但得到一个

"c"

。因为此失败消耗了输入（

"a"

消耗了

string "a"

），整个解析器

many (string "a" >> string "b")

因相同的“原因”而失败。

解析器

string "ab"

略有不同，自 4.4.0 起，Parsec 和 Megaparsec 版本之间的行为有所不同（请参阅

tokens

的文档）。

在秒差距中，应用于输入

string "ab"

的解析器

"ac"

消耗了

"a"

，然后在

"c"

上失败，因此它在消耗输入后失败了 。这可能是一个坏主意，这就是 Parsec 在 3.1.16.0 版本中引入

string'

的原因。解析器

string' "ab"

做了更明智的事情：它要么消耗所有

"ab"

，要么在不消耗任何东西的情况下失败。特别是，当它应用于输入

"ac"

并且无法消耗

"ab"

时，它会失败而不消耗输入。

在Megaparsec中，

string

最初的行为类似于Parsec的

string

，但是当他们修复了这个设计缺陷时，他们没有引入新的

string'

组合器，而是对

string

做了不兼容的更改，所以Megaparsec中的

string "ab"

就像秒差距中的

string' "ab"

一样，要么消耗掉所有

"ab"

，要么失败而不消耗任何东西。

（为了增加混乱，Megaparsec 还有一个

string'

组合器，但它是

string

的不区分大小写的版本，因此与 Parsec 的

string'

版本无关。）