Can parser combinators be made efficient?

Posted by Jon Harrop on Stack Overflow See other posts from Stack Overflow or by Jon Harrop
Published on 2010-12-30T01:46:54Z Indexed on 2010/12/30 14:54 UTC
Read the original article Hit count: 294

Around 6 years ago, I benchmarked my own parser combinators in OCaml and found that they were ~5× slower than the parser generators on offer at the time. I recently revisited this subject and benchmarked Haskell's Parsec vs a simple hand-rolled precedence climbing parser written in F# and was surprised to find the F# to be 25× faster than the Haskell.

Here's the Haskell code I used to read a large mathematical expression from file, parse and evaluate it:

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"

and here's my self-contained precedence climbing parser in F#:

let rec (|Expr|) (P(f, xs)) = Expr(loop (' ', f, 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)
      let op = match op with
        | '+' -> (+) | '-' -> (-) | '*' -> (*) | '/' -> (/)
      loop (oop, op f h, xs)
  | _, f, xs -> f, xs
and (|P|) = function
  | '('::Expr(f, ')'::xs) -> P(f, xs)
  | c::xs when '0' <= c && c <= '9' -> P(int(string c), xs)

My impression is that even state-of-the-art parser combinators waste a lot of time back tracking. Is that correct? If so, is it possible to write parser combinators that generate state machines to obtain competitive performance or is it necessary to use code generation?

© Stack Overflow or respective owner

Related posts about haskell

Related posts about F#