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


From ed9dcfac0bd24c21333f25cca9231ce00f42aee8 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 24 Jan 2017 14:46:13 +0100
Subject: Systematically use English names for nonterminals; also replace
 "unary" by "factor".  (Akim's suggestion.)

---
 tp2.tex | 92 ++++++++++++++++++++++++++++++++---------------------------------
 1 file changed, 46 insertions(+), 46 deletions(-)

(limited to 'tp2.tex')

diff --git a/tp2.tex b/tp2.tex
index 7ae17dd..b37af69 100644
--- a/tp2.tex
+++ b/tp2.tex
@@ -169,7 +169,7 @@ 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 \texttt{23.0}).  Pour cela, on peut par exemple introduire un
-nouveau nonterminal $\mathit{terme}$ représentant un terme d'une somme
+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.
 
@@ -185,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
@@ -204,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()
@@ -264,35 +264,35 @@ 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
+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; }
@@ -302,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}
@@ -329,37 +329,37 @@ $\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}
@@ -367,18 +367,18 @@ double puissance():
 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\\
-- 
cgit v1.2.3


From 9dc8b13f469d4e945a49384c1273a98dc3fbf28a Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 24 Jan 2017 14:48:29 +0100
Subject: Unary minus must work before parentheses.

---
 tp2.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'tp2.tex')

diff --git a/tp2.tex b/tp2.tex
index b37af69..4137561 100644
--- a/tp2.tex
+++ b/tp2.tex
@@ -260,7 +260,7 @@ 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 \texttt{18.0}, et \texttt{-1-2} doit
-renvoyer \texttt{-3.0}.  Vérifier que le moins unaire marche aussi
+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
-- 
cgit v1.2.3


From bcc113e0355f17834cbc3e14d6ae9781347fa8e1 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 24 Jan 2017 15:02:10 +0100
Subject: Additional explanations, including one on why implementing optional
 power uses the '?' metacharacter.

---
 tp2.tex | 28 ++++++++++++++++++++++++----
 1 file changed, 24 insertions(+), 4 deletions(-)

(limited to 'tp2.tex')

diff --git a/tp2.tex b/tp2.tex
index 4137561..31b0b12 100644
--- a/tp2.tex
+++ b/tp2.tex
@@ -145,9 +145,9 @@ Initialement, la grammaire de la calculatrice définie dans
 \]
 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
+« ${*}$ », « ${+}$ » 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
@@ -318,12 +318,17 @@ 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 \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}$.
 
@@ -364,6 +369,21 @@ double power():
 }
 \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}
@@ -389,7 +409,7 @@ Voici la grammaire finale :
 \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}
 
-- 
cgit v1.2.3

