From 4eaff56432b60cf7544f3d35fe41fa004401b20e Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 17 Jan 2017 00:22:27 +0100
Subject: Fix mistaken exercise/solution on the "dangling else" problem.

Still not satisfied with the fix, but at least it should be correct.
---
 exercices2.tex | 49 +++++++++++++++++--------------------------------
 1 file changed, 17 insertions(+), 32 deletions(-)

(limited to 'exercices2.tex')

diff --git a/exercices2.tex b/exercices2.tex
index 8fe0e79..2a4416f 100644
--- a/exercices2.tex
+++ b/exercices2.tex
@@ -127,16 +127,13 @@ 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
+(4) Modifier légèrement la grammaire proposée 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.
+introduire des nouveaux nonterminaux pour des variantes de
+$\mathit{Instruction}$ et $\mathit{Conditional}$ qui interdisent
+récursivement les conditionnelles sans $\mathtt{else}$.
 
 \begin{corrige}
 (1) L'arbre d'analyse de
@@ -319,12 +316,13 @@ 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}\\
+\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\
 |&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
-\mathit{InstrNoSC} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{FullCond}\\
+\mathit{InstrNoSC} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{CondNoSC}\\
 |&\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{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{Instruction}\\
+|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
+\mathit{InstrNoSC} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{InstrNoSC}\\
 \mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
 \mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
 \end{aligned}
@@ -332,27 +330,14 @@ la grammaire comme suit :
 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).
+$\mathtt{else}$ devrait se rattacher à elle), et ce, récursivement.
+On peut montrer que la grammaire ci-dessus est inambiguë et faiblement
+équivalente à celle de départ.
+
+J'ignore s'il existe une grammaire inambiguë naturelle, faiblement
+équivalente à celle de départ, qui force l'autre interprétation (le
+$\mathtt{else}$ se rapporte au $\mathtt{if}$ le plus lointain
+possible).
 \end{corrige}
 
 
-- 
cgit v1.2.3

