异常糟糕的解析时间

Question

我需要分析Elisp (Emacs )代码，所以我使用英斯塔帕斯为它编写了一个解析器。我以为它会很慢，但是每秒做1k行太慢了，即使是在计算器(或我非常老的i7)上也是如此。会有那么糟糕吗?还是我做错了什么？

这是明确的，我试图保持向前/后面的最低限度，不幸的是，Elisp是非常自由的构成作为一个符号，所以我不得不添加一些在前面/后面，以区分数字和符号。此外，我试图通过将符号、数字和关键字解析为"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

正如@akond建议的那样，我将语法移植到了ANTLR (使用https://github.com/aphyr/clj-antlr)。它在20毫秒或更短的时间内分析1k行.看来英斯塔帕斯真的很慢。

不需要改变太多，但是因斯塔帕斯确实觉得写规则更好。它有简单的排序和展望，标准的正则表达式，简单的方法隐藏垃圾。

反语法：

(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

如果您对速度感兴趣，并且不想担心堆栈溢出发生，您可以尝试隧道语法工作室，这是我工作的解析器生成器。生成的解析器是在词法、解析、树构造、树迭代、树到字符串转换和树释放过程中产生的迭代。接受的语法在ABNF (RFC 5234)中，每个令牌的大小写敏感(RFC 7405)。

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

有一个演示的工具，你可以自己测试速度。该工具中有一个选项可以生成完全就绪的测试用例项目，该项目将在运行时登录到控制台，解析、迭代和释放树所需的时间，只需提供输入数据。这意味着，如果您想测试语法的速度，就不会期望您的开发(编译生成的代码除外)。

在我的测试中，JSON语法(RFC 8259)去掉了歧义，只有发射语法树构建事件(如SAX)迭代解析器每秒运行约8MB，即每秒多行，并且只占用与解析深度成比例的内存，因为LL(1)语法在运行时只需要一个令牌，即实际上是“流”输入。

您还可以拥有静态类型或动态类型的具体语法树，或者具有不同抽象级别(即自动节点剪枝)的动态类型化抽象语法树。此树的语法树构造器(如果被选中)将使用构建事件创建相关的树。然而，您将需要一个ABNF语法和C++作为语言目标。

该工具支持解析器语法中的标记范围(除了lexer语法中的字符范围之外)。这意味着你可以在没有词汇规则顺序的情况下发展你的语法。