Grammaire d'opérateurs

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 $2\cdot 6+7$ est différente de $2\cdot (6+7)$, 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

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

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

Les grammaires d'opérateurs ne sont utilisables que pour un petit sous-ensembles des langages de type 2.

Voir aussi

• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Addison Wesley Publishing Company, 1986