Около 6 лет назад я провел сравнительный анализ своих собственных комбинаторов синтаксического анализа в OCaml и обнаружил, что они были примерно в 5 раз медленнее, чем предлагаемые в данный момент генераторы синтаксического анализатора. Недавно я вернулся к этой теме и протестировал Parsec на Haskell против простого обработанного вручную анализатора восхождений , написанного на F #, и с удивлением обнаружил, что F # в 25 раз быстрее, чем Haskell.
Вот код на 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
У меня сложилось впечатление, что даже самые современные комбинаторы парсеров тратят много времени на отслеживание. Это верно? Если да, возможно ли написать комбинаторы синтаксического анализатора, которые генерируют конечные автоматы для достижения конкурентоспособной производительности, или необходимо использовать генерацию кода?
EDIT:
Вот скрипт OCaml, который я использовал для генерации выражения ~ 2Mb для бенчмаркинга:
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