diff options
Diffstat (limited to 'tp2.tex')
| -rw-r--r-- | tp2.tex | 170 |
1 files changed, 101 insertions, 69 deletions
@@ -138,11 +138,23 @@ Initialement, la grammaire de la calculatrice définie dans ){*}\\ \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]*)?\\ +[\ldquote\texttt{0}\rdquote\endash\ldquote\texttt{9}\rdquote]{+} \; +(\ldquote\texttt{.}\rdquote \; +[\ldquote\texttt{0}\rdquote\endash\ldquote\texttt{9}\rdquote]*)?\\ \end{aligned} \] +Il s'agit d'une grammaire « étendue » au sens où le membre de droite +des règles de production autorise l'utilisation des métacaractères +« ${*}$ », « ${+}$ » et « ${?}$ » des expressions rationnelles — pour +désigner respectivement un nombre quelconque de répétitions, au moins +une répétition, ou un groupe facultatif. En principe, on pourrait +éliminer l'utilisation de ces métacaractères en s'inspirant de la +manière dont on démontre que tout langage rationnel est algébrique +(par exemple $X\rightarrow Y{*}$ peut être remplacé par $X\rightarrow +\varepsilon\,|\,YX$), mais l'analyseur LL de JavaCC ne sera pas +forcément capable de gérer la grammaire ainsi transformée, donc il est +préférable d'utiliser les métacaractères lorsque c'est possible. + 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 @@ -154,11 +166,11 @@ elle est rencontrée. la calculatrice ? Pourquoi ? Modifier la grammaire pour avoir une priorité correcte des opérations -(\texttt{*} et \texttt{/} doivent être prioritaires sur -\texttt{+} et \texttt{-}, et en particulier \texttt{3+4*5} doit -renvoyer $23$). Pour cela, on peut par exemple introduire un nouveau -nonterminal $\mathit{terme}$ représentant un terme d'une somme ou -différence, et qui est lui-même formé de produits ou quotients. +(\texttt{*} et \texttt{/} doivent être prioritaires sur \texttt{+} et +\texttt{-}, et en particulier \texttt{3+4*5} doit +renvoyer \texttt{23.0}). Pour cela, on peut par exemple introduire un +nouveau nonterminal $\mathit{term}$ 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} @@ -173,17 +185,17 @@ 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} \; +\mathit{expression} & \rightarrow \mathit{term} \; +( \ldquote\hbox{\texttt{+}}\rdquote \mathit{term} +\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{term}){*}\\ +\mathit{term} & \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+4*5} à comporter deux $\mathit{term}$, 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 @@ -192,14 +204,14 @@ grammaire en question : double expression(): { double a,b; } { - a=terme() + a=term() ( - "+" b=terme() { a += b; } - | "-" b=terme() { a -= b; } + "+" b=term() { a += b; } + | "-" b=term() { a -= b; } )* { return a; } } -double terme(): +double term(): { double a,b; } { a=element() @@ -217,7 +229,7 @@ quand on lui demande de calculer \texttt{3+4*5}. (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 +renvoyer \texttt{2.0}. Pour cela, on pourra ajouter une nouvelle production pour $\mathit{element}$ correspondant à une $\mathit{expression}$ entourée de parenthèses. @@ -247,40 +259,40 @@ contente d'ajouter une deuxième production). (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 -renvoyer $-3$. Vérifier que le moins unaire marche aussi devant les -parenthèses (\texttt{-(2+3)} doit renvoyer $-5$). On pourra aussi -ajouter le $+$ unaire (qui ne change pas le nombre). Pour cela, on -pourra introduire un nouveau nonterminal $\mathit{unaire}$ -représentant un élément éventuellement précédé d'un $-$ (ou d'un $+$) -unaire. +\texttt{-3*-6} doit renvoyer \texttt{18.0}, et \texttt{-1-2} doit +renvoyer \texttt{-3.0}. On veut que le moins unaire marche aussi +devant les parenthèses : par exemple, \texttt{-(2+3)} doit +renvoyer \texttt{-5.0}. On pourra aussi ajouter le $+$ unaire (qui ne +change pas le nombre). Pour cela, on pourra introduire un nouveau +nonterminal $\mathit{factor}$ 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{term} & \rightarrow \mathit{factor} \; +(\ldquote\hbox{\texttt{*}}\rdquote \mathit{factor} +\,|\, \ldquote\hbox{\texttt{/}}\rdquote \mathit{factor} ){*}\\ -\mathit{unaire} & \rightarrow \mathit{element} \; +\mathit{factor} & \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 term(): { double a,b; } { - a=unaire() + a=factor() ( - "*" b=unaire() { a *= b; } - | "/" b=unaire() { a /= b; } + "*" b=factor() { a *= b; } + | "/" b=factor() { a /= b; } )* { return a; } } -double unaire(): +double factor(): { double a; } { a=element() { return a; } @@ -290,7 +302,7 @@ double unaire(): \end{verbatim} (Plusieurs variations sont possibles : par exemple, si on fait suivre -le \texttt{-} unaire d'un $\mathit{unaire}$ au lieu d'un +le \texttt{-} unaire d'un $\mathit{factor}$ au lieu d'un $\mathit{element}$, cela permet d'autoriser \texttt{-{}-3} comme façon d'écrire \texttt{+3}.) \end{corrige} @@ -306,78 +318,98 @@ veut qu'elle soit associative \emph{à droite}, c'est-à-dire par exemple que \texttt{2\char"5E\relax 3\char"5E\relax 2} doit calculer $2^{3^2} = 2^9 = 512$. +On pourra pour cela introduire un nouveau nonterminal $\mathit{power}$ +représentant un $\mathit{element}$ suivi facultativement d'un +\texttt{\char"5E} et d'un nouveau $\mathit{power}$. + La méthode Java permettant de calculer $a^b$ s'écrit \texttt{Math.pow(a,b)}. Tester notamment les calculs suivants : $\hbox{\texttt{2\char"5E\relax - 3\char"5E\relax 2}} \rightsquigarrow 512$ ; -$\hbox{\texttt{-1\char"5E\relax 2}} \rightsquigarrow -1$ ; -$\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$. + 3\char"5E\relax 2}} \rightsquigarrow \texttt{512.0}$ ; +$\hbox{\texttt{-1\char"5E\relax 2}} \rightsquigarrow \texttt{-1.0}$ ; +$\hbox{\texttt{(-1)\char"5E\relax 2}} \rightsquigarrow \texttt{1.0}$ ; +$\hbox{\texttt{(2+3)\char"5E\relax 2}} \rightsquigarrow \texttt{25.0}$ ; +$\hbox{\texttt{2\char"5E\relax -1}} \rightsquigarrow \texttt{0.5}$ ; +$\hbox{\texttt{2*3\char"5E\relax 2*3}} \rightsquigarrow \texttt{54.0}$. \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 +nonterminal $\mathit{power}$ pour lequel on va définir une +production faisant qu'une $\mathit{power}$ peut s'analyser comme un $\mathit{element}$ suivi d'un ``$\texttt{\char"5E}$'' suivi -facultativement d'une nouvelle $\mathit{puissance}$, c'est-à-dire +facultativement d'une nouvelle $\mathit{power}$, 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} +\mathit{factor} & \rightarrow \mathit{power} \; +\,|\, \ldquote\hbox{\texttt{+}}\rdquote \mathit{power} +\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{power}\\ +\mathit{power} & \rightarrow \mathit{element} +( \ldquote\hbox{\texttt{\char"5E}}\rdquote \mathit{factor} ){?}\\ \end{aligned} \] avec le code JavaCC suivant : \begin{verbatim} -double unaire(): +double factor(): { double a; } { - a=puissance() { return a; } -| "+" a=puissance() { return a; } -| "-" a=puissance() { return -a; } + a=power() { return a; } +| "+" a=power() { return a; } +| "-" a=power() { return -a; } } -double puissance(): +double power(): { double a,b; } { a=element() ( - "^" b=unaire() { a = Math.pow(a,b); } + "^" b=factor() { a = Math.pow(a,b); } )? { return a; } } \end{verbatim} +Remarquez l'utilisation du métacaractère « $?$ » pour marquer le +caractère facultatif de la partie +$\ldquote\hbox{\texttt{\char"5E}}\rdquote \mathit{factor}$ ; on aurait +pu tenter d'écrire la règle sous la forme $\mathit{power} \rightarrow +\mathit{element} \;|\; \mathit{element} +\ldquote\hbox{\texttt{\char"5E}}\rdquote \mathit{factor}$ pour un code +JavaCC qui ressemblerait à « \texttt{\{ a=element() \{ return a; \} + |\penalty-100\hskip.5emplus1em a=element() "\char"5E" b=factor() + \{ return Math.pow(a,b); \} \}} », mais ce code fait échouer +JavaCC car au moment où il reconnaît le nonterminal +$\mathit{element}$, l'analyseur ne peut pas encore savoir dans quelle +branche de l'alternative il sera. + +\smallbreak + 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{expression} & \rightarrow \mathit{term} \; +( \ldquote\hbox{\texttt{+}}\rdquote \mathit{term} +\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{term}){*}\\ +\mathit{term} & \rightarrow \mathit{factor} \; +(\ldquote\hbox{\texttt{*}}\rdquote \mathit{factor} +\,|\, \ldquote\hbox{\texttt{/}}\rdquote \mathit{factor} ){*}\\ -\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{factor} & \rightarrow \mathit{power} \; +\,|\, \ldquote\hbox{\texttt{+}}\rdquote \mathit{power} +\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{power}\\ +\mathit{power} & \rightarrow \mathit{element} +( \ldquote\hbox{\texttt{\char"5E}}\rdquote \mathit{factor} ){?}\\ \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]*)?\\ +[\ldquote\texttt{0}\rdquote\endash\ldquote\texttt{9}\rdquote]{+} \; +(\ldquote\texttt{.}\rdquote \; +[\ldquote\texttt{0}\rdquote\endash\ldquote\texttt{9}\rdquote]*)?\\ \end{aligned} \] -Le code JavaCC correspondant peut se trouve à l'adresse +Le code JavaCC correspondant peut se trouver à l'adresse \url{http://perso.enst.fr/~madore/inf105/Calculatrice-final.jj} \end{corrige} |