"Ho bisogno di prestazioni (per 20 Mb) ... quindi ho deciso Javascript". Questi sono contraddittori.
Gli analizzatori di discesa ricorsivi codificati con cura possono essere abbastanza veloci, ma è necessario scrivere molto codice. Generalmente, i parser LALR (1) (generati da Bison da una grammatica ecc.) Sono abbastanza veloci e facili da codificare. (Ci sono documenti tecnici che mostrano come compilare i parser LALR direttamente sul codice macchina, questi parser sono incredibilmente veloci ma è necessario implementare un sacco di macchinari personalizzati per crearne uno).
Se si desidera eseguire il parsing di un rendimento elevato con una quantità minima di sudore, è necessario considerare LRStar. (Conosco e rispetto molto l'autore ma per il resto non ho nulla da fare). Questo produce parser LALR molto veloci . Lato negativo: devi rendere la tua grammatica LALR compatibile. Dovrai estendere le tue "regole" nello stesso modo in cui tu, , estendi qualsiasi altro programma C: scrivendo codice C. Questo non sembra molto peggio rispetto alla scrittura di JavaScript IMHO, ma probabilmente le regole verranno eseguite molto più velocemente e alla scala che state considerando ciò sarà importante.
L'analisi GLR è necessariamente più lenta rispetto a LALR perché ha più contabilità da fare. Ma questo è solo un fattore costante. Può essere significativo (ad es. 100x) su un motore di prestazioni alto come LRStar. Potrebbe valere la pena, perché è molto più facile sterilizzare la grammatica e una grammatica meno complessa probabilmente renderà più semplice la scrittura di regole personalizzate.Se hai veramente 1 file MSLOC, questi parser preferiranno la velocità media nel migliore dei casi.
PEG è fondamentalmente un backtracking. Deve provare le cose e tornare indietro quando non funzionano. Devono essere più lenti dei parser LALR di almeno la quantità di backtracking che fanno. Hai anche il problema di modellatura della grammatica.
Quello che scoprirete, però, è che l'analisi semplicemente non è sufficiente se volete fare qualcosa di leggermente più sofisticato. In tal caso, non si desidera ottimizzare l'analisi; si desidera ottimizzare l'infrastruttura per l'analisi del programma. Vedi il mio articolo su Life After Parsing per un'altra alternativa.
fonte
2012-08-01 14:23:06
Grazie! E per quanto riguarda il confronto delle prestazioni? – shytikov
Se le restrizioni che verranno applicate alla grammatica da un parser LR come GLR o LALR (GLR utilizza solo un po 'di memoria in più, ed è un po' più lento) allora è probabile che LR sarà un parser più veloce. Il parser richiede più tempo per generare, dal momento che ha bisogno di calcolare le sue tabelle. Ma nel caso generale i parser LR sono macchine molto efficienti. – Dervall
Nessuno, a parte il tizio che usa il generatore di parser, si preoccupa di quanto tempo impiega il parser generator per funzionare. Anche a lui non importa molto; i grandi parser sono generati in secondi, almeno per i generatori di parser LALR e la maggior parte degli altri che conosco. –