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.

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}