En programación de computadoras , un combinador de analizadores 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 es una función que acepta cadenas como entrada y devuelve alguna estructura como salida, normalmente un árbol de análisis o un conjunto de índices que representan ubicaciones en la cadena donde el análisis se detuvo con éxito. Los combinadores de analizadores permiten una estrategia de análisis de descenso recursivo que facilita la construcción y las pruebas modulares por partes. Esta técnica de análisis se llama análisis combinatorio .
Los analizadores que utilizan combinadores se han utilizado ampliamente en la creación de prototipos de compiladores y procesadores para lenguajes de dominios específicos , como interfaces de lenguaje natural para bases de datos, donde 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 básico en 1992 [2] y el análisis monádico en 1996. [3] SD Swierstra también exhibió los aspectos prácticos de los combinadores de analizadores sintácticos en 2001. [4] En 2008, Frost, Hafiz y Callaghan [ 5] describió un conjunto de combinadores de analizadores en Haskell que resuelven el problema de larga data de acomodar la recursividad izquierda y funcionan como una herramienta completa de análisis de arriba hacia abajo en tiempo y espacio polinómicos.
En cualquier lenguaje de programación que tenga funciones de primera clase , los combinadores de analizadores se pueden utilizar para combinar analizadores básicos y construir analizadores para reglas más complejas. Por ejemplo, una regla de producción de una gramática libre de contexto (CFG) puede tener una o más alternativas y cada alternativa puede consistir en una secuencia de no terminales y/o terminales, o la alternativa puede consistir en un único no terminal o terminal o la cadena vacía. Si hay un analizador simple disponible para cada una de estas alternativas, se puede usar un combinador de analizadores para combinar cada uno de estos analizadores, devolviendo un nuevo analizador que puede reconocer cualquiera o todas las alternativas.
En los lenguajes que admiten la sobrecarga de operadores , un combinador de analizadores puede tomar la forma de un operador infijo , que se utiliza para unir diferentes analizadores para formar una regla completa. Los combinadores de analizadores permiten así definir los analizadores en un estilo integrado, en un código que tiene una estructura similar a las reglas de la gramática formal. Como tal, las implementaciones pueden considerarse como especificaciones ejecutables con todas las ventajas asociadas, como la legibilidad.
Para mantener la discusión relativamente sencilla, analizamos los combinadores de analizadores en términos de reconocedores únicamente. Si la cadena de entrada es larga #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 índices en los que el analizador terminó exitosamente de reconocer una secuencia de tokens que comienzan en el índice j. Un conjunto de resultados vacío indica que el reconocedor no pudo reconocer ninguna secuencia que comience en index j.
emptyreconocedor reconoce la cadena vacía. Este analizador siempre tiene éxito y devuelve un conjunto singleton que contiene el índice de entrada:
term xxjxj + 1Dados dos reconocedores py q, podemos definir dos combinadores de analizadores principales, uno para hacer coincidir reglas alternativas y otro para reglas de secuenciación:
jy devuelve la unión de los índices finales de los reconocedores:
pal índice de entrada jy, para cada índice final, aplica el segundo reconocedor qcon ese índice inicial. Devuelve la unión de los índices de acabado devueltos por todas las invocaciones de q:Puede haber varias formas distintas de analizar una cadena mientras se termina en el mismo índice, lo que indica una gramática ambigua . Los reconocedores simples no reconocen estas ambigüedades; cada índice de acabado posible aparece solo una vez en el conjunto de resultados. Para obtener un conjunto de resultados más completo, se debe devolver un objeto más complicado, como un árbol de análisis .
Considere una gramática libre de contexto altamente ambigua , s ::= ‘x’ s s | ε. Utilizando los combinadores definidos anteriormente, podemos definir de forma modular notaciones ejecutables de esta gramática en un lenguaje funcional moderno (por ejemplo, Haskell ) como s = term ‘x’ <*> s <*> s <+> empty. Cuando el reconocedor sse aplica en el índice 2de la secuencia de entrada , x x x x xdevolverá un conjunto de resultados {2,3,4,5}, indicando que hubo coincidencias comenzando en el índice 2 y terminando en cualquier índice entre 2 y 5 inclusive.
Los combinadores de analizadores, como todos los analizadores de descenso recursivo , no se limitan a las gramáticas libres de contexto y, por lo tanto, no realizan una búsqueda global de ambigüedades en el análisis LL( k ) de los conjuntos First k y Follow k . Por lo tanto, las ambigüedades no se conocen hasta el tiempo de ejecución si la entrada las activa. En tales casos, el analizador de descenso recursivo puede utilizar de forma predeterminada (quizás sin que el diseñador gramatical lo sepa) una de las posibles rutas ambiguas, lo que genera confusión semántica (aliasing) en el uso del lenguaje. Esto genera errores por parte de los usuarios de lenguajes de programación ambiguos, que no se informan en el momento de la compilación y que no se introducen por error humano, sino por una gramática ambigua. La única solución que elimina estos errores es eliminar las ambigüedades y utilizar una gramática libre de contexto.
Las implementaciones simples de los combinadores de analizadores tienen algunas deficiencias, que son comunes en el análisis de arriba hacia abajo. El análisis combinatorio ingenuo requiere tiempo y espacio exponenciales al analizar una gramática ambigua y libre de contexto. En 1996, Frost y Szydlowski demostraron cómo se puede utilizar la memorización con combinadores de analizadores para reducir la complejidad del tiempo a polinomio. [6] Más tarde, Frost usó mónadas para construir los combinadores para el enhebrado sistemático y correcto de la tabla de notas durante todo el cálculo. [7]
Como cualquier análisis de descenso recursivo de arriba hacia abajo , los combinadores de analizadores convencionales (como los combinadores descritos anteriormente) no terminarán mientras procesan una gramática recursiva por la izquierda (por ejemplo s ::= s <*> term ‘x’|empty). Frost y Hafiz describen en 2006 un algoritmo de reconocimiento que se adapta a gramáticas ambiguas con reglas recursivas a la izquierda directas. [8] El algoritmo restringe el análisis recursivo a la izquierda, que de otro modo estaría en constante crecimiento, imponiendo restricciones de profundidad. Ese algoritmo se extendió a un algoritmo de análisis completo para acomodar la recursión izquierda directa e indirecta 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 por Frost, Hafiz y Callaghan en 2007. [9] Este algoritmo extendido se adapta a 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 de programación Haskell basados en el mismo algoritmo. [5] [10]
{{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: CS1 maint: bot: original URL status unknown (link){{cite book}}: |journal=ignorado ( ayuda ){{cite book}}: |journal=ignorado ( ayuda )