Analyse des expressions arithmétiques

L'écriture d'un analyseur doit être abordée de façon systématique si l'on veut pouvoir s'en sortir pour des grammaires plus complexes. Le but de ce td est de vous donner une idée de l'analyse syntaxique en écrivant un analyseur d'expressions arithmétiques très simplifié, mais en utilisant une approche modulaire.

Préalable à l'écriture d'un analyseur syntaxique, il est nécessaire de décrire la grammaire sous une forme symbolique similaire à celle dans laquelle est définie la syntaxe du langage Pascal à la fin du poly. Celle des expressions arithmétiques est la suivante:

        expression  ::=  somme '.'
                        
        somme       ::=  produit {'+' produit} 
                        
        produit     ::=  atome {'*' atome}
                        
        atome       ::=  nombre
                      |  variable
                      |  '(' somme ')'
                        
        nombre      ::=  '0' | ... '9'
        variable    ::=  'a' | ... 'z'

La grammaire se lit de la façon suivante: une expression est une somme suivie du caractère point; une somme est un produit suivi d'une répétition arbitraire du symbole + et d'un produit. Un produit est un atome suivit d'une répétition arbitraire du caractère * et d'un atome. Écrire un analyseur pour cette grammaire c'est d'abord écrire un programme qui reconnaît si une suite de caractères définit une expression bien formée. Pour simplifier, nous supposons que les mots sont des caractères, c'est-à-dire on se contente de:

        typedef char lexeme;

Écrire une fonction qui retourne un lexème en lisant des caractères au clavier (avec la fonction fonction getchar). Les blancs et le retour à la ligne seront ignorés. On refusera également (mais avec un message d'erreur) les caractères qui ne sont pas des mots.
En utilisant un tampon,
```
        typedef lexeme valeur_tampon;
        typedef int etat_tampon;       /* 0 pour vide, 1 pou plein */
```
écrire deux fonctions
```
        lexeme consulte (void);
        lexeme accepte (void);
```
La première consulte le lexème suivant sans s'engager à le prendre (i.e. elle remplit le tampon si nécessaire (en lisant un caractère au clavier), puis retourne le contenu du le tampon.
La seconde vide le tampon et retourne sa valeur.
En particulier, plusieurs appels à consulte qui ne sont pas séparés par un appel à accepte retourneront le même lexème.
Vérifier manuellement que les séquences de caractères ``1.'' et ``(1+2)*4.'' sont reconnus par la grammaire ci-dessus, mais que ``2-3`` ne l'est pas.
On veut représenter l'arbre de l'expression arithmétique lue.
Écrire une définition de type permettant de représenter les expressions arithmétiques par des arbres. Puis une procédure de création pour chaque type de noeud de l'arbre.
Écrire une fonction d'impression des expressions en mettant des parenthèses autour de tous les opérateurs.
En supposant que la fonction lit_somme est donnée, écrire une fonction lit_atome qui reconnaît un atome et retourne sa représentation. Puis écrire une autre fonction lit_produit qui reconnaît un produit et retourne sa représentation. Enfin écrire la procédure lit_somme.
Tester le programme sur les exemples précédents...
Écrire une fonction qui évalue les expressions sans variables.
Modifier, si ce n'est pas fait la lecture des lexèmes lecture pour ignorer les caractères d'espacement, de retour à la ligne et de tabulation.
Réécrire la procédure d'impression en écrivant le minimum de parenthèses.
Modifier la grammaire des expressions en:
```
        expression  ::=  somme '.'
                      |  '?' somme '.'
```
la nouvelle forme évaluant l'expression après l'avoir construite.

Facultatif

On veut maintenant inclure la soustraction. L'opérateur de soustraction a une priorité égale à celle de l'addition. Il suffit donc de modifier la règle somme en:
```
        somme              ::= produit {plus_ou_moins produit} 

        plus_ou_moins      ::= '+' | '-'
```
modifier l'analyseur pour reconnaître la soustraction. (Attention dans la construction de l'arbre de syntaxe abstraite à lire 1-2-3 comme (1-2)-3.):
On peut facilement ajouter des commandes parmi les expressions
```
        expression         ::= '!' var ':' '=' somme '.'
                             | ...
```
La nouvelle forme lie l'expression reconnu à la variable indiquée.
On peut maintenant ajouter des vrais lexèmes composés de nombres, de variables, de symboles. Définir le type des lexèmes. Faire les modifications nécessaires dans le reste du programme.
On pourra aussi dessiner l'arbre de l'expression arithmétique.

Pour mémoire

Sous unix, il existe des programmes lex et yacc qui permettent de générer automatiquement un programme C reconnaissant une grammaire décrite par une définition symbolique (semblable à celle donnée ici).

Solution

Elle est donnée sous forme de plusieurs fichiers.

Les programmes expr.c, analyse.c, eval.c, imprime.c, interface.c.
Leurs interfaces expr.h, analyse.h, eval.h, imprime.h.
Un fichier Makefile, qui permet de compiler l'ensemble en faisant simplement la commande
```
        make 
        ./arithmetique
```
sous le shell.