IFT313 - Introduction aux langages formels

Département d'informatique
Université de Sherbrooke

Été 2014
Devoir 3 - à remettre le mardi 10 juin 2014

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

1. Tâches

Étant donné la grammaire G = {{S, B, D, E, F}, {u, v, w, x, y, z}, P,S), telle que
P = {    S → uBDz
            B → Bv | w
            D → EF
            E → y | ε
            F → x | ε }
  1. Calculer nullable, FIRST et Follow pour la grammaire.
  2. Donner la table d’analyse LL(1).
  3. La grammaire est-elle LL(1) ? Justifiez.
  4. Si la réponse à la question précédente est que la grammaire est non LL(1) :
    1. Donnez une grammaire équivalente qui est LL(1), et qui est la plus proche possible de la grammaire précédente (avec le moins de modifications possibles aux règles de productions et symboles)
    2. Donnez la table d’analyse LL(1) pour la nouvelle grammaire.

2. Fichiers à remettre et autres directives

Vous devez remettre un seul fichier contenant vos réponses avec la commande turnin suivante sous Unix:
turnin -c ift313 -p tp3 devoir3.pdf

L'entête du fichier doit clairement indiquer votre prénom, nom, et maticule.

Votre soumission doit être claire et lisible. Vous devez suivre les conventions du cours pour spécifier les tables nullable, FIRST et Follow, ainsi que les tables d’analyse. Les symboles indexant ces tables doivent être dans l’ordre lexicographique pour faciliter la correction. Seuls les éléments demandés doivent être soumis. On ne veut pas les traces du raisonnement menant à la solution.

Ce travail est individuel.

Vous devez soumettre votre travail au plus tard le mardi 10 juin 2014 à 23 h 59.

Pour toute question, contactez francis.bisson@usherbrooke.ca

3. Évaluation

Ce projet compte pour 5% de la note finale.