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