Introduction aux grammaires

L'objectif de ce TD est de se familiariser avec les grammaires algébriques, les arbres de dérivation et la désambiguïsation des grammaires.

Écrire une grammaire G₁ qui reconnaît le langage des palindromes (mots non vides qui peuvent se lire de droite à gauche et de gauche à droite) sur l'alphabet {a,b} ;
Écrire une grammaire non ambiguë G₂ qui reconnaît les mots du langage décrit par l'expression rationnelle a*b* et qui contient plus (strictement) de a que de b ;
Dessiner l'arbre de dérivation pour la grammaire G₂ du mot aaaabb.

Écrire une grammaire qui reconnaît les suites de déclarations de méthodes dans les interfaces Java.

Donner l'abre de dérivation de la suite de déclarations suivantes :

					
	public void m(int i) throws Ex1, Ex2;
	int m(Object o);

Soit la grammaire suivante :

G₃	S ::= E '$'	E ::= EE
	E ::= '(' E ')'	E ::= ε

Donner un arbre de dérivation de (()()) pour cette grammaire.
Cette grammaire est-elle ambiguë ? Expliquer.
Proposer une autre grammaire équivalente qui ne soit pas ambiguë.
Le langage décrit par cette grammaire peut-il être décrit par une expression rationnelle ?

Soit la grammaire suivante :

Soit les petites grammaires suivantes reconnaissant des expressions booléennes partielles :

Gbool1 :	(p0) S := E '$'	(p2) E := E '\|' E
	(p1) E := E '&' E	(p3) E := 'value'

Gbool2 :	(p0) S := E '$'	(p2) E := '!' E
	(p1) E := E '&' E	(p3) E := 'value'

Gbool3 :	(p0) S := E '$'	(p2) E := '!' E
	(p1) E := E '\|' E	(p3) E := 'value'