summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-12 22:29:46 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-12 22:29:46 (GMT)
commit8133bc2845d446d850a28eba6df8098a1da4e921 (patch)
treee8c6bb1d2c087a6d64dfa27222dadc995ccaecc4
parent92d71034af1cf33a9237e8687e20b89ca0d35821 (diff)
downloadinf105-8133bc2845d446d850a28eba6df8098a1da4e921.zip
inf105-8133bc2845d446d850a28eba6df8098a1da4e921.tar.gz
inf105-8133bc2845d446d850a28eba6df8098a1da4e921.tar.bz2
Continue writing about the dangling else ambiguity.
-rw-r--r--exercices2.tex100
-rw-r--r--figs/ex2p1a.dot36
-rw-r--r--figs/ex2p1b.dot36
3 files changed, 171 insertions, 1 deletions
diff --git a/exercices2.tex b/exercices2.tex
index 70d030b..aac8a19 100644
--- a/exercices2.tex
+++ b/exercices2.tex
@@ -127,7 +127,7 @@ Que peut-on dire de la grammaire présentée ?
$\mathit{Instruction}$, $\mathit{Condition}$ et
$\mathit{Expression}$ respectivement) :
\begin{center}
-\tikzstyle{automaton}=[scale=0.5]
+\tikzstyle{automaton}=[scale=0.4]
%%% begin ex2p1 %%%
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
@@ -183,6 +183,104 @@ 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).
+
+\vskip .5explus.1fil
+
+(2) Un arbre d'analyse possible consiste à associer le
+$\mathtt{else}\penalty0\ \mathtt{bar}$ avec
+$\mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}$ :
+\begin{center}
+\tikzstyle{automaton}=[scale=0.4]
+%%% begin ex2p1a %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$};
+ \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 (I1) at (243bp,234bp) [draw,draw=none] {$I$};
+ \node (I0) at (135bp,378bp) [draw,draw=none] {$I$};
+ \node (I3) at (423bp,90bp) [draw,draw=none] {$I$};
+ \node (I2) at (279bp,90bp) [draw,draw=none] {$I$};
+ \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
+ \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$};
+ \node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
+ \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
+ \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
+ \node (C0) at (135bp,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 (149.48bp,276.85bp) and (156.64bp,262.92bp) .. (then0);
+ \draw [] (I0) ..controls (135bp,348.85bp) and (135bp,334.92bp) .. (C0);
+ \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp) .. (then1);
+ \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp) .. (else1);
+ \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp) .. (bar);
+ \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 (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 (91.844bp,277.03bp) and (70.277bp,263.05bp) .. (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 (178.16bp,277.03bp) and (199.72bp,263.05bp) .. (I1);
+ \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp) .. (I2);
+ \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp) .. (C1);
+ \draw [] (C0) ..controls (120.52bp,276.85bp) and (113.36bp,262.92bp) .. (E0);
+%
+\end{tikzpicture}
+
+%%% end ex2p1a %%%
+\end{center}
+un autre consiste à associer le $\mathtt{else}\penalty0\ \mathtt{bar}$
+avec
+$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ ...$ :
+\begin{center}
+\tikzstyle{automaton}=[scale=0.4]
+%%% begin ex2p1b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (bar) at (387bp,162bp) [draw,draw=none] {$\mathtt{bar}$};
+ \node (then1) at (279bp,90bp) [draw,draw=none] {$\mathtt{then}$};
+ \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
+ \node (if1) at (135bp,90bp) [draw,draw=none] {$\mathtt{if}$};
+ \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
+ \node (I0) at (207bp,378bp) [draw,draw=none] {$I$};
+ \node (I2) at (351bp,90bp) [draw,draw=none] {$I$};
+ \node (I4) at (387bp,234bp) [draw,draw=none] {$I$};
+ \node (trippy) at (207bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
+ \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$};
+ \node (foo) at (351bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
+ \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 (207bp,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 (351bp,60.846bp) and (351bp,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) .. (I2);
+ \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp) .. (bar);
+ \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp) .. (happy);
+ \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp) .. (E1);
+ \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 (199.84bp,133.03bp) and (178.28bp,119.05bp) .. (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 (207bp,60.846bp) and (207bp,46.917bp) .. (trippy);
+ \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp) .. (I1);
+ \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp) .. (then1);
+ \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp) .. (C1);
+ \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp) .. (E0);
+%
+\end{tikzpicture}
+
+%%% end ex2p1b %%%
+\end{center}
+La grammaire présentée est donc ambiguë.
\end{corrige}
diff --git a/figs/ex2p1a.dot b/figs/ex2p1a.dot
new file mode 100644
index 0000000..fbf84b0
--- /dev/null
+++ b/figs/ex2p1a.dot
@@ -0,0 +1,36 @@
+graph ex2p1a {
+ 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"];
+ 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"];
+ 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;
+ E0 -- happy;
+ I1 -- C1;
+ C1 -- if1;
+ C1 -- E1;
+ C1 -- then1;
+ C1 -- I2;
+ C1 -- else1;
+ C1 -- I3;
+ E1 -- trippy;
+ I2 -- foo;
+ I3 -- bar;
+}
diff --git a/figs/ex2p1b.dot b/figs/ex2p1b.dot
new file mode 100644
index 0000000..79ad50c
--- /dev/null
+++ b/figs/ex2p1b.dot
@@ -0,0 +1,36 @@
+graph ex2p1b {
+ 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"];
+ bar [label="bar",texlbl="$\mathtt{bar}$"];
+ trippy [label="trippy",texlbl="$\mathtt{trippy}$"];
+ foo [label="foo",texlbl="$\mathtt{foo}$"];
+ I0 -- C0;
+ C0 -- if0;
+ C0 -- E0;
+ C0 -- then0;
+ C0 -- I1;
+ C0 -- else0;
+ C0 -- I4;
+ E0 -- happy;
+ I1 -- C1;
+ I4 -- bar;
+ C1 -- if1;
+ C1 -- E1;
+ C1 -- then1;
+ C1 -- I2;
+ E1 -- trippy;
+ I2 -- foo;
+}