haskell - 解析器组合器可以变得高效吗？

Question

大约 6 年前，我在 OCaml 中对自己的解析器组合器进行了基准测试，发现它们比当时提供的解析器生成器慢约 5 倍。我最近重新审视了这个主题，并对 Haskell 的 Parsec 与简单的手卷 precedence climbing parser 进行了基准测试。用 F# 编写，并惊讶地发现 F# 比 Haskell 快 25 倍。

这是我用来从文件中读取大型数学表达式、解析并计算它的 Haskell 代码:

import Control.Applicative
import Text.Parsec hiding ((<|>))

expr = chainl1 term ((+) <$ char '+' <|> (-) <$ char '-')

term = chainl1 fact ((*) <$ char '*' <|> div <$ char '/')

fact = read <$> many1 digit <|> char '(' *> expr <* char ')'

eval :: String -> Int
eval = either (error . show) id . parse expr "" . filter (/= ' ')

main :: IO ()
main = do
    file <- readFile "expr"
    putStr $ show $ eval file
    putStr "\n"

这是我在 F# 中的独立优先级攀爬解析器:

let rec (|Expr|) = function
  | P(f, xs) -> Expr(loop (' ', f, xs))
  | xs -> invalidArg "Expr" (sprintf "%A" xs)
and loop = function
  | ' ' as oop, f, ('+' | '-' as op)::P(g, xs)
  | (' ' | '+' | '-' as oop), f, ('*' | '/' as op)::P(g, xs) ->
      let h, xs = loop (op, g, xs)
      match op with
      | '+' -> (+) | '-' -> (-) | '*' -> (*) | '/' | _ -> (/)
      |> fun op -> loop (oop, op f h, xs)
  | _, f, xs -> f, xs
and (|P|_|) = function
  | '('::Expr(f, ')'::xs) -> Some(P(f, xs))
  | c::_ as xs when '0' <= c && c <= '9' ->
      let rec loop n = function
        | c2::xs when '0' <= c2 && c2 <= '9' -> loop (10*n + int(string c2)) xs
        | xs -> Some(P(n, xs))
      loop 0 xs
  | _ -> None

我的印象是，即使是最先进的解析器组合器也会浪费大量时间回溯。那是对的吗？如果是这样，是否可以编写生成状态机的解析器组合器以获得有竞争力的性能，或者是否有必要使用代码生成？

编辑:

这是我用来生成约 2Mb 表达式进行基准测试的 OCaml 脚本:

open Printf

let rec f ff n =
  if n=0 then fprintf ff "1" else
    fprintf ff "%a+%a*(%a-%a)" f (n-1) f (n-1) f (n-1) f (n-1)

let () =
  let n = try int_of_string Sys.argv.(1) with _ -> 3 in
  fprintf stdout "%a\n" f n

Answer 1

我提出了一个 Haskell 解决方案，它比您发布的 Haskell 解决方案(使用我编写的测试表达式)快 30 倍。

主要变化:

1. 将 Parsec/String 更改为 Attoparsec/ByteString
2. 在fact函数中，将read和many1digit更改为decimal
3. 严格执行 chainl1 递归(对于较懒的版本，删除 $!)。

我尝试让其他所有内容尽可能相似。

import Control.Applicative
import Data.Attoparsec
import Data.Attoparsec.Char8
import qualified Data.ByteString.Char8 as B

expr :: Parser Int
expr = chainl1 term ((+) <$ char '+' <|> (-) <$ char '-')

term :: Parser Int
term = chainl1 fact ((*) <$ char '*' <|> div <$ char '/')

fact :: Parser Int
fact = decimal <|> char '(' *> expr <* char ')'

eval :: B.ByteString -> Int
eval = either (error . show) id . eitherResult . parse expr . B.filter (/= ' ')

chainl1 :: (Monad f, Alternative f) => f a -> f (a -> a -> a) -> f a
chainl1 p op = p >>= rest where
  rest x = do f <- op
              y <- p
              rest $! (f x y)
           <|> pure x

main :: IO ()
main = B.readFile "expr" >>= (print . eval)

我想我从中得出的结论是，解析器组合器的大部分减速是因为它位于一个低效的基础上，而不是它本身是一个解析器组合器。

我想，如果有更多的时间和分析，这可能会进展得更快，因为当我超过 25× 标记时我就停了下来。

我不知道这是否会比移植到 Haskell 的优先级攀登解析器更快。也许这会是一个有趣的测试？