diff options
| -rw-r--r-- | exercices2.tex | 80 |
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} |