Compilation : série 1

Compilation : série 1

À rendre avant le mercredi 6 novembre 2002, 12h00 dans la boîte située devant le bureau IN/R 318

Exercice 1 (10 points)

Trouver une grammaire non contextuelle (BNF) pour les langages suivants :

Tous les mots sur l'alphabet T = {1, ..., 9} représentant des nombres premiers inférieurs à 20 exprimés en base 10 ; par ex. 2, 3, ... 19.
Tous les mots sur l'alphabet T = {a, b} dont toutes les suites de a sont de longueur paire ; par ex. aa, bbaaaabaabbb, bbb, etc.
Tous les mots sur l'alphabet T = {a, b} qui contiennent un nombre pair de a ; par ex. aa, abbabaa, b, etc.
Tous les mots sur l'alphabet T = {f, g, (, ,, )} représentant des expressions formées exclusivement d'appels de fonctions f et g où les appels à g possèdent un nombre arbitraire d'arguments et les appels à f possèdent excatement un seul argument ; par ex. g(), f(g()), g(g(), f(g())), g(g(), g(), g()), etc.

Si vous utilisez plusieurs non-terminaux, indiquez clairement lequel est le symbol initial.

Exercice 2 (4 points)

Parmi les langages de la question 1, lesquels sont réguliers ? Pour ceux qui le sont, prouvez-le.

Exercice 3 (12 points)

Les grammaires ci-dessous définissent des langages réguliers. Pour chacune d'elle, donnez une seule règle EBNF non récursive définissant le même langage, puis écrivez une fonction Java qui retourne vrai si et seulement si un mot donné appartient à ce langage.

```
A = a | A b c
```
```
A = a | A b c | A A
```

Dans le code des fonctions utilisez la variable ch pour obtenir le caractère courant et la fonction next() pour faire passer ch au caractère suivant. La fin du mot est atteinte lorsque ch vaut EOF.

Exercice 4 (6 points)

Trouvez une grammaire EBNF non récursive qui spécifie la syntaxe des nombres à virgule flottante dont la spécification est la suivante :

Un nombre à virgule flottante est constitué de trois parties: un signe, une mantisse et un exposant. Ces trois parties sont toujours placées dans cet ordre. Le signe et l'exposant sont optionnels.
Un signe est formé d'un seul caractère '+' ou '-'.
La mantisse est une suite non vide de chiffres contenant un caractère '.' (placé au début, au sein ou à la fin de la suite de chiffres)
L'exposant est constitué de trois parties: un caractère 'e', un signe et une suite non vide de chiffres. Ces trois parties sont toujours placées dans cet ordre. Le signe est optionnel.

Voici quelques exemples de nombres à virgule flottante:

    -3.1415927, 1.4e10, 127.0e-2, -0.1e-1, .0