Free Web Hosting Provider - Web Hosting - E-commerce - High Speed Internet - Free Web Page
Search the Web

escudo.jpg (17355 bytes)

MUSICA MIENTRAS NAVEGAS CON REAL AUDIO

sacanimado.GIF (139839 bytes)

205 PERSONAS QUE NOS VISITAN

iconobusca.gif (415 bytes)

TABLAS DE TRANSICION

La condición que impone el análisis LR(0),es muy restrictiva, ya que los items completos han de aparecer en conjuntos separados. Existe una forma sencilla de ampliar la aplicación de ésta a una gama más amplia de gramáticas, mediante la lectura de un símbolo en la entrada para determinar la función a realizar.
Cuando una máquina de reconocimiento LR está en un determinado estado, el conjunto de items válidos para la subcadena que se encuentra en la pila en ese momento es precisamente el conjunto de la colección asociado a dicho estado. Si en este conjunto aparece un ítem completo y otro ítem más , se produce un conflicto en el análisis LR(0), ya que no podemos decidir que acción realizar. Supongamos el caso del análisis de la cadena tas. Supongamos que en un momento determinado del análisis, y tras leer la subcadena t, tendremos en la pila una subcadena viable , quedando por leer aún la subcadena as. Esto nos indica que as es una forma sentencial del lenguaje. Supongamos también que existe un ítem completo válido asociado a esta subcadena viable, de la forma [A -> ·]. Tras efectuar la reducción correspondiente obtendríamos la tira Aas, que debe ser una forma sentencial de nuestro lenguaje. Es evidente que una condición necesaria para que esto suceda es que el símbolo a pueda aparecer a la derecha de A en alguna forma sentencial. Es decir, que a pertenezca al conjunto SIGUIENTE(A), tal y como se definió en el apartado dedicado al análisis LL(1).
Esto proporciona un método para eliminar algunas de las duplicidades que pueden aparecer en la tabla de acciones del análisis LR(0). El nuevo método se denomina SLR(1). El algoritmo de construcción de las tablas de análisis SLR(1) queda de la siguiente forma:
a) Construimos la colección de conjuntos de items. Este paso es igual que en el análisis LR(0).
b) Los estados de la máquina SLR(1) corresponden a cada uno de los conjuntos de items Ij de la colección C.
El estado inicial será el asociado al conjunto de items que contenga al primer ítem asociado al axioma, [S' -> ·S]. También es igual que en el análisis LR(0).
c) La tabla de transiciones es la definida por la función de transición entre conjuntos de items . Ídem.
d) La tabla de acciones para la máquina SLR(1) depende del estado en que se encuentra la máquina y del primer símbolo de la entrada:
Si el ítem [A -> ·a] pertenece al conjunto asociado al estado q, entonces:
ACCIÓN(q,a)=Desplazamiento
Si el ítem [A -> ·], A<>S, pertenece al conjunto asociado al estado q, entonces para todo a que pertenezca a
SIGUIENTE(A):
ACCIÓN(q,a)=Reducción A ->
Si el ítem [S -> ·] pertenece al conjunto asociado al estado q, entonces:
ACCIÓN(q,$)=Aceptar.
Nota: Esto equivale a suponer que el único símbolo siguiente al axioma es el de final de cadena ($), que ocurre siempre en las gramáticas aumentadas.
Si tras efectuar las asignaciones correspondientes a todos los items de la gramática no obtenemos ninguna duplicidad en la tabla de acciones, entonces la gramática se dice que es SLR(1). Todas las gramáticas LR(0) son SLR(1).
Ejemplo: Sea la gramática aumentada
(0) S -> E
(1) E -> E+T
(2) E -> T
(3) T -> T*F
(4) T -> F
(5) F -> (E)
(6) F -> a
La colección de items estará compuesta por los conjuntos siguientes:
I0 = {[S -> ·E],[E -> ·E+T],[E -> ·T],[T -> ·T*F], [T -> ·F],[F -> ·(E)],[F -> ·a]}
I1 = {[S -> E·],[E -> E·+T]}
I2 = {[E -> T·],[T -> T·*F]}
I3 = {[T -> F·]}
I4 = {[F -> (·E)],[E -> ·E+T],[E -> ·T],[T -> ·T*F], [T -> ·F],[F -> ·(E)],[F -> ·a]}
I5 = {[E -> a·]}
I6 = {[E -> E+·T],[T -> ·T*F],[T -> ·F],[F -> ·(E)], [F -> ·a]}
I7 = {[E -> T*·F],[F -> ·(E)],[F -> ·a]}
I8 = {[F -> (E·)],[E -> E·+T]}
I9 = {[E -> E+T·],[T -> T·*F]}
I10 = {[T -> T*F·]}
I11 = {[F -> (E)·]}
Como se ve, esta gramática no es LR(0), ya que en los conjuntos I1, I2 e I9 hay dos estados, y uno de ellos es completo. Se produce un conflicto del tipo reducción/desplazamiento en la casilla correspondiente a dichos estados. Sin embargo, aplicando el procedimiento SLR pueden construirse las siguientes tablas de análisis:
Para el estado 2, por ejemplo, existen dos items:
[E -> T·] [E -> T·*F]
Según el primero de ellos, se puede aplicar la reducción E -> T
solamente para aquellos elementos pertenecientes a SIGUIENTE(E).
SIGUIENTE(E) = {+,),$}, por tanto:
ACCIÓN (2,"+") = Reducción E -> T
ACCIÓN (2,")") = Reducción E -> T
ACCIÓN (2,"$") = Reducción E -> T
El segundo de los items del conjunto I2 nos indica que la acción a realizar cuando el símbolo siguiente es * es:
ACCIÓN(2,*) = Desplazamiento.

REGRESAR

CONTINUAR