PUERTA | PUERTA CS 2008 | Pregunta 55

Un analizador LALR(1) para una gramática G puede tener conflictos de desplazamiento-reducción (SR) si y solo si
(A) el analizador SLR(1) para G tiene conflictos SR
(B) el analizador LR(1) para G tiene SR conflictos
(C) el analizador LR(0) para G tiene conflictos SR
(D) el analizador LALR(1) para G tiene conflictos de reducción-reducción

Respuesta: (B)
Explicación:
Tanto el analizador LALR(1) como el LR(1) utilizan LR(1) conjunto de elementos para formar sus tablas de análisis. Y los estados LALR (1) se pueden encontrar fusionando los estados LR (1) del analizador LR (1) que tienen el mismo conjunto de primeros componentes de sus elementos.

es decir, si el analizador LR(1) tiene 2 estados I y J con elementos A->a.bP,x y A->a.bP,y respectivamente, donde x e y son símbolos anticipados, entonces estos elementos son iguales con con respecto a su primer componente, pueden fusionarse y formar un solo estado, digamos K. Aquí tenemos que tomar la unión de los símbolos de anticipación. Después de la fusión, el Estado K tendrá un solo elemento como A->a.bP,x,y . De esta manera se forman los estados LALR(1) (es decir, después de fusionar los estados de LR(1)).

Ahora, el conflicto SR en los elementos LR (1) puede estar presente siempre que un estado tenga elementos de la forma:

A-> a.bB , p
C-> d. , b

i.e. it is getting both shift and reduce at symbol b, 
hence a conflict. 

Ahora, como LALR(1) tiene elementos similares a LR(1) en términos de su primer componente, la forma de reducción de desplazamiento solo tendrá lugar si ya está allí en los estados LR(1). Si no hay conflicto de SR en el estado LR(1), nunca se reflejará en el estado LALR(1) obtenido al combinar los estados LR(1).

Nota: Pero este proceso de fusión puede introducir un conflicto de RR, y entonces la Gramática no será LALR(1).

Cuestionario de esta pregunta