"Necesito rendimiento (para 20Mb) ... así que decidí Javascript". Estos son contradictorios
Los analizadores de descenso recursivo cuidadosamente codificados pueden ser bastante rápidos, pero debe escribir mucho código. En general, los analizadores LALR (1) (generados por Bison a partir de una gramática, etc.) son bastante rápidos y bastante fáciles de codificar. (Hay documentos técnicos que muestran cómo compilar los analizadores LALR directamente a código de máquina; estos analizadores son increíblemente rápidos, pero es necesario implementar una gran cantidad de maquinaria personalizada para compilar uno).
Si quieres un análisis de alto rendimiento con un mínimo de sudor, debes considerar LRStar. (Conozco y respeto mucho al autor, pero por lo demás no tengo nada que hacer). Esto produce analizadores LALR muy rápidos. Desventaja: tienes que hacer tu gramática LALR compatible. Tendrá que ampliar sus "reglas" de la misma manera que extender cualquier otro programa C: escribiendo el código C. Eso no parece mucho peor que escribir JavaScript en mi humilde opinión, pero las reglas probablemente se ejecutarán mucho más rápido y en la escala que está contemplando esto importará.
El análisis de GLR es necesariamente más lento que LALR porque tiene más contabilidad por hacer. Pero eso es solo un factor constante. Puede ser significativo (p. Ej., 100x) en comparación con un motor de alto rendimiento , como LRStar. Puede valer la pena, porque es mucho más fácil adaptar tu gramática a tu forma, y una gramática menos intrincada probablemente hará que escribir reglas personalizadas sea más fácil.Si realmente tiene 1 archivo MSLOC, a estos analizadores les gustará tener una velocidad media en el mejor de los casos.
PEG básicamente es un retroceso. Tiene que probar cosas, y retroceder cuando no funcionan. Deben ser más lentos que los analizadores LALR al menos por la cantidad de retrocesos que realizan. También tienes el problema de configuración gramatical.
Lo que descubrirá, sin embargo, es que el análisis simplemente no es suficiente si desea hacer algo un poco sofisticado. En ese caso, no desea optimizar al analizar; desea optimizar en la infraestructura para el análisis de programas. Vea mi ensayo en Life After Parsing para otra alternativa.
¡Gracias! ¿Y qué hay de la comparación de rendimiento? – shytikov
Si las restricciones que se le aplicarán a su gramática desde un analizador LR como GLR o LALR (GLR solo usa un poco más de memoria y es un poco más lento), entonces es probable que LR sea un analizador más rápido. Sin embargo, el analizador tarda más en generar ya que necesita calcular sus tablas. Pero en el caso general, los analizadores LR son máquinas muy eficientes. – Dervall
Nadie más que el tipo que usa el generador de analizadores sintácticos, se preocupa por cuánto tiempo tarda el generador del analizador en ejecutarse. Incluso a él no le importa mucho; los analizadores grandes se generan en segundos, al menos para los generadores de analizadores LALR y la mayoría de los otros que conozco. –