Download Premios Semana 15

Premios Semana 15
Analizadores LR(1) y LALR()
Analizador Sintactico LR(1)
• Similar al analizador SLR().
• El LR(1) utiliza únicamente un subconjunto de
los siguientes de cada no terminal.
• Asi, se refina el conjunto de los terminales
validos, reduciendo los conflictos
• Es un analizador mas poderoso que el SLR()
• Sin embargo, posee mas estados que este.
Definición LR(1)
• Dado un elemento LR(1)[A->αβµ,a] donde B es
un no terminal, existen transiciones ε para
elementos [B->β,b] para cada producción B->β y
para cada token b en Primero(µa).
Autómata para gramática LR(1)
Autómata para la gramática:
A(A)|a
Analizador Sintáctico LALR
• Genera tablas mucho mas pequeñas que las
obtenidas con el LR(1).
• Tiene la misma cantidad de estados que el
SLR(), sin presentar tantos conflictos
• Es decir, mayor potencia de análisis, con el
mismo tamaño.
• En pocas palabras, es reducir el LR(1)
Analizador Sintáctico LALR
• Consiste en comparar estados semejantes para
reducirlos
• Los estados que se comparan, solo presentan
diferencias en los símbolos de pre-analisis.
• Al comparar los “corazones”, se unen los estados
semejantes, asignando como conjunto de
símbolos de pre-analisis, la unión de ambos
Analizador Sintáctico LALR
• Como corazón se entenderá a aquellos estados
que tengan el mismo conjunto de primeros
elementos.