Exercices 1
Exercice 1
Quel langage décrit la grammaire sur l'alphabet { a, b } avec les règles
suivantes (e signifiant le mot vide)?
S --> E a E
E --> E b | e
Les mots "abb" et "aba" appartiennent-ils au langage?
Justifiez votre réponse.
Exercice 2
Donnez une grammaire sur l'alphabet { a, b } décrivant les
palindromes (mots
qui sont les mêmes lus de gauche à droite ou de droite
à
gauche). Par exemple, "abba" appartient au langage, mais pas "aaba".
Exercice 3
Quelle est l'intersection des langages des exercices 1 et 2? Donnez une
grammaire pour ce langage.
Exercice 4 (Programmation)
L'exercice suivant vous permet de vous rappeler des principes de base de
Java, afin d'expérimenter avec quelques fondements de la compilation
(grammaires, arbres syntaxiques, interprétation, tables de symboles).
Il est conseillé de prendre le temps pour le finir en tout cas, même si vous n'y
parvenez pas pendant les heures de cours. Notez que des connaissances
de base en Java sont indispensables pour le projet.
La grammaire suivante décrit un langage de commandes.
Stm --> Stm ";" Stm | id ":=" Exp | "print" Exp
Exp --> num | id | Exp Bop Exp
Bop --> "+" | "-" | "*" | "/"
Le fichier Ex1.java contient une représentation
incomplète en java de cette grammaire, ainsi qu'un interprète
également à compléter.
- Compilez le programme (javac Ex1.java) et exécutez-le
(java Ex1).
- Ajoutez le code nécessaire à l'interprétation de
"print 15 + 3 + 2002". (Voir aussi dans la méthode main.)
- Complétez le reste du code. Il est conseillé de
travailler exemple par exemple.
Que faudrait-il ajouter au programme pour ne plus devoir définir
les arbres à la main?
Christine Röckl
Last modified: Thu Mar 14 16:08:30 CET 2002