summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-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}