Entropic Thoughts

Parser Combinators Beat Regexes

• Home
• Archive
• Tags
• About
• xkqr.org

Parser Combinators Beat Regexes

作者：kqr，发布于 2025-04-08 标签：

• haskell

有人在网上解决 Advent of Code 的问题，并提出了关于去年第 3 天的问题。他们有一个使用正则表达式（regexes）在 String 值上工作的解决方案，但出于性能原因，他们希望使用 ByteString 值代替。然而，令他们惊讶的是，Haskell 中似乎缺乏围绕 regex 库的社区凝聚力。

这是有原因的。我们通常不在 Haskell 中使用 regexes。我们改用 parser combinators，因为它们几乎总是更好。在其他语言中，当一个简单的 regex 可以做同样的事情时，编写一个完整的 parser 会被认为是过度设计。在 Haskell 中，编写一个 parser 没什么大不了的。我们只是做了它，然后继续我们的生活。

regex 解决方案

Advent of Code 问题的第一个部分非常适合基于 regex 的解决方案。以下是 Haskell 中这样的解决方案的样子。它使用 pcre-heavy Haskell 库，该库反过来调用系统范围内的 pcre C 库来实际编译和运行 regex。

In[1]:

{-# LANGUAGE QuasiQuotes #-}
module Main where
import      Data.ByteString    (ByteString)
import qualified Data.ByteString.Char8 as Char8
import      Data.Monoid      (Sum (..))
import qualified Text.Regex.PCRE.Heavy as Re
import      Text.Regex.PCRE.Heavy (re)
test_input :: ByteString
test_input = Char8.pack "xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))"
regex_matches :: ByteString -> Int
regex_matches input =
 let
  -- 获取一个带有提取数字的 regex 匹配列表。
  -- 're' quasi-quoter 在编译时编译 regex，
  -- 避免了运行时的成本。
  hits = Re.scan [re|mul\((\d+),(\d+)\)|] input
  -- 获取一个命中并计算其乘积，将字符串化的
  -- 数字转换为实际数字，然后将其包装为
  -- 总和中的一项。
  compute (_, [a, b]) =
   Sum (read (Char8.unpack a) * read (Char8.unpack b))
 in
  -- 将总和中的所有项折叠成一个数字。
  getSum (foldMap compute hits)
main :: IO ()
main = do
 print (regex_matches test_input)

这完成了工作并返回了预期的总和 161。如果我们在不到 1 MB 的输入数据上运行它，在我的机器上需要 19 秒，几乎所有的时间都花在了 pcre 库中。1 虽然这有点奇怪，因为如果我在 Perl 中做同样的事情，它需要 0.02 秒。我希望我有时间调查出了什么问题。

但我不喜欢它的主要原因是 regex 和 compute 函数之间存在非常强的隐式约定。compute 函数假定恰好有两个捕获组，并且它们是可以安全地转换为整数的字符串。这是真的，但代码中没有任何东西可以保证这一点。如果这些假设从现在起一年后被违反，那将不是编译器错误，而是在重要客户会议前一天凌晨 3 点中断生产服务的异常。

parser 解决方案

对于我们在这里面临的问题，基于 parser 的解决方案乍一看似乎更复杂。部分原因是 regex 库带有一种获取所有匹配项的方法，而不管它们在输入中的位置如何。Parser combinators 旨在编写为消耗所有输入，因此我们必须手动编写 parser 代码来迭代输入并找到下一个匹配项。

此解决方案使用 attoparsec 库，该库专门用于处理 ByteString 值，因为提出问题的人似乎关心性能。

In[2]:

module Main where
import      Control.Applicative       ((<|>))
import qualified Data.Attoparsec.ByteString.Char8 as Parser
import      Data.ByteString         (ByteString)
import qualified Data.ByteString.Char8      as Char8
import qualified Data.Either           as Either
test_input :: ByteString
test_input = Char8.pack "xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))"
parser_matches :: ByteString -> Int
parser_matches input =
 let
  -- 解析 mul 指令。首先读取开始
  -- 序列，然后是第一个值，然后是分隔符，
  -- 然后是第二个值，然后是终止符。最后，
  -- 它返回这对值的乘积。
  mul = do
   Parser.string (Char8.pack "mul(")
   first <- Parser.decimal
   Parser.char ','
   second <- Parser.decimal
   Parser.char ')'
   pure (first * second)
  -- 解析下一个 mul 指令。首先尝试
  -- 立即解析一个 mul 指令。如果失败，
  -- 则改为 (1) 将 parser 前进一个步骤，并
  -- (2) 再次尝试。
  next =
   mul <|> do
    Parser.anyChar
    next
  -- 扫描整个输入以查找所有 mul 指令，
  -- 返回其乘积的总和。
  scan = do
   muls <- Parser.many1 next
   pure (sum muls)
 in
  -- 在输入上运行 parser，
  -- 通过抛出异常来处理解析错误。
  Either.fromRight (error "Failed to parse input.")
   (Parser.parseOnly scan input)
main :: IO ()
main = do
 print (parser_matches test_input)

这是以人们可能称之为 direct, monadic 风格编写的，使用 do notation 进行排序，只做 Advent of Code 难题的第一部分中要求的。我们可以重写它以使其更简洁，但我们现在将抵制重构。我们永远不知道 Advent of Code 难题的第二部分会引入什么要求。（好奇的人可以在附录中查看重构。）

这确实涉及更多的前期编写，但有一些好处。当然，我们使用 Either.fromRight 来丢弃我们可以从 attoparsec 获得的所有有用的错误报告，但如果我们不这样做，当出现问题时，我们会获得更有用的错误消息。我们也不必手动将字符串转换为整数，或者盲目地希望解析正确数量的整数。编译器会为我们检查所有这些假设。

刚接触这里？我打算在接下来的几个月中撰写更多关于 Haskell 应用于现实世界问题的文章。你应该订阅以通过电子邮件接收新文章的每周摘要。 如果你不喜欢它，你可以随时取消订阅。

当我们在相同的 1 MB 输入上运行它时，它需要 0.07 秒。这在 Perl regex 的数量级内，但我们也获得了更具表现力的语言的所有好处。正如我们很快将看到的，parsers 的另一个主要好处是它们可以更灵活地适应未来的要求。

使 parser 具有状态

Advent of Code 难题的下一部分涉及解释名为 do() 和 don't() 的指令，这些指令打开和关闭 mul 指令对总和的贡献。当我们解析时，我们现在需要跟踪一个状态位。这对于 regexes 来说是一场噩梦，因为它们识别常规语言，而常规语言实际上是无状态语言。2 当然，还有更多的细微差别，但作为第一个近似值。从技术上讲，常规语言是可以被有限状态自动机识别的语言，并且如果存在有限数量的状态（如此处的情况），则所有这些状态都可以编码在 fsa 中，但我们不要在这里吹毛求疵。

但是通过基于 parser 的解决方案，我们可以将其提升到状态转换器中，并且我们获得了一个有状态的 parser。3 请注意，在严肃的应用程序中，我们可能会将 lexing 和 parsing 作为单独的步骤，但是 parser combinators 使我们可以自由地组合这两个步骤以用于像这样的小型 parsers。

In[3]:

module Main where
import      Control.Applicative       (asum, (<|>))
import qualified Control.Monad.State.Class    as State
import qualified Control.Monad.State.Strict    as State
import qualified Data.Attoparsec.ByteString.Char8 as Parser
import      Data.Bool            (bool)
import      Data.ByteString         (ByteString)
import qualified Data.ByteString         as ByteString
import qualified Data.ByteString.Char8      as Char8
import qualified Data.Either           as Either
test_input :: ByteString
test_input = Char8.pack "xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))"
parser_matches :: ByteString -> Int
parser_matches input =
 let
  -- 成功解析 do 指令后，
  -- 启用 mul 指令的贡献。
  enable = do
   State.lift (Parser.string (Char8.pack "do()"))
   State.put True
  -- 成功解析 don't 指令后，
  -- 禁用 mul 指令的贡献。
  disable = do
   State.lift (Parser.string (Char8.pack "don't()"))
   State.put False
  -- 像以前一样解析 mul 指令，除了
  -- 现在被提升为有状态的操作。
  mul = State.lift $ do
   Parser.string (Char8.pack "mul(")
   first <- Parser.decimal
   Parser.char ','
   second <- Parser.decimal
   Parser.char ')'
   pure (first * second)
  -- 如果解析了 do 或 don't 指令，
  -- 继续搜索下一个 mul。
  --
  -- 如果遇到 mul，请检查
  -- 状态的值。如果启用了 muls，则将其保留
  -- 不变 (id)，但如果禁用了 muls，
  -- 则强制其值为零 (const 0)。
  --
  -- 如果未识别任何指令，请执行步骤
  -- 向前一个字符并重试。
  next = asum
   [ enable *> next
   , disable *> next
   , bool (const 0) id <$> State.get <*> mul
   , State.lift Parser.anyChar *> next
   ]
  scan = sum <$> Parser.many1 next
 in
  -- 从启用 mul 贡献开始评估。
  Either.fromRight (error "Failed to parse input.") $
   Parser.parseOnly (State.evalStateT scan True) input
main :: IO ()
main = do
 print (parser_matches test_input)

在专门使 attoparsec parsers 具有状态时，必须格外小心，因为 attoparsec 非常乐意在失败时回溯输入，但它不会撤消由初始解析尝试引起的状态更改。因此，在使 attoparsec parsers 具有状态时，我们必须编写它们，以便它们永远不会回溯到状态更改之后。4 可以想象一个名为 cut 的 attoparsec 原语（灵感来自 Prolog），它会停止在某个点之后回溯。这可以与状态更改结合使用，以确保 parser 永远不会回溯到该更改之后。这样的原语很容易编写，但需要由库提供 - 不能由库用户编写。从积极的一面来看，避免长时间的回溯序列也有利于内存使用和性能，因此我们无论如何都应该这样做。

细心的读者可能会注意到，我们使用 parser 结果来存储总和的值，但将贡献位存储在状态中。我们可以用任何其他方式做到这一点。我们可以将总和和位都存储在状态中，或者两者都存储在结果中，或者以另一种方式将总和存储在状态中，而将位存储在结果中。这只是我能想到的最快的方法，可以使其启动并运行。Haskell 使以后重构变得廉价且安全。

以上代码在大约 1 MB 的输入上运行需要 0.12 秒。我什至不会尝试为第二部分编写基于 regex 的解决方案，但我非常有信心它会更慢、更不灵活且更难维护。

附录 A：重构 direct, monadic parser

mul 指令实际上是一个更通用的“分隔值对” parser 的实例。我们可以将其提取到自己的函数中。

In[4]:

pair :: Parser open -> Parser sep -> Parser close -> Parser value -> Parser (value, value)
pair open sep close value =
 liftA2 (,) (open *> value) (sep *> value <* close)

这采用了三个 parsers 来处理开始序列、分隔符和结束序列，然后是一个 parser 来处理实际值，并构造一个返回一对值的 parser。我们可以使用它来解析 mul 指令，还可以使用任何其他基于值对的指令。

同样，我们缺少一个返回 parser 的所有匹配项的函数，而不管它们位于输入中的哪个位置。regex 库具有该函数，但它不是开箱即用的 attoparsec。我们可以做到这一点。

In[5]:

scan_all :: Parser a -> Parser [a]
scan_all p =
 let next = p <|> Parser.anyChar *> next
 in Parser.many1 next

通过将代码的这些部分分解为它们自己的函数，最终 parser 可以以更 applicative 的风格编写为

In[6]:

parser_matches :: ByteString -> Int
parser_matches input =
 let
  mul = uncurry (*) <$> pair
   (Parser.string (Char8.pack "mul("))
   (Parser.char ',')
   (Parser.char ')')
   Parser.decimal
  result = sum <$> scan_all mul
 in
  Either.fromRight (error "Failed to parse input.")
   (Parser.parseOnly result input)

这读起来很不错：result parser 是所有 mul 指令的总和，这些指令被指定为具有特定分隔符的值对的乘积。

旁注

1 虽然这有点奇怪，因为如果我在 Perl 中做同样的事情，它需要 0.02 秒。我希望我有时间调查出了什么问题。 2 当然，还有更多的细微差别，但作为第一个近似值。从技术上讲，常规语言是可以被有限状态自动机识别的语言，并且如果存在有限数量的状态（如此处的情况），则所有这些状态都可以编码在 fsa 中，但我们不要在这里吹毛求疵。 3 请注意，在严肃的应用程序中，我们可能会将 lexing 和 parsing 作为单独的步骤，但是 parser combinators 使我们可以自由地组合这两个步骤以用于像这样的小型 parsers。 4 可以想象一个名为 cut 的 attoparsec 原语（灵感来自 Prolog），它会停止在某个点之后回溯。这可以与状态更改结合使用，以确保 parser 永远不会回溯到该更改之后。这样的原语很容易编写，但需要由库提供 - 不能由库用户编写。 如果你喜欢这个，并且想要更多，你应该请我喝杯咖啡。这可以帮助我将我的 110 多个想法积压变成文章。

感谢我的妻子，没有她的支持，我永远无法完成第一句话。♥

S = k log W。评论？给我发电子邮件。您也可以订阅更新。