Hispanopedia Wiki
Articulo de referencia

Recursión izquierda

En la teoría del lenguaje formal de la informática , la recursión izquierda es un caso especial de recursión en el que una cadena se reconoce como parte de un lenguaje por el he...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría del lenguaje formal de la informática , la recursión 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,1+2+3{\displaystyle 1+2+3}puede reconocerse como una suma porque se puede dividir en1+2{\displaystyle 1+2}, también una suma, y+3{\displaystyle {}+3}, un sufijo adecuado.

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 directa por la izquierda) o puede convertirse en sí mismo mediante alguna secuencia de sustituciones (en el caso de recursión indirecta por la izquierda).

Definición

Una gramática es recursiva por la izquierda si y solo si existe un símbolo no terminal.A{\displaystyle A}que puede derivar en una forma sentencial con ella misma como el símbolo más a la izquierda. [ 1 ] Simbólicamente,

A⇒+Aα{\displaystyle A\Rightarrow ^{+}A\alpha },

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

Recursión directa por la izquierda

La recursión izquierda directa ocurre cuando la definición se puede satisfacer con una sola sustitución. Requiere una regla de la forma

A→Aα{\displaystyle A\to A\alpha }

dóndeα{\displaystyle \alpha }es una secuencia de no terminales y terminales. Por ejemplo, la regla

miincógnitapagrmissionorte→miincógnitapagrmissionorte+Tmirmetro{\displaystyle {\mathit {Expresión}}\to {\mathit {Expresión}}+{\mathit {Término}}}

es directamente recursivo por la izquierda. Un analizador sintáctico 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 izquierda indirecta

La recursión izquierda indirecta se produce cuando la definición de recursión izquierda se satisface mediante varias sustituciones. Implica un conjunto de reglas que siguen el patrón

A0→β0A1α0{\displaystyle A_{0}\to \beta _{0}A_{1}\alpha _{0}}
A1→β1A2α1{\displaystyle A_{1}\to \beta _{1}A_{2}\alpha _{1}}
⋯{\displaystyle \cdots }
Anorte→βnorteA0αnorte{\displaystyle A_{n}\to \beta _{n}A_{0}\alpha _{n}}

dóndeβ0,β1,…,βnorte{\displaystyle \beta _{0},\beta _{1},\ldots ,\beta _{n}}son secuencias que pueden producir cada una la cadena vacía , mientras queα0,α1,…,αnorte{\displaystyle \alpha _{0},\alpha _{1},\ldots ,\alpha _{n}}Puede ser cualquier secuencia de símbolos terminales y no terminales. Tenga en cuenta que estas secuencias pueden estar vacías. La derivación

A0⇒β0A1α0⇒+A1α0⇒β1A2α1α0⇒+⋯⇒+A0αnorte…α1α0{\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 daA0{\displaystyle A_{0}}como la más a la izquierda en su forma oracional final.

Usos

La recursión 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.

miincógnitapagrmissionorte→Tmirmetro{\displaystyle {\mathit {Expresión}}\to {\mathit {Término}}}
miincógnitapagrmissionorte→miincógnitapagrmissionorte+Tmirmetro{\displaystyle {\mathit {Expresión}}\to {\mathit {Expresión}}+{\mathit {Término}}}
miincógnitapagrmissionorte→miincógnitapagrmissionorte−Tmirmetro{\displaystyle {\mathit {Expresión}}\to {\mathit {Expresión}}-{\mathit {Término}}}

Estos solo permiten analizar elmiincógnitapagrmissionorte{\displaystyle {\mathit {Expresión}}}a+b-c-d+ecomo compuesto pormiincógnitapagrmissionorte{\displaystyle {\mathit {Expresión}}}a+b-c-dyTmirmetro{\displaystyle {\mathit {Término}}}e, donde a+b-c-da su vez consiste en elmiincógnitapagrmissionorte{\displaystyle {\mathit {Expresión}}}a+b-cyTmirmetro{\displaystyle {\mathit {Término}}}d, mientras que a+b-cconsta de lamiincógnitapagrmissionorte{\displaystyle {\mathit {Expresión}}}a+byTmirmetro{\displaystyle {\mathit {Término}}}c, etc.

Eliminando la recursión izquierda

La recursión izquierda suele plantear problemas a los analizadores sintácticos, ya sea porque los lleva a una recursión infinita (como en el caso de la mayoría de los analizadores descendentes ) o porque esperan reglas en una forma normal que la prohíbe (como en el caso de muchos analizadores ascendentes ). Por lo tanto, a menudo se preprocesa una gramática para eliminar la recursión izquierda.

Eliminando la recursión directa por la izquierda.

A continuación se muestra el algoritmo general para eliminar la recursión izquierda directa. Se han realizado varias mejoras a este método. [ 2 ] Para un no terminal recursivo izquierdoA{\displaystyle A}, descartar cualquier regla de la formaA→A{\displaystyle A\rightarrow A}y consideremos a los que quedan:

A→Aα1∣…∣Aαnorte∣β1∣…∣βmetro{\displaystyle A\rightarrow A\alpha _{1}\mid \ldots \mid A\alpha _{n}\mid \beta _{1}\mid \ldots \mid \beta _{m}}

dónde:

  • cadaα{\displaystyle \alpha }es una secuencia no vacía de no terminales y terminales, y
  • cadaβ{\displaystyle \beta }es una secuencia de no terminales y terminales que no comienza conA{\displaystyle A}.

Reemplazar estos con dos conjuntos de producciones, un conjunto paraA{\displaystyle A}:

A→β1A′∣…∣βmetroA′{\displaystyle A\rightarrow \beta _{1}A^{\prime }\mid \ldots \mid \beta _{m}A^{\prime }}

y otro conjunto para el nuevo no terminalA′{\displaystyle A'}(a menudo llamada la "cola" o el "resto"):

A′→α1A′∣…∣αnorteA′∣ϵ{\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 izquierda directa.

Como ejemplo, consideremos el conjunto de reglas.

miincógnitapagrmissionorte→miincógnitapagrmissionorte+miincógnitapagrmissionorte∣Inortetmigramomir∣Strinortegramo{\displaystyle {\mathit {Expresión}}\rightarrow {\mathit {Expresión}}+{\mathit {Expresión}}\mid {\mathit {Entero}}\mid {\mathit {Cadena}}}

Esto podría reescribirse para evitar la recursión izquierda como

miincógnitapagrmissionorte→Inortetmigramomirmiincógnitapagrmissionorte′∣Strinortegramomiincógnitapagrmissionorte′{\displaystyle {\mathit {Expresión}}\rightarrow {\mathit {Entero}}\,{\mathit {Expresión}}'\mid {\mathit {Cadena}}\,{\mathit {Expresión}}'}
miincógnitapagrmissionorte′→+miincógnitapagrmissionorte miincógnitapagrmissionorte′∣ϵ{\displaystyle {\mathit {Expresión}}'\rightarrow {}+{\mathit {Expresión}}{\text{ }}{\mathit {Expresión}}'\mid \epsilon }

Eliminando toda la recursión izquierda.

El proceso anterior se puede extender para eliminar toda la recursión izquierda, convirtiendo primero la recursión izquierda indirecta en recursión izquierda directa en el no terminal de mayor número en un ciclo.

Entradas Una gramática: un conjunto de no terminalesA1,…,Anorte{\displaystyle A_{1},\ldots ,A_{n}}y sus producciones
Salida: Una gramática modificada que genera el mismo lenguaje pero sin recursión izquierda.
  1. Para cada no terminalAi{\displaystyle A_{i}}:
    1. Repita el proceso hasta que una iteración no altere la gramática:
      1. Para cada reglaAi→αi{\displaystyle A_{i}\rightarrow \alpha _{i}}, elαi{\displaystyle \alpha _{i}}siendo una secuencia de terminales y no terminales:
        1. Siαi{\displaystyle \alpha _{i}}comienza con un no terminalAj{\displaystyle A_{j}}yj<i{\displaystyle j<i}:
          1. Dejarβi{\displaystyle \beta _{i}}serαi{\displaystyle \alpha _{i}}sin su liderazgoAj{\displaystyle A_{j}}.
          2. Eliminar la reglaAi→αi{\displaystyle A_{i}\rightarrow \alpha _{i}}.
          3. Para cada reglaAj→αj{\displaystyle A_{j}\rightarrow \alpha _{j}}:
            1. Agregar la reglaAi→αjβi{\displaystyle A_{i}\rightarrow \alpha _{j}\beta _{i}}.
    2. Eliminar la recursión izquierda directa paraAi{\displaystyle A_{i}}como se describió anteriormente.

El paso 1.1.1 consiste en expandir el no terminal inicial.Aj{\displaystyle A_{j}}en el lado derecho de alguna reglaAi→Ajβ{\displaystyle A_{i}\to A_{j}\beta }, pero solo sij<i{\displaystyle j<i}. SiAi→Ajβ{\displaystyle A_{i}\to A_{j}\beta }Si se trataba de un paso en un ciclo de producciones que daba lugar a una recursión izquierda, entonces esto ha acortado ese ciclo en un paso, pero a menudo a costa de aumentar el número de reglas.

El algoritmo puede considerarse como el establecimiento de un orden topológico en no terminales: después solo puede haber una regla.Ai→Ajβ{\displaystyle A_{i}\to A_{j}\beta }sij>i{\displaystyle j>i}Cabe señalar que este algoritmo es muy sensible al ordenamiento no terminal; las optimizaciones suelen centrarse en elegir bien dicho ordenamiento.

Escollos

Si bien las transformaciones anteriores preservan el lenguaje generado por una gramática, pueden modificar los árboles de análisis sintáctico que registran el reconocimiento de cadenas. Con una gestión adecuada, la reescritura de árboles puede recuperar los originales, pero si se omite este paso, las diferencias pueden alterar la semántica del análisis.

La asociatividad es particularmente vulnerable; los operadores asociativos por la izquierda suelen aparecer en configuraciones similares a las asociativas por la derecha bajo la nueva gramática. Por ejemplo, partiendo de esta gramática:

miincógnitapagrmissionorte→miincógnitapagrmissionorte−Tmirmetro∣Tmirmetro{\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Expression}}\,-\,{\mathit {Term}}\mid {\mathit {Term}}}
Tmirmetro→Tmirmetro∗Fadotor∣Fadotor{\displaystyle {\mathit {Term}}\rightarrow {\mathit {Term}}\,*\,{\mathit {Factor}}\mid {\mathit {Factor}}}
Fadotor→(miincógnitapagrmissionorte)∣Inortetmigramomir{\displaystyle {\mathit {Factor}}\rightarrow ({\mathit {Expression}})\mid {\mathit {Integer}}}

Las transformaciones estándar para eliminar la recursión izquierda dan como resultado lo siguiente:

miincógnitapagrmissionorte→Tmirmetro miincógnitapagrmissionorte′{\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Term}}\ {\mathit {Expression}}'}
miincógnitapagrmissionorte′→−Tmirmetro miincógnitapagrmissionorte′∣ϵ{\displaystyle {\mathit {Expression}}'\rightarrow {}-{\mathit {Term}}\ {\mathit {Expression}}'\mid \epsilon }
Tmirmetro→Fadotor Tmirmetro′{\displaystyle {\mathit {Term}}\rightarrow {\mathit {Factor}}\ {\mathit {Term}}'}
Tmirmetro′→∗Fadotor Tmirmetro′∣ϵ{\displaystyle {\mathit {Term}}'\rightarrow {}*{\mathit {Factor}}\ {\mathit {Term}}'\mid \epsilon }
Fadotor→(miincógnitapagrmissionorte)∣Inortetmigramomir{\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 doble resta
Análisis recursivo por la izquierda de una doble resta

Este árbol de análisis agrupa los términos de la izquierda, dando la semántica correcta (1 - 2) - 3 .

El análisis sintáctico con la segunda gramática da como resultado

Análisis recursivo por la derecha de una doble resta
Análisis recursivo por la derecha de una doble resta

lo cual, 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. Nótese cómo los términos de la derecha aparecen más abajo en el árbol, de forma similar a como una gramática recursiva derecha los organizaría para 1 - (2 - 3) .

Adaptación de la recursión izquierda en el análisis sintáctico descendente

Una gramática formal que contiene recursión izquierda no puede ser analizada por un analizador LL(k) u otro analizador descendente recursivo ingenuo a menos que se convierta a una forma recursiva derecha débilmente equivalente . Por el contrario, la recursión izquierda es preferida para los analizadores LALR porque resulta en un menor uso de pila que la recursión derecha . Sin embargo, los analizadores descendentes más sofisticados pueden implementar gramáticas libres de contexto generales mediante el uso de la restricción. En 2006, Frost y Hafiz describieron un algoritmo que admite gramáticas ambiguas con reglas de producción recursivas izquierdas directas . [ 3 ] Ese algoritmo fue extendido a un algoritmo de análisis sintáctico 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 ] Los autores luego 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

Referencias

  1. ↑ "Notas sobre teoría del lenguaje formal y análisis sintáctico" (PDF) . Archivado del original el 27/11/2007 . Consultado el 30/10/2023 .{{cite web}}: CS1 maint: bot: estado de la URL original desconocido ( enlace ) . James Power, Departamento de Ciencias de la Computación, Universidad Nacional de Irlanda, Maynooth, Condado de Kildare, Irlanda. JPR02
  2. ↑ Moore, Robert C. (mayo de 2000). "Eliminación de la recursión izquierda de las gramáticas libres de contexto" (PDF) . 6.ª Conferencia de Procesamiento del Lenguaje Natural Aplicado : 249–255 .
  3. ↑ Frost, R.; R. Hafiz (2006). "Un nuevo algoritmo de análisis sintáctico descendente para acomodar la ambigüedad y la recursión izquierda en tiempo polinomial" . ACM SIGPLAN Notices . 41 (5): 46– 54. doi : 10.1145/1149982.1149988 . S2CID 8006549 . Disponible a través 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 sintáctico descendente modular y eficiente para gramáticas recursivas izquierdas ambiguas" (PDF) . 10.º Taller Internacional sobre Tecnologías de Análisis Sintáctico (IWPT), ACL-SIGPARSE : 109–120 . Archivado del 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 izquierdas ambiguas». Aspectos prácticos de los lenguajes declarativos (PDF) . Lecture Notes in Computer Science. Vol. 4902. págs. 167–181 . doi : 10.1007/978-3-540-77442-6_12 . ISBN   978-3-540-77441-9Archivado del original (PDF) el 21 de diciembre de 2008.
  • Consideraciones prácticas para las gramáticas LALR(1) Archivado el 1 de diciembre de 2020 en Wayback Machine