Grammaire d'opérateurs

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. Ainsi, par exemple, il est possible de décrire des expressions mathématiques simple à 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\cdot6+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.

Sommaire

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Grammaire d'opérateurs de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • 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. Ainsi, par exemple, il est possible de décrire des… …   Wikipédia en Français

  • Grammaire d'operateurs — 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. Ainsi, par exemple, il est possible… …   Wikipédia en Français

  • Grammaire Formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… …   Wikipédia en Français

  • Grammaire Française — La grammaire française est l étude des règles régissant cette langue. Sommaire 1 Introduction 2 L orthographe 3 Les parties du discours 3.1 Le nom …   Wikipédia en Français

  • Grammaire du français — Grammaire française La grammaire française est l étude des règles régissant cette langue. Sommaire 1 Introduction 2 L orthographe 3 Les parties du discours 3.1 Le nom …   Wikipédia en Français

  • Grammaire francaise — Grammaire française La grammaire française est l étude des règles régissant cette langue. Sommaire 1 Introduction 2 L orthographe 3 Les parties du discours 3.1 Le nom …   Wikipédia en Français

  • Grammaire Lexicale-Fonctionnelle — Le formalisme des grammaires lexicales fonctionnelles (en anglais Lexical Functional Grammars, d où l acronyme que nous utiliserons désormais, LFG) est un formalisme grammatical utilisé pour formaliser les langues naturelles. C est un formalisme… …   Wikipédia en Français

  • Grammaire formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… …   Wikipédia en Français

  • Grammaire française — Cet article fait partie de la série : Langue française Langue d oïl Dialectes Créoles Francophonie Histoire Serments de Strasbourg Ordonnance de Villers Cotterêts …   Wikipédia en Français

  • Grammaire S-attribuée — Une grammaire S attribuée est une grammaire ne contenant que des attributs synthetisés où chaque attribut ne dépend que des attributs fils. Sommaire 1 Généralités 2 Méthodes d évaluation des attributs 2.1 Méthode à plusieurs passes …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”