Un modo per velocizzare l'instaparse?

Question

Sto cercando di utilizzare instaparse su un DIMACS il file meno di 700k in termini di dimensioni, con la seguente grammatica

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

chiamare in questo modo

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

e sta prendendo un centinaio di secondi. Sono tre ordini di grandezza più lenti di quanto speravo. C'è un modo per velocizzarlo, un modo per modificare la grammatica o qualche opzione che mi manca?

Answer 1

La grammatica è sbagliata. Non può essere soddisfatto.

• Ogni file termina con un clause.
• Ogni clause termina con un '0'.
• Il literal nel clause, essendo un greedy reg-exp, mangerà l'ultimo '0'.

Conclusione: n. clause sarà mai trovato.

Ad esempio ...

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

possiamo analizzare un literal

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

... ma non un 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*" 

---

W è così lento?

Se c'è un comment:

• può ingoiare l'intero file;
• o essere rotto in qualsiasi 'c' carattere in successivi comment s;
• o terminare in qualsiasi momento dopo l'iniziale 'c'.

Questo implica che ogni coda deve essere presentata al resto della grammatica, che include un reg-exp per literal che Instaparse non può vedere all'interno.Quindi tutti devono essere provati e alla fine tutti falliranno. Non c'è da stupirsi che sia lento.

---

ho il sospetto che questo file è in realtà diviso in linee. E che i tuoi problemi derivano dal cercare di confondere le nuove linee con altre forme di spazio bianco.

Posso sottolineare gentilmente che giocare con alcuni piccoli esempi - che è tutto ciò che ho fatto - potrebbe averti risparmiato un sacco di problemi.

Answer 2

Penso che il tuo ampio uso di * stia causando il problema. La tua grammatica è troppo ambigua/ambiziosa (credo). Vorrei verificare due cose:

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

che vi mostrerà quanta ambiguità è nella definizione della grammatica: check "grammatica ambigua".

Leggi Engelberg performance notes, aiuterebbe a capire il tuo problema e probabilmente a trovare quello che si adatta meglio per te.