IFT313 - Introduction aux langages formels

Département d'informatique
Université de Sherbrooke

Été 2014
Travail pratique 5 - Grammaires LR(0), SLR, LR(1) et LALR(1)
à remettre mardi 22 juillet 2014 à 23 h 59

Enseignant  : froduald.kabanza@usherbrooke.ca
 Correcteur : francis.bisson@usherbrooke.ca (personne contact pour les questions)

Question


Étant donnée la grammaire G = ( {S, B, C}, {a, b, c}, P, S) P contient les productions suivantes:

S → a S b
S → c b
S → B
B → C
C → c

a) (1 point) Donnez l'AFD LR(0) de la grammaire.
b) (0.5 point) Est-ce que la grammaire est LR(0)? Justifiez clairement sans référer à la table.
c) (0.5 point) Est-ce que la grammaire est SLR(1)? Justifiez clairement votre réponse.
d) (1 point) Donnez l'AFD LR(1).
e) (0.5 pointt) Donnez la table d'analyse LR(1)
f)  (0.5 point) Est-ce que la grammaire est LR(1)? Justifiez clairement.
g) (0.5 point) Donnez la table d'analyse LALR(1).
h) (0.5 point) Est-ce que la grammaire est LALR(1)? Justifiez clairement

2. Remise

Ce travail est individuel. Il compte pour 5% de la note finale.

Vous devez soumettre un seul fichier au format PDF, nommé tp5.pdf, à l'aide de la commande turnin suivante sous Unix:

turnin -c ift313 -p tp5 tp5.pdf

Inscrivez vos noms, matricules et adresses courriel dans l'entête.

Vous devez soumettre votre travail au plus tard le mardi 22 juillet 2014 à 23 h 59. Prévoyez le soumettre en avance en cas de problèmes techniques.