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 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. 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 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. Les grammaires d'opérateurs ne sont utilisables que pour un petit sous-ensembles des langages de type 2. Alfred V.