¿Qué es la poda de mango?

El identificador es la substring que coincide con el cuerpo de una producción cuya reducción representa un paso junto con el reverso de una derivación más a la derecha.

El identificador de la forma secuencial derecha Y es la producción de Y donde la string S se puede encontrar y reemplazar por A para producir la forma secuencial derecha anterior en RMD (derivación más a la derecha) de Y.

Forma oracional: S => a aquí, ‘a’ se llama forma oracional, ‘a’ puede ser una mezcla de terminales y no terminales.

Ejemplo:

Consider Grammar : S -> aSa | bSb | ε
Derivation:              S => aSa => abSba => abbSbba => abbbba

Forma Sentencial Izquierda y Sentencial Derecha:

• Una forma oracional izquierda es una forma oracional que ocurre en la derivación más a la izquierda de alguna oración.
• Una forma oracional derecha es una forma oracional que ocurre en la derivación más a la derecha de alguna oración.

El mango contiene dos cosas:

• Producción
• Posición

Ejemplo: 

S -> aABe
A -> Abc | b
B -> d

Pasos:

abbcde : γ = abbcde , A->b; Handle = b
aAbcde : γ = RHS = aAbcde , A->Abc; Handle = Abc
aAde : γ = aAde , B->d; Handle = d
aABe : γ = aABe, S-> aABe; Handle = aABe

Nota: los identificadores están subrayados en las formas oracionales derechas.

¿Siempre se maneja la substring más a la izquierda?

No, elegir la substring más a la izquierda como el identificador siempre puede no dar un análisis SR (Shift-Reduce) correcto .

Poda de mango:

La eliminación de los elementos secundarios del no terminal del lado izquierdo del árbol de análisis se denomina poda de manejo . 

Se puede obtener una derivación hacia la derecha en sentido inverso mediante la poda del mango.

Pasos a seguir:

• Comience con una string de terminales ‘w’ que se va a analizar.
• Sea w = γ _n , donde γ _n es la enésima forma secuencial derecha de un RMD desconocido.
• Para reconstruir el RMD a la inversa, ubique el identificador βn en _γn . Reemplace βn con LHS de algún A _n ⇢ βn para obtener (n-1) ^th RSF γ _n-1. Repetir.

Ejemplo 1:

Forma secuencial derecha	Resolver	Reducción de la producción
identificación + identificación * identificación	identificación	E ⇒ identificación
E + identificación * identificación	identificación	E ⇒ identificación
E + E * identificación	identificación	E ⇒ identificación
mi + mi * mi	E + E	E ⇒ E + E
mi * mi	mi * mi	mi ⇒ mi * mi
E (Raíz)

Ejemplo 2:

Forma secuencial derecha	Resolver	Producción
identificación + identificación + identificación	identificación	E ⇒ identificación
E + identificación + identificación	identificación	E ⇒ identificación
E + E + identificación	identificación	E ⇒ identificación
mi + mi + mi	E + E	E ⇒ E + E
E + E	E + E	E ⇒ E + E
E (Raíz)