que tiene la siguiente gramática, que me dijeron que es LR (1), pero no SLR (1):¿Cómo es esta gramática LR (1) pero no SLR (1)?
S :: = a Un | b A c | d c | b d a
Un :: = d
No entiendo por qué es. ¿Cómo probarías esto?
Una forma de resolver esto sería intentar construir analizadores LR (1) y SLR (1) para la gramática. Si encontramos algún cambio/reducción o reducción/reducción de conflictos en el curso de hacerlo, podemos demostrar que la gramática no debe pertenecer a una de esas clases de idiomas.
Comencemos con el analizador SLR (1). Primero, necesitamos calcular los conjuntos de configuración LR (0) para la gramática. Estos son vistos aquí:
(1)
S -> .aA
S -> .bAc
S -> .dc
S -> .bda
(2)
S -> a.A
A -> .d
(3)
S -> aA.
(4)
A -> d.
(5)
S -> b.Ac
S -> b.da
A -> .d
(6)
S -> bA.c
(7)
S -> bAc.
(8)
S -> bd.a
A -> d.
(9)
S -> bda.
(10)
S -> d.c
(11)
S -> dc.
A continuación, hay que sacar a los conjuntos seguir para todos los no terminales. Esto se muestra aquí:
FOLLOW(S) = { $ }
FOLLOW(A) = { $, c }
Teniendo en cuenta esto, podemos volver atrás y actualizar los LR conjuntos (0) configuradora en SLR (1) conjuntos configurating:
(1)
S -> .aA [ $ ]
S -> .bAc [ $ ]
S -> .dc [ $ ]
S -> .bda [ $ ]
(2)
S -> a.A [ $ ]
A -> .d [ $, c ]
(3)
S -> aA. [ $ ]
(4)
A -> d. [ $, c ]
(5)
S -> b.Ac [ $ ]
S -> b.da [ $ ]
A -> .d [ $, c ]
(6)
S -> bA.c [ $ ]
(7)
S -> bAc. [ $ ]
(8)
S -> bd.a [ $ ]
A -> d. [ $, c ]
(9)
S -> bda. [ $ ]
(10)
S -> d.c [ $ ]
(11)
S -> dc. [ $ ]
Curiosamente, no hay conflictos ¡aquí! El único conflicto posible de cambio/reducción está en el estado (8), pero aquí no hay conflicto porque la acción de cambio está en a y la reducción está en $. En consecuencia, esta gramática en realidad es SLR (1). Como cualquier gramática SLR (1) también es LR (1), esto significa que la gramática es tanto SLR (1) como LR (1).
Espero que esto ayude!
Solo tenga en cuenta que cada gramática SLR (1) es LR (1) gramática pero no todo LR (1) es SLR (1) –
Si busca un ejemplo, puede utilizar esta gramática: '1) S -> XX 2) X -> aX 3) X -> b' –
@templatetypedef, ¿Y si hubiera sido BDA. [$] en el estado 8. ¿Habría una reducción reducir el conflicto? Porque tenemos un solo símbolo de seguimiento que es común. – Zephyr
no tengo suficiente karma para comentar sobre la respuesta anterior, y estoy un poco tarde a esta pregunta, pero ...
que he visto esta gramática como ejemplo en otros lugares y el PO hecho un error tipográfico. Debe ser:
S :: = A a | b A c | d c | b d a
A :: = d
es decir, la primera cláusula de S es 'A a', no 'un A'.
En este caso la siguiente manera fija para un {$ es, a, c} y hay un conflicto en el estado SLR 8.
Si va a hacer una carrera en el negocio de los ordenadores, es necesario para aprender a leer cuando no sabes algo. Lea Wikipedia en LR idiomas cuidadosamente, y resolver esto.Si toma algo de tiempo mirarlo y entenderlo, que así sea; esto es típico. http://en.wikipedia.org/wiki/LR_parser –
¡Gracias, has sido muy útil! –
De una manera brusca, sí: -} –