有办法加快速度吗？

Question

我试图在小于700 K大小的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 in 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字符；
• 或在初始'c'之后的任何点终止。

这意味着每个尾都必须呈现给语法的其余部分，其中包括一个Instaparse无法看到的literal的reg-exp。因此，所有这些都必须加以尝试，最终都将失败。怪不得这么慢。

我怀疑这个文件实际上被分成了几行。你的问题产生于试图将换行符与其他形式的空白混为一谈。

请允许我温和地指出，玩几个小例子--这就是我所做的--可能会给你省下不少麻烦。

Answer 2

我认为你对*的广泛使用造成了这个问题。你的语法太模糊了/太雄心勃勃了(我想)。我会检查两件事：

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

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

阅读Engelberg 执行情况说明，它将有助于理解您自己的问题，并可能找到最适合您的方法。