32 Office: & S1.27 (1st floor Strand Building)\\ |
32 Office: & S1.27 (1st floor Strand Building)\\ |
33 Slides: & KEATS (also home work is there)\\ |
33 Slides: & KEATS (also home work is there)\\ |
34 \end{tabular} |
34 \end{tabular} |
35 \end{center} |
35 \end{center} |
36 \end{frame} |
36 \end{frame} |
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
38 |
38 |
39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
40 \mode<presentation>{ |
40 \begin{frame}[c] |
41 \begin{frame}[c] |
41 \frametitle{\begin{tabular}{c}Last Week\\ Regexes and Values\end{tabular}} |
42 \frametitle{DFA Minimisation} |
42 |
43 |
43 Regular expressions and their corresponding values: |
44 \begin{enumerate} |
44 |
45 \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} |
45 \begin{center} |
46 \item Mark all pairs that accepting and non-accepting states |
46 \begin{columns} |
47 \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} tests wether |
47 \begin{column}{3cm} |
48 \begin{center} |
48 \begin{tabular}{@{}rrl@{}} |
49 \bl{$(\delta(q, c), \delta(p,c))$} |
49 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$}\\ |
50 \end{center} |
50 & \bl{$\mid$} & \bl{$\epsilon$} \\ |
51 are marked. If yes, then also mark \bl{$(q, p)$}. |
51 & \bl{$\mid$} & \bl{$c$} \\ |
52 \item Repeat last step until no change. |
52 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ |
53 \item All unmarked pairs can be merged. |
53 & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ |
54 \end{enumerate} |
54 \\ |
55 |
55 & \bl{$\mid$} & \bl{$r^*$} \\ |
56 \end{frame}} |
56 \end{tabular} |
57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
57 \end{column} |
58 |
58 \begin{column}{3cm} |
59 |
59 \begin{tabular}{@{\hspace{-7mm}}rrl@{}} |
60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
60 \bl{$v$} & \bl{$::=$} & \\ |
61 \begin{frame}[c] |
61 & & \bl{$Empty$} \\ |
62 |
62 & \bl{$\mid$} & \bl{$Char(c)$} \\ |
63 \begin{center} |
63 & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ |
64 \begin{tikzpicture}[>=stealth',very thick,auto, |
64 & \bl{$\mid$} & \bl{$Left(v)$} \\ |
65 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
65 & \bl{$\mid$} & \bl{$Right(v)$} \\ |
66 \node[state,initial] (q_0) {$q_0$}; |
66 & \bl{$\mid$} & \bl{$[v_1,\ldots\,v_n]$} \\ |
67 \node[state] (q_1) [right=of q_0] {$q_1$}; |
67 \end{tabular} |
68 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
68 \end{column} |
69 \node[state] (q_3) [right=of q_2] {$q_3$}; |
69 \end{columns} |
70 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
70 \end{center} |
71 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
71 |
72 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
72 |
73 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
73 \end{frame} |
74 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
74 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
75 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
75 |
76 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
76 |
77 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
77 |
78 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
78 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
79 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
79 \begin{frame}[c] |
80 \end{tikzpicture} |
80 |
81 \end{center} |
81 \begin{textblock}{10}(3,5) |
82 |
82 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
83 \mbox{}\\[-20mm]\mbox{} |
83 \node (r1) {\bl{$r_1$}}; |
84 |
84 \node (r2) [right=of r1] {\bl{$r_2$}}; |
85 \begin{center} |
85 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
86 \begin{tikzpicture}[scale=0.8,line width=0.8mm] |
86 \node (r3) [right=of r2] {\bl{$r_3$}}; |
87 \draw (0,0) -- (4,0); |
87 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
88 \draw (0,1) -- (4,1); |
88 \node (r4) [right=of r3] {\bl{$r_4$}}; |
89 \draw (0,2) -- (3,2); |
89 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
90 \draw (0,3) -- (2,3); |
90 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
91 \draw (0,4) -- (1,4); |
91 \node (v4) [below=of r4] {\bl{$v_4$}}; |
92 |
92 \draw[->,line width=1mm] (r4) -- (v4); |
93 \draw (0,0) -- (0, 4); |
93 \node (v3) [left=of v4] {\bl{$v_3$}}; |
94 \draw (1,0) -- (1, 4); |
94 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
95 \draw (2,0) -- (2, 3); |
95 \node (v2) [left=of v3] {\bl{$v_2$}}; |
96 \draw (3,0) -- (3, 2); |
96 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
97 \draw (4,0) -- (4, 1); |
97 \node (v1) [left=of v2] {\bl{$v_1$}}; |
98 |
98 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
99 \draw (0.5,-0.5) node {$q_0$}; |
99 \draw[->,line width=0.5mm] (r3) -- (v3); |
100 \draw (1.5,-0.5) node {$q_1$}; |
100 \draw[->,line width=0.5mm] (r2) -- (v2); |
101 \draw (2.5,-0.5) node {$q_2$}; |
101 \draw[->,line width=0.5mm] (r1) -- (v1); |
102 \draw (3.5,-0.5) node {$q_3$}; |
102 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
103 |
|
104 \draw (-0.5, 3.5) node {$q_1$}; |
|
105 \draw (-0.5, 2.5) node {$q_2$}; |
|
106 \draw (-0.5, 1.5) node {$q_3$}; |
|
107 \draw (-0.5, 0.5) node {$q_4$}; |
|
108 |
|
109 \draw (0.5,0.5) node {\large$\star$}; |
|
110 \draw (1.5,0.5) node {\large$\star$}; |
|
111 \draw (2.5,0.5) node {\large$\star$}; |
|
112 \draw (3.5,0.5) node {\large$\star$}; |
|
113 \end{tikzpicture}\\ |
|
114 \end{center} |
|
115 |
|
116 \end{frame} |
|
117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
118 |
|
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
120 \begin{frame}[c] |
|
121 |
|
122 \begin{center} |
|
123 \begin{tabular}{@{\hspace{-8mm}}cc@{}} |
|
124 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
125 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
126 \node[state,initial] (q_0) {$q_0$}; |
|
127 \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
128 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
129 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
130 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
|
131 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
132 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
133 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
|
134 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
135 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
136 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
137 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
138 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
139 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
|
140 \end{tikzpicture} |
|
141 & |
|
142 \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] |
|
143 \draw (0,0) -- (4,0); |
|
144 \draw (0,1) -- (4,1); |
|
145 \draw (0,2) -- (3,2); |
|
146 \draw (0,3) -- (2,3); |
|
147 \draw (0,4) -- (1,4); |
|
148 |
|
149 \draw (0,0) -- (0, 4); |
|
150 \draw (1,0) -- (1, 4); |
|
151 \draw (2,0) -- (2, 3); |
|
152 \draw (3,0) -- (3, 2); |
|
153 \draw (4,0) -- (4, 1); |
|
154 |
|
155 \draw (0.5,-0.5) node {$q_0$}; |
|
156 \draw (1.5,-0.5) node {$q_1$}; |
|
157 \draw (2.5,-0.5) node {$q_2$}; |
|
158 \draw (3.5,-0.5) node {$q_3$}; |
|
159 |
|
160 \draw (-0.5, 3.5) node {$q_1$}; |
|
161 \draw (-0.5, 2.5) node {$q_2$}; |
|
162 \draw (-0.5, 1.5) node {$q_3$}; |
|
163 \draw (-0.5, 0.5) node {$q_4$}; |
|
164 |
|
165 \draw (0.5,0.5) node {\large$\star$}; |
|
166 \draw (1.5,0.5) node {\large$\star$}; |
|
167 \draw (2.5,0.5) node {\large$\star$}; |
|
168 \draw (3.5,0.5) node {\large$\star$}; |
|
169 \draw (0.5,1.5) node {\large$\star$}; |
|
170 \draw (2.5,1.5) node {\large$\star$}; |
|
171 \draw (0.5,3.5) node {\large$\star$}; |
|
172 \draw (1.5,2.5) node {\large$\star$}; |
|
173 \end{tikzpicture}} |
|
174 \end{tabular} |
|
175 \end{center} |
|
176 |
|
177 |
|
178 \mbox{}\\[-20mm]\mbox{} |
|
179 |
|
180 \begin{center} |
|
181 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
182 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
183 \node[state,initial] (q_02) {$q_{0, 2}$}; |
|
184 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; |
|
185 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; |
|
186 \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); |
|
187 \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); |
|
188 \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); |
|
189 \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); |
|
190 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
191 \end{tikzpicture}\\ |
|
192 minimal automaton |
|
193 \end{center} |
|
194 |
|
195 \end{frame} |
|
196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
197 |
|
198 |
|
199 |
|
200 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
201 \mode<presentation>{ |
|
202 \begin{frame}[c] |
|
203 |
|
204 \begin{center} |
|
205 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
206 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
207 \only<1>{\node[state,initial] (q_0) {$q_0$};} |
|
208 \only<2->{\node[state,accepting] (q_0) {$q_0$};} |
|
209 \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
210 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
211 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
212 \only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};} |
|
213 \only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};} |
|
214 \only<1-2>{ |
|
215 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
216 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
217 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
218 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
219 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
220 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
221 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
222 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
223 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} |
|
224 \only<3->{ |
|
225 \path[<-] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
226 \path[<-] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
227 \path[<-] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
228 \path[<-] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
229 \path[<-] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
230 \path[<-] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
231 \path[<-] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
232 \path[<-] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
233 \path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} |
|
234 \end{tikzpicture} |
|
235 \end{center} |
|
236 |
|
237 \begin{itemize} |
|
238 \item<2-> exchange initial / accepting states |
|
239 \item<3-> reverse all edges |
|
240 \item<4-> subset construction $\Rightarrow$ DFA |
|
241 \item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA} |
|
242 |
|
243 \end{itemize} |
|
244 |
|
245 \end{frame}} |
|
246 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
247 |
|
248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
249 \mode<presentation>{ |
|
250 \begin{frame}[c] |
|
251 |
|
252 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
|
253 |
|
254 \end{frame}} |
|
255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
256 |
|
257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
258 \mode<presentation>{ |
|
259 \begin{frame}[c] |
|
260 |
|
261 \mbox{\lstinputlisting[language=while]{../progs/collatz.while}} |
|
262 |
|
263 \end{frame}} |
|
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
265 |
|
266 |
|
267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
268 \mode<presentation>{ |
|
269 \begin{frame}[c] |
|
270 |
|
271 \mbox{\lstinputlisting[language=while]{../progs/collatz.while}} |
|
272 |
|
273 \begin{textblock}{6}(10,2) |
|
274 \begin{tikzpicture}[scale=0.46] |
|
275 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
|
276 xlabel=n, |
|
277 enlargelimits=0.05, |
|
278 ybar interval=0.7, legend style=small] |
|
279 \addplot file {interpreted2.data}; |
|
280 \addplot file {compiled2.data}; |
|
281 %\legend{interpreted, compiled} |
|
282 \end{axis} |
|
283 \end{tikzpicture} |
103 \end{tikzpicture} |
284 \end{textblock} |
104 \end{textblock} |
285 |
105 |
286 \end{frame}} |
106 \only<2->{ |
287 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
107 \begin{textblock}{6}(1,0.8) |
288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
108 \begin{bubble}[6cm] |
289 \mode<presentation>{ |
109 \small |
290 \begin{frame}[c] |
110 \begin{tabular}{ll} |
291 |
111 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ |
292 \begin{tikzpicture}[scale=1] |
112 \bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ |
293 |
113 \bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ |
294 \draw[line width=1mm] (-.3, 0) rectangle (1.5,2); |
114 \bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ |
295 \draw (4.2,1) node {Code Gen}; |
115 \end{tabular} |
296 \draw (0.6,1.7) node {\footnotesize Parser}; |
116 \end{bubble} |
297 \draw (-2.7,1.7) node {\footnotesize Lexer}; |
117 \end{textblock}} |
298 |
118 |
299 \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2); |
119 \only<2->{ |
300 |
120 \begin{textblock}{6}(5,11.4) |
301 \draw[white] (1.7,1) node (X) {}; |
121 \begin{bubble}[7.6cm] |
302 \draw[white] (3.2,1) node (Y) {}; |
122 \small |
303 \draw[red, ->, line width = 2mm] (X) -- (Y); |
123 \begin{tabular}{ll} |
304 |
124 \bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ |
305 \draw[red, <-, line width = 2mm] (-0.6,1) -- (-1.6,1); |
125 \bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ |
306 \draw[red, <-, line width = 2mm] (-3.8,1) -- (-4.8,1); |
126 \bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ |
|
127 \bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ |
|
128 \end{tabular} |
|
129 \end{bubble} |
|
130 \end{textblock}} |
|
131 \end{frame} |
|
132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
133 |
|
134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
135 \begin{frame}[c] |
|
136 \frametitle{Mkeps} |
|
137 |
|
138 Finding a (posix) value for recognising the empty string: |
|
139 |
|
140 \begin{center} |
|
141 \begin{tabular}{lcl} |
|
142 \bl{$mkeps\,\epsilon$} & \bl{$\dn$} & \bl{$Empty$}\\ |
|
143 \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
|
144 & & \bl{then $Left(mkeps(r_1))$}\\ |
|
145 & & \bl{else $Right(mkeps(r_2))$}\\ |
|
146 \bl{$mkeps\,r_1 \cdot r_2$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ |
|
147 \bl{$mkeps\,r^*$} & \bl{$\dn$} & \bl{$[]$} \\ |
|
148 \end{tabular} |
|
149 \end{center} |
|
150 |
|
151 \end{frame} |
|
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
153 |
|
154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
155 \begin{frame}[c] |
|
156 \frametitle{Inject} |
|
157 |
|
158 Injecting (``Adding'') a character to a value\\ |
|
159 |
|
160 \begin{center} |
|
161 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
162 \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\ |
|
163 \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ |
|
164 \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ |
|
165 \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
|
166 \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
|
167 \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ |
|
168 \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\ |
|
169 \end{tabular} |
|
170 \end{center}\bigskip |
|
171 |
|
172 \footnotesize |
|
173 \bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value |
|
174 \end{frame} |
|
175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
176 |
|
177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
178 \begin{frame}[c] |
|
179 \frametitle{Flatten} |
|
180 |
|
181 Obtaining the string underlying a value: |
|
182 |
|
183 \begin{center} |
|
184 \begin{tabular}{lcl} |
|
185 \bl{$|Empty|$} & \bl{$\dn$} & \bl{$[]$}\\ |
|
186 \bl{$|Char(c)|$} & \bl{$\dn$} & \bl{$[c]$}\\ |
|
187 \bl{$|Left(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\ |
|
188 \bl{$|Right(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\ |
|
189 \bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\ |
|
190 \bl{$|[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\ |
|
191 \end{tabular} |
|
192 \end{center} |
|
193 |
|
194 \end{frame} |
|
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
196 |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 \begin{frame}[c] |
|
199 |
|
200 \begin{textblock}{10}(3,5) |
|
201 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
|
202 \node (r1) {\bl{$r_1$}}; |
|
203 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
204 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
|
205 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
206 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
|
207 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
208 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
|
209 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
|
210 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
211 \draw[->,line width=1mm] (r4) -- (v4); |
|
212 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
213 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
|
214 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
215 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
|
216 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
217 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
|
218 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
219 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
220 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
221 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
307 \end{tikzpicture} |
222 \end{tikzpicture} |
308 |
223 \end{textblock} |
309 |
224 |
310 \end{frame}} |
225 \begin{textblock}{6}(1,0.8) |
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
226 \begin{bubble}[6cm] |
312 |
227 \small |
313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
228 \begin{tabular}{ll} |
314 |
229 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ |
315 \mode<presentation>{ |
230 \bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ |
316 \begin{frame}[t] |
231 \bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ |
317 |
232 \bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ |
318 \consolas |
233 \end{tabular} |
319 \begin{center} |
234 \end{bubble} |
320 "if true then then 42 else +" |
235 \end{textblock} |
321 \end{center} |
236 |
322 |
237 \begin{textblock}{6}(1,11.4) |
323 |
238 \begin{bubble}[7.6cm] |
324 \begin{tabular}{@{}l} |
239 \small |
325 KEYWORD: \\ |
240 \begin{tabular}{ll} |
326 \hspace{5mm}{if}, {then}, {else},\\ |
241 \bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ |
327 WHITESPACE:\\ |
242 \bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ |
328 \hspace{5mm}{" "}, {$\backslash$n},\\ |
243 \bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ |
329 IDENT:\\ |
244 \bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ |
330 \hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\ |
245 \end{tabular} |
331 NUM:\\ |
246 \end{bubble} |
332 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\ |
247 \end{textblock} |
333 OP:\\ |
248 |
334 \hspace{5mm}{+}\\ |
249 \begin{textblock}{6}(12,11.4) |
335 COMMENT:\\ |
250 \begin{bubble}[2cm] |
336 \hspace{5mm}{$\slash$*} $\cdot$ (ALL$^*$ $\cdot$ {*$\slash$} $\cdot$ ALL$^*$) $\cdot$ {*$\slash$} |
251 \small |
337 \end{tabular} |
252 \begin{tabular}{ll} |
338 |
253 \bl{$|v_1|$}: & \bl{$abc$}\\ |
339 \end{frame}} |
254 \bl{$|v_2|$}: & \bl{$bc$}\\ |
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
255 \bl{$|v_3|$}: & \bl{$c$}\\ |
|
256 \bl{$|v_4|$}: & \bl{$[]$} |
|
257 \end{tabular} |
|
258 \end{bubble} |
|
259 \end{textblock} |
|
260 |
|
261 |
|
262 \end{frame} |
|
263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
264 |
|
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
266 \begin{frame}[c] |
|
267 \frametitle{Simplification} |
|
268 |
|
269 \begin{itemize} |
|
270 \item If we simplify after the derivative, then we are builing the |
|
271 value for the simplified regular expression, but \emph{not} for the original |
|
272 regular expression. |
|
273 \end{itemize} |
|
274 |
|
275 \begin{center} |
|
276 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
|
277 \node (r1) {\bl{$r_1$}}; |
|
278 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
279 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
|
280 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
281 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
|
282 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
283 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
|
284 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
|
285 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
286 \draw[->,line width=1mm] (r4) -- (v4); |
|
287 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
288 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
|
289 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
290 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
|
291 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
292 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
|
293 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
294 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
295 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
296 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
|
297 \end{tikzpicture} |
|
298 \end{center} |
|
299 |
|
300 \small |
|
301 \hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$} |
|
302 $\mapsto$ |
|
303 \bl{$\epsilon$} |
|
304 |
|
305 \end{frame} |
|
306 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
307 |
|
308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
309 \begin{frame}[c] |
|
310 \frametitle{Rectification} |
|
311 |
|
312 \begin{center} |
|
313 \begin{tabular}{l} |
|
314 \bl{$simp(r)$}:\\ |
|
315 \quad case \bl{$r = r_1 + r_2$}\\ |
|
316 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ |
|
317 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ |
|
318 \qquad case \bl{$r_{1s} = \varnothing$}: |
|
319 return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\ |
|
320 \qquad case \bl{$r_{2s} = \varnothing$}: |
|
321 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ |
|
322 \qquad case \bl{$r_{1s} = r_{2s}$}: |
|
323 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ |
|
324 \qquad otherwise: |
|
325 return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\ |
|
326 \end{tabular} |
|
327 \end{center} |
|
328 |
|
329 \small |
|
330 \begin{center} |
|
331 \begin{tabular}{l@{\hspace{1mm}}l} |
|
332 \bl{$f_{alt}(f_1, f_2) \dn$}\\ |
|
333 \qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}: |
|
334 & return \bl{$Left(f_1(v'))$}\\ |
|
335 \qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}: |
|
336 & return \bl{$Right(f_2(v'))$}\\ |
|
337 \end{tabular} |
|
338 \end{center} |
|
339 |
|
340 |
|
341 \end{frame} |
|
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
343 |
|
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
345 \begin{frame}[c] |
|
346 \frametitle{Rectification} |
|
347 |
|
348 \begin{center} |
|
349 \begin{tabular}{@{\hspace{-3mm}}l} |
|
350 \bl{$simp(r)$}:\ldots\\ |
|
351 \quad case \bl{$r = r_1 \cdot r_2$}\\ |
|
352 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ |
|
353 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ |
|
354 \qquad case \bl{$r_{1s} = \varnothing$}: |
|
355 return \bl{$(\varnothing, f_{error})$}\\ |
|
356 \qquad case \bl{$r_{2s} = \varnothing$}: |
|
357 return \bl{$(\varnothing, f_{error})$}\\ |
|
358 \qquad case \bl{$r_{1s} = \epsilon$}: |
|
359 return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\ |
|
360 \qquad case \bl{$r_{2s} = \epsilon$}: |
|
361 return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\ |
|
362 \qquad otherwise: |
|
363 return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\ |
|
364 \end{tabular} |
|
365 \end{center} |
|
366 |
|
367 \small |
|
368 \begin{center} |
|
369 \begin{tabular}{l@{\hspace{1mm}}l} |
|
370 \bl{$f_{seq}(f_1, f_2) \dn$}\\ |
|
371 \qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}: |
|
372 & return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\ |
|
373 \end{tabular} |
|
374 \end{center} |
|
375 \end{frame} |
|
376 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
377 |
|
378 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
379 \begin{frame}[c] |
|
380 \frametitle{Lexing with Simplification} |
|
381 |
|
382 \begin{center} |
|
383 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
384 \bl{$lex\,r\,[]$} & \bl{$\dn$} & \bl{if $nullable(r)$ then $mkeps(r)$ else $error$}\\ |
|
385 \bl{$lex\,r\,c::s$} & \bl{$\dn$} & \bl{let $(r', frect) = simp(der(c, r))$}\smallskip\\ |
|
386 & & \bl{$inj\,r\,c\,(frect(lex(r', s)))$}\\ |
|
387 \end{tabular} |
|
388 \end{center}\bigskip |
|
389 |
|
390 \begin{center}\small |
|
391 \begin{tikzpicture}[node distance=1.1cm,every node/.style={minimum size=7mm}] |
|
392 \node (r1) {\bl{$r_1$}}; |
|
393 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
394 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
|
395 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
396 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
|
397 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
398 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
|
399 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
|
400 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
401 \draw[->,line width=1mm] (r4) -- (v4); |
|
402 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
403 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
|
404 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
405 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
|
406 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
407 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
|
408 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
409 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
410 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
411 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
|
412 \end{tikzpicture} |
|
413 \end{center} |
|
414 |
|
415 |
|
416 \end{frame} |
|
417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
418 |
|
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
420 \begin{frame}[c] |
|
421 \frametitle{Records} |
|
422 |
|
423 \begin{itemize} |
|
424 \item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause |
|
425 |
|
426 \item \bl{$nullable(x:r) \dn nullable(r)$} |
|
427 \item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$} |
|
428 \item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} |
|
429 \item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} |
|
430 \end{itemize}\bigskip\bigskip\pause |
|
431 |
|
432 \small |
|
433 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} |
|
434 |
|
435 \end{frame} |
|
436 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
437 |
|
438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
439 \begin{frame}[c] |
|
440 \frametitle{While Tokens} |
|
441 |
|
442 \begin{center} |
|
443 \begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}} |
|
444 \pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ |
|
445 & & \phantom{(}\pcode{("i" : ID)} +\\ |
|
446 & & \phantom{(}\pcode{("o" : OP)} + \\ |
|
447 & & \phantom{(}\pcode{("n" : NUM)} + \\ |
|
448 & & \phantom{(}\pcode{("s" : SEMI)} +\\ |
|
449 & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ |
|
450 & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ |
|
451 & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$} |
|
452 \end{tabular} |
|
453 \end{center} |
|
454 |
|
455 \end{frame} |
|
456 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
341 |
457 |
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
458 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
343 \mode<presentation>{ |
459 \mode<presentation>{ |
344 \begin{frame}[t] |
460 \begin{frame}[t] |
345 |
461 |