Prerrequisito – Clasificación de gramáticas libres de contexto , ambigüedad y analizadores Recursividad izquierda: gramática de la forma,
S --> S / a / b
Se llama recursivo por la izquierda, donde S es cualquier no Terminal y a, yb son cualquier conjunto de terminales. Problema con la recursión izquierda: si una recursión izquierda está presente en cualquier gramática, durante el análisis en la parte de análisis de sintaxis de la compilación existe la posibilidad de que la gramática cree un bucle infinito. Esto se debe a que en cada momento de producción de la gramática S se producirá otra S sin comprobar ninguna condición. Algoritmo para eliminar la recursividad por la izquierda con un ejemplo: supongamos que tenemos una gramática que contiene la recursividad por la izquierda:
S-->S a / S b / c / d
- Verifique si la gramática dada contiene recursividad izquierda, si está presente, separe la producción y comience a trabajar en ella. En nuestro ejemplo,
S-->S a/ S b /c / d
- Introduzca un nuevo no terminal y escríbalo al final de cada terminal. Producimos una nueva S’ no terminal y escribimos nueva producción como,
S-->cS' / dS'
- Escriba no terminal recién producido en LHS y en RHS puede producir o puede producir nueva producción en la que los terminales o no terminales que siguieron al LHS anterior serán reemplazados por un nuevo no terminal al final.
S'-->? / aS' / bS'
- Entonces, después de la conversión, la nueva producción equivalente es
S-->cS' / dS' S'-->? / aS' / bS'
Recursión indirecta por la izquierda: se dice que una gramática tiene recursión indirecta por la izquierda si, a partir de cualquier símbolo de la gramática, es posible derivar una string cuya cabeza es ese símbolo. Por ejemplo,
A --> Br B --> Cd C --> At
Donde A, B, C son no terminales y r, d, t son terminales. Aquí, comenzando con A, podemos derivar A nuevamente al sustituir C por B y B por A. Algoritmo para eliminar la recursividad indirecta con la ayuda de un ejemplo:
A1 --> A2 A3 A2 --> A3 A1 / b A3 --> A1 A1 / a
Donde A1, A2, A3 no son terminales y a, b son terminales.
- Identificar las producciones que pueden causar recursividad indirecta a la izquierda. En nuestro caso,
A3--> A1 A1 / a
- Sustituya su producción en el lugar donde está presente el terminal en cualquier otra producción. Sustituya A1–> A2 A3 en la producción de A3. A3 -> A2 A3 A1. Ahora, en esta producción, sustituya A2–> A3 A1 / b y luego reemplácelo por,
A3 --> A3 A1 A3 A1 / b A3 A1
- Ahora la nueva producción se convierte en forma de recursión directa a la izquierda, resuelva esto mediante el método de recursión directa a la izquierda. Eliminando la recursión directa a la izquierda en lo anterior,
A3 --> a | b A3 A1 | aA' | b A3 A1A' A' --> A1 A3 A1 | A1 A3 A1A'
- La gramática resultante es entonces:
A1 --> A2 A3 A2 --> A3 A1 | b A3 --> a | b A3 A1 | aA' | b A3 A1A' A' --> A1 A3 A1 | A1 A3 A1A'
Publicación traducida automáticamente
Artículo escrito por madarsh986 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA