summaryrefslogtreecommitdiffstats
path: root/exercices2.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-12 23:02:04 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-12 23:02:04 (GMT)
commit865a7f441a8a4e401910a5b5a26b87d0148fe819 (patch)
tree5350f9783fc4a38a039b3630a9a97d16144d9316 /exercices2.tex
parent8133bc2845d446d850a28eba6df8098a1da4e921 (diff)
downloadinf105-865a7f441a8a4e401910a5b5a26b87d0148fe819.zip
inf105-865a7f441a8a4e401910a5b5a26b87d0148fe819.tar.gz
inf105-865a7f441a8a4e401910a5b5a26b87d0148fe819.tar.bz2
Explain how to work around the dangling else problem at the programmer and at the grammar levels.
This is probably very unclear. Needs to be improved.
Diffstat (limited to 'exercices2.tex')
-rw-r--r--exercices2.tex80
1 files changed, 76 insertions, 4 deletions
diff --git a/exercices2.tex b/exercices2.tex
index aac8a19..bfcb023 100644
--- a/exercices2.tex
+++ b/exercices2.tex
@@ -99,10 +99,10 @@ de programmation hypothétique :
\[
\begin{aligned}
\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\
-|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InsList}\ \mathtt{end}\\
-\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
-|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\ \mathtt{else}\ \mathit{Instruction}\\
-\mathit{InsList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InsList}\\
+|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
+\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\ \mathtt{else}\ \mathit{Instruction}\\
+|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
+\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
\end{aligned}
\]
@@ -120,6 +120,24 @@ expliquer brièvement pourquoi il n'y en a qu'un.
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$.
Que peut-on dire de la grammaire présentée ?
+(3) En supposant que, dans ce langage,
+$\mathtt{begin}\penalty0\ I\penalty0\ \penalty0\mathtt{end}$ (où $I$
+est une instruction) a le même effet que $I$ seul, comment un
+programmeur peut-il réécrire l'instruction considérée en (2) pour
+obtenir un comportant équivalent à l'une ou l'autre des deux
+interprétations ?
+
+(4) Modifier légèrement la grammaire proposée, en remplaçant le
+nonterminal $\mathit{Conditional}$ par deux nonterminaux
+$\mathit{FullCond}$ et $\mathit{ShortCond}$ (respectivement pour le
+cas avec et sans clause $\mathtt{else}$) de manière à obtenir une
+grammaire faiblement équivalente dans laquelle seul l'un des arbres
+d'analyse obtenus en (2) est possible (i.e., une grammaire qui force
+cette interprétation-là par défaut) ; on pourra être amené à
+introduire aussi une nouvelle variante de $\mathit{Instruction}$ qui
+interdit l'une ou l'autre production de conditionnelle. Procéder de
+même pour l'autre interprétation.
+
\begin{corrige}
(1) L'arbre d'analyse de
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$
@@ -281,6 +299,60 @@ $\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ ...$ :
%%% end ex2p1b %%%
\end{center}
La grammaire présentée est donc ambiguë.
+
+\vskip .5explus.1fil
+
+(3) Pour forcer la première interprétation (le
+$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au
+$\mathtt{if}\penalty0\ \mathtt{trippy}$), on peut écrire :
+$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{end}$.
+
+Pour forcer la seconde interprétation (le
+$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au
+$\mathtt{if}\penalty0\ \mathtt{happy}$), on peut écrire :
+$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{end}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$.
+
+\vskip .5explus.1fil
+
+(4) Pour forcer la première interprétation (le $\mathtt{else}$ se
+rapporte au $\mathtt{if}$ le plus proche possible), on peut modifier
+la grammaire comme suit :
+\[
+\begin{aligned}
+\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{FullCond} \;|\; \mathit{ShortCond}\\
+|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
+\mathit{InstrNoSC} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{FullCond}\\
+|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
+\mathit{FullCond} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{Instruction}\\
+\mathit{ShortCond} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
+\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
+\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
+\end{aligned}
+\]
+L'idée est d'obliger une instruction conditionnelle qui apparaîtrait
+après le $\mathtt{then}$ d'une conditionnelle complète à être
+elle-même complète (elle ne peut pas être courte, car alors le
+$\mathtt{else}$ devrait se rattacher à elle).
+
+Pour forcer l'autre interprétation (le $\mathtt{else}$ se rapporte au
+$\mathtt{if}$ le plus lointain possible), on peut modifier la
+grammaire comme suit :
+\[
+\begin{aligned}
+\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{FullCond} \;|\; \mathit{ShortCond}\\
+|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
+\mathit{InstrNoFC} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{ShortCond}\\
+|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
+\mathit{FullCond} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\ \mathtt{else}\ \mathit{Instruction}\\
+\mathit{ShortCond} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoFC}\\
+\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
+\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
+\end{aligned}
+\]
+L'idée est d'obliger une instruction conditionnelle qui apparaîtrait
+après le $\mathtt{then}$ d'une conditionnelle courte à être elle-même
+courte (elle ne peut pas être complète, car alors le $\mathtt{else}$
+devrait se rattacher à la conditionnelle extérieure).
\end{corrige}