Scala Parser Combinator, ambiguous Grammar & Parse Forest

Question

Estoy tratando de hacer que el analizador devuelva todos los resultados de análisis posibles (bosque de análisis sintáctico) de una gramática ambigua y elegir del bosque de análisis evaluando el contexto/historial del usuario y un conocimiento base. Por razones de rendimiento, esto probablemente debería hacerse con el analizador packrat y un parámetro de límite de búsqueda/límite superior para limitar el número de llamadas recursivas al aplicar reglas de producción para evitar bucles infinitos.

Siendo nuevo en Scala y sus Parser Combinators, no puedo encontrar la manera de hacerlo ni de hacer nada. ¿Podría alguien ayudarme? Muy apreciado.

Saludos cordiales, Thomas Juan

Answer 1

No se puede hacer esto con Scala de una función de combinadores de analizadores sintácticos. Los combinadores de Packrat están restringidos solo a gramáticas no ambiguas. Si intenta lidiar con la ambigüedad, pierde la capacidad de memorizar y la complejidad de análisis se convierte en O (k^n) incluso para pistas no ambiguas. Entonces, no hagas eso.

Lo que desea es un marco de combinación del analizador que maneje correctamente la ambigüedad. Hasta donde yo sé, el único marco de este tipo para Scala es mi GLL combinators. La sintaxis es casi idéntica a los combinadores de analizador de Scala (la principal diferencia es que las funciones de mayor aria funcionan correctamente ), pero la salida es Stream[A], donde A es el tipo de resultado. Por lo tanto, obtienes un bosque de análisis. Tenga en cuenta que el resultado no es en realidad un SPPF (bosque de análisis empaquetado compartido), por lo que si produce un número exponencial de resultados, la secuencia tendrá un tamaño proporcional. Esto se hizo para mantener la máxima flexibilidad en el tipo de resultado.

GLL combinadores es O (n^3) en el peor caso, incluso para gramáticas patológicamente ambiguas. En el caso promedio, donde el camino de análisis sintáctico no es ambiguo, los combinadores GLL son O (n). La sobrecarga de tiempo constante es actualmente un poco excesiva, pero la optimización es un proyecto en curso. Usamos los combinadores GLL en producción en Precog, por lo que puede esperar que la biblioteca se mantenga bien en el futuro.