約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