En la teoría del lenguaje formal de la informática , la recursividad por la izquierda es un caso especial de recursividad en el que una cadena se reconoce como parte de un lenguaje por el hecho de que se descompone en una cadena de ese mismo idioma (a la izquierda) y un sufijo (en la derecha). Por ejemplo, puede reconocerse como una suma porque se puede dividir en , también una suma, y , un sufijo adecuado.
En términos de gramática libre de contexto , un no terminal es recursivo a la izquierda si el símbolo más a la izquierda en una de sus producciones es él mismo (en el caso de la recursión directa a la izquierda) o puede hacerse mediante alguna secuencia de sustituciones (en el caso de la recursividad indirecta). recursión izquierda).
Definición
Una gramática es recursiva a la izquierda si y solo si existe un símbolo no terminal que puede derivar a una forma enunciativa con él mismo como el símbolo más a la izquierda. [1] Simbólicamente,
- ,
dónde indica la operación de hacer una o más sustituciones, y es cualquier secuencia de símbolos terminales y no terminales.
Recursión directa a la izquierda
La recursividad directa a la izquierda ocurre cuando la definición puede satisfacerse con una sola sustitución. Requiere una regla de la forma
dónde es una secuencia de no terminales y terminales. Por ejemplo, la regla
es directamente recursivo a la izquierda. Un analizador de descenso recursivo de izquierda a derecha para esta regla podría verse como
Void Expression () { Expresión (); coincidir ( '+' ); Término (); }
y dicho código caería en una recursividad infinita cuando se ejecutara.
Recursividad indirecta por la izquierda
La recursividad indirecta por la izquierda se produce cuando la definición de recursión por la izquierda se satisface mediante varias sustituciones. Implica un conjunto de reglas que siguen el patrón
dónde son secuencias que pueden producir la cadena vacía , mientras quepuede ser cualquier secuencia de símbolos terminales y no terminales. Tenga en cuenta que estas secuencias pueden estar vacías. La derivación
luego da como más a la izquierda en su forma sentencial final.
Eliminando la recursividad por la izquierda
Recursión por la izquierda menudo supone un problema para los analizadores, ya sea porque se los lleva a la repetición infinita (como en el caso de la mayoría de programas de análisis de arriba hacia abajo ) o porque esperan reglas en una forma normal que lo prohíbe (como en el caso de muchos de abajo hacia arriba analizadores sintácticos , incluido el algoritmo CYK ). Por lo tanto, una gramática a menudo se procesa previamente para eliminar la recursividad por la izquierda.
Eliminando la recursividad directa por la izquierda
A continuación se muestra el algoritmo general para eliminar la recursividad directa a la izquierda. Se han realizado varias mejoras a este método. [2] Para un no terminal recursivo por la izquierda, descarte las reglas del formulario y considere los que quedan:
dónde:
- cada es una secuencia no vacía de no terminales y terminales, y
- cada es una secuencia de no terminales y terminales que no comienza con .
Reemplácelos con dos conjuntos de producciones, uno para :
y otro conjunto para el no terminal fresco (a menudo llamado "cola" o "resto"):
Repita este proceso hasta que no quede ninguna recursividad directa a la izquierda.
Como ejemplo, considere el conjunto de reglas
Esto podría reescribirse para evitar la recursividad a la izquierda como
Eliminando toda la recursividad izquierda
Al establecer un orden topológico en los no terminales, el proceso anterior se puede extender para eliminar también la recursividad indirecta por la izquierda [ cita requerida ] :
- Entradas Una gramática: un conjunto de no terminales y sus producciones
- Salida Una gramática modificada que genera el mismo idioma pero sin recursividad izquierda
- Para cada no terminal :
- Repita hasta que una iteración deje la gramática sin cambios:
- Para cada regla , siendo una secuencia de terminales y no terminales:
- Si comienza con un no terminal y :
- Dejar ser sin su liderazgo .
- Eliminar la regla .
- Para cada regla :
- Agrega la regla .
- Si comienza con un no terminal y :
- Para cada regla , siendo una secuencia de terminales y no terminales:
- Quitar recursividad directa a la izquierda para como se describió anteriormente.
- Repita hasta que una iteración deje la gramática sin cambios:
- Para cada no terminal :
Tenga en cuenta que este algoritmo es muy sensible al orden no terminal; las optimizaciones a menudo se centran en elegir bien este orden. [ aclaración necesaria ]
Trampas
Aunque las transformaciones anteriores conservan el lenguaje generado por una gramática, pueden cambiar los árboles de análisis sintáctico que son testigos del reconocimiento de cadenas. Con una contabilidad adecuada, la reescritura de árbol puede recuperar los originales, pero si se omite este paso, las diferencias pueden cambiar la semántica de un análisis sintáctico.
La asociatividad es particularmente vulnerable; Los operadores asociativos por la izquierda aparecen típicamente en arreglos similares a los asociativos por la derecha bajo la nueva gramática. Por ejemplo, comenzando con esta gramática:
las transformaciones estándar para eliminar la recursividad por la izquierda producen lo siguiente:
Analizar la cadena "1 - 2 - 3" con la primera gramática en un analizador LALR (que puede manejar gramáticas recursivas a la izquierda) habría dado como resultado el árbol de análisis sintáctico:
Este árbol de análisis agrupa los términos de la izquierda, proporcionando la semántica correcta (1 - 2) - 3 .
Analizar con la segunda gramática da
que, correctamente interpretado, significa 1 + (-2 + (-3)) , también correcto, pero menos fiel a la entrada y mucho más difícil de implementar para algunos operadores. Observe cómo los términos de la derecha aparecen más profundamente en el árbol, de la misma manera que una gramática recursiva a la derecha los ordenaría para 1 - (2 - 3) .
Acomodar la recursividad izquierda en el análisis de arriba hacia abajo
Una gramática formal que contiene recursividad por la izquierda no puede ser analizada por un analizador LL (k) u otro analizador de descendencia recursivo ingenuo a menos que se convierta a una forma recursiva derecha débilmente equivalente . Por el contrario, la recursividad a la izquierda se prefiere para los analizadores LALR porque da como resultado un uso de pila menor que la recursividad a la derecha . Sin embargo, los analizadores de arriba hacia abajo más sofisticados pueden implementar gramáticas generales libres de contexto mediante el uso de restricciones. En 2006, Frost y Hafiz describieron un algoritmo que acomoda gramáticas ambiguas con reglas de producción recursivas directas a la izquierda . [3] Ese algoritmo se extendió a un algoritmo de análisis completo para acomodar la recursión izquierda indirecta y directa en tiempo polinomial , y para generar representaciones compactas de tamaño polinomial del número potencialmente exponencial de árboles de análisis sintáctico para gramáticas altamente ambiguas por Frost, Hafiz y Callaghan en 2007. [4] Luego, los autores implementaron el algoritmo como un conjunto de combinadores de analizadores sintácticos escritos en el lenguaje de programación Haskell . [5]
Ver también
Referencias
- ^ Notas sobre análisis y teoría del lenguaje formal , James Power, Departamento de Ciencias de la Computación de la Universidad Nacional de Irlanda, Maynooth Maynooth, Co. Kildare, Irlanda. JPR02
- ^ Moore, Robert C. (mayo de 2000). "Eliminación de la recursividad izquierda de las gramáticas libres de contexto" (PDF) . Sexta Conferencia de Procesamiento del Lenguaje Natural Aplicado : 249-255.
- ^ Frost, R .; R. Hafiz (2006). "Un nuevo algoritmo de análisis de arriba hacia abajo para adaptarse a la ambigüedad y la recursividad izquierda en el tiempo polinomial" . Avisos ACM SIGPLAN . 41 (5): 46–54. doi : 10.1145 / 1149982.1149988 ., disponible del autor en http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf Archivado el 8 de enero de 2015 en Wayback Machine
- ^ Frost, R .; R. Hafiz; P. Callaghan (junio de 2007). "Análisis de arriba hacia abajo modular y eficiente para gramáticas recursivas de izquierda ambiguas" (PDF) . Décimo taller internacional sobre tecnologías de análisis (IWPT), ACL-SIGPARSE : 109–120. Archivado desde el original (PDF) el 27 de mayo de 2011.
- ^ Frost, R .; R. Hafiz; P. Callaghan (enero de 2008). Combinadores de analizadores para gramáticas recursivas izquierdas ambiguas (PDF) . X Simposio Internacional sobre Aspectos Prácticos de los Lenguajes Declarativos (PADL), ACM-SIGPLAN . Apuntes de conferencias en informática. 4902 . págs. 167-181. doi : 10.1007 / 978-3-540-77442-6_12 . ISBN 978-3-540-77441-9.
enlaces externos
- Consideraciones prácticas para las gramáticas LALR (1)