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. 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