parsing - usar - ventajas y desventajas de la recursividad
Diferencia entre el factoraje izquierdo y la recursión izquierda (6)
¿Cuál es la diferencia entre el Left Factoring Left Recursion y la Left Recursion ? Entiendo que la Left factoring es una técnica predictiva de análisis descendente. Pero me confundo cuando escucho estos dos términos.
Esta es la forma en que he visto los dos términos utilizados:
- Recursión a la izquierda: cuando se pueden alcanzar una o más producciones desde sí mismas sin que se consuman fichas intermedias.
- Factorización a la izquierda: un proceso de transformación que convierte la gramática de una forma recursiva a la izquierda a una forma recursiva no a la izquierda equivalente.
La factorización izquierda es eliminar el factor izquierdo común que aparece en dos producciones del mismo no terminal. Se hace para evitar el rastreo por el analizador. Supongamos que el analizador tiene una vista al futuro, considere este ejemplo:
A -> qB | qc
donde A, B, C son no terminales y q es una oración. En este caso, el analizador se confundirá en cuanto a cuál de las dos producciones elegir y podría tener que realizar un seguimiento. Después de la factorización a la izquierda, la gramática se convierte a
A -> qD
D -> B | do
En este caso, un analizador con vista previa siempre elegirá la producción correcta.
La recursión a la izquierda es un caso en el que el no terminal más a la izquierda en una producción de un no terminal es el mismo no terminal (recursión a la izquierda directa) o, a través de algunas otras definiciones no terminales, se vuelve a escribir en el no terminal nuevamente (indirecta recursión izquierda). Considere estos ejemplos:
(1) A -> Aq (directo)
(2) A -> Bq B -> Ar (indirecto)
La recursión izquierda debe eliminarse si el analizador realiza un análisis de arriba hacia abajo
factor de izquierda
Deje la gramática dada: A -> ab1 | ab2 | ab3
1) podemos ver que, para cada producción, hay un prefijo común y si elegimos cualquier producción aquí, no se confirma que no tendremos que retroceder.
2) no es determinista, porque no podemos elegir ninguna producción y estar seguros de que alcanzaremos la cadena deseada haciendo el árbol de análisis correcto. pero si reescribimos la gramática de una manera que sea determinista y que también nos deje ser lo suficientemente flexibles como para hacer que cualquier cadena sea posible sin retroceso ... será:
A -> aA '', A'' -> b1 | b2 | b3 ahora, si se nos pide que hagamos el árbol de análisis para la cadena ab2 ... no necesitamos un seguimiento posterior. Como siempre podemos elegir la producción correcta cuando obtenemos A '', generaremos el árbol de análisis correcto.
Recursion izquierda
A -> Aa | b aquí está claro que el hijo izquierdo de A siempre será A si elegimos la primera producción, esto es la recursión izquierda, porque A se llama a sí mismo una y otra vez. la cadena generada a partir de esta gramática es: ba * ya que no puede estar en una gramática ... eliminamos la recursión izquierda escribiendo:
A -> bA ''A'' -> E | aA ''ahora no nos quedará la recursión y también podemos generar ba *.
recursión a la izquierda: = cuando la mano izquierda no terminal es igual que la mano derecha no terminal. Ejemplo: A-> A & | B donde & es alfa. Podemos eliminar la ricursión izquierda reescribiendo esta producción como me gusta.
A-> BA ''A'' -> & A ''| €
El factor de la media izquierda no debe ser no determinista. . Ejemplo: A -> & A | & B | & C
El factoring izquierdo es una técnica de transformación gramatical. Consiste en prefijos "factoring out" que son comunes a dos o más producciones.
Por ejemplo, pasando de:
A → α β | α γ
a:
A → α A ''
A ''→ β | γ
La recursión a la izquierda es una propiedad que tiene una gramática cada vez que puede derivar de una variable dada (no terminal) una rs que comienza con la misma variable, en uno o más pasos.
Por ejemplo:
A → A α
o
A → B α
B → A γ
Existe una técnica de transformación gramatical llamada Eliminación de la recursión izquierda , que proporciona un método para generar, dada una gramática recursiva izquierda, otra gramática que es equivalente y no se deja recursiva.
La relación / confusión entre ambos términos probablemente se deriva del hecho de que ambas técnicas de transformación deben aplicarse a una gramática antes de poder derivar un analizador predictivo de arriba hacia abajo.
Recursión izquierda: una gramática se deja recursiva si tiene un A no terminal de tal manera que hay una derivación A -> Aα | β donde α y β son secuencias de terminales y no terminales que no comienzan con A.
Mientras se diseña un analizador descendente superior, si la recursión izquierda existe en la gramática, entonces el analizador cae en un bucle infinito, aquí porque A intenta concordar con A, lo que no es posible. Podemos eliminar la recursión de la izquierda anterior reescribiendo la producción ofensiva. Como-
A -> βA ''
A ''-> αA'' | épsilon
Factoraje izquierdo: el factoraje izquierdo es necesario para eliminar el no determinismo de una gramática. Supongamos una gramática, S -> abS | aSb
Aquí, S está derivando el mismo terminal a en la regla de producción (dos opciones alternativas para S), que sigue al no determinismo. Podemos reescribir la producción para diferir la decisión de S
S -> aS ''
S ''-> bS | Sb
Por lo tanto, S ''puede ser reemplazado por bS o Sb