Comment identifier si une grammaire est LL(1), LR(0) ou SLR(1)?
Comment identifiez-vous si une grammaire est LL (1), LR(0) ou SLR(1)?
Quelqu'un peut-il l'expliquer en utilisant cet exemple ou tout autre exemple?
X → Yz / a
Y → bZ / ε
Z → ε
5 réponses
Pour vérifier si une grammaire est LL (1), une option consiste à construire la table D'analyse LL(1) et à vérifier les conflits éventuels. Ces conflits peuvent être
- conflits premier/Premier, où deux productions différentes devraient être prédites pour une paire Non Terminale/Terminale.
- conflits FIRST / FOLLOW, où deux productions différentes sont prédites, l'une représentant qu'une production doit être prise et s'étend à un nombre non nul de symboles, et l'autre représentant qu'une production devrait être utilisé pour indiquer que certains non terminaux devraient être finalement étendus à la chaîne vide.
- conflits de SUIVI/SUIVI, où deux productions indiquant qu'un non-terminal devrait finalement être étendu à la chaîne vide en conflit les unes avec les autres.
Essayons ceci sur votre grammaire en construisant les premiers ensembles et en suivant pour chacun des non-terminaux. Ici, nous obtenons que
FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}
Nous avons aussi que les ensembles suivants sont
FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}
De cela, nous pouvons construire la table D'analyse LL(1) suivante:
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), Nous commençons par construire tous les ensembles de configuration LR(0) pour la grammaire. Dans ce cas, en supposant que X est votre symbole de départ, nous obtenons ce qui suit:
(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 là, nous pouvons voir que la grammaire N'est pas LR(0) car il y a des conflits shift/reduce dans les états (1) et (6). Spécifiquement, parce que nous avons les éléments de réduction z → . et y → ., nous ne pouvons pas dire s'il faut réduire la chaîne vide à ces symboles ou déplacer un autre symbole. Plus généralement, aucune grammaire avec ε-productions N'est LR (0).
Cependant, cette grammaire peut être SLR (1). Pour voir cela, nous augmentons chaque réduction avec l'ensemble lookahead pour les non-terminaux particuliers. Cela rend cet ensemble de jeux de configuration SLR(1):
(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 plus de changement-réduire les conflits. Le conflit dans l'état (1) a été éliminé car nous ne réduisons que lorsque le lookahead est z, ce qui n'est en conflit avec aucun des autres éléments. De même, le conflit dans (6) a disparu pour la même raison.
Espérons que cela aide!
Si vous n'avez aucun conflit premier/premier et aucun conflit premier / suivi, 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 a, vous ne pouvez pas savoir s'il faut appliquer la production s - > Xb ou S - > Yc, car a est dans le premier ensemble de X et Y.
Un exemple de conflit de premier/suivi:
S -> AB
A -> fe | epsilon
B -> fg
En ne voyant que le premier symbole d'entrée f, vous ne pouvez pas décider d'appliquer la production A - > fe ou a - > epsilon, parce que f est à la fois dans le premier ensemble de A et L'ensemble suivant de A (A peut être analysé comme epsilon et B comme f).
Notez que si vous n'avez pas de EPSILON-productions, vous ne pouvez pas avoir de conflit de premier / suivi.
Réponse Simple: une grammaire est dite LL (1), si la table D'analyse ll(1) associée a au plus une production dans chaque entrée de table.
Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals]
then find the First and follow sets A.
First{A}={b}.
Follow{A}={$,a}.
Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element.
a b $
--------------------------------------------
S | A-->a |
| A-->Aa. |
--------------------------------------------
Comme [S, b] contient deux Productions, il existe une confusion quant à la règle à choose.So ce N'est pas LL (1).
Quelques vérifications simples pour voir si une grammaire est LL(1) ou non. cochez 1 : la grammaire ne doit pas rester récursive. Exemple: E -- > E + T. N'est pas LL (1) car il est récursif. Vérifiez 2 : La Grammaire devrait être laissé factorisé.
L'affacturage à gauche est requis lorsque deux ou Plusieurs choix de règles de grammaire partagent une chaîne de préfixe commune. Exemple: S-->Un+int|Un.
Vérifier 3 : la grammaire ne doit pas être ambiguë.
These are some simple checks.
LL (1) grammar est une grammaire non ambiguë sans contexte qui peut être analysée par des analyseurs LL(1).
Dans LL (1)
- Le Premier L représente l'entrée de balayage de gauche à droite. Deuxième l stands pour la dérivation la plus à gauche. 1 signifie utiliser un symbole d'entrée à chaque étape.
Pour vérifier la grammaire est LL (1), vous pouvez dessiner une table d'analyse prédictive. Et si vous trouvez plusieurs entrées dans la table, vous pouvez dire que la grammaire N'est pas LL (1).
Leur est également raccourci pour vérifier si la grammaire est LL (1) ou non . Technique De Raccourci
Avec ces deux étapes, nous pouvons vérifier si LL(1) ou non. Deux d'entre eux doivent être satisfaits.
1.Si nous avons la production: a - > a1 / a2 / a3 / a4/.....|un. Puis,le Premier(a(i)) à l'intersection de la Première(a(j)) doit être phi(ensemble vide)[a(i)-un indice i.]
2.Pour chaque 'a' non terminal, si First(A) contient epsilon Ensuite, la première intersection (a) suit (A) doit être phi (ensemble vide).