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 <
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"
gt; 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

У меня сложилось впечатление, что даже самые современные комбинаторы парсеров тратят много времени на отслеживание. Это правильно? Если это так, возможно ли написать комбинаторы синтаксического анализатора, которые генерируют конечные автоматы для получения конкурентоспособной производительности, или необходимо использовать генерацию кода?

РЕДАКТИРОВАТЬ:

Вот скрипт 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