0

星期一早上的 Haskell 帖子Parsing Part 2: Applicative Parsing说这个关于交替的regex-applicative：

请注意，顺序很重要！如果我们把整数解析器放在第一位，我们就有麻烦了！如果遇到小数，整数解析器会贪婪地成功解析小数点之前的所有内容。我们将丢失小数点后的所有信息，或者更糟糕的是，解析失败。

从他们的 Git 存储库中引用这个函数：

numberParser :: RE Char Value
numberParser = (ValueNumber . read) <$>
  (negativeParser <|> decimalParser <|> integerParser)
  where
    integerParser = some (psym isNumber)
    decimalParser = combineDecimal <$> many (psym isNumber) <*> sym '.' <*> some (psym isNumber)
    negativeParser = (:) <$> sym '-' <*> (decimalParser <|> integerParser)

    combineDecimal :: String -> Char -> String -> String
    combineDecimal base point decimal = base ++ (point : decimal)

但是，我无法弄清楚为什么会这样。当我更改decimalParser <|> integerParser为 时integerParser <|> decimalParser，它似乎仍然总是解析正确的东西（特别是，我这样做并运行stack test时，他们的测试仍然通过）。小数解析器必须有小数点，而整数解析器不能有小数点，所以它会在那里停止解析，导致小数点导致下一段解析失败，将我们回溯到小数解析器。似乎唯一不会发生这种情况的情况是，如果整个解析器的下一部分在此之后可以接受小数点（使其成为模棱两可的语法），但您仍然不会“丢失所有信息之后小数点，或更糟糕的是，解析失败”。我的推理是否正确并且那篇文章中有一个错误，或者是否有一个案例我没有看到他们的结果之一可能发生在哪里？

4

2 回答 2

4

有区别，这很重要，但部分原因是解析器的其余部分非常脆弱。

当我更改decimalParser <|> integerParser为 时integerParser <|> decimalParser，它似乎仍然总是解析正确的东西（特别是，我这样做并运行了堆栈测试，他们的测试仍然通过）。

测试通过是因为测试没有涵盖解析器的这一部分（最接近的只有练习stringParser）。

这是一个当前通过的测试，但如果您交换了那些解析器（test/Spec.hs将其插入并将其添加到do下的块中main），则不会：

badex :: Spec
badex = describe "Bad example" $ do
  it "Should fail" $
    shouldMatch
      exampleLineParser
      "| 3.4 |\n"
      [ ValueNumber 3.4 ]

如果你交换解析器，你会得到结果ValueNumber 3.0：（integerParser现在是第一个）成功解析3，但随后输入的其余部分被丢弃。

为了提供更多上下文，我们必须看看在哪里numberParser使用：

  1. numberParser是valueParser...的替代方案之一
  2. 用于exampleLineParser， wherevalueParser后面是readThroughBar（我的意思是相关的代码是字面意思valueParser <* readThroughBar）；
  3. readThroughBar丢弃所有字符，直到下一个竖线（使用many (psym (\c -> c /= '|' && c /= '\n'))）。

因此，如果valueParser只是解析成功3，那么后续readThroughBar将愉快地消耗并丢弃其余的.4 |。

您引用的博文中的解释仅部分正确：

请注意，顺序很重要！如果我们把整数解析器放在第一位，我们就有麻烦了！如果遇到小数，整数解析器会贪婪地成功解析小数点之前的所有内容。我们将丢失小数点后的所有信息，或者更糟糕的是，解析失败。

（强调我的）如果你的解析器主动丢弃它，你只会丢失信息，readThroughBar这里就是这样。

正如您已经建议的那样， 的回溯行为RE意味着 的 非交换性实际上只对模棱两可的语法的正确性很重要（它可能仍然会对一般性能产生影响），如果不那么宽松，<|>这在此处不会成为问题，例如，通过readThroughBar之前只消耗空格|。

我认为这表明使用psymwith(/=)至少是一种代码味道，如果不是一个明确的反模式的话。通过只查找分隔符而不限制中间的字符，很难发现前面的解析器没有消耗尽可能多的输入的错误。更好的选择是确保使用的字符可能不包含任何有意义的信息，例如，要求它们都是空格。

于 2020-01-12T19:53:07.517 回答
1

问题与解析类似：

12.34

如果您先尝试整数解析器，那么它将找到12，得出结论认为它找到了一个整数，然后尝试将 解析.34为下一个标记。

[...] 导致下一段解析失败的小数点，让我们回溯到小数解析器。

是的，只要您的解析器进行回溯。出于性能原因，大多数生产解析器（例如megaparsec）不这样做，除非他们被明确告知（通常使用try组合器）。博客文章中使用的RE解析器很可能是一个例外，但我找不到它的解释器来检查。

于 2020-01-12T18:23:19.923 回答