Análisis Sintáctico Ascendente

Análisis Sintáctico Ascendente

4.5 en adelante

Por desplazamiento y reducciónLa entrada se “reduce” al símbolo inicialDesplazando elementos de la entradaLlegar de las hojas hacia la raíz

ProcedimientoA partir de la entrada

Se sustituye una subcadena• Adecuadamente elegida• Que concuerde con un lado derecho

Por el no terminal del lado izquierdo• Trazando una derivación inversa• Por el lado derecho

EjemploGramática

S => aABeA => Abc | bB => d

Entrada “abbcde” se reduce a S por:

abbcde

EjemploGramática

S => aABeA => Abc | bB => d

Entrada “abbcde” se reduce a S por:

abbcdeaAbcde

EjemploGramática

S => aABeA => Abc | bB => d

Entrada “abbcde” se reduce a S por:

abbcdeaAbcdeaAde

¿Por qué no aAAcde?

EjemploGramática

S => aABeA => Abc | bB => d

Entrada “abbcde” se reduce a S por:

abbcdeaAbcdeaAdeaABe

EjemploGramática

S => aABeA => Abc | bB => d

Entrada “abbcde” se reduce a S por:

abbcdeaAbcdeaAdeaABeS

EjemploGramática

S => aABeA => Abc | bB => d

Entrada “abbcde” se reduce a S por:

abbcdeaAbcdeaAdeaABeS

MangosMangosMangosMangos

MangosSubcadenaConcuerda con un lado derechoSe reduce al no terminal de la izquierdaAvanza un paso en la derivación inversa

De una derivación derechaSi la gramática no es ambigua

Existe exactamente un mango

Volviendo al ejemploGramática

S => aABeA => Abc | bB => d

Es recursiva por la izquierda¿Puede derivar abbcde?

Volviendo al ejemploGramática

S => aABeA => Abc | bB => d

Es recursiva por la izquierda¿Puede derivar abbcde?

Solo por la derecha

EjercicioPrograma -> Instrucción | { Rutina

}Rutina -> Instrucción ; Instrucción

|Instrucción ; Rutina

Instrucción -> nil | Variable ++ |Variable -- |While Prueba do

ProgramaPrueba -> Variable <> 0 |

Variable = 0

Analizar Ascendentemente

While v<>0 do {y++;x++;v--;

}

Gramáticas LRGramáticas LR

Left to Right • de izquierda a derecha

Rightmost production• La producción de más a la derecha

Variaciones: SLR, LALR, LR(k)

Tercer proyectoCompilador de programas whileGenerando script de assembler para debugTomando en cuenta los macrosFecha de entrega 21-10-2006