Recursión izquierda

En la teoría formal del lenguaje de la informática , la recursión por la izquierda es un caso especial de recursión 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 derecha). Por ejemplo, se puede reconocer como una suma porque se puede descomponer 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 por la izquierda si el símbolo más a la izquierda en una de sus producciones es él mismo (en el caso de recursión por la izquierda directa) o puede convertirse en él mismo mediante alguna secuencia de sustituciones (en el caso de recursión por la izquierda indirecta).

Definición

Una gramática es recursiva por la izquierda si y solo si existe un símbolo no terminal que puede derivar a una forma oracional con él mismo como 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 }$

Recursión directa por la izquierda

La recursión directa por la izquierda se produce cuando la definición se puede satisfacer 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 descendente recursivo de izquierda a derecha para esta regla podría verse así

void Expresión () { Expresión (); coincidencia ( '+' ); Término (); }     

y dicho código caería en una recursión infinita al ejecutarse.

Recursión indirecta por la izquierda

La recursión izquierda indirecta ocurre cuando la definición de recursión 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 son secuencias que pueden producir la cadena vacía , mientras que pueden ser cualquier secuencia de símbolos terminales y no terminales. Nótese que estas secuencias pueden estar vacías. La derivación ${\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 se da como más a la izquierda en su forma oracional final. ${\displaystyle A_{0}}$

Usos

La recursión por la izquierda se utiliza 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 como que consiste en y , donde a su vez consiste en y , mientras que consiste en 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 recursión izquierda

La recursión por la izquierda suele plantear 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 ^{[ aclaración necesaria ]} ). Por lo tanto, a menudo se preprocesa una gramática para eliminar la recursión por la izquierda.

Eliminación de la recursión izquierda directa

A continuación se presenta el algoritmo general para eliminar la recursión directa por 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}$

Reemplace estos con dos conjuntos de producciones, un conjunto para : ${\displaystyle A}$

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

y otro conjunto para el no terminal fresco (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 recursión 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 recursión 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 recursión izquierda

El proceso anterior se puede ampliar para eliminar toda recursión izquierda, convirtiendo primero la recursión izquierda indirecta en recursión izquierda directa en el no terminal con el número más alto en 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 recursión 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. Dejar sin su líder . ${\displaystyle \beta _{i}}$ ${\displaystyle \alpha _{i}}$ ${\displaystyle A_{j}}$
            2. Eliminar 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. Eliminar la recursión izquierda directa como se describe arriba. ${\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 que dio lugar a una recursión por 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 }$

El algoritmo puede considerarse como el establecimiento de un ordenamiento topológico de los no terminales: después, solo puede haber una regla si . Nótese que este algoritmo es muy sensible al ordenamiento de los no terminales; las optimizaciones a menudo se centran en elegir bien este ordenamiento. ^{[ aclaración necesaria ]} ${\displaystyle A_{i}\to A_{j}\beta }$ ${\displaystyle j>i}$

Trampas

Aunque las transformaciones anteriores preservan el lenguaje generado por una gramática, pueden cambiar los árboles de análisis que dan testimonio del reconocimiento de 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 por la izquierda suelen aparecer en disposiciones similares a las asociativas por la 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 recursión por 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}}}$

El análisis de 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:

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 a la derecha de una resta doble

que, interpretado correctamente, 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 a la derecha aparecen más profundos en el árbol, de forma muy similar a como una gramática recursiva a la derecha los organizaría para 1 - (2 - 3) .

Acomodación de la recursión por la izquierda en el análisis de arriba hacia abajo

Una gramática formal que contiene recursión por la izquierda no puede ser analizada por un analizador LL(k) u otro analizador sintáctico de descenso recursivo ingenuo a menos que se convierta a una forma recursiva por la derecha débilmente equivalente . Por el contrario, la recursión por la izquierda es la preferida para los analizadores sintácticos LALR porque da como resultado un menor uso de la pila que la recursión por la derecha . Sin embargo, los analizadores sintácticos de arriba hacia abajo más sofisticados pueden implementar gramáticas generales libres de contexto mediante el uso de reducción. En 2006, Frost y Hafiz describieron un algoritmo que acomoda gramáticas ambiguas con reglas de producción recursivas por la izquierda directas . ^[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 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]

Véase también

• Recursión de cola

Referencias

1. Notas sobre teoría y 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). "Eliminación de la recursión por la izquierda en gramáticas libres de contexto" (PDF) . 6.ª Conferencia sobre procesamiento del lenguaje natural aplicado : 249–255.
3. Frost, R.; R. Hafiz (2006). "Un nuevo algoritmo de análisis descendente para acomodar la ambigüedad y la recursión por la izquierda en tiempo polinomial". Avisos SIGPLAN de ACM . 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. Frost, R.; R. Hafiz; P. Callaghan (junio de 2007). "Análisis modular y eficiente de arriba hacia abajo para gramáticas recursivas por la izquierda ambiguas" (PDF) . 10.º 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. Frost, R.; R. Hafiz; P. Callaghan (enero de 2008). "Combinadores de analizadores sintácticos para gramáticas recursivas por la izquierda ambiguas". Aspectos prácticos de los lenguajes declarativos (PDF) . Apuntes de clase en 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)