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
|
