From b3ef7af199ccebe7bccfe8d18b80022a23e7fcf3 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 24 Jan 2017 14:37:58 +0100 Subject: Briefly discuss "extended" grammar + various small changes (thanks, Antoine). --- tp2.tex | 60 ++++++++++++++++++++++++++++++++++++------------------------ 1 file changed, 36 insertions(+), 24 deletions(-) diff --git a/tp2.tex b/tp2.tex index 6c820eb..7ae17dd 100644 --- a/tp2.tex +++ b/tp2.tex @@ -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 au plus une répétition. 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{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} @@ -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,13 +259,13 @@ 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}. Vérifier 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{unaire}$ représentant un élément éventuellement +précédé d'un $-$ (ou d'un $+$) unaire. \begin{corrige} On modifie la grammaire comme suit : @@ -309,11 +321,11 @@ exemple que \texttt{2\char"5E\relax 3\char"5E\relax 2} doit calculer $2^{3^2} 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\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 @@ -371,9 +383,9 @@ Voici la grammaire finale : \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} \] -- cgit v1.2.3