From b3ef7af199ccebe7bccfe8d18b80022a23e7fcf3 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
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(-)

(limited to 'tp2.tex')

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

