0

我需要分析 Elisp (Emacs Lisp) 代码，所以我使用Instaparse为它编写了一个解析器。我预计它会很慢，但是每秒执行 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))
4

2 回答 2

1

正如@akond 建议的那样，我将语法移植到了 ANTLR（使用https://github.com/aphyr/clj-antlr）。它在 20 毫秒或更短的时间内解析 1k 行......是的，看起来 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))
于 2020-10-03T07:41:09.530 回答
0

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

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

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

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

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

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

于 2020-10-02T08:50:52.303 回答