parsing - Scala Parsers: disponibilidad, diferencias y combinación?

parser-generator parser-combinators (4)

Solo quería actualizar esta respuesta con un puntero a la última iteración del proyecto sancochado, llamado parboiled2:

parboiled2 solo está dirigido a Scala (a diferencia de Scala + Java), hace uso de las macros de Scala y se mantiene de forma muy activa.

Mi pregunta es sobre Scala Parsers:

Cuáles están disponibles (en la biblioteca estándar y fuera),
cual es la diferencia entre ellos,
comparten una API común y
¿Pueden combinarse diferentes Parsers para analizar una cadena de entrada?

Encontré al menos estos:

Analizador "estándar" de Scala (parece ser un analizador de LL)
Analizador de Packrat de Scala (desde 2.8, es un analizador LALR)
El analizador Parboiled (analizador PEG?)
Combinador del analizador GLL de Spiewak

También está la implementación por Dan Spiewak de los combinadores de analizadores GLL .

También hay un nuevo enfoque conocido como "análisis sintáctico con derivados". El enfoque se describe here . Hay una implementación en Scala por Daniel Spiewak.

Vale la pena señalar que los combinadores de analizadores estándar de Scala no son LL, ni los combinadores de Packrat LALR. Los combinadores de analizadores son una forma de descenso recursivo con retroceso infinito. Puedes pensar un poco como "LL (*)". La clase de idiomas soportados por esta técnica es precisamente la clase de lenguajes libres de contexto sin ambigüedades, o la misma clase que LALR (1) y Packrat. Sin embargo, la clase de gramática es bastante diferente, y la debilidad más notable es que no admite la recursión a la izquierda.

Los combinadores de Packrat son compatibles con la recursión a la izquierda, pero aún no son compatibles con muchas otras características más sutiles de LALR. Esta debilidad en general se deriva del operador de elección ordenada, lo que puede conducir a algunos errores de gramática diabólicamente difíciles, así como previene ciertas agradables formulaciones gramaticales. El ejemplo más visto de estos errores ocurre cuando accidentalmente ordena las opciones ambiguas como las más cortas primero, lo que resulta en una coincidencia ambiciosa que impide que se pruebe la rama correcta. LALR no tiene este problema, ya que simplemente intenta todas las ramas posibles a la vez, difiriendo el punto de decisión hasta el final de la producción.