Comment identifiez-vous si une grammaire est LL (1), LR (0) ou SLR (1)?
Quelqu'un peut-il s'il vous plaît expliquer en utilisant cet exemple, ou tout autre exemple?
X → Yz | une
Y → bZ | ε
Z → ε
Réponses
Trop de publicités?
Pour vérifier si une grammaire est LL(1), une option est de construire le LL(1) analyse de la table et de vérifier d'éventuels conflits. Ces conflits peuvent être
- PREMIER/PREMIÈRE conflits, où les deux productions différentes devraient être prévues pour un non-terminal en question/terminal paire.
- PREMIÈRE/SUIVEZ les conflits, où deux spectacles différents sont prévus, l'un représentant qu'une partie de la production doit être prise et s'étend à un nombre non nul de symboles, et un représentant de que la production devrait être utilisé pour indiquer qu'un non-terminal en question devrait être finalement élargi à la chaîne vide.
- SUIVEZ/respecter les conflits, où les deux productions, indiquant qu'un non-terminal en question devraient à terme être étendu à la chaîne vide conflit les uns avec les autres.
Nous allons essayer ceci sur votre grammaire par la construction de la PREMIÈRE et de SUIVRE définit pour chacun des nonterminals. Ici, nous obtenons que
FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}
Nous avons aussi que le SUIVRE ensembles sont
FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}
À partir de cela, nous pouvons construire les LL(1) analyse d'un tableau:
a b z $
X a Yz Yz
Y bZ eps
Z eps
Puisque nous pouvons construire cette table d'analyse sans conflits, la grammaire est LL(1).
Pour vérifier si une grammaire est LR(0) ou SLR(1), on commence par construire l'ensemble de la LR(0) configurant ensembles pour la grammaire. Dans ce cas, en supposant que X est votre symbole de démarrage, nous obtenons les suivantes:
(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ
(2)
X' -> X.
(3)
X -> Y.z
(4)
X -> Yz.
(5)
X -> a.
(6)
Y -> b.Z
Z -> .
(7)
Y -> bZ.
À partir de cela, nous pouvons voir que la grammaire n'est pas LR(0), car il y a des maj/réduire les conflits dans les états (1) et (6). Plus précisément, parce que nous avons du réduire les éléments de Z → . et Y → ., on ne peut pas dire que ce soit pour réduire la chaîne vide à ces symboles ou de déplacer quelque autre symbole. Plus généralement, aucune grammaire avec ε-productions est LR(0).
Cependant, cette grammaire peut être SLR(1). Pour voir cela, nous augmentons chaque réduction de l'anticipation fixée pour le particulier nonterminals. Cela donne à l'arrière de cet ensemble de SLR(1) configurant ensembles:
(1)
X' -> .X
X -> .Yz [$]
X -> .a [$]
Y -> . [z]
Y -> .bZ [z]
(2)
X' -> X.
(3)
X -> Y.z [$]
(4)
X -> Yz. [$]
(5)
X -> a. [$]
(6)
Y -> b.Z [z]
Z -> . [z]
(7)
Y -> bZ. [z]
Maintenant, nous n'avons pas plus de maj de réduire les conflits. Le conflit dans l'état (1) a été éliminée car nous avons seulement à diminuer lorsque l'anticipation est z, qui n'entre pas en conflit avec les autres éléments. De même, le conflit en (6) est parti pour la même raison.
Espérons que cette aide!
Kent Munthe Caspersen
Points
642
Si vous n'avez pas d'ABORD/tout d'ABORD les conflits et les n PREMIERS/SUIVEZ les conflits, votre grammaire est LL(1).
Un exemple de PREMIER/PREMIER conflit:
S -> Xb | Yc
X -> a
Y -> a
En ne voyant que le premier symbole d'entrée, vous ne pourrez pas savoir si à appliquer à la production de S -> Xb ou S -> Yc, parce que l'un est dans le PREMIER set, à la fois de X et de Y.
Un exemple d'une PREMIÈRE/SUIVEZ conflit:
S -> AB
A -> fe | epsilon
B -> fg
En ne voyant que le premier symbole d'entrée f, vous ne pouvez pas décider de l'appliquer à la production d'Un -> fe ou Un -> epsilon, puisque f est à la fois le PREMIER jeu de Un et le SUIVI d'Un A peut être analysée comme epsilon et de B à f).
Notez que si vous n'avez pas d'epsilon-productions vous ne pouvez pas avoir un PREMIER/SUIVEZ conflit.
