summaryrefslogtreecommitdiffstats
path: root/tp2.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-24 16:10:40 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-24 16:10:40 +0100
commitc0144ee707a03caffae6963c429f17078c6dc89e (patch)
tree227102a94e90e26772d0ac5cc902a79a0db9955c /tp2.tex
parent06043c0f14dc6ddb1be75ff1247834cd23cb64f7 (diff)
parent228342757a709fddffc3c08209b7376680e1b2ba (diff)
downloadinf105-c0144ee707a03caffae6963c429f17078c6dc89e.tar.gz
inf105-c0144ee707a03caffae6963c429f17078c6dc89e.tar.bz2
inf105-c0144ee707a03caffae6963c429f17078c6dc89e.zip
Merge branch 'master' of git.madore.org:teach/inf105
Diffstat (limited to 'tp2.tex')
-rw-r--r--tp2.tex170
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}