From 5795955cc6e46ee50f8f3526be2a3b7657e161f0 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 23 Jan 2017 15:14:31 +0100 Subject: Proposed answers to handout on JavaCC. --- tp2.tex | 223 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file 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= { 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} + % -- cgit v1.2.3