Невероятно плохое время синтаксического анализа

Question

Мне нужно проанализировать код Elisp (Emacs Lisp), поэтому я написал для него парсер с помощью Instaparse. Я ожидал, что это будет медленно, но делать 1 Кб строк в секунду слишком медленно, чтобы быть правильным даже на калькуляторе (или моем довольно старом i7). Неужели все так плохо или я делаю что-то крайне не так?

Это недвусмысленно, и я старался как минимум смотреть вперед / назад, к сожалению, Elisp очень либерален в отношении того, что представляет собой символ, поэтому мне пришлось добавить туда несколько вперед / назад, чтобы различать числа и символы. Также я пытался определить это, анализируя символы, числа и ключевые слова как "идентификатор", это возвращало мне только 30% времени. Судя по моим тестам, похоже, что Instaparse много борется с рекурсивными правилами, а шепелявые имеют очень рекурсивную природу, так что, возможно, я не напортачил - это просто так медленно...

Парсер:

(ns slowparse
  (:require [clojure.string :as str]
            [instaparse.combinators :as c]
            [instaparse.core :as insta]))

(def grammar
  "Elisp grammar."
  "<root> = any +

  <any> = sexp | keyword | number | symbol | prefix | string | vector |
          comment | whitespace | char | Epsilon

  comment = comment-tok #'(?:[^\\n]*|$)'

  string = <str-l-tok> #'(?:(?:\\\\\\\\)|(?:\\\\\")|[^\"])*' <str-r-tok>

  char = <char-tok> #'(?:(?:\\\\(?:C|M)-)|(?:\\\\))?(?:.|\\s)'

  <whitespace> = <#'\\s+'>

  sexp   = sexp-l-tok any + sexp-r-tok

  vector = vec-l-tok any + vec-r-tok

  <prefix>   = quote | template | spread | hole

  <prfxbl> = sexp | symbol | keyword | number | prefix | vector

  quote    = quote-tok prfxbl
  template = tmpl-tok prfxbl
  hole     = hole-tok ! spread-tok prfxbl
  spread   = hole-tok spread-tok prfxbl

  <sexp-l-tok>      = <'('>
  <sexp-r-tok>      = <')'>

  <vec-l-tok>       = <'['>
  <vec-r-tok>       = <']'>

  <str-l-tok>       = <'\"'>
  <str-r-tok>       = <'\"'>

  <quote-tok>       = '#' ? <\"'\">

  <tmpl-tok>        = <'`'>

  <num-b-x-tok>     = '#'

  <hole-tok>        = <','>

  <spread-tok>      = <'@'>

  <comment-tok>     = <';'>

  <char-tok>        = '?'

  <kv-tok>          = <':'>

  symbol    = ! ( number | kv-tok | comment-tok | num-b-x-tok | char-tok )
               ident

  keyword = kv-tok ident

  number    = num-b10 | num-bx
  <num-b10> = #'[-+]?(?:(?:[\\d]*\\.[\\d]+)|(?:[\\d]+\\.[\\d]*)|(?:[\\d]+))' &
              ( ! ident )
  <num-bx>  = #'(?i)#(?:b|o|x|(?:\\d+r))[-+]?[a-z0-9]+'")

(def ident
  {:ident
   (let [esc-ch (str/join ["\\[" "\\]" "\\(" "\\)" "\"" "\\s" "'" "," "`" ";"])
         tmpl "(?:(?:\\\\[{{ec}}])|[^{{ec}}])+"]
     (->> esc-ch (str/replace tmpl "{{ec}}") c/regexp c/hide-tag))})

(insta/defparser ^{:doc "Elisp parser."} elisp-parser
  (merge ident (c/ebnf grammar))
  :start :root)

(def test-text (slurp "/tmp/foo.el"))

(time (insta/parse elisp-parser test-text))

Answer 1

Как предложил @akond, я перенес грамматику на ANTLR (используя https://github.com/aphyr/clj-antlr). Он разбирает 1k строк за 20 мс или меньше... Да, похоже, Instaparse действительно медленный.

Не нужно было сильно менять, но Instaparse определенно чувствует себя намного приятнее писать правила. Он имеет простой порядок и просмотр вперед / назад, стандартное регулярное выражение, простой способ скрыть мусор.

Грамматика ANTLR:

(ns fastparse
  (:require [clj-antlr.core :as antlr]))

(def grammar
  "Elisp grammar."
  "grammar EmacsLisp ;

   source: any* EOF ;

   any: list | keyword | number | symbol | prefix | string | vector | char |
        whitespace | comment;

   vector: '[' any* ']' ;

   list: '(' any* ')' ;

   prefix: quote | template | spread | hole ;

   quote: '#' ? '\\'' any ;

   template: '`' any ;

   spread: ',@' any ;

   hole: ',' any ;

   number: NUMB10 | NUMBX ;

   char: CHAR ;

   string: STRING ;

   keyword: KEYWORD ;

   symbol: IDENT ;

   whitespace: WS ;

   comment: COMLINE ;

   CHAR: '?' ( ( '\\\\' ( 'C' | 'M' ) '-' ) | '\\\\' )? . ;

   STRING: '\"' ( '\\\\\\\\' | '\\\\\"' | . )*? '\"' ;

   NUMB10: [+-] ? ( ( D* '.' D+ ) | ( D+ '.' D* ) | D+ ) ;

   NUMBX: '#' ( 'b' | 'o' | 'x' | ( D+ 'r' ) ) [-+]? ( A | D )+ ;

   fragment
   D: '0'..'9' ;

   fragment
   A: 'a'..'z' ;

   KEYWORD: ':' IDENT ;

   IDENT: ( ( '\\\\' [\\\\[\\]() \\n\\t\\r\"',`;] )+? |
            ( ~[[\\]() \\n\\t\\r\"',`;] )+? )+ ;

   COMLINE: ';' ~[\\n\\r]* ;

   WS: [ \\n\\t\\r]+ ;")

(def elisp-str->edn (antlr/parser grammar))

(def text (slurp "/tmp/foo.el"))

(time (elisp-str->edn text))

Answer 2

Если вас интересует скорость и вы не хотите беспокоиться о переполнении стека, вы можете попробовать Tunnel Grammar Studio, генератор парсеров, над которым я работаю. Сгенерированные из него парсеры являются итеративными во время лексирования, синтаксического анализа, построения дерева, итерации дерева, преобразования дерева в строку и освобождения дерева. Принятые грамматики находятся в ABNF (RFC 5234) с учетом регистра на токен (RFC 7405).

Its a good idea to have a deterministic grammar with any parser you use. TGS does check for LL(1) conflicts at compile time, and will help you to create a deterministic grammar by visualizing the conflict places.

There is a demo of the tool, you can test the speed yourself. There is an option in the tool to generate fully ready test case project that will log into the console at runtime the time taken to parse, iterate the tree and free it, by only supplying the input data. Meaning that no development (except compiling the generated code) from you is expected if you want to test the speed for a grammar.

In my tests with a JSON grammar (RFC 8259) with removed ambiguity, that only emits syntax tree build events (like SAX) the iterative parser runs with around 8 megabytes per second, that are many lines per second and takes memory only proportional to the depth of the parsing, because only one token is technically needed at runtime for LL(1) grammars, i.e. it is practically "streaming" the input.

You can have also statically typed or dynamically typed concrete syntax tree, or dynamically typed abstract syntax tree with different levels of abstraction (i.e. automatic node pruning). The syntax trees builders (if chosen) for this trees are using the build events to create the relevant trees. You will need an ABNF grammar and C++ as a language target however.

The tool supports token ranges inside the parser grammar (additionally to the character ranges inside the lexer grammar). This means that you may develop your grammar without the extra care of the lexical rules order.