Proposed answers to handout on JavaCC.

1 files changed, 209 insertions, 14 deletions

diff --git a/tp2.tex b/tp2.tex
index 8fb0917..6c820eb 100644
--- a/tp2.tex
+++ b/tp2.tex
@@ -98,20 +98,21 @@ de description du langage (sous forme de productions dans une syntaxe
 évoquant les expressions régulières) et de code Java à exécuter
 lorsque ces différentes productions sont rencontrées.  Le programme
 \texttt{javacc} convertit ce fichier \texttt{.jj} en un fichier
-\texttt{.java} qui contient le code de l'analyseur (on peut ensuite
+\texttt{.java} qui contient le code de l'analyseur ; on peut ensuite
 compiler ce fichier avec \texttt{javac} comme n'importe quel code
-Java).
+Java (puis l'exécuter avec \texttt{java}).
 
 La documentation de JavaCC est accessible en ligne sur
 \url{http://javacc.java.net/doc/docindex.html} mais il est
-probablement plus simple d'apprendre par imitation.
+probablement plus simple d'apprendre par imitation à partir du fichier
+proposé.
 
 Sur \url{http://perso.enst.fr/~madore/inf105/Calculatrice.jj} (à
-télécharger, ou à recopier depuis
+télécharger, ou à recopier directement depuis
 \texttt{\char`\~madore/Calculatrice.jj} dans les salles de TP) on
 trouvera le code d'une calculatrice très simple écrit en JavaCC.  On
-peut compiler et lancer ce code (après l'avoir recopié) en lançant
-successivement :
+peut compiler et lancer ce code (après l'avoir recopié chez soi) en
+lançant successivement :
 
 \noindent
 \indent\texttt{\char`\~madore/bin/javacc Calculatrice.jj}\\
@@ -123,23 +124,31 @@ On peut alors taper des expressions arithmétiques telles que
 Enter, et terminer le programme en tapant Control-D).  Vérifier que
 cela fonctionne correctement.
 
-Initialement, la grammaire de la calculatrice dans
-$\texttt{Calculatrice.jj}$ est donnée par :
+\bigbreak
+
+Initialement, la grammaire de la calculatrice définie dans
+\texttt{Calculatrice.jj} est donnée par :
 \[
-\begin{array}{rcl}
-\mathit{expression} & \rightarrow & \mathit{element} \;
+\begin{aligned}
+\mathit{expression} & \rightarrow \mathit{element} \;
 ( \ldquote\hbox{\texttt{+}}\rdquote \mathit{element}
 \,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{element}
 \,|\, \ldquote\hbox{\texttt{*}}\rdquote \mathit{element}
 \,|\, \ldquote\hbox{\texttt{/}}\rdquote \mathit{element}
 ){*}\\
-\mathit{element} & \rightarrow & \mathit{Number}\\
-\mathit{Number} & \rightarrow &
+\mathit{element} & \rightarrow \mathit{Number}\\
+\mathit{Number} & \rightarrow
 [\ldquote\mathtt{0}\rdquote\endash\ldquote\mathtt{9}\rdquote]{+} \;
 (\ldquote\mathtt{.}\rdquote \;
-[\ldquote\mathtt{0}\rdquote\endash\ldquote\mathtt{9}\rdquote]*)?
-\end{array}
+[\ldquote\mathtt{0}\rdquote\endash\ldquote\mathtt{9}\rdquote]*)?\\
+\end{aligned}
 \]
+Le code important se situe dans \texttt{Calculatrice.jj} au niveau de
+la ligne \texttt{double expression():} ; le bloc qui suit définit la
+production $\mathit{expression}$ ainsi que le code à exécuter quand
+elle est rencontrée.
+
+\bigbreak
 
 (1) Que se passe-t-il quand on demande de calculer \texttt{3+4*5} à
 la calculatrice ?  Pourquoi ?
@@ -152,12 +161,90 @@ nonterminal $\mathit{terme}$ représentant un terme d'une somme ou
 différence, et qui est lui-même formé de produits ou quotients.
 Tester la calculatrice ainsi modifiée.
 
+\begin{corrige}
+La calculatrice renvoie \texttt{35.0} quand on lui demande de calculer
+\texttt{3+4*5}, c'est-à-dire qu'elle analyse ce mot comme
+\texttt{(3+4)*5}.  La raison en est que la production
+$\mathit{expression}$ produit un arbre d'analyse « plat », et le code
+est alors exécuté séquentiellement (on part de \texttt{a=3}, on
+exécute ensuite \texttt{a+=4} et enfin \texttt{a*=5}).
+
+Pour corriger ce problème, on va modifier la grammaire de la manière
+suivante :
+\[
+\begin{aligned}
+\mathit{expression} & \rightarrow \mathit{terme} \;
+( \ldquote\hbox{\texttt{+}}\rdquote \mathit{terme}
+\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{terme}){*}\\
+\mathit{terme} & \rightarrow \mathit{element} \;
+(\ldquote\hbox{\texttt{*}}\rdquote \mathit{element}
+\,|\, \ldquote\hbox{\texttt{/}}\rdquote \mathit{element}
+){*}\\
+\end{aligned}
+\]
+(le reste est inchangé) : ceci forcera l'arbre d'analyse de
+\texttt{3+4*5} à comporter deux $\mathit{terme}$, en l'occurrence
+\texttt{3} et \texttt{4*5}, qui s'évalueront dans les bonnes valeurs.
+
+Voici à quoi peut ressembler le code JavaCC modifié pour refléter la
+grammaire en question :
+\begin{verbatim}
+double expression():
+{ double a,b; }
+{
+    a=terme()
+    (
+      "+" b=terme() { a += b; }
+    | "-" b=terme() { a -= b; }
+    )* { return a; }
+}
+
+double terme():
+{ double a,b; }
+{
+    a=element()
+    (
+      "*" b=element() { a *= b; }
+    | "/" b=element() { a /= b; }
+    )* { return a; }
+}
+\end{verbatim}
+On vérifie bien que la nouvelle calculatrice renvoie \texttt{23.0}
+quand on lui demande de calculer \texttt{3+4*5}.
+\end{corrige}
+
+\medbreak
+
 (2) La calculatrice ne gère pas les parenthèses : ajouter cette
 fonctionnalité et tester.  Par exemple, \texttt{(3+5)/(2*2)} doit
 revoyer $2$.  Pour cela, on pourra ajouter une nouvelle production
 pour $\mathit{element}$ correspondant à une $\mathit{expression}$
 entourée de parenthèses.
 
+\begin{corrige}
+On va maintenant modifier la production pour $\mathit{element}$ et en
+ajouter une nouvelle, à savoir :
+\[
+\mathit{element} \rightarrow \mathit{Number}
+\,|\, \ldquote\hbox{\texttt{(}}\rdquote \mathit{expression} \ldquote\hbox{\texttt{)}}\rdquote
+\]
+
+Le code JavaCC pour cette production peut ressembler à ceci :
+\begin{verbatim}
+double element():
+{ Token t; double a; }
+{
+    t=<NUMBER> { return Double.parseDouble(t.toString()); }
+|   "(" a=expression() ")" { return a; }
+}
+\end{verbatim}
+(ici, \texttt{Token} est un type interne à JavaCC utilisé pour les
+productions du lexer ; on ne touche pas à la première partie, on se
+contente d'ajouter une deuxième production).
+\end{corrige}
+
+\medbreak
+
 (3) La calculatrice ne gère pas le $-$ unaire (pour indiquer l'opposé
 d'un nombre) : ajouter cette fonctionnalité et tester.  Par exemple,
 \texttt{-3*-6} doit renvoyer $18$, et \texttt{-1-2} doit
@@ -168,6 +255,48 @@ pourra introduire un nouveau nonterminal $\mathit{unaire}$
 représentant un élément éventuellement précédé d'un $-$ (ou d'un $+$)
 unaire.
 
+\begin{corrige}
+On modifie la grammaire comme suit :
+\[
+\begin{aligned}
+\mathit{terme} & \rightarrow \mathit{unaire} \;
+(\ldquote\hbox{\texttt{*}}\rdquote \mathit{unaire}
+\,|\, \ldquote\hbox{\texttt{/}}\rdquote \mathit{unaire}
+){*}\\
+\mathit{unaire} & \rightarrow \mathit{element} \;
+\,|\, \ldquote\hbox{\texttt{+}}\rdquote \mathit{element}
+\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{element}\\
+\end{aligned}
+\]
+et le code JavaCC correspondant pourrait être :
+\begin{verbatim}
+double terme():
+{ double a,b; }
+{
+    a=unaire()
+    (
+      "*" b=unaire() { a *= b; }
+    | "/" b=unaire() { a /= b; }
+    )* { return a; }
+}
+
+double unaire():
+{ double a; }
+{
+    a=element() { return a; }
+|   "+" a=element() { return a; }
+|   "-" a=element() { return -a; }
+}
+\end{verbatim}
+
+(Plusieurs variations sont possibles : par exemple, si on fait suivre
+le \texttt{-} unaire d'un $\mathit{unaire}$ au lieu d'un
+$\mathit{element}$, cela permet d'autoriser \texttt{-{}-3} comme façon
+d'écrire \texttt{+3}.)
+\end{corrige}
+
+\medbreak
+
 (4) La calculatrice ne gère pas l'opération puissance : introduire
 celle-ci sous la notation du caractère ``\texttt{\char"5E}''
 (accent circonflexe) : attention, on veut que l'opération
@@ -186,6 +315,72 @@ $\hbox{\texttt{(-1)\char"5E\relax 2}} \rightsquigarrow 1$ ;
 $\hbox{\texttt{2\char"5E\relax -1}} \rightsquigarrow 0.5$ ;
 $\hbox{\texttt{2*3\char"5E\relax 2*3}} \rightsquigarrow 54$.
 
+\begin{corrige}
+Pour obtenir l'associativité \emph{à droite}, on va définir un
+nonterminal $\mathit{puissance}$ pour lequel on va définir une
+production faisant qu'une $\mathit{puissance}$ peut s'analyser comme
+un $\mathit{element}$ suivi d'un ``$\texttt{\char"5E}$'' suivi
+facultativement d'une nouvelle $\mathit{puissance}$, c'est-à-dire
+qu'on modifie la grammaire ainsi :
+\[
+\begin{aligned}
+\mathit{unaire} & \rightarrow \mathit{puissance} \;
+\,|\, \ldquote\hbox{\texttt{+}}\rdquote \mathit{puissance}
+\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{puissance}\\
+\mathit{puissance} & \rightarrow \mathit{element}
+( \ldquote\hbox{\texttt{\char"5E}}\rdquote \mathit{unaire}
+){?}\\
+\end{aligned}
+\]
+avec le code JavaCC suivant :
+\begin{verbatim}
+double unaire():
+{ double a; }
+{
+    a=puissance() { return a; }
+|   "+" a=puissance() { return a; }
+|   "-" a=puissance() { return -a; }
+}
+
+double puissance():
+{ double a,b; }
+{
+    a=element()
+    (
+      "^" b=unaire() { a = Math.pow(a,b); }
+    )? { return a; }
+}
+\end{verbatim}
+
+Voici la grammaire finale :
+\[
+\begin{aligned}
+\mathit{expression} & \rightarrow \mathit{terme} \;
+( \ldquote\hbox{\texttt{+}}\rdquote \mathit{terme}
+\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{terme}){*}\\
+\mathit{terme} & \rightarrow \mathit{unaire} \;
+(\ldquote\hbox{\texttt{*}}\rdquote \mathit{unaire}
+\,|\, \ldquote\hbox{\texttt{/}}\rdquote \mathit{unaire}
+){*}\\
+\mathit{unaire} & \rightarrow \mathit{puissance} \;
+\,|\, \ldquote\hbox{\texttt{+}}\rdquote \mathit{puissance}
+\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{puissance}\\
+\mathit{puissance} & \rightarrow \mathit{element}
+( \ldquote\hbox{\texttt{\char"5E}}\rdquote \mathit{unaire}
+){?}\\
+\mathit{element} &\rightarrow \mathit{Number}
+\,|\, \ldquote\hbox{\texttt{(}}\rdquote \mathit{expression} \ldquote\hbox{\texttt{)}}\rdquote\\
+\mathit{Number} & \rightarrow
+[\ldquote\mathtt{0}\rdquote\endash\ldquote\mathtt{9}\rdquote]{+} \;
+(\ldquote\mathtt{.}\rdquote \;
+[\ldquote\mathtt{0}\rdquote\endash\ldquote\mathtt{9}\rdquote]*)?\\
+\end{aligned}
+\]
+
+Le code JavaCC correspondant peut se trouve à l'adresse
+\url{http://perso.enst.fr/~madore/inf105/Calculatrice-final.jj}
+\end{corrige}
+
 
 
 %