Grammaire d'opérateurs
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Les grammaires d'opérateurs permettent d'analyser un sous-ensemble des langages de type 2 (voir Langage formel). Elles permettent en particulier de décrire des expressions mathématiques. Par exemple, il est possible de décrire des expressions mathématiques simples à l'aide de la syntaxe suivante :
EXPR :== NOMBRE
| EXPR OPERATEUR EXPR
où OPERATEUR est un opérateur dans la liste (+, -, * ou /). Mais une telle représentation est ambigüe ! En effet, cette façon de décrire ces expressions ne tient pas compte de la différence de priorité entre un + et un *. Par exemple
est différente de , mais avec la représentation donnée plus haut, il n'y a pas de différence.
Par contre, si on considère que + et - sont moins prioritaires que * et /, alors il n'y a plus d'ambiguïté. Il est alors possible d'utiliser la priorité de ces opérateurs pour analyser une expression.
Algorithme d'analyse des grammaires d'opérateurs[modifier | modifier le code]
Cet algorithme prend en entrée une chaîne de symboles terminaux terminée par le symbole spécial $.
AnalyseParPrioriteOperateur :
faire pointer PS sur le premier symbole de la chaine d'entrée
REPETER
SI $ est au sommet de la pile et PS pointe sur $ ALORS
RETOURNER VRAI -- La chaine est bien formée
FIN SI
Copier le symbole au sommet de la pile dans une variable A
Copier le symbole pointé par PS dans une variable B
SI la priorité de A est inférieur ou égale à celle de B ALORS
empiler B sur la pile
Avancer PS sur le symbole suivant
SINON SI la priorité de A est strictement supérieur à celle de B ALORS
REPETER
dépiler le sommet de la pile
JUSQU'À priorité du sommet de la pile est inférieur au terminal précédemment dépilé
SINON
RETOURNER FAUX -- La chaine est mal formée
FIN SI
FIN REPETER
Avantages des grammaires d'opérateurs[modifier | modifier le code]
Une analyse d'une grammaire d'opérateur est assez simple à mettre en œuvre. De plus, il est possible, suivant l'implémentation utilisée de modifier dynamiquement la priorité des opérateurs. Une telle capacité est essentiel pour l'implémentation de langage tel que le Prolog.
Inconvénients des grammaires d'opérateurs[modifier | modifier le code]
Les grammaires d'opérateurs ne sont utilisables que pour un petit sous-ensembles des langages de type 2.
Voir aussi[modifier | modifier le code]
- Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Addison Wesley Publishing Company, 1986
