Combinador o generador de analizador GLL en/para C o C++

parsing parser-combinators

Question

¿Existe alguna implementación existente del algoritmo GLL , ya sea en forma de combinadores de analizador (preferido) o como un generador de analizador para C o C ++?

Mis requisitos son que la salida sea un bosque de análisis empaquetado compartido (SPPF) que luego puedo desambiguar utilizando reglas semánticas y / o contextuales. Hay otros algoritmos de análisis, como el GLR, que son capaces de hacer frente a las gramáticas generales sin contexto, sin embargo, todos los generadores de analizador GLR que puedo encontrar devuelven el primer árbol de análisis exitoso o fallan si queda alguna ambigüedad al final.

Answer 1

¿Qué pasa si prueba GLL Combinators ? Aunque utiliza Scala, puede escribir envolturas "delgadas" para él mediante el JNI .

GLL Combinators es un marco diseñado para implementar el algoritmo de análisis GLL (Scott y Johnstone, LDTA 2009) de una manera funcional. Más específicamente, el marco hace uso de combinadores de analizadores atómicos para componer gramáticas que luego se evalúan utilizando el algoritmo GLL. El marco proporciona una sintaxis para esta tarea que es casi idéntica a la del marco combinador de analizador integrado en Scala. Por ejemplo, podemos representar la clásica "gramática de paréntesis" utilizando los combinadores GLL:

lazy val expr: Parser[Any] = ( "(" ~ expr ~ ")" | "" )

Como indica la anotación de tipo, expr hará referencia a una instancia de tipo Parser[Any] . Es decir, un analizador atómico que consume alguna entrada y devuelve un valor de tipo Any . Podemos invocar este analizador contra una entrada de String de la siguiente manera:

expr("((()))")

Esto devolverá un valor de tipo Stream[Result[Any]] . El Result[A] ADT se define como uno de los siguientes (para algunos tipos A ):

• Success[A] : representa un análisis exitoso y contiene el valor resultante.
• Error: representa un análisis fallido y contiene el mensaje de error relevante, así como el resto de la secuencia de análisis (los caracteres que no se consumieron).

Si algún resultado es exitoso (es decir, una instancia de Success[A] ), no se devolverán fallas. Por lo tanto, el Stream devuelto será completamente homogéneo, con Success o Failure , pero no con ambos. Se devuelve un Stream lugar de un solo valor para permitir la ambigüedad en la gramática (ver más abajo).

Vale la pena mencionar que GLL es una forma de análisis de descendencia recursiva . Tiene todas las ventajas del descenso recursivo convencional, que incluye un flujo de control intuitivo, posicionamiento arbitrario de acciones semánticas y mensajes de error superiores. De hecho, es el hecho de que la GLL es descendente recursiva lo que permite que se implemente utilizando combinadores atómicos. Otros algoritmos que comparten las mismas capacidades que GLL (como GLR, Earley Parsing, etc.) son fundamentalmente incompatibles con el modelo de combinator debido a su flujo de control altamente intuitivo. En el análisis de GLL, el flujo de control sigue el de la gramática, como lo hace en los combinadores de analizadores tradicionales o en cualquier otra forma de descenso recursivo.