summaryrefslogtreecommitdiffstats
path: root/exercices2.tex
diff options
context:
space:
mode:
Diffstat (limited to 'exercices2.tex')
-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}