Комбинированные синтаксические анализаторы могут быть эффективными?

Question

Около 6 лет назад я сравнивал свои собственные синтаксические анализаторы в OCaml и обнаружил, что они были ~ 5 × медленнее, чем генераторы парсеров, предлагаемые в то время. Недавно я пересматривал эту тему и сравнивал Parsec Haskell с простым ручным списком precedence climbing parser, написанным на 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 

Answer 1

В настоящее время я работаю над следующей версией FParsec (версия 0.9), которая во многих ситуациях улучшит производительность на коэффициент до 2 раз относительно current version.

[Update: FParsec 0,9 был освобожден, см http://www.quanttec.com/fparsec]

Я проверил F # реализации парсера Jon против двух реализаций FParsec. Первый парсер FParsec - это прямой перевод парсера дджахандари. Второй использует встроенный компонент приоритета оператора FParsec. В качестве ввода я использовал строку, сгенерированную с помощью скрипта Jonam OCaml с параметром 10, который дает мне размер ввода около 2,66 МБ. Все синтаксические анализаторы были скомпилированы в режиме выпуска и выполнялись на 32-битной .NET 4 CLR. Я только измерил чистое время синтаксического анализа и не включил время запуска или время, необходимое для построения входной строки (для парсеров FParsec) или списка символов (анализатор Jon).

Я измерил следующие номера (обновленные номера для V 0,9 в круглых скобках.):

• Джон скрученных вручную анализатор: ~ 230ms
• FParsec анализатор # 1: ~ 270ms (~ 235ms)
• FParsec анализатор # 2: ~ 110ms (~ 102ms)

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

• автоматически генерирует весьма читаемые сообщения об ошибках,
• поддерживает очень большие файлы в качестве входных данных (с произвольными возвратами) и
• поставляется с декларативным, во время выполнения конфигурируемого модуля синтаксического анализатора оператора-старшинства.

Вот код для двух FParsec реализаций:

Parser # 1 (Перевод парсер 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 

Parser # 2 (реализация Идиоматические FParsec):

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 2

вы пробовали один из известных быстрых библиотек парсера? Цели Parsec никогда не были скоростью, но простотой использования и ясностью. Сравнение с чем-то вроде attoparsec может быть более справедливым сравнением, особенно потому, что типы строк, вероятно, будут более равными (ByteString вместо String).

Я также задаюсь вопросом, какие компиляционные флаги были использованы. Это был еще один троллинговый пост от пресловутого Джона Харропа, меня не удивило бы, если бы вообще никаких оптимизаций для кода Haskell не было.

Answer 3

Я придумал решение Haskell, которое на 30 раз быстрее, чем решение Haskell, которое вы разместили (с моим выдуманным тестовым выражением).

Основные изменения:

1. Изменение Парсек/Строка Attoparsec/байтовой строки
2. В функции fact измените read & many1 digit в decimal
3. Сделано chainl1 рекурсии строги (удалить $ за ленивее! версия).

Я попытался сохранить все остальное, что у вас было как можно более похожее.

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) 

Я предполагаю, что я пришел к выводу из этого является то, что большая часть замедления для синтаксического анализатора комбинатора, что он сидел на неэффективное основе, не то, что это был анализатор комбинатор, сам по себе.

Я думаю, что с большим количеством времени и профилирования это может ускориться, поскольку я остановился, когда я прошел мимо отметки 25 ×.

Я не знаю, будет ли это быстрее, чем синтаксический анализатор приоритета, перенесенный в Haskell. Может быть, это будет интересный тест?

Answer 4

Вкратце, комбинаторы парсеров медленны для лексинга.

Для сборки лексеров была сборщица комбинаторов Хаскеля (см. «Lazy Lexing is Fast» Manuel M. T. Chakravarty) - поскольку таблицы были созданы во время выполнения, не возникало хлопот генерации кода. Библиотека немного испортилась - она ​​была первоначально использована в одном из препроцессоров FFI, но я не думаю, что она когда-либо загружалась в Hackage, поэтому, возможно, это было слишком неудобно для регулярного использования.

В приведенном выше коде OCaml синтаксический анализатор непосредственно сопоставляется с символьными списками, поэтому он может быть таким же быстрым, как разрушение списка на хост-языке (он был бы намного быстрее, чем Parsec, если бы он был повторно реализован в Haskell) , Кристиан Линдиг имел библиотеку OCaml, в которой был набор комбинаторов парсеров и набор комбинаторов лексера. Комбинаторы лексера были, конечно, намного проще, чем Manuel Chakravarty, и, возможно, было бы полезно отслеживать эту библиотеку и оценивать ее перед написанием лексера генератор.