有什么办法可以加快 instaparse 的速度吗？

Question

我正在尝试在小于 700k 的 dimacs 文件上使用 instaparse，语法如下

<file>=<comment*> <problem?> clause+
comment=#'c.*'
problem=#'p\s+cnf\s+\d+\s+\d+\s*'
clause=literal* <'0'>
<literal>=#'[1-9]\d*'|#'-\d+'

像这样打电话

(def parser
  (insta/parser (clojure.java.io/resource "dimacs.bnf") :auto-whitespace :standard))
...
(time (parser (slurp filename)))

这大约需要一百秒。这比我希望的要慢三个数量级。有什么方法可以加快速度、调整语法或我缺少的某些选项吗？

Answer 1

我认为您对 * 的大量使用导致了问题。你的语法太ambiguous/ambitious（我猜）。我会检查两件事：

;;run it as
 (insta/parses grammar input)
;; with a small input

这将告诉您语法定义中有多少歧义：check "ambiguous grammar".

阅读 Engelberg performance notes，这将有助于了解您自己的问题，并可能找出最适合您的内容。

Answer 2

语法错误。它无法满足。

每个 file 都以 clause 结尾。
每个 clause 都以 '0' 结尾。
clause中的literal，作为greedy reg-exp，会吃最后的'0'。

结论：永远找不到 clause。

例如...

=> (parser "60")
Parse error at line 1, column 3:
60
  ^
Expected one of:
"0"
#"\s+"
#"-\d+"
#"[1-9]\d*"

我们可以解析一个literal

=> (parser "60" :start :literal)
("60")

...但不是 clause

=> (parser "60" :start :clause)
Parse error at line 1, column 3:
60
  ^
Expected one of:
"0" (followed by end-of-string)
#"\s+"
#"-\d+"
#"[1-9]\d*"

为什么这么慢？

如果有comment：

它可以吞下整个文件；
或在任何 'c' 字符处被分解为连续的 comments;
或在初始 'c'.

这意味着每个尾巴都必须呈现给语法的其余部分，其中包括 Instaparse 在内部看不到的 literal 的 reg-exp。所以都得试，最后都得失败。难怪它很慢。

我怀疑这个文件实际上分为行。而且您的问题是由于试图将换行符与其他形式的 white-space 混为一谈。

请允许我温和地指出，尝试一些小示例 - 这就是我所做的一切 - 可能会为您省去很多麻烦。

有什么办法可以加快 instaparse 的速度吗？

Any way to speed up instaparse?

clojure

instaparse