clojure - 有什么方法可以加快 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

语法是错误的。它不能满足。

• 每个都file以clause.
• 每个都clause以'0'.
• 在literal中clause，作为一个贪婪的正则表达式，会吃掉最终的'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'字符处分成连续comment的 s；
• 或在初始'c'.

这意味着每个尾部都必须呈现给语法的其余部分，其中包括literalInstaparse 无法看到的正则表达式。因此，一切都必须尝试，最终都会失败。难怪它很慢。

---

我怀疑这个文件实际上是分成几行的。并且您的问题源于试图将换行符与其他形式的空白混为一谈。

请允许我轻轻地指出，使用几个小例子——这就是我所做的一切——可能会为你省去很多麻烦。

Answer 2

我认为您对 * 的广泛使用导致了问题。你的语法太模棱两可/雄心勃勃（我猜）。我会检查两件事：

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

这将显示您的语法定义中有多少歧义：检查“歧义语法”。

阅读 Engelberg性能说明，这将有助于了解您自己的问题，并可能找出最适合您的方法。