Start writing a new exercise on the "dangling else" problem.

2 files changed, 145 insertions, 0 deletions

diff --git a/exercices2.tex b/exercices2.tex
index 10cd7d7..70d030b 100644
--- a/exercices2.tex
+++ b/exercices2.tex
@@ -87,6 +87,105 @@ Git: \input{vcline.tex}
 \tolerance=50000
 
 
+
+%
+%
+%
+
+\exercice
+
+Considérons le fragment simplifié suivant de la grammaire d'un langage
+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}\\
+\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
+\end{aligned}
+\]
+(Ici, les « lettres » ou tokens ont été écrits comme des mots, par
+exemple $\mathtt{foo}$ est une « lettre » : les terminaux sont écrits
+en police à espacement fixe tandis que les nonterminaux sont en
+italique et commencent par une majuscule.  On prendra
+$\mathit{Instruction}$ pour axiome.)
+
+(1) Donner 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}$ ;
+expliquer brièvement pourquoi il n'y en a qu'un.
+
+(2) Donner deux arbres d'analyse distincts 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}$.
+Que peut-on dire de la grammaire présentée ?
+
+\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}$
+  est le suivant (en notant $I$, $C$ et $E$ pour
+  $\mathit{Instruction}$, $\mathit{Condition}$ et
+  $\mathit{Expression}$ respectivement) :
+\begin{center}
+\tikzstyle{automaton}=[scale=0.5]
+%%% begin ex2p1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
+  \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$};
+  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
+  \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$};
+  \node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$};
+  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
+  \node (I0) at (207bp,378bp) [draw,draw=none] {$I$};
+  \node (I3) at (423bp,90bp) [draw,draw=none] {$I$};
+  \node (I2) at (279bp,90bp) [draw,draw=none] {$I$};
+  \node (I4) at (387bp,234bp) [draw,draw=none] {$I$};
+  \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
+  \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$};
+  \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$};
+  \node (qux) at (387bp,162bp) [draw,draw=none] {$\mathtt{qux}$};
+  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
+  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
+  \node (C0) at (207bp,306bp) [draw,draw=none] {$C$};
+  \node (E1) at (135bp,90bp) [draw,draw=none] {$E$};
+  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
+  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
+  \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp)  .. (foo);
+  \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp)  .. (then0);
+  \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp)  .. (C0);
+  \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp)  .. (else0);
+  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (else1);
+  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (I2);
+  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
+  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (E1);
+  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (then1);
+  \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp)  .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp)  .. (I4);
+  \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp)  .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp)  .. (if1);
+  \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp)  .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp)  .. (if0);
+  \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp)  .. (trippy);
+  \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp)  .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp)  .. (I3);
+  \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp)  .. (I1);
+  \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp)  .. (qux);
+  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
+  \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp)  .. (bar);
+  \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp)  .. (E0);
+%
+\end{tikzpicture}
+
+%%% end ex2p1 %%%
+\end{center}
+
+Il est le seul possible car une fois acquis que les deux $\mathtt{if}$
+comportent chacun un $\mathtt{else}$, il se construit ensuite en
+descendant de façon unique (l'instruction est forcément une condition,
+qui s'analyse en $\mathtt{if}\ E\ \mathtt{then}\ I\ \mathtt{else}\ I$
+de façon unique, et chacun des morceaux s'analyse de nouveau de façon
+unique).
+\end{corrige}
+
+
 %
 %
 %
@@ -186,6 +285,10 @@ $x_1\cdots x_{2i-1}$ et $x_{2i}\cdots x_{2n}$.)
 \end{corrige}
 
 
+%
+%
+%
+
 \exercice\label{square-words-not-algebraic}
 
 Soit $\Sigma = \{a,b\}$.  Montrer que le langage $Q := \{ww :
diff --git a/figs/ex2p1.dot b/figs/ex2p1.dot
new file mode 100644
index 0000000..cde6c66
--- /dev/null
+++ b/figs/ex2p1.dot
@@ -0,0 +1,42 @@
+graph ex2p1 {
+	node [texmode="math",shape="none"];
+	I0 [label="I"];
+	C0 [label="C"];
+	if0 [label="if",texlbl="$\mathtt{if}$"];
+	E0 [label="E"];
+	then0 [label="then",texlbl="$\mathtt{then}$"];
+	I1 [label="I"];
+	else0 [label="else",texlbl="$\mathtt{else}$"];
+	I4 [label="I"];
+	happy [label="happy",texlbl="$\mathtt{happy}$"];
+	C1 [label="C"];
+	if1 [label="if",texlbl="$\mathtt{if}$"];
+	E1 [label="E"];
+	then1 [label="then",texlbl="$\mathtt{then}$"];
+	I2 [label="I"];
+	else1 [label="else",texlbl="$\mathtt{else}$"];
+	I3 [label="I"];
+	qux [label="qux",texlbl="$\mathtt{qux}$"];
+	trippy [label="trippy",texlbl="$\mathtt{trippy}$"];
+	foo [label="foo",texlbl="$\mathtt{foo}$"];
+	bar [label="bar",texlbl="$\mathtt{bar}$"];
+	I0 -- C0;
+	C0 -- if0;
+	C0 -- E0;
+	C0 -- then0;
+	C0 -- I1;
+	C0 -- else0;
+	C0 -- I4;
+	E0 -- happy;
+	I1 -- C1;
+	I4 -- qux;
+	C1 -- if1;
+	C1 -- E1;
+	C1 -- then1;
+	C1 -- I2;
+	C1 -- else1;
+	C1 -- I3;
+	E1 -- trippy;
+	I2 -- foo;
+	I3 -- bar;
+}