大约 6 年前，我在 OCaml 中对自己的解析器组合器进行了基准测试，发现它们比当时提供的解析器生成器慢约 5 倍。我最近重新审视了这个主题，并将 Haskell 的 Parsec 与用 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