Les opérateurs
Cette feuille en Postscript

1  Retour à l'école primaire

L'instituteur explique qu'un calcul est soit une addition, soit une soustraction, etc. En termes de grammaires, il définit la grammaire suivante des expressions arithmétique.
S → E         E → int
 
E → E + E          E → E - E          E → E * E          E → E / E
Notez que int est au niveau des élèves de l'école primaire qui ne connaissent que les entiers « naturels ».
  1. Grâce à votre expérience des quatre opérations et des grammaires, distinguer terminaux et non-terminaux.
  2. L'instituteur demande aux élèves d'écrire un calcul.
    Oscar Amélie Samir Pamela
    1 + 2 * 3 3 - 2 - 1 1 + 2 + 3 2 + - 1
    1. Montrer qu'Oscar a juste. Pour ce faire on exhibera une dérivation de S (symbole de départ) vers le mot d'Oscar. Une dérivation est tout bêtement une suite de réécritures d'un mot de terminaux et de non-terminaux, chaque réécriture consistant à remplacer un non-terminal par le membre droit d'une production de ce non-nonterminal.
    2. Montrer que Pamela a faux. Quel est l'ensemble des mots de terminaux (le langage) généré par la grammaire ?
    3. Compter les dérivations possibles produisant le calcul d'Oscar.
    4. Le soir, après la classe, aidez Pamela à ratrapper son erreur. Pamela avait en fait déjà une vague idée des entiers relatifs, mais elle doit s'exprimer à l'aide de la grammaire de son instituteur.


  3. Le lendemain, l'instituteur demande d'effectuer les calculs. Oscar et Samir s'y collent. Voici leurs résultats.
      1 + 2 * 3 3 - 2 - 1 1 + 2 + 3
    Oscar 9 0 6
    Samir 7 2 6

    L'instituteur est tenté de s'enerver, mais il se souvient de sa formation pédagogique. Comment va-t-il interpréter les résultats et comment va-t-il leur présenter la « bonne » méthode.

  4. Une grammaire peut exprimer un calcul effectif, il suffit de donner un sens comme un entier aux symboles de la grammaire et de décorer les symboles des productions selon les calculs effectués. Par exemple :
    E [i] → int [i]          E [i1 + i2] → E [i1]+ E [i2]
    Un calcul effectif s'apparente alors à une analyse grammaticale (montrer qu'un mot appartient au langage généré par la grammaire). Plus exactement un calcul est l'inverse d'une dérivation.

    Donner deux analyses de 1 + 2 * 3 qui donnent respectivement le résultat d'Oscar et celui de Samir.

    Concevoir deux grammaires qui expriment les méthodes de calcul d'Oscar et de Samir. Ces grammaires seront d'une part équivalentes à la grammaire de départ (elles permettent d'effectuer tous le calculs syntaxiquement valides), et d'autre part non-ambigües (leurs règles n'autorisent qu'un seul résultat possible).

  5. Concevoir la grammaire de l'instituteur dans le même esprit.
Solution.

2  Vérification

Dans tous les programmes qui vont suivre, on considère une production de départ de la forme S → E eof afin de s'assurer que tout le flux d'entrée est bien analysé.

On se donne une définitions des mots (classe Token) et un analyseur lexical fonctionnant selon le principe du flux (classe Lexer). On veut écrire une classe Parser dans le style du lecteur des graphes de la PC précédente.
class Parser {
  private Lexer lexer ;
  Parser (Lexer lexer) {
    this.lexer = lexer ;
    step() ;
  }

  private Token tok ;
  private void step() {
    tok = lexer.read() ;
  }

 // Échoue en affichant « msg attendu, tok trouvé ».
  private void error (String msg, Token tok) { … }

  void ok() { … }
}
  1. Écrire la méthode ok qui échoue qand le flux de lexème donné en entrée n'est pas une expression arithmétique valide. (On utilisera une boucle while).
  2. Remplacer la boucle while du programme par des appels recursifs. Puis associer le programme transformé à l'une des grammaires de la question précédente.
Solution.

3  Retour à l'École polytechnique

La définition de l'ambiguïté à l'aide de calculs arithmétiques manque quand même un peu de généralité. Pour une expression arithmétique donnée, il existe un moyen plus direct de lever l'ambiguïté : mettre des parenthèses.

Nous pouvons décrire l'effet les méthodes de calcul en disant qu'il faut d'abord traduire l'expression donnée en expression « complètement parenthésée », selon une méthode propre à chaque calculateur. Ensuite on peut calculer selon la règle universelle de d'abord effectuer les calculs les plus à l'intérieur. Par exemple, en considérant l'expression 1 * 2 + 3 * 4 on obtient :
Oscar Samir Instituteur
( ( ( 1 * 2 ) + 3 ) * 4 ) ( 1 * ( 2 + ( 3 * 4 ) ) ) ( ( 1 * 2 ) + ( 3 * 4 ) )
Le but de l'exercice est de programmer les traducteurs. On réutilise le modèle de la classe Parser pour écrire cette fois une classe Translate, munie de trois méthodes samir, oscar et instit.
  1. Écrire les deux méthodes auxiliaires suivantes :
     // Lire un entier, échoue si la tête du flux n'est pas un entier
    String readInt() { …}
         // Renvoie l'expression parenthésée « ( i1 tok i2 ) »
    String echo(String i1, Token tok, String i2)
  2. Écrire d'abord la méthode String samir() qui parenthèse selon Samir. La technique est ici très simple, car on peut s'inspirer directement des règles de la grammaire.

  3. Écrire la méthode String oscar(). La technique précédente ne fonctionne pas, mais on peut s'en tirer en lisant le flux comme Samir.

  4. Écrire la méthode String instit().

  5. Comment pourrait-on effectuer les calculs,
Solution.

4  Bonus

  1. Prouver la non-ambiguïté de la grammaire de l'instituteur, en utilisant la notion d'arbre de dérivation du cours.
  2. Modifier la grammaire de l'instituteur pour traiter les moins et plus unaires (productions E → - E et E → + E, et les parenthèses données par l'utilisateur (production E → ( E )).

  3. Les analyseurs que nous avons écrits sont des méthodes mutuellement récursives qui font leur choix au vu d'un seul lexème. Il sont obtenus quasiment mécaniquement à partir des grammaires.

    Trouver une grammaire non-ambigüe pour laquelle cette méthode d'analyse ne fonctionne pas.

    Indication : considérer une grammaire procédant comme Oscar ou comme Samir en fonction d'un symbole se trouvant à la fin du flux.
Solution.

Ce document a été traduit de LATEX par HEVEA et HACHA.