summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-24 13:37:58 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-24 13:38:02 (GMT)
commitb3ef7af199ccebe7bccfe8d18b80022a23e7fcf3 (patch)
tree4c58df085f9c1352105870e152a39ee26e80a149
parent5795955cc6e46ee50f8f3526be2a3b7657e161f0 (diff)
downloadinf105-b3ef7af199ccebe7bccfe8d18b80022a23e7fcf3.zip
inf105-b3ef7af199ccebe7bccfe8d18b80022a23e7fcf3.tar.gz
inf105-b3ef7af199ccebe7bccfe8d18b80022a23e7fcf3.tar.bz2
Briefly discuss "extended" grammar + various small changes (thanks, Antoine).
-rw-r--r--tp2.tex60
1 files 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}
\]