令人难以置信的糟糕解析时间

Question

我需要分析 Elisp (Emacs Lisp) 代码，所以我使用 Instaparse 为它编写了一个解析器。我预计它会很慢，但每秒执行 1k 行的速度太慢了，即使在计算器（或我相当老的 i7）上也是如此。会这么糟糕还是我做错了什么？

它是明确的，我尽量保持外观 ahead/behinds，不幸的是，Elisp 对符号的构成非常自由，所以我不得不在其中添加一些 ahead/behinds区分数字和符号。我也试图通过将符号、数字和关键字解析为“ident”来推迟它，它只给了我 30% 的时间。从我的测试来看，Instaparse 似乎在递归规则方面遇到了很多困难，而 lisps 具有高度递归的性质，所以也许我没有把它搞砸 - 它只是那么慢......

解析器：

(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

如果您对速度感兴趣，并且不想担心堆栈溢出的发生，您可以试试 Tunnel Grammar Studio，我正在研究的一个解析器生成器。从中生成的解析器在词法分析、解析、树构造、树迭代、树到字符串转换和树释放期间是迭代。接受的语法在 ABNF (RFC 5234) 中，每个标记区分大小写 (RFC 7405)。

对您使用的任何解析器使用确定性语法是个好主意。 TGS 会在编译时检查 LL(1) 冲突，并将通过可视化冲突位置来帮助您创建确定性语法。

有工具的demo，可以自己测试速度。该工具中有一个选项可以生成完全就绪的测试用例项目，该项目将在运行时登录到控制台，只需提供输入数据即可解析、迭代树并释放它。这意味着如果您想测试语法的速度，则不需要您进行任何开发（编译生成的代码除外）。

在我使用 JSON 语法 (RFC 8259) 进行的测试中，消除了歧义，它只发出语法树构建事件（如 SAX），迭代解析器以每秒大约 8 兆字节的速度运行，即 [=每秒 22=]many 行并且只占用与解析深度成比例的内存，因为 LL(1) 语法在运行时技术上只需要一个标记，即它实际上是“流式传输”输入。

您还可以拥有静态类型或动态类型的具体语法树，或具有不同抽象级别的动态类型抽象语法树（即自动节点修剪）。此树的语法树构建器（如果选择）正在使用构建事件来创建相关树。但是，您将需要 ABNF 语法和 C++ 作为语言目标。

该工具支持解析器语法内的标记范围（除了词法分析器语法内的字符范围）。这意味着您可以在不额外注意词汇规则顺序的情况下开发语法。

Answer 2

正如@akond 建议的那样，我将语法移植到 ANTLR（使用 https://github.com/aphyr/clj-antlr）。它在 20 毫秒或更短的时间内解析 1k 行...是的，看起来 Instaparse 真的很慢。

不需要做太多改变，但 Instaparse 编写规则确实感觉更好。它具有简单的排序和外观 ahead/behind、标准正则表达式、隐藏垃圾的简单方法。

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))

令人难以置信的糟糕解析时间

Unbelievably bad parse time

optimization

performance

parsing

clojure

instaparse