WikiMath

On souhaite créer un programme qui reconnaît le langage suivant : « Les expressions correctes sont constituées d'un nombre quelconque, mais non nul, de 0, suivi d'un nombre quelconque, mais non nul, de 1. »

Principes généraux

On suivra cette démarche :

1. Commencer par écrire la grammaire du langage (des expressions correctes).
2. Écrire l'analyseur syntaxique pur.
3. Passer à l'analyseur syntaxique avec messages d'erreur.
4. Puis à l'analyseur syntaxique avec interprétation sémantique.

La grammaire du langage

La grammaire

Voici la grammaire du langage à reconnaître :

  <expression> ::= <groupe0> <groupe1>
  <groupe0>    ::= «0» <suite0>
  <suite0>     ::= <groupe0>
               ::=
  <groupe1>    ::= «1» <suite1>
  <suite1>     ::= <groupe1>
               ::=

Pour la rédiger, on a suivi les règles suivantes :

• Subdiviser au maximum les expressions en sous-expressions cohérentes, en n'hésitant pas à multiplier les niveaux.
• Retarder au maximum les alternatives (en multipliant les niveaux) pour ne les faire intervenir que lorsqu'on ne peut plus faire autrement.

Travaux pratiques

1. Faire tourner la grammaire à la main, sur des exemples qui marchent et sur des exemples qui ne marchent pas.
2. Comment l'adapter pour remplacer « Un nombre quelconque, mais non nul, de 0», par « Exactement un 0 » ?
3. Comment l'adapter avoir non plus « Un nombre quelconque, mais non nul, de 1», mais « Un nombre quelconque, éventuellement nul, de 1 » ?

Analyseur syntaxique pur

La partie analyseur

Voici le code de l'analyseur pur : il répond par « bon » ou « mauvais », c'est-à-dire 1 ou 0.

  #include <stdio.h>

  char s[512];
  char *ss;

  int expression(){
      if (groupe0()==1)
          return groupe1();
      return 0;
  }

  int groupe0(){
      if (*ss == '0'){
          ss++;
          return suite0();
          }
      return 0;
  }

  int suite0(){
      if (groupe0() == 0)
          return 1;
      return 1;
  }

Il faut constater le lien très fort entre ce code et la grammaire ci-dessus. On n'a à réfléchir qu'au moment de la rédaction de la grammaire, le code est alors une conséquence directe de cette dernière. A un point tel qu'on verra qu'il est possible de générer automatiquement le code à partir de la grammaire, à l'aide d'outils prévus à cet effet.

Notons qu'une fonction prévue pour analyser une sous-expression ne connaît pas ce qui précède, et ne s'occupe pas de ce qui suit.

Le main

Passons au programme principal :

  int main(){
    printf("Une expression à analyser ? \n");
    scanf("%s",s);
    ss = s;
    if (expression()==1)
          if (*ss == '\0')
              printf("Bon \n");
          else
              printf("Mauvais\n");
    else
        printf("Mauvais\n");
  }

Remarque : Toujours commencer par l'analyseur syntaxique pur.

Travaux pratiques

1. On n'a fait ci-dessus que groupe0() et suite0(). Faire la même chose pour groupe1() et suite1().
2. Faire tourner le programme.

Analyseur syntaxique avec messages d'erreur

On souhaite dorénavant que les retours de notre analyseur soient plus parlant. On va donc renvoyer du texte, des messages d'erreurs...

  int groupe0(){
      if (*ss == '0'){
          ss++;
          return suite0();
      }
      printf("L'expression doit commencer par 0\n");
      return 0;
  }

  int suite0(){
      if (*ss == '0'){
          ss++;
          return suite0();
      }
      return 1;
  }

Le programme principal devient alors :

  int main(){
    printf("Une expression à analyser ? \n");
    scanf("%s",s);
    ss = s;
    if (expression()==1)
        if (*ss == '\0')
            printf("Bon \n");
        else if (*ss == '0')
            printf("Pas de 0 apres le(s) un(s).\n");
        else
            printf("Caractère interdit : %c\n",*ss);
    }

Analyseur syntaxique avec interprétation sémantique

  int groupe0(){
      if (*ss == '0'){
          ss++;
          return 1+suite0();
      }
      printf("L'expression doit commencer par 0\n")
      return 0;
  }

  int suite0(){
      if (*ss == '0'){
          ss++;
          return 1+suite0();
      }
      return 0;
  }

Le programme principal devient alors :

  int main(){
    printf("Une expression a analyser ? \n");
    scanf("%s»,s);
    ss = s;
    Expression = expression()

    if (*ss == '\0')
        printf("Bon \n");
    else if (*ss == '0')
        printf("Nombre de 0 : d",expression.zero, expression.un);
    else
        printf("Caractère interdit : %c\n",*ss);
  }

où la structure Expression et la fonction expression() sont ainsi définis :

  struct Expression{
      int zero;
      int un;
  }

  struct Expression expression(){
      struct Expression a;
      a.zero = groupe0();
      if (a.zero !=0)
          a.un = groupe1();
      return a;  
  }

Cet exemple, et d'autres, seront (re)vus en TP.

Travaux pratiques

1. Faire pareil pour groupe1() et suite1().
2. Faire marcher le programme principal.