Есть ли способ ускорить инстапарс?

Question

Я пытаюсь использовать instaparse для файла dimacs размером менее 700 КБ со следующей грамматикой

<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' характер в последовательный comments;
• или прекратить в любой момент после первоначального'c',

Это подразумевает, что каждый хвост должен быть представлен остальной части грамматики, которая включает в себя reg-exp для literal что Instaparse не может видеть внутри. Следовательно, все должны быть испытаны, и все в конечном итоге потерпит неудачу. Не удивительно, что это медленно.

---

Я подозреваю, что этот файл на самом деле разделен на строки. И что ваши проблемы возникают из-за попыток сопоставить новые строки с другими формами пустого пространства.

Позвольте мне мягко указать на то, что игра с несколькими крошечными примерами - и это все, что я сделал - могла бы сэкономить вам массу хлопот.

Answer 2

Я думаю, что ваше широкое использование * вызывает проблему. Ваша грамматика слишком двусмысленная / амбициозная (наверное). Я бы проверил две вещи:

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

Это покажет вам, как много неопределенности в вашем определении грамматики: отметьте "неоднозначность грамматики".

Прочитайте заметки о производительности Engelberg, это поможет понять вашу проблему и, возможно, выяснить, что вам больше подходит.