Chaque LR (0) grammaire est SLR (1), mais vice-versa ne doit pas nécessairement vrai, pourquoi?

Question

Chaque grammaire LR (0) est SLR (1), mais vice-versa ne doit pas nécessairement vrai, pourquoi?

Answer 1

Fondamentalement, un reflex (1) grammaire peut résoudre décalage-réduire les conflits qui existent dans une grammaire LR (0) correspondant. Prenez la grammaire par exemple sur Wikipedia SLR analyseur page (ce qui explique cela à un faible niveau plus rigoureux) :

1. S ? E
2. E ? 1 E
3. E ? 1

Quand un LR (0) analyseur est l'analyse d'un E et un "1" est le symbole d'entrée suivante, il pourrait reconnaître E et réduire (règle 3) ou il pourrait se déplacer afin d'analyser une suite E (règle 2). Parce qu'il ne peut pas regarder vers l'avenir, un LR (0) ne peut pas déterminer le faire. Cela devient plus évident si nous regardons le LR (0) pourrait être le traitement lorsque il rencontre un « 1 » (la fin de chaîne symbole a été ajouté):

• E ? 1 • E $
• E ? 1 • $

La première nécessiterait un changement, la seconde nécessite une réduire.

Avec la grammaire ci-dessus, un reflex (1) la grammaire peut regarder vers l'avenir un symbole et de déterminer les mesures à prendre. E ne peut être suivi de $, donc une action est de réduire uniquement valable à la fin de la chaîne. Cela correspond à la deuxième question, où vous pouvez voir le symbole suivant est un « $ ».

Pour une autre grammaire exemple qui est SLR (1) et non LR (0), voir Fegaras'