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