summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-16 23:22:27 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-16 23:22:27 (GMT)
commit4eaff56432b60cf7544f3d35fe41fa004401b20e (patch)
tree5faa7f516947dea8b51565ae4a9480e6fb4a1710
parent2df4c8300a6c0923868288b3421641b43ceb1f43 (diff)
downloadinf105-4eaff56432b60cf7544f3d35fe41fa004401b20e.zip
inf105-4eaff56432b60cf7544f3d35fe41fa004401b20e.tar.gz
inf105-4eaff56432b60cf7544f3d35fe41fa004401b20e.tar.bz2
Fix mistaken exercise/solution on the "dangling else" problem.
Still not satisfied with the fix, but at least it should be correct.
-rw-r--r--exercices2.tex49
1 files changed, 17 insertions, 32 deletions
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}