recursividad izquierda

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). la derecha). Por ejemplo, puede reconocerse como una suma porque puede dividirse en , también una suma, y ​​, un sufijo adecuado. ${\displaystyle 1+2+3}$ ${\displaystyle 1+2}$ ${\displaystyle {}+3}$

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, ${\displaystyle A}$

${\displaystyle A\Rightarrow ^{+}A\alpha }$,

donde indica la operación de realizar una o más sustituciones, y es cualquier secuencia de símbolos terminales y no terminales. ${\displaystyle \Rightarrow ^{+}}$ ${\displaystyle \alpha }$

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

${\displaystyle A\to A\alpha }$

donde es una secuencia de no terminales y terminales. Por ejemplo, la regla ${\displaystyle \alpha }$

${\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}+{\mathit {Term}}}$

es directamente recursivo a la izquierda. Un analizador de descenso recursivo de izquierda a derecha para esta regla podría verse así

expresión vacía () { expresión (); coincidir ( '+' ); Término (); }     

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

${\displaystyle A_{0}\to \beta _{0}A_{1}\alpha _{0}}$

${\displaystyle A_{1}\to \beta _{1}A_{2}\alpha _{1}}$

${\displaystyle \cdots }$

${\displaystyle A_{n}\to \beta _{n}A_{0}\alpha _{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 ${\displaystyle \beta _{0},\beta _{1},\ldots ,\beta _{n}}$ ${\displaystyle \alpha _{0},\alpha _{1},\ldots ,\alpha _{n}}$

${\displaystyle A_{0}\Rightarrow \beta _{0}A_{1}\alpha _{0}\Rightarrow ^{+}A_{1}\alpha _{0}\Rightarrow \beta _{1}A_{2}\alpha _{1}\alpha _{0}\Rightarrow ^{+}\cdots \Rightarrow ^{+}A_{0}\alpha _{n}\dots \alpha _{1}\alpha _{0}}$

luego da como extremo a la izquierda en su forma de oración final. ${\displaystyle A_{0}}$

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.

${\displaystyle {\mathit {Expression}}\to {\mathit {Term}}}$

${\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}+{\mathit {Term}}}$

${\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}-{\mathit {Term}}}$

Estos solo permiten analizar el que consta de y , donde a su vez consta de y , mientras que consta de y , etc. ${\displaystyle {\mathit {Expression}}}$ a+b-c-d+e ${\displaystyle {\mathit {Expression}}}$ a+b-c-d ${\displaystyle {\mathit {Term}}}$ ea+b-c-d ${\displaystyle {\mathit {Expression}}}$ a+b-c ${\displaystyle {\mathit {Term}}}$ da+b-c ${\displaystyle {\mathit {Expression}}}$ a+b ${\displaystyle {\mathit {Term}}}$ c

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 recursión 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: ${\displaystyle A}$ ${\displaystyle A\rightarrow A}$

${\displaystyle A\rightarrow A\alpha _{1}\mid \ldots \mid A\alpha _{n}\mid \beta _{1}\mid \ldots \mid \beta _{m}}$

dónde:

• cada uno es una secuencia no vacía de no terminales y terminales, y ${\displaystyle \alpha }$
• cada uno es una secuencia de no terminales y terminales que no comienza con . ${\displaystyle \beta }$ ${\displaystyle A}$

Reemplácelos con dos conjuntos de producciones, uno para : ${\displaystyle A}$

${\displaystyle A\rightarrow \beta _{1}A^{\prime }\mid \ldots \mid \beta _{m}A^{\prime }}$

y otro conjunto para el no terminal nuevo (a menudo llamado "cola" o "resto"): ${\displaystyle A'}$

${\displaystyle A^{\prime }\rightarrow \alpha _{1}A^{\prime }\mid \ldots \mid \alpha _{n}A^{\prime }\mid \epsilon }$

Repita este proceso hasta que no quede ninguna recursividad directa hacia la izquierda.

Como ejemplo, considere el conjunto de reglas

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Expression}}+{\mathit {Expression}}\mid {\mathit {Integer}}\mid {\mathit {String}}}$

Esto podría reescribirse para evitar la recursividad por la izquierda como

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Integer}}\,{\mathit {Expression}}'\mid {\mathit {String}}\,{\mathit {Expression}}'}$

${\displaystyle {\mathit {Expression}}'\rightarrow {}+{\mathit {Expression}}\,{\mathit {Expression}}'\mid \epsilon }$

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. ${\displaystyle A_{1},\ldots ,A_{n}}$

Salida Una gramática modificada que genera el mismo lenguaje pero sin recursividad por la izquierda.

1. Para cada no terminal : ${\displaystyle A_{i}}$
   1. Repita hasta que una iteración deje la gramática sin cambios:
      1. Para cada regla , siendo una secuencia de terminales y no terminales: ${\displaystyle A_{i}\rightarrow \alpha _{i}}$ ${\displaystyle \alpha _{i}}$
         1. Si comienza con un no terminal y : ${\displaystyle \alpha _{i}}$ ${\displaystyle A_{j}}$ ${\displaystyle j<i}$
            1. Quedémonos sin su guía . ${\displaystyle \beta _{i}}$ ${\displaystyle \alpha _{i}}$ ${\displaystyle A_{j}}$
            2. Quitar la regla . ${\displaystyle A_{i}\rightarrow \alpha _{i}}$
            3. Para cada regla : ${\displaystyle A_{j}\rightarrow \alpha _{j}}$
               1. Añade la regla . ${\displaystyle A_{i}\rightarrow \alpha _{j}\beta _{i}}$
   2. Elimine la recursividad directa hacia la izquierda como se describe anteriormente. ${\displaystyle A_{i}}$

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. ${\displaystyle A_{j}}$ ${\displaystyle A_{i}\to A_{j}\beta }$ ${\displaystyle j<i}$ ${\displaystyle A_{i}\to A_{j}\beta }$

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 orden no terminal; Las optimizaciones a menudo se centran en elegir bien este orden. ${\displaystyle A_{i}\to A_{j}\beta }$ ${\displaystyle j>i}$

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:

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Expression}}\,-\,{\mathit {Term}}\mid {\mathit {Term}}}$

${\displaystyle {\mathit {Term}}\rightarrow {\mathit {Term}}\,*\,{\mathit {Factor}}\mid {\mathit {Factor}}}$

${\displaystyle {\mathit {Factor}}\rightarrow ({\mathit {Expression}})\mid {\mathit {Integer}}}$

las transformaciones estándar para eliminar la recursividad hacia la izquierda producen lo siguiente:

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Term}}\ {\mathit {Expression}}'}$

${\displaystyle {\mathit {Expression}}'\rightarrow {}-{\mathit {Term}}\ {\mathit {Expression}}'\mid \epsilon }$

${\displaystyle {\mathit {Term}}\rightarrow {\mathit {Factor}}\ {\mathit {Term}}'}$

${\displaystyle {\mathit {Term}}'\rightarrow {}*{\mathit {Factor}}\ {\mathit {Term}}'\mid \epsilon }$

${\displaystyle {\mathit {Factor}}\rightarrow ({\mathit {Expression}})\mid {\mathit {Integer}}}$

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

Una gramática formal que contiene recursividad hacia la izquierda no puede ser analizada por un analizador LL(k) u otro analizador de descenso recursivo ingenuo a menos que se convierta a una forma recursiva hacia la derecha débilmente equivalente . Por el contrario, se prefiere la recursividad hacia la izquierda para los analizadores LALR porque da como resultado un menor uso de la pila que la recursividad hacia 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 se adapta a gramáticas ambiguas con reglas de producción recursivas directas a la izquierda . ^[3] Frost , Hafiz y Frost , Hafiz y Callaghan en 2007. ^[4] Luego, los autores implementaron el algoritmo como un conjunto de combinadores de analizadores escritos en el lenguaje de programación Haskell . ^[5]

Ver también

• recursividad de cola

Referencias

1. 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
2. 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.
3. 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.
4. 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.
5. 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. ISBN 978-3-540-77441-9.

enlaces externos

• Consideraciones prácticas para las gramáticas LALR(1)