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 lenguaje (a la izquierda) y un sufijo (a la izquierda). el derecho). Por ejemplo, puede reconocerse como una suma porque puede dividirse 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 recursividad directa a la izquierda) o puede convertirse en sí mismo 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 sólo si existe un símbolo no terminal que pueda derivar a una forma oracional siendo él mismo el símbolo más a la izquierda. [1] Simbólicamente,
,
donde indica la operación de realizar una o más sustituciones, y es cualquier secuencia de símbolos terminales y no terminales.
Recursividad directa hacia la izquierda
La recursividad directa hacia la izquierda ocurre cuando la definición puede satisfacerse con una sola sustitución. Requiere una regla de la forma
donde 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 así
y dicho código caería en una recursividad infinita cuando se ejecutara.
Recursión izquierda indirecta
La recursión izquierda indirecta ocurre cuando la definición de recursividad izquierda se satisface mediante varias sustituciones. Implica un conjunto de reglas que siguen el patrón
donde hay secuencias que pueden producir la cadena vacía , mientras que puede haber cualquier secuencia de símbolos terminales y no terminales. Tenga en cuenta que estas secuencias pueden estar vacías. la derivacion
luego da como más a la izquierda en su forma de oración final.
Usos
La recursividad por la izquierda se usa comúnmente como un modismo para hacer que las operaciones sean asociativas por la izquierda : que una expresión a+b-c-d+ese evalúe como (((a+b)-c)-d)+e. En este caso, ese orden de evaluación podría lograrse como una cuestión de sintaxis a través de las tres reglas gramaticales.
Estos solo permiten analizar el que consta de y , donde a su vez consta de y , mientras que consta de y , etc.a+b-c-d+ea+b-c-dea+b-c-da+b-cda+b-ca+bc
Eliminando la recursividad hacia la izquierda
La recursividad hacia la izquierda a menudo plantea problemas a los analizadores, ya sea porque los lleva a una recursividad infinita (como en el caso de la mayoría de los analizadores de arriba hacia abajo ) o porque esperan reglas en una forma normal que lo prohíban (como en el caso de muchos analizadores de abajo hacia arriba ). analizadores [ aclaración necesaria ] ). Por lo tanto, a menudo se preprocesa una gramática para eliminar la recursividad por la izquierda.
Eliminando la recursividad directa hacia la izquierda
A continuación se muestra el algoritmo general para eliminar la recursividad directa hacia la izquierda. Se han realizado varias mejoras a este método. [2]
Para un no terminal recursivo por la izquierda , descarte cualquier regla de la forma y considere las que quedan:
dónde:
cada uno es una secuencia no vacía de no terminales y terminales, y
cada uno 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 nuevo (a menudo llamado "cola" o "resto"):
Repita este proceso hasta que no quede ninguna recursividad directa hacia la izquierda.
Como ejemplo, considere el conjunto de reglas
Esto podría reescribirse para evitar la recursividad por la izquierda como
Eliminando toda recursividad izquierda
El proceso anterior se puede ampliar para eliminar toda recursividad por la izquierda, convirtiendo primero la recursividad por la izquierda indirecta en recursividad por la izquierda directa en el no terminal con el número más alto de un ciclo.
Entradas Una gramática: un conjunto de no terminales y sus producciones.
Salida Una gramática modificada que genera el mismo lenguaje pero sin recursividad por la 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 :
Quedémonos sin su guía .
Quitar la regla .
Para cada regla :
Añade la regla .
Elimine la recursividad directa hacia la izquierda como se describe anteriormente.
El paso 1.1.1 equivale a expandir el no terminal inicial en el lado derecho de alguna regla , pero sólo si . Si fue un paso en un ciclo de producciones el que dio lugar a una recursión hacia la izquierda, entonces esto ha acortado ese ciclo en un paso, pero a menudo al precio de aumentar el número de reglas.
Se puede considerar que el algoritmo establece un orden topológico en no terminales: después sólo puede haber una regla si . Tenga en cuenta que este algoritmo es muy sensible al ordenamiento no terminal; Las optimizaciones a menudo se centran en elegir bien este orden. [ se necesita aclaración ]
Escollos
Aunque las transformaciones anteriores preservan el lenguaje generado por una gramática, pueden cambiar los árboles de análisis que atestiguan el reconocimiento de las cadenas. Con una contabilidad adecuada, la reescritura de árboles puede recuperar los originales, pero si se omite este paso, las diferencias pueden cambiar la semántica de un análisis.
La asociatividad es particularmente vulnerable; Los operadores asociativos de izquierda suelen aparecer en arreglos de tipo asociativo de derecha en la nueva gramática. Por ejemplo, comenzando con esta gramática:
las transformaciones estándar para eliminar la recursividad hacia 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 por la izquierda) habría dado como resultado el árbol de análisis:
Análisis recursivo por la izquierda de una resta doble
Este árbol de análisis agrupa los términos de la izquierda, dando la semántica correcta (1 - 2) - 3 .
El análisis con la segunda gramática da
Análisis recursivo por la derecha de una resta doble
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 por la derecha los ordenaría para 1 - (2 - 3) .
Acomodando la recursividad izquierda en el análisis de arriba hacia abajo
^ Notas sobre la teoría y el análisis del lenguaje formal en Wayback Machine (archivado el 27 de noviembre de 2007). James Power, Departamento de Ciencias de la Computación Universidad Nacional de Irlanda, Maynooth Maynooth, Co. Kildare, Irlanda.JPR02
^ Moore, Robert C. (mayo de 2000). "Eliminar la recursividad izquierda de las gramáticas libres de contexto" (PDF) . Sexta Conferencia sobre procesamiento aplicado del lenguaje natural : 249–255.
^ Escarcha, R.; R. Hafiz (2006). "Un nuevo algoritmo de análisis de arriba hacia abajo para adaptarse a la ambigüedad y la recursividad hacia la izquierda en tiempo polinomial". Avisos ACM SIGPLAN . 41 (5): 46–54. doi :10.1145/1149982.1149988. S2CID 8006549., disponible del autor en http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf Archivado el 8 de enero de 2015 en Wayback Machine.
^ Escarcha, R.; R. Hafiz; P. Callaghan (junio de 2007). "Análisis de arriba hacia abajo modular y eficiente para gramáticas recursivas a la 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.
^ Escarcha, R.; R. Hafiz; P. Callaghan (enero de 2008). "Combinadores de analizadores para gramáticas ambiguas recursivas por la izquierda". Aspectos prácticos de los lenguajes declarativos (PDF) . Apuntes de conferencias sobre informática. vol. 4902, págs. 167–181. doi :10.1007/978-3-540-77442-6_12. ISBN978-3-540-77441-9.
Enlaces externos
Consideraciones prácticas para las gramáticas LALR(1)