Réponse:
La grammaire G1 est ambigüe car, par exemple, on peut reconnaître le mot
vide par des dérivations appartenant à des arbres syntaxiques (ou arbres de
dérivations) différents:
S1 ®
E ® |
ì
í
î |
|
S1 ®
E ® e
|
Donc elle n'est pas LR(1) ni a fortiori LL(1).
La grammaire G2 est LL(1).
Pour le vérifier, nous calculons pour chaque règle a ®
b
les ensembles first (b), follow (a), et nous vérifions si
a ®
*e; finalement nous construisons la relation de
transition de domain V × S.
Les calculs sont résumés dans la table suivante:
a |
b |
first (b) |
follow (a) |
a ®
*e |
g |
d |
S |
E |
g |
g |
yes |
Ö |
|
E |
g E d E |
g |
d |
yes |
Ö |
|
|
e |
|
|
|
|
Ö |
La fonction de transition donnée par les Ö dans la sous-matrice en
bas à droite ne comporte qu'un élément par case; elle définie donc bien une
fonction.
La grammaire est donc LL(1). Par conséquence, elle est aussi LR(1) et n'est
pas ambigüe.