IFT313 - Introduction aux langages formels

Département d'informatique
Université de Sherbrooke

Été 2014
Travail pratique 4 - Analyse syntaxique avec JavaCC
à remettre le mardi 15 juillet 2014



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

1. Tâches

Le TP #4 consiste à écrire un parseur à l'aide de JavaCC pour charger un graphique Graph313. Graph313 est un pseudolangage pour des graphiques vectoriels dévelopé par Professeur Eric Beaudry (UQAM) pour des fins didactiques.

Vous devez partir des fichiers fournis dans l'archive suivante : tp4-sources.zip. Vous devez modifier uniquement le fichier parser.jcc.

La grammaire d'un graphique Graph313:

<Graphique> ::= <Fonction>* "main" <EnonceBloc>

<Fonction> ::= "define" <ID> "(" <NomsParams> ")" <EnonceBloc>

<NomsParams> ::= (<ID> ( "," <ID>)*)?

<EnonceBloc> ::= "{" <Enonce>* "}"

<Enonce> ::= <Assign>
           | <EnonceAppel>
           | <EnonceIfElse>
           | <EnonceFor>
           | <EnonceReturn>
           | <EnonceWhile>
           | <EnonceBloc>
           | <Commande> ";"

<Assign> ::= <ID> "=" <ExpReel> ";"

<EnonceAppel> ::= "@" <ID>:nomfonction "(" <ExpsParams> ")" ";"

<EnonceIfElse> ::= "if" "(" <ExpBool> ")" <Enonce> ( "else" <Enonce>)?

<EnonceFor> ::= "for" "(" <ID>:var "," <ExpReel>:debut "," <ExpReel>:max "," <ExpReel>:incre ")" <Enonce>

<EnonceReturn> ::= "return" <ExpReel> ";"

<EnonceWhile> ::= "while" "(" <ExpBool> ")" <Enonce>

<ExpReel> ::= <ID>
            | "(" <ExpReel> ")"
            | <Number>
            | "@" <ID>:nomfonction "(" <ExpsParams> ")"
            | <ExpReel> "+" <ExpReel>
            | <ExpReel> "-" <ExpReel>
            | <ExpReel> "*" <ExpReel>
            | <ExpReel> "/" <ExpReel>

<ExpBool> ::= <ExpBool> "||" <ExpBool>
            | <ExpBool> "&&" <ExpBool>
            | "(" <ExpBool> ")"         // Cas difficile. Faites-le en dernier.
            | <ExpReel> "<" <ExpReel>
            | <ExpReel> "<=" <ExpReel>
            | <ExpReel> "==" <ExpReel>
            | <ExpReel> ">=" <ExpReel>
            | <ExpReel> ">" <ExpReel>

<
ExpsParams> ::= (<ExpReel> ( "," <ExpReel>)*)?

<Commande> ::= <CmdLine> | <CmdRect> | <CmdBegin> | <CmdPoints> | <CmdEnd>

<CmdLine> ::= "LINE" <ExpReel>:x1 "," <ExpReel>:y1 "," <ExpReel>:x2 "," <ExpReel>:y2

<CmdRect> ::= "RECT" <ExpReel>:x "," <ExpReel>:y "," <ExpReel>:w "," <ExpReel>:h

<CmdBegin> ::= "BEGIN" ("MODE_LINE" | "MODE_POLY")

<CmdPoints> ::= "POINTS" (<ExpReel>:x1 "," <ExpReel>:y1 ("," <ExpReel>:x "," <ExpReel>:y)*)?

<CmdEnd> ::= "END"

<ID> ::= <Lettre>(<Lettre>|<Chiffre>)*

<Number> ::= <Chiffre>+ ("." <Chiffre>+)



Cette grammaire est écrite en format EBNF (Extended Backus-Naur form). En EBNF, les opérateurs +, *, | et ? ont la même signification que pour les expressions régulières. Pour certaines règles, des attributs ont été spécifiés pour expliquer leur sens sémantique. Les lexèmes (tokens) peuvent être séparés par des espaces (" "), des sauts et des retours de ligne (\n et \r), des tabulations (\t) ou des commentaires du style C (/* ... */).

Commandes Graph313

LINE x1 y1 x2 y2
Trace une ligne du point (x1, y1) au point (x2, y2)

RECT x y w h
Trace un rectangle, dont le coin haut gauche est à (x, y), d'une largeur w et d'une hauteur h.

BEGIN mode
Amorce le mode points. Lorsque la commande BEGIN est appelée, l'interpréteur Graph313 vide un vecteur temporaire dans lequel il stoquera tous les points (x, y) passés en paramètres par des appels de la commande POINTS. Si mode est MODE_LINE, une polyligne sera tracée lorsque la commande END sera appelée, tandis qu'un polygone fermé sera dessiné si mode est MODE_POLY.

POINTS x1, y1 [,x2, y2[ ... [,xn, yn] ] ]
Mets n points dans le vecteur temporaire.
 

END
Termine le mode points. Affiche la polyligne ou le polygone formé par les points spécifiés par la ou les commandes POINTS.

1.1  Traduisez cette grammaire en une spécification JavaCC [4 points]

Modifiez la grammaire selon vos besoins, et ce, sans changer son langage. Vous devez entre autres éliminer la récursivité à gauche et effectuer les factorisations nécessaires. Ensuite, codez la grammaire dans une spécification JavaCC afin de valider la syntaxe d'un graphique Graph313.

Pour tester votre parseur, faites:
javacc parser.jcc
javac -classpath .;Graph313.jar *.java
java
-classpath .;Graph313.jar Parser test1.g313

1.2  Construisez l'arbre syntaxique abstrait (AST) [6 points]

Adaptez votre précédente spécification JavaCC pour construire l'arbre syntaxique abstrait du fichier en entrée. Vous devez construire des noeuds à l'aide des classes fournies dans le package graph313.ast. Vous devrez sans doute adapter votre grammaire pour faciliter la construction de l'AST. Bien que l'évaluation porte principalement sur le résultat final, essayer de garder votre grammaire le plus simple possible.

N'oubliez pas de tenir en compte de la priorité des opérateurs booléens et arithmétiques.

Pour compiler le projet avec votre parseur, faites:

javacc parser.jcc
javac
-classpath .;Graph313.jar *.java

Pour valider la sémantique de votre parseur, comme la priorité des opérateurs, faites:
java -classpath .;Graph313.jar TestSemantique test0.g313

test0.g313:

define f(x, y, z){
   return x+y*z;
}
main{
  a = 1 + 2 * 3;
  b = 1 * 2 + 3;
  if( 1>2 || 2<3 && 3<4)
    c = 1;
  else
    c = 2;

  /* Faites tous les autres tests que vous jugez pertinants */
}
Sortie:

Contexte:
vars={{b=5.0, c=1.0, a=7.0}}


Pour tester les deux exemples ci-bas, faites:
java -classpath .;Graph313.jar MainFrame test1.g313
java -classpath .;Graph313.jar MainFrame test2.g313

Tests

test1.g313

define etoile(cx, cy, r){
   PI=3.141592654;
   BEGIN MODE_LINE;
   for(i,0,6,1){
      a = i*4*PI/5;
      x = @cos(a) * r;
      y = @sin(a) * r;
      POINTS cx+x, cy+y;
   }
   END;
}

main{
  lx = 0;
  ly = 0;
  for(x, 0, 1000, 1){
    y = 50 + @sin(x/10.0) * 20;
    LINE lx,ly,x,y;
    lx = x;
    ly = y;
  }

  /* test */
  BEGIN MODE_LINE;
  for(x, 0, 1000, 1){
    y = 150 + @sin(x/10.0) * 20;
    POINTS x,y;
  }
  END;

  for(x, 0, 100, 2){
    cx = 250 + @cos(x/2)*(x+20);
    cy = 250 + @sin(x/2)*(x+20);
    @etoile(cx, cy, x/10+4);
  }
}

Exemple de rendu

test2.g313

define PolyRegulier(cx, cy, r, n){
   PI=3.141592654;
   BEGIN MODE_LINE;
   for(i,0,n,1){
      a = i*2*PI/n;
      x = @cos(a) * r;
      y = @sin(a) * r;
      POINTS cx+x, cy+y;
   }
   END;
}

main{
  for(i,3,20,1){
    @PolyRegulier(80*i-160, 80, 35, i);
  }
  for(i,3,12,1)
    @PolyRegulier(400,400,10+i*20,i);
}



2. Remise

Vous devez soumettre votre fichier à l'aide de la commande turnin suivante sous Unix:

turnin -c ift313 -p tp4 parser.jcc

Dans votre fichier, vous devez inscrire vos noms, matricules et adresses courriels dans l'entête.

Vous ne devez pas utiliser de packages autres que Graph313, JavaCC et ceux fournis avec Java 1.7 SE.

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

3. Évaluation

Ce projet compte pour 10% de la note finale. L’évaluation sera basée sur le niveau de correction de vos programmes, l’efficacité et la simplicité. Le plus votre code sera simple (succinct) et plus il fonctionnera correctement (par exemple, identifier le plus de tokens valides et le moins de tokens invalides) et rapidement, mieux il sera. De manière générale, vous devez respecter les critères usuels d’un code modulaire et bien écrit selon la pratique courante de la programmation.

Votre travail sera évalué en utilisant des scripts automatiques. Si l’évaluation échoue parce que vous n’avez pas respecté les directives, vous serez pénalisé avec la possibilité d’avoir une note nulle si tous les tests échouent. Il est donc important de ne pas modifier les noms de classe et de package (l'instruction package ne doit pas être présente en haut des fichiers .java et .jcc).