haskell - que - ¿Se pueden hacer eficientes los combinadores de analizador?

youtube google videos

Question

Hace aproximadamente 6 años, comparé mis propios analizadores sintácticos en OCaml y descubrí que eran ~ 5 veces más lentos que los generadores de analizadores sintácticos que se ofrecían en ese momento. Hace poco volví a visitar este tema y comparé el Parsec de Haskell con un analizador sintáctico de escalada de precedencia rodado a mano escrito en F # y me sorprendió descubrir que el F # era 25 veces más rápido que el Haskell.

Aquí está el código de Haskell. Solía ​​leer una gran expresión matemática de un archivo, analizar y evaluarlo:

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"

y aquí está mi analizador autónomo de escalada de precedencia en 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

Mi impresión es que incluso los combinadores de analizador de última generación desperdician mucho tiempo en el seguimiento. ¿Es eso correcto? Si es así, ¿es posible escribir combinadores de analizador que generan máquinas de estado para obtener un rendimiento competitivo o es necesario usar la generación de código?

EDITAR:

Aquí está el script OCaml que utilicé para generar una expresión de ~ 2Mb para el benchmarking:

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

¿Has probado alguna de las conocidas bibliotecas de analizadores rápidos? Los objetivos de Parsec nunca han sido realmente la velocidad, sino la facilidad de uso y la claridad. Comparar con algo como attoparsec puede ser una comparación más justa, especialmente porque los tipos de cadena son más ByteString ( ByteString lugar de String ).

También me pregunto qué banderas de compilación se utilizaron. Siendo este otro post de trolling por el infame Jon Harrop, no me sorprendería si no se utilizaron optimizaciones para el código Haskell.

Answer 2

Actualmente estoy trabajando en la próxima versión de FParsec (v. 0.9), que en muchas situaciones mejorará el rendimiento hasta en un factor de 2 con respecto a la versión actual .

[Actualización: Se ha lanzado FParsec 0.9, consulte http://www.quanttec.com/fparsec ]

He probado la implementación del analizador F # de Jon con dos implementaciones de FParsec. El primer analizador FParsec es una traducción directa del analizador de djahandarie. El segundo utiliza el componente de precedencia de operador incrustable de FParsec. Como entrada, utilicé una cadena generada con el script OCaml de Jon con el parámetro 10, que me da un tamaño de entrada de aproximadamente 2.66MB. Todos los analizadores sintácticos se compilaron en modo de lanzamiento y se ejecutaron en .NET 4 CLR de 32 bits. Solo medí el tiempo puro de análisis y no incluí el tiempo de inicio o el tiempo necesario para construir la cadena de entrada (para los analizadores FParsec) o la lista de caracteres (analizador de Jon).

Medí los siguientes números (números actualizados para v. 0.9 en parens):

• Analizador enrollado a mano de Jon: ~ 230ms
• Analizador FParsec # 1: ~ 270ms (~ 235ms)
• Analizador FParsec # 2: ~ 110ms (~ 102ms)

A la luz de estos números, diría que los combinadores de analizadores definitivamente pueden ofrecer un rendimiento competitivo, al menos para este problema en particular, especialmente si se tiene en cuenta que FParsec

• genera automáticamente mensajes de error altamente legibles,
• admite archivos muy grandes como entrada (con retroceso arbitrario), y
• viene con un módulo de análisis de precedente de operador declarativo, configurable en tiempo de ejecución.

Aquí está el código para las dos implementaciones de FParsec:

Parser # 1 ( Traducción del parser de djahandarie ):

open FParsec

let str s = pstring s
let expr, exprRef = createParserForwardedToRef()

let fact = pint32 <|> between (str "(") (str ")") expr
let term =   chainl1 fact ((str "*" >>% (*)) <|> (str "/" >>% (/)))
do exprRef:= chainl1 term ((str "+" >>% (+)) <|> (str "-" >>% (-)))

let parse str = run expr str

Analizador # 2 ( Implementación FParsec Idiomatic ):

open FParsec

let opp = new OperatorPrecedenceParser<_,_,_>()
type Assoc = Associativity

let str s = pstring s
let noWS = preturn () // dummy whitespace parser

opp.AddOperator(InfixOperator("-", noWS, 1, Assoc.Left, (-)))
opp.AddOperator(InfixOperator("+", noWS, 1, Assoc.Left, (+)))
opp.AddOperator(InfixOperator("*", noWS, 2, Assoc.Left, (*)))
opp.AddOperator(InfixOperator("/", noWS, 2, Assoc.Left, (/)))

let expr = opp.ExpressionParser
let term = pint32 <|> between (str "(") (str ")") expr
opp.TermParser <- term

let parse str = run expr str

Answer 3

En pocas palabras, los combinadores de parser son lentos para el lexing.

Hubo una biblioteca de combinadores Haskell para construir lexers (consulte "Lazy Lexing is Fast" Manuel MT Chakravarty). Dado que las tablas se generaron en tiempo de ejecución, no hubo la molestia de la generación de código. La biblioteca se usó un poco, inicialmente se usaba en uno de los preprocesadores de FFI, pero no creo que alguna vez se haya subido a Hackage, así que tal vez era un poco inconveniente para el uso regular.

En el código OCaml anterior, el analizador se corresponde directamente en las listas de caracteres, por lo que puede ser tan rápido como la desestructuración de listas en el idioma principal (sería mucho más rápido que Parsec si se volviera a implementar en Haskell). Christian Lindig tenía una biblioteca OCaml que tenía un conjunto de combinadores de analizador y un conjunto de combinadores de lexer; los combinadores de lexer eran ciertamente mucho más simples que los de Manuel Chakravarty, y podría valer la pena rastrear esta biblioteca y marcarla antes de escribir un lexer generador.

Answer 4

He encontrado una solución Haskell que es 30 veces más rápida que la solución Haskell que publicaste (con mi expresión de prueba inventada).

Cambios principales:

1. Cambie Parsec / String a Attoparsec / ByteString
2. En la función de fact , cambie la read y many1 digit a decimal
3. Hizo que la recursión chainl1 estricta (elimine $! Para la versión más perezosa).

Intenté mantener todo lo que tenías lo más parecido posible.

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)

Creo que lo que concluí de esto es que la mayor parte de la desaceleración para el combinador analizador fue que estaba sentado en una base ineficiente, no que fuera un combinador analizador, per se.

Me imagino que con más tiempo y perfilado esto podría ir más rápido, ya que me detuve cuando pasé la marca de 25x.

No sé si esto sería más rápido que el analizador ascendente de precedencia transferido a Haskell. Tal vez esa sería una prueba interesante?