Combinador de analizadores sintácticos

En programación informática , un combinador de analizadores sintácticos es una función de orden superior que acepta varios analizadores como entrada y devuelve un nuevo analizador como salida. En este contexto, un analizador sintáctico es una función que acepta cadenas como entrada y devuelve alguna estructura como salida, normalmente un árbol de análisis sintáctico o un conjunto de índices que representan las posiciones en la cadena donde el análisis se detuvo correctamente. Los combinadores de analizadores sintácticos permiten una estrategia de análisis sintáctico descendente recursivo que facilita la construcción y prueba modular por partes. Esta técnica de análisis sintáctico se denomina análisis sintáctico combinatorio .

Los analizadores sintácticos que utilizan combinadores se han utilizado ampliamente en la creación de prototipos de compiladores y procesadores para lenguajes específicos de dominio, como las interfaces de usuario en lenguaje natural para bases de datos, donde las acciones semánticas complejas y variadas están estrechamente integradas con el procesamiento sintáctico. En 1989, Richard Frost y John Launchbury demostraron ^{[ 1 ]} el uso de combinadores de analizadores sintácticos para construir intérpretes de lenguaje natural . Graham Hutton también utilizó funciones de orden superior para el análisis sintáctico básico en 1992 ^{[ 2 ]} y el análisis sintáctico monádico en 1996. ^{[ 3 ]} SD Swierstra también mostró los aspectos prácticos de los combinadores de analizadores sintácticos en 2001. ^{[ 4 ]} En 2008, Frost, Hafiz y Callaghan ^{[ 5 ]} describieron un conjunto de combinadores de analizadores sintácticos en el lenguaje de programación funcional Haskell que resuelven el problema de larga data de acomodar la recursión izquierda y funcionan como una herramienta completa de análisis sintáctico descendente en tiempo y espacio polinomiales .

En cualquier lenguaje de programación con funciones de primera clase , los combinadores de analizadores sintácticos permiten combinar analizadores básicos para construir analizadores que respondan a reglas más complejas. Por ejemplo, una regla de producción de una gramática libre de contexto (GLC) puede tener una o más alternativas, y cada alternativa puede consistir en una secuencia de no terminales y/o terminales, o bien en un único no terminal, terminal o la cadena vacía. Si se dispone de un analizador simple para cada una de estas alternativas, se puede usar un combinador para combinarlos, obteniendo así un nuevo analizador capaz de reconocer cualquiera o todas las alternativas.

En los lenguajes que admiten sobrecarga de operadores , un combinador de analizadores sintácticos puede adoptar la forma de un operador infijo , utilizado para unir diferentes analizadores y formar una regla completa. De este modo, los combinadores de analizadores sintácticos permiten definirlos en un estilo integrado, en un código cuya estructura es similar a la de las reglas de la gramática formal. Así, las implementaciones pueden considerarse especificaciones ejecutables con todas las ventajas asociadas, como la legibilidad.

Para mantener la discusión relativamente sencilla, hablaremos de los combinadores de analizadores en términos de reconocedores únicamente. Si la cadena de entrada tiene una longitud #inputy se accede a sus miembros a través de un índice j, un reconocedor es un analizador que devuelve, como salida, un conjunto de índices que representan los índices en los que el analizador terminó de reconocer con éxito una secuencia de tokens que comienza en el índice j. Un conjunto de resultados vacío indica que el reconocedor no pudo reconocer ninguna secuencia que comience en el índice j.

• El emptyreconocedor reconoce la cadena vacía. Este analizador siempre tiene éxito, devolviendo un conjunto unitario que contiene el índice de entrada:

${\displaystyle vacío(j)=\{j\}}$

• Un reconocedor reconoce el terminal . Si el token en el índice de la cadena de entrada es , este analizador devuelve un conjunto unitario que contiene ; de lo contrario, devuelve el conjunto vacío.term xxjxj + 1

${\displaystyle term(x,j)={\begin{cases}\left\{\right\},&j\geq \#input\\\left\{j+1\right\},&j^{th}{\mbox{ elemento de }}input=x\\\left\{\right\},&{\mbox{en otro caso}}\end{cases}}}$

Dados dos reconocedores py q, podemos definir dos combinadores de analizadores principales, uno para hacer coincidir reglas alternativas y otro para secuenciar reglas:

• El combinador de analizadores 'alternativos', ⊕, aplica cada uno de los reconocedores al mismo índice jy devuelve la unión de los índices finales de los reconocedores:

${\displaystyle (p\oplus q)(j)=p(j)\cup q(j)}$

• El combinador 'secuencia', ⊛, aplica el primer reconocedor pal índice de entrada jy, para cada índice final, aplica el segundo reconocedor qcon ese como índice inicial. Devuelve la unión de los índices finales devueltos por todas las invocaciones de q:

${\displaystyle (p\circledast q)(j)=\bigcup \{q(k):k\in p(j)\}}$

Puede haber varias formas distintas de analizar una cadena, aunque el resultado final se encuentre en el mismo índice, lo que indica una gramática ambigua . Los reconocedores simples no reconocen estas ambigüedades; cada posible índice final se muestra solo una vez en el conjunto de resultados. Para obtener un conjunto de resultados más completo, se debe devolver un objeto más complejo, como un árbol de análisis sintáctico .

Consideremos una gramática libre de contexto altamente ambigua , . Utilizando los combinadores definidos anteriormente, podemos definir de forma modular notaciones ejecutables de esta gramática en un lenguaje de programación funcional moderno (por ejemplo, Haskell ) como . Cuando el reconocedor se aplica en el índice de la secuencia de entrada, devolvería un conjunto de resultados , lo que indica que hubo coincidencias comenzando en el índice 2 y terminando en cualquier índice entre 2 y 5 inclusive.s ::= ‘x’ s s | εs = term ‘x’ <*> s <*> s <+> emptys2x x x x x{2,3,4,5}

Los combinadores de analizadores, como todos los analizadores descendentes recursivos , no se limitan a las gramáticas libres de contexto y, por lo tanto, no realizan una búsqueda global de ambigüedades en los conjuntos First _k y Follow _{k del análisis} LL( k ) . Así, las ambigüedades no se conocen hasta el tiempo de ejecución, si es que la entrada las activa. En tales casos, el analizador descendente recursivo puede optar por defecto (quizás sin que el diseñador de la gramática lo sepa) por una de las posibles rutas ambiguas, lo que genera confusión semántica (aliasing) en el uso del lenguaje. Esto provoca errores en los usuarios de lenguajes de programación ambiguos, que no se notifican en tiempo de compilación y que no se deben a errores humanos, sino a la ambigüedad de la gramática. La única solución para eliminar estos errores es eliminar las ambigüedades y utilizar una gramática libre de contexto.

Las implementaciones simples de combinadores de analizadores sintácticos tienen algunas deficiencias, comunes en el análisis sintáctico descendente. El análisis sintáctico combinatorio ingenuo requiere tiempo y espacio exponenciales al analizar una gramática libre de contexto ambigua. En 1996, Frost y Szydlowski demostraron cómo se puede usar la memorización con combinadores de analizadores sintácticos para reducir la complejidad temporal a polinómica. ^{[ 6 ]} Posteriormente, Frost usó mónadas para construir los combinadores para el encadenamiento sistemático y correcto de la tabla de memorización a lo largo del cálculo. ^{[ 7 ]}

Como cualquier análisis descendente recursivo de arriba hacia abajo , los combinadores de analizadores convencionales (como los combinadores descritos anteriormente) no terminarán mientras procesan una gramática recursiva izquierda (por ejemplo, ). Frost y Hafiz describieron en 2006 un algoritmo de reconocimiento que admite gramáticas ambiguas con reglas recursivas izquierdas directas. ^{[ 8 ]} El algoritmo limita el análisis recursivo izquierdo, que de otro modo crecería continuamente, imponiendo restricciones de profundidad. Frost, Hafiz y Callaghan extendieron ese algoritmo a un algoritmo de análisis completo para admitir tanto la recursión izquierda indirecta como la directa en tiempo polinomial , y para generar representaciones compactas de tamaño polinomial del número potencialmente exponencial de árboles de análisis para gramáticas altamente ambiguas. ^{[ 9 ]} Este algoritmo extendido admite la recursión izquierda indirecta comparando su "contexto calculado" con el "contexto actual". Los mismos autores también describieron su implementación de un conjunto de combinadores de analizadores escritos en el lenguaje Haskell basados ​​en el mismo algoritmo. ^{[ 5 ] [ 10 ]}s ::= s <*> term ‘x’|empty