Merge branch 'master' of git.madore.org:teach/inf105

1 files changed, 101 insertions, 69 deletions

diff --git a/tp2.tex b/tp2.tex
index 6c820eb..31b0b12 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 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}