24 \normalsize |
23 \normalsize |
25 \begin{center} |
24 \begin{center} |
26 \begin{tabular}{ll} |
25 \begin{tabular}{ll} |
27 Email: & christian.urban at kcl.ac.uk\\ |
26 Email: & christian.urban at kcl.ac.uk\\ |
28 Office: & N\liningnums{7.07} (North Wing, Bush House)\\ |
27 Office: & N\liningnums{7.07} (North Wing, Bush House)\\ |
29 Slides: & KEATS (also home work is there)\\ |
28 Slides: & KEATS (also homework is there)\\ |
30 \end{tabular} |
29 \end{tabular} |
31 \end{center} |
30 \end{center} |
32 |
31 |
33 \end{frame} |
32 \end{frame} |
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
35 |
34 |
36 |
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
37 \newcommand{\qq}{\mbox{\texttt{"}}} |
36 \begin{frame}[c] |
38 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
37 \frametitle{Bird's Eye View} |
39 \begin{frame}[c] |
|
40 \frametitle{CFGs} |
|
41 |
|
42 A \alert{context-free} grammar (CFG) \bl{$G$} consists of: |
|
43 |
|
44 \begin{itemize} |
|
45 \item a finite set of nonterminal symbols (upper case) |
|
46 \item a finite terminal symbols or tokens (lower case) |
|
47 \item a start symbol (which must be a nonterminal) |
|
48 \item a set of rules |
|
49 \begin{center} |
|
50 \bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$} |
|
51 \end{center} |
|
52 |
|
53 where \bl{rhs} are sequences involving terminals and nonterminals (can also be empty).\medskip\pause |
|
54 |
|
55 \end{itemize} |
|
56 |
|
57 \end{frame} |
|
58 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
59 |
|
60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
61 \mode<presentation>{ |
|
62 \begin{frame}[c] |
|
63 \frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}} |
|
64 |
|
65 Recall that languages are sets of strings. |
|
66 |
38 |
67 \begin{center} |
39 \begin{center} |
68 \begin{tikzpicture} |
40 \begin{tikzpicture} |
69 [rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}] |
41 \node (rexp) {\bl{\bf Lexer}}; |
70 |
42 \node (nfa) [right=of rexp] {\bl{\bf Parser}}; |
71 \draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages}; |
43 \node (dfa) [right=of nfa] |
72 \draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages}; |
44 {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Java Byte Code\end{tabular}}}; |
73 \draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages}; |
45 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm] |
74 \draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages}; |
46 sequence\end{tabular}} (nfa); |
75 \draw (0,-1.4) node [rect] {regular languages}; |
47 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree\end{tabular}}(dfa); |
76 \end{tikzpicture} |
48 \end{tikzpicture}\\ |
77 |
49 \end{center} |
78 \end{center} |
50 |
79 |
51 \end{frame} |
80 \end{frame}} |
52 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
81 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
53 |
82 |
54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
55 \begin{frame}[c] |
84 \mode<presentation>{ |
56 \begin{textblock}{10}(0.5,0.5) |
85 \begin{frame}[c] |
57 \LARGE |
86 \frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}} |
58 \fontspec{Hoefler Text Black} |
87 |
59 \textcolor{ProcessBlue}{JVM\\ Code} |
88 A grammar for arithmetic expressions and numbers: |
60 \\[12mm] |
89 |
61 |
90 \begin{center} |
62 \normalsize |
91 \bl{\begin{tabular}{lcl} |
63 Jasmin\\ |
92 $E$ & $\rightarrow$ & $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\ |
64 Krakatau\\ |
93 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ |
65 ASM lib |
94 \end{tabular}} |
66 \end{textblock} |
95 \end{center} |
67 |
96 |
68 |
97 Unfortunately it is left-recursive (and ambiguous).\medskip\\ |
69 \fontsize{8}{10}\selectfont |
98 A problem for \alert{recursive descent parsers} (e.g.~parser combinators). |
70 %\footnotesize |
99 \bigskip\pause |
71 \mbox{}\\[-8mm]\mbox{} |
100 |
72 |
101 \end{frame}} |
73 \begin{columns} |
102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
74 \begin{column}{2cm} |
103 |
75 \lstinputlisting[numbers=none]{../progs/appHa.j} |
104 |
76 \end{column} |
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
77 |
106 \mode<presentation>{ |
78 \begin{column}{2cm} |
107 \begin{frame}[t] |
79 \lstinputlisting[numbers=none]{../progs/appHb.j} |
108 \frametitle{\begin{tabular}{c}Numbers\end{tabular}} |
80 \end{column} |
109 |
81 |
110 |
82 \end{columns} |
111 |
83 |
112 \begin{center} |
84 \end{frame} |
113 \bl{\begin{tabular}{lcl} |
85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
114 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\ |
86 |
115 \end{tabular}} |
87 |
116 \end{center} |
88 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
117 |
89 \begin{frame}[t] |
118 A non-left-recursive, non-ambiguous grammar for numbers: |
|
119 |
|
120 \begin{center} |
|
121 \bl{\begin{tabular}{lcl} |
|
122 $N$ & $\rightarrow$ & $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\ |
|
123 \end{tabular}} |
|
124 \end{center} |
|
125 |
|
126 |
|
127 \end{frame}} |
|
128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
129 |
|
130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
131 \mode<presentation>{ |
|
132 \begin{frame}[c] |
|
133 \frametitle{\begin{tabular}{c}Operator Precedences\end{tabular}} |
|
134 |
|
135 |
|
136 To disambiguate |
|
137 |
|
138 \begin{center} |
|
139 \bl{\begin{tabular}{lcl} |
|
140 $E$ & $\rightarrow$ & $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\ |
|
141 \end{tabular}} |
|
142 \end{center} |
|
143 |
|
144 Decide on how many precedence levels, say\medskip\\ |
|
145 \hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+} |
|
146 |
|
147 \begin{center} |
|
148 \bl{\begin{tabular}{lcl} |
|
149 $E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\ |
|
150 $E_{med}$ & $\rightarrow$ & $E_{hi} \cdot * \cdot E_{med} \;|\; E_{hi}$\\ |
|
151 $E_{hi}$ & $\rightarrow$ & $( \cdot E_{low} \cdot ) \;|\;N$ \\ |
|
152 \end{tabular}} |
|
153 \end{center}\pause |
|
154 |
|
155 \small What happens with \bl{$1 + 3 + 4$}? |
|
156 \end{frame}} |
|
157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
158 |
|
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
160 \mode<presentation>{ |
|
161 \begin{frame}[c] |
|
162 \frametitle{\begin{tabular}{c}Removing Left-Recursion\end{tabular}} |
|
163 |
|
164 The rule for numbers is directly left-recursive: |
|
165 |
|
166 \begin{center} |
|
167 \bl{\begin{tabular}{lcl} |
|
168 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ |
|
169 \end{tabular}} |
|
170 \end{center} |
|
171 |
|
172 Translate |
|
173 |
|
174 \begin{center} |
|
175 \begin{tabular}{ccc} |
|
176 \bl{\begin{tabular}{lcl} |
|
177 $N$ & $\rightarrow$ & $N \cdot \alpha$\\ |
|
178 & $\;|\;$ & $\beta$\\ |
|
179 \\ |
|
180 \end{tabular}} |
|
181 & {\Large$\Rightarrow$} & |
|
182 \bl{\begin{tabular}{lcl} |
|
183 $N$ & $\rightarrow$ & $\beta \cdot N'$\\ |
|
184 $N'$ & $\rightarrow$ & $\alpha \cdot N'$\\ |
|
185 & $\;|\;$ & $\epsilon$ |
|
186 \end{tabular}} |
|
187 \end{tabular} |
|
188 \end{center}\pause |
|
189 |
|
190 Which means |
|
191 |
|
192 \begin{center} |
|
193 \bl{\begin{tabular}{lcl} |
|
194 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1 \cdot N'$\\ |
|
195 $N'$ & $\rightarrow$ & $N \cdot N' \;|\; \epsilon$\\ |
|
196 \end{tabular}} |
|
197 \end{center} |
|
198 |
|
199 |
|
200 \end{frame}} |
|
201 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
202 |
|
203 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
204 \mode<presentation>{ |
|
205 \begin{frame}[c] |
|
206 \frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}} |
|
207 |
|
208 All rules must be of the form |
|
209 |
|
210 \begin{center} |
|
211 \bl{$A \rightarrow a$} |
|
212 \end{center} |
|
213 |
|
214 or |
|
215 |
|
216 \begin{center} |
|
217 \bl{$A \rightarrow B\cdot C$} |
|
218 \end{center} |
|
219 |
|
220 No rule can contain \bl{$\epsilon$}. |
|
221 |
|
222 \end{frame}} |
|
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
224 |
|
225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
226 \mode<presentation>{ |
|
227 \begin{frame}[c] |
|
228 \frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}} |
|
229 |
|
230 \begin{enumerate} |
|
231 \item If \bl{$A\rightarrow \alpha \cdot B \cdot \beta$} and \bl{$B \rightarrow \epsilon$} are in the grammar, |
|
232 then add \bl{$A\rightarrow \alpha \cdot \beta$} (iterate if necessary). |
|
233 \item Throw out all \bl{$B \rightarrow \epsilon$}. |
|
234 \end{enumerate} |
|
235 |
|
236 \small |
|
237 \begin{center} |
|
238 \begin{tabular}{ccc} |
|
239 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
240 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\ |
|
241 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$\\ |
|
242 \\ |
|
243 \\ |
|
244 \\ |
|
245 \\ |
|
246 \\ |
|
247 \end{tabular}} & |
|
248 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
249 \\ |
|
250 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\ |
|
251 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\ |
|
252 \\ |
|
253 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\ |
|
254 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;N$\\ |
|
255 \end{tabular}} |
|
256 \end{tabular} |
|
257 \end{center} |
|
258 |
|
259 \pause\normalsize |
|
260 \begin{center} |
|
261 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
262 $N$ & $\rightarrow$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\ |
|
263 \end{tabular}} |
|
264 |
|
265 \end{center} |
|
266 \end{frame}} |
|
267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
268 |
|
269 |
|
270 |
|
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
272 \mode<presentation>{ |
|
273 \begin{frame}[c] |
|
274 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}} |
|
275 |
|
276 If grammar is in Chomsky normalform \ldots |
|
277 |
|
278 \begin{center} |
|
279 \bl{\begin{tabular}{@ {}lcl@ {}} |
|
280 $S$ & $\rightarrow$ & $N\cdot P$ \\ |
|
281 $P$ & $\rightarrow$ & $V\cdot N$ \\ |
|
282 $N$ & $\rightarrow$ & $N\cdot N$ \\ |
|
283 $N$ & $\rightarrow$ & $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\ |
|
284 $V$ & $\rightarrow$ & $\texttt{trains}$ |
|
285 \end{tabular}} |
|
286 \end{center} |
|
287 |
|
288 \bl{\texttt{Jeff trains geometry students}} |
|
289 |
|
290 \end{frame}} |
|
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
293 \mode<presentation>{ |
|
294 \begin{frame}[c] |
|
295 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}} |
|
296 |
|
297 |
|
298 \begin{itemize} |
|
299 \item fastest possible algorithm for recognition problem |
|
300 \item runtime is \bl{$O(n^3)$}\bigskip |
|
301 \item grammars need to be transferred into CNF |
|
302 \end{itemize} |
|
303 |
|
304 \end{frame}} |
|
305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
306 |
|
307 |
|
308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
309 \mode<presentation>{ |
|
310 \begin{frame}[c] |
|
311 \frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}} |
|
312 |
|
313 Recall that languages are sets of strings. |
|
314 |
|
315 \begin{center} |
|
316 \begin{tikzpicture} |
|
317 [rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}] |
|
318 |
|
319 \draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages}; |
|
320 \draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages}; |
|
321 \draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages}; |
|
322 \draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages}; |
|
323 \draw (0,-1.4) node [rect] {regular languages}; |
|
324 \end{tikzpicture} |
|
325 |
|
326 \end{center} |
|
327 |
|
328 \end{frame}} |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 |
|
331 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
332 \mode<presentation>{ |
|
333 \begin{frame}[c] |
|
334 \frametitle{\begin{tabular}{c}Context Sensitive Grms\end{tabular}} |
|
335 |
|
336 |
|
337 \begin{center} |
|
338 \bl{\begin{tabular}{lcl} |
|
339 $S$ & $\Rightarrow$ & $bSAA\;|\; \epsilon$\\ |
|
340 $A$ & $\Rightarrow$ & $a$\\ |
|
341 $bA$ & $\Rightarrow$ & $Ab$\\ |
|
342 \end{tabular}} |
|
343 \end{center}\pause |
|
344 |
|
345 \begin{center} |
|
346 \bl{$S \Rightarrow\ldots\Rightarrow^? "ababaa"$} |
|
347 \end{center} |
|
348 |
|
349 \end{frame}} |
|
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
351 |
|
352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
353 \mode<presentation>{ |
|
354 \begin{frame}[c] |
|
355 |
90 |
356 \begin{center} |
91 \begin{center} |
357 \bl{\begin{tabular}{@{}lcl@{}} |
92 \bl{\begin{tabular}{@{}lcl@{}} |
358 \textit{Stmt} & $\rightarrow$ & $\texttt{skip}$\\ |
93 \\[-12mm] |
359 & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\ |
94 \meta{Stmt} & $::=$ & $\texttt{skip}$\\ |
360 & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\ |
95 & $|$ & \textit{Id}\;\texttt{:=}\;\meta{AExp}\\ |
361 & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\ |
96 & $|$ & \texttt{if}\; \meta{BExp} \;\texttt{then}\; \meta{Block} \;\texttt{else}\; \meta{Block}\\ |
|
97 & $|$ & \texttt{while}\; \meta{BExp} \;\texttt{do}\; \meta{Block}\\ |
362 & $|$ & \texttt{read}\;\textit{Id}\\ |
98 & $|$ & \texttt{read}\;\textit{Id}\\ |
363 & $|$ & \texttt{write}\;\textit{Id}\\ |
99 & $|$ & \texttt{write}\;\textit{Id}\\ |
364 & $|$ & \texttt{write}\;\textit{String}\medskip\\ |
100 & $|$ & \texttt{write}\;\textit{String}\medskip\\ |
365 \textit{Stmts} & $\rightarrow$ & \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\ |
101 \meta{Stmts} & $::=$ & \meta{Stmt} \;\texttt{;}\; \meta{Stmts}\\ |
366 & $|$ & \textit{Stmt}\medskip\\ |
102 & $|$ & \meta{Stmt}\medskip\\ |
367 \textit{Block} & $\rightarrow$ & \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\ |
103 \meta{Block} & $::=$ & \texttt{\{}\,\meta{Stmts}\,\texttt{\}}\\ |
368 & $|$ & \textit{Stmt}\medskip\\ |
104 & $|$ & \meta{Stmt}\medskip\\ |
369 \textit{AExp} & $\rightarrow$ & \ldots\\ |
105 \meta{AExp} & $::=$ & \ldots\\ |
370 \textit{BExp} & $\rightarrow$ & \ldots\\ |
106 \meta{BExp} & $::=$ & \ldots\\ |
371 \end{tabular}} |
107 \end{tabular}} |
372 \end{center} |
108 \end{center} |
373 \end{frame}} |
109 \end{frame} |
374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
375 |
111 |
376 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
112 |
377 \mode<presentation>{ |
113 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
378 \begin{frame}[c] |
114 \begin{frame}[c] |
379 |
115 \frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}} |
380 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
116 |
381 |
117 \mbox{}\\[-18mm]\mbox{} |
382 \end{frame}} |
118 |
383 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
119 {\lstset{language=While}\fontsize{10}{12}\selectfont |
384 |
120 \texttt{\lstinputlisting{../progs/fib.while}}} |
385 |
121 |
386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
122 \end{frame} |
387 \mode<presentation>{ |
123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
388 \begin{frame}[c] |
124 |
389 \frametitle{\begin{tabular}{c}An Interpreter\end{tabular}} |
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
390 |
126 \begin{frame}[c] |
391 \begin{center} |
127 \frametitle{Interpreter} |
392 \bl{\begin{tabular}{l} |
|
393 $\{$\\ |
|
394 \;\;$x := 5 \text{;}$\\ |
|
395 \;\;$y := x * 3\text{;}$\\ |
|
396 \;\;$y := x * 4\text{;}$\\ |
|
397 \;\;$x := u * 3$\\ |
|
398 $\}$ |
|
399 \end{tabular}} |
|
400 \end{center} |
|
401 |
|
402 \begin{itemize} |
|
403 \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause |
|
404 \item \bl{\text{eval}(stmt, env)} |
|
405 \end{itemize} |
|
406 |
|
407 |
|
408 \end{frame}} |
|
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
410 |
|
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
412 \mode<presentation>{ |
|
413 \begin{frame}[c] |
|
414 \frametitle{\begin{tabular}{c}Interpreter\end{tabular}} |
|
415 |
128 |
416 \begin{center} |
129 \begin{center} |
417 \bl{\begin{tabular}{@{}lcl@{}} |
130 \bl{\begin{tabular}{@{}lcl@{}} |
418 $\text{eval}(n, E)$ & $\dn$ & $n$\\ |
131 $\text{eval}(n, E)$ & $\dn$ & $n$\\ |
419 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\ |
132 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\ |
448 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\ |
161 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\ |
449 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\ |
162 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\ |
450 \end{tabular}} |
163 \end{tabular}} |
451 \end{center} |
164 \end{center} |
452 |
165 |
453 \end{frame}} |
166 \end{frame} |
454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
167 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
455 |
168 |
456 |
169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
170 \begin{frame}[c] |
458 \mode<presentation>{ |
171 \frametitle{Test Program} |
459 \begin{frame}[c] |
|
460 \frametitle{\begin{tabular}{c}Test Program\end{tabular}} |
|
461 |
172 |
462 \mbox{}\\[-18mm]\mbox{} |
173 \mbox{}\\[-18mm]\mbox{} |
463 |
174 |
464 {\lstset{language=While}%%\fontsize{10}{12}\selectfont |
175 {\lstset{language=While}\fontsize{10}{12}\selectfont |
465 \texttt{\lstinputlisting{../progs/loops.while}}} |
176 \texttt{\lstinputlisting{../progs/loops.while}}} |
466 |
177 |
467 \end{frame}} |
178 \end{frame} |
468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
469 |
180 |
470 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
181 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
471 \mode<presentation>{ |
182 \begin{frame}[c] |
472 \begin{frame}[t] |
183 \fontsize{7}{9}\selectfont |
473 \frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}} |
184 |
|
185 |
|
186 \begin{columns} |
|
187 \begin{column}{7cm} |
|
188 \lstinputlisting[numbers=none]{../progs/appHa.j} |
|
189 \end{column} |
|
190 |
|
191 \begin{column}{7cm} |
|
192 \lstinputlisting[numbers=none]{../progs/appHb.j} |
|
193 \end{column} |
|
194 \end{columns} |
|
195 |
|
196 \end{frame} |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 |
|
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
200 \begin{frame}[t] |
|
201 \frametitle{Interpreted Code} |
474 |
202 |
475 \begin{center} |
203 \begin{center} |
476 \begin{tikzpicture} |
204 \begin{tikzpicture} |
477 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
205 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
478 \addplot+[smooth] file {interpreted.data}; |
206 \addplot+[smooth] file {interpreted.data}; |
479 \end{axis} |
207 \end{axis} |
480 \end{tikzpicture} |
208 \end{tikzpicture} |
481 \end{center} |
209 \end{center} |
482 |
210 |
483 \end{frame}} |
211 \end{frame} |
484 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
485 |
213 |
486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
487 \mode<presentation>{ |
215 \begin{frame}[c] |
488 \begin{frame}[c] |
216 \frametitle{Java Virtual Machine} |
489 \frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}} |
|
490 |
217 |
491 \begin{itemize} |
218 \begin{itemize} |
492 \item introduced in 1995 |
219 \item introduced in 1995 |
493 \item is a stack-based VM (like Postscript, CLR of .Net) |
220 \item is a stack-based VM (like Postscript, CLR of .Net) |
494 \item contains a JIT compiler |
221 \item contains a JIT compiler |
495 \item many languages take advantage of JVM's infrastructure (JRE) |
222 \item many languages take advantage of JVM's infrastructure (JRE) |
496 \item is garbage collected $\Rightarrow$ no buffer overflows |
223 \item is garbage collected $\Rightarrow$ no buffer overflows |
497 \item some languages compile to the JVM: Scala, Clojure\ldots |
224 \item some languages compiled to the JVM: Scala, Clojure\ldots |
498 \end{itemize} |
225 \end{itemize} |
499 |
226 |
|
227 \end{frame} |
|
228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
229 |
|
230 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
231 \begin{frame}[t,fragile] |
|
232 \frametitle{Compiling AExps} |
|
233 |
|
234 For example \liningnums{\bl{$1 + ((2 * 3) + (4 - 3))$}}:\medskip |
|
235 |
|
236 \begin{columns}[T] |
|
237 \begin{column}{.3\textwidth} |
|
238 \begin{center} |
|
239 \bl{\begin{tikzpicture} |
|
240 \tikzset{level distance=12mm,sibling distance=4mm} |
|
241 \tikzset{edge from parent/.style={draw,very thick}} |
|
242 \Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]] |
|
243 \end{tikzpicture}} |
|
244 \end{center} |
|
245 \end{column} |
|
246 \begin{column}{.3\textwidth} |
|
247 \begin{lstlisting}[language=JVMIS,numbers=none] |
|
248 ldc 1 |
|
249 ldc 2 |
|
250 ldc 3 |
|
251 imul |
|
252 ldc 4 |
|
253 ldc 3 |
|
254 isub |
|
255 iadd |
|
256 iadd |
|
257 \end{lstlisting} |
|
258 \end{column} |
|
259 \end{columns}\bigskip |
|
260 |
|
261 \small |
|
262 Traverse tree in post-order \bl{$\Rightarrow$} code for |
|
263 stack-machine |
|
264 |
|
265 \end{frame} |
|
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
267 |
|
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
269 \begin{frame}[t,fragile] |
|
270 \frametitle{Compiling AExps} |
|
271 |
|
272 \liningnums{\textbf{\Large\bl{1 + 2 + 3}}} |
|
273 |
|
274 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm] |
|
275 ldc 1 |
|
276 ldc 2 |
|
277 iadd |
|
278 ldc 3 |
|
279 iadd |
|
280 \end{lstlisting} |
|
281 |
|
282 |
|
283 \end{frame} |
|
284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
285 |
|
286 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
287 \begin{frame}[t,fragile] |
|
288 \frametitle{Compiling AExps} |
|
289 |
|
290 \liningnums{\textbf{\Large\bl{1 + (2 + 3)}}} |
|
291 |
|
292 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm] |
|
293 ldc 1 |
|
294 ldc 2 |
|
295 ldc 3 |
|
296 iadd |
|
297 iadd |
|
298 \end{lstlisting} |
|
299 \bigskip\pause |
|
300 \vfill |
|
301 |
|
302 \textcolor{codepurple}{\textbf{\texttt{dadd}}}, |
|
303 \textcolor{codepurple}{\textbf{\texttt{fadd}}}, |
|
304 \textcolor{codepurple}{\textbf{\texttt{ladd}}}, \ldots |
|
305 |
|
306 \end{frame} |
|
307 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
308 |
|
309 |
|
310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
311 \begin{frame}[t] |
|
312 \frametitle{Compiling AExps} |
|
313 |
|
314 \begin{center} |
|
315 \bl{\begin{tabular}{@{}lcl@{}} |
|
316 $\text{compile}(n)$ & $\dn$ & $\text{ldc}\;n$\\ |
|
317 $\text{compile}(a_1 + a_2)$ & $\dn$\\ |
|
318 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\;\text{compile}(a_2)\;@\; \text{iadd}$}\smallskip\\ |
|
319 $\text{compile}(a_1 - a_2)$ & $\dn$\\ |
|
320 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{isub}$}\smallskip\\ |
|
321 $\text{compile}(a_1 * a_2)$ & $\dn$\\ |
|
322 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{imul}$}\smallskip\\ |
|
323 \end{tabular}} |
|
324 \end{center} |
|
325 |
|
326 \end{frame} |
|
327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
328 |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 \begin{frame}[t,fragile] |
|
331 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
332 |
|
333 \liningnums{\textbf{\Large\bl{1 $+$ 2 $*$ 3 $+$ (4 $-$ 3)}}} |
|
334 |
|
335 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm] |
|
336 ldc 1 |
|
337 ldc 2 |
|
338 ldc 3 |
|
339 imul |
|
340 ldc 4 |
|
341 ldc 3 |
|
342 isub |
|
343 iadd |
|
344 iadd |
|
345 \end{lstlisting} |
|
346 |
|
347 \end{frame} |
|
348 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
349 |
|
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
351 \begin{frame}[c] |
|
352 \frametitle{Variables} |
|
353 \liningnums{\textbf{\Large\bl{x $:=$ 5 $+$ y $*$ 2}}}\bigskip\pause |
|
354 |
|
355 \begin{itemize} |
|
356 \item lookup: \bl{$\textcolor{codepurple}{\textbf{\texttt{iload}}}\; index$} |
|
357 \item store: \bl{$\textcolor{codepurple}{\textbf{\texttt{istore}}}\; index$} |
|
358 \end{itemize}\bigskip\pause |
|
359 |
|
360 while compilating we have to maintain a map between our identifiers and the |
|
361 Java bytecode indices |
|
362 |
|
363 \begin{center} |
|
364 \bl{$\text{compile}(a, E)$} |
|
365 \end{center} |
|
366 |
|
367 \end{frame} |
|
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
369 |
|
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
371 \begin{frame}[t] |
|
372 \frametitle{Compiling AExps} |
|
373 |
|
374 \begin{center} |
|
375 \bl{\begin{tabular}{@{}lcl@{}} |
|
376 $\text{compile}(n, E)$ & $\dn$ & $\text{ldc}\;n$\\ |
|
377 $\text{compile}(a_1 + a_2, E)$ & $\dn$\\ |
|
378 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{iadd}$}\smallskip\\ |
|
379 $\text{compile}(a_1 - a_2, E)$ & $\dn$\\ |
|
380 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{isub}$}\smallskip\\ |
|
381 $\text{compile}(a_1 * a_2, E)$ & $\dn$\\ |
|
382 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{imul}$}\bigskip\\ |
|
383 $\text{compile}(x, E)$ & $\dn$ & $\text{iload}\;E(x)$\\ |
|
384 \end{tabular}} |
|
385 \end{center} |
|
386 |
|
387 \end{frame} |
|
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
389 |
|
390 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
391 \begin{frame}[c, fragile] |
|
392 \frametitle{Mathematical Functions} |
|
393 |
|
394 Compilation of some mathematical functions: |
|
395 |
|
396 \begin{center} |
|
397 \begin{tabular}{lcl} |
|
398 \texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\ |
|
399 \texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\ |
|
400 \texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\ |
|
401 \texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\ |
|
402 \texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\ |
|
403 \end{tabular} |
|
404 \end{center} |
|
405 |
|
406 \end{frame} |
|
407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
408 |
|
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
410 \begin{frame}[c] |
|
411 \frametitle{Compiling Statements} |
|
412 |
|
413 We return a list of instructions and an environment for the |
|
414 variables |
|
415 |
|
416 \begin{center} |
|
417 \bl{\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} |
|
418 $\text{compile}(\text{skip}, E)$ & $\dn$ & $(\textit{Nil}, E)$\bigskip\\ |
|
419 $\text{compile}(x := a, E)$ & $\dn$\\ |
|
420 \multicolumn{3}{l}{$(\text{compile}(a, E) \;@\;\text{istore}\;index, E(x\mapsto index))$}\\ |
|
421 \end{tabular}} |
|
422 \end{center}\medskip |
|
423 |
|
424 where \bl{$index$} is \bl{$E(x)$} if it is already defined, |
|
425 or if it is not, then the largest index not yet seen |
|
426 |
|
427 \end{frame} |
|
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
429 |
|
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
431 \begin{frame}[c,fragile] |
|
432 \frametitle{Compiling Assignments} |
|
433 |
|
434 \liningnums{\textbf{\Large\bl{x $:=$ x $+$ 1}}} |
|
435 |
|
436 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm] |
|
437 iload /*@\bl{$n_x$}@*/ |
|
438 ldc 1 |
|
439 iadd |
|
440 istore /*@\bl{$n_x$}@*/ |
|
441 \end{lstlisting}\medskip |
|
442 |
|
443 where \bl{$n_x$} is the index corresponding to the variable~\bl{$x$} |
|
444 |
|
445 \end{frame} |
|
446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
447 |
|
448 |
|
449 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
450 \begin{frame}[t] |
|
451 \frametitle{Compiling Ifs} |
|
452 |
|
453 {\Large\bl{$\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2$}}\bigskip\bigskip |
|
454 |
|
455 \onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:} |
|
456 |
|
457 \begin{center} |
|
458 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
459 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
460 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
461 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
462 \node (A1) [point] {}; |
|
463 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
464 \node (A2) [point, right=of b] {}; |
|
465 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; |
|
466 \node (A3) [point, right=of cs1] {}; |
|
467 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; |
|
468 \node (A4) [point, right=of cs2] {}; |
|
469 |
|
470 \only<2>{ |
|
471 \draw (A1) edge [->, red, line width=1mm] (b); |
|
472 \draw (b) edge [->, red, line width=1mm] (cs1); |
|
473 \draw (cs1) edge [->, red, line width=1mm] (A3); |
|
474 \draw (A3) edge [->,skip loop] (A4); |
|
475 \node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};} |
|
476 \only<3>{ |
|
477 \draw (A1) edge [->, red, line width=1mm] (b); |
|
478 \draw (b) edge [->, red, line width=1mm] (A2); |
|
479 \draw (A2) edge [skip loop] (A3); |
|
480 \draw (A3) edge [->, red, line width=1mm] (cs2); |
|
481 \draw (cs2) edge [->,red, line width=1mm] (A4); |
|
482 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} |
|
483 \end{tikzpicture} |
|
484 \end{center} |
|
485 |
|
486 \end{frame} |
|
487 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
488 |
|
489 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
490 \begin{frame}[t,fragile] |
|
491 \frametitle{Conditional Jumps} |
|
492 |
|
493 \begin{minipage}{1.1\textwidth} |
|
494 \begin{itemize} |
|
495 \item \textcolor{codepurple}{\textbf{\texttt{if\_icmpeq}}} \bl{$label$} |
|
496 if two ints are equal, then jump\medskip |
|
497 \item \textcolor{codepurple}{\textbf{\texttt{if\_icmpne}}} \bl{$label$} |
|
498 if two ints aren't equal, then jump\medskip |
|
499 \item \textcolor{codepurple}{\textbf{\texttt{if\_icmpge}}} \bl{$label$} |
|
500 if one int is greater or equal then another, then jump |
|
501 \item[]\ldots |
|
502 \end{itemize} |
|
503 \end{minipage}\pause |
|
504 |
|
505 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=2cm] |
|
506 /*@\bl{$L_1$:}@*/ |
|
507 if_icmpeq /*@\bl{$L_2$}@*/ |
|
508 iload 1 |
|
509 ldc 1 |
|
510 iadd |
|
511 if_icmpeq /*@\bl{$L_1$}@*/ |
|
512 /*@\bl{$L_2$:}@*/ |
|
513 \end{lstlisting} |
|
514 |
|
515 |
|
516 \begin{textblock}{3.5}(11,12) |
|
517 \only<3>{labels must be unique} |
|
518 \end{textblock} |
|
519 \end{frame} |
|
520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
521 |
|
522 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
523 \begin{frame}[c,fragile] |
|
524 \frametitle{Compiling Ifs} |
|
525 |
|
526 For example |
|
527 |
|
528 \begin{lstlisting}[mathescape,numbers=none,language=While] |
|
529 if 1 = 1 then x := 2 else y := 3 |
|
530 \end{lstlisting} |
|
531 |
|
532 |
|
533 \begin{center} |
|
534 \begin{lstlisting}[mathescape,language=JVMIS,numbers=none] |
|
535 ldc 1 |
|
536 ldc 1 |
|
537 if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$ |
|
538 ldc 2 |
|
539 istore 0 |
|
540 goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$ |
|
541 L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$ |
|
542 ldc 3 |
|
543 istore 1 |
|
544 L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$ |
|
545 \end{lstlisting} |
|
546 \end{center} |
|
547 |
|
548 \begin{tikzpicture}[remember picture,overlay] |
|
549 \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm) |
|
550 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east); |
|
551 \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm) |
|
552 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east); |
|
553 \end{tikzpicture} |
|
554 |
|
555 \end{frame} |
|
556 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
557 |
|
558 |
|
559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
560 \begin{frame}[t] |
|
561 \frametitle{Compiling BExps} |
|
562 |
|
563 {\Large\bl{$a_1 = a_2$}} |
|
564 |
|
565 \begin{center} |
|
566 \bl{\begin{tabular}{lcl} |
|
567 $\text{compile}(a_1 = a_2, E, lab)$ & $\dn$\\ |
|
568 \multicolumn{3}{l}{$\quad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{if\_icmpne}\;lab$} |
|
569 \end{tabular}} |
|
570 \end{center} |
|
571 |
|
572 \end{frame} |
|
573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
574 |
|
575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
576 \begin{frame}[c, fragile] |
|
577 \frametitle{Boolean Expressions} |
|
578 |
|
579 Compilation of boolean expressions: |
|
580 |
|
581 \begin{center} |
|
582 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
583 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
584 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
585 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
586 \node (A1) [point] {}; |
|
587 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
588 \node (A2) [point, right=of b] {}; |
|
589 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; |
|
590 \node (A3) [point, right=of cs1] {}; |
|
591 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; |
|
592 \node (A4) [point, right=of cs2] {}; |
|
593 |
|
594 \only<1>{ |
|
595 \draw (A1) edge [->, red, line width=1mm] (b); |
|
596 \draw (b) edge [->, red, line width=1mm] (A2); |
|
597 \draw (A2) edge [skip loop] (A3); |
|
598 \draw (A3) edge [->, red, line width=1mm] (cs2); |
|
599 \draw (cs2) edge [->,red, line width=1mm] (A4); |
|
600 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} |
|
601 \end{tikzpicture} |
|
602 \end{center} |
|
603 |
|
604 \begin{center} |
|
605 \begin{tabular}{lcl} |
|
606 \texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\ |
|
607 \texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\ |
|
608 \texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\ |
|
609 \texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\ |
|
610 \end{tabular} |
|
611 \end{center} |
|
612 |
|
613 \end{frame} |
|
614 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
615 |
|
616 |
|
617 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
618 \begin{frame}[t] |
|
619 \frametitle{Compiling Ifs} |
|
620 |
|
621 {\Large\bl{if $b$ then $cs_1$ else $cs_2$}} |
|
622 |
|
623 \begin{center} |
|
624 \bl{\begin{tabular}{lcl} |
|
625 $\text{compile}(\text{if}\;b\;\text{then}\; cs_1\;\text{else}\; cs_2, E)$ & $\dn$\\ |
|
626 \multicolumn{3}{l}{$\quad l_{ifelse}\;$ \textcolor{black}{(fresh label)}}\\ |
|
627 \multicolumn{3}{l}{$\quad l_{ifend}\;$ \textcolor{black}{(fresh label)}}\\ |
|
628 \multicolumn{3}{l}{$\quad (is_1, E') = \text{compile}(cs_1, E)$}\\ |
|
629 \multicolumn{3}{l}{$\quad (is_2, E'') = \text{compile}(cs_2, E')$}\\ |
|
630 \multicolumn{3}{l}{$\quad(\text{compile}(b, E, l_{ifelse})$}\\ |
|
631 \multicolumn{3}{l}{$\quad\phantom{(}@\;is_1$}\\ |
|
632 \multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{ifend}$}\\ |
|
633 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifelse}:$}\\ |
|
634 \multicolumn{3}{l}{$\quad\phantom{(}@\;is_2$}\\ |
|
635 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifend}:, E'')$}\\ |
|
636 \end{tabular}} |
|
637 \end{center} |
|
638 |
|
639 \end{frame} |
|
640 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
641 |
|
642 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
643 \begin{frame}[t] |
|
644 \frametitle{Compiling Whiles} |
|
645 |
|
646 {\Large\bl{$\text{while}\;b\;\text{do}\;cs$}}\bigskip\bigskip |
|
647 |
|
648 \onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:} |
|
649 |
|
650 \begin{center} |
|
651 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
652 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
653 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
654 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
655 \node (A0) [point, left=of A1] {}; |
|
656 \node (A1) [point] {}; |
|
657 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
658 \node (A2) [point, right=of b] {}; |
|
659 \node (cs1) [block, right=of A2] {code of \bl{$cs$}}; |
|
660 \node (A3) [point, right=of cs1] {}; |
|
661 \node (A4) [point, right=of A3] {}; |
|
662 |
|
663 \only<2>{ |
|
664 \draw (A0) edge [->, red, line width=1mm] (b); |
|
665 \draw (b) edge [->, red, line width=1mm] (cs1); |
|
666 \draw (cs1) edge [->, red, line width=1mm] (A3); |
|
667 \draw (A3) edge [->,skip loop] (A1);} |
|
668 \only<3>{ |
|
669 \draw (A0) edge [->, red, line width=1mm] (b); |
|
670 \draw (b) edge [->, red, line width=1mm] (A2); |
|
671 \draw (A2) edge [skip loop] (A3); |
|
672 \draw (A3) edge [->, red, line width=1mm] (A4);} |
|
673 \end{tikzpicture} |
|
674 \end{center} |
|
675 |
|
676 \end{frame} |
|
677 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
678 |
|
679 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
680 \begin{frame}[t] |
|
681 \frametitle{Compiling Whiles} |
|
682 |
|
683 {\Large\bl{while $b$ do $cs$}} |
|
684 |
|
685 \begin{center} |
|
686 \bl{\begin{tabular}{lcl} |
|
687 $\text{compile}(\text{while}\; b\; \text{do} \;cs, E)$ & $\dn$\\ |
|
688 \multicolumn{3}{l}{$\quad l_{wbegin}\;$ \textcolor{black}{(fresh label)}}\\ |
|
689 \multicolumn{3}{l}{$\quad l_{wend}\;$ \textcolor{black}{(fresh label)}}\\ |
|
690 \multicolumn{3}{l}{$\quad (is, E') = \text{compile}(cs_1, E)$}\\ |
|
691 \multicolumn{3}{l}{$\quad(l_{wbegin}:$}\\ |
|
692 \multicolumn{3}{l}{$\quad\phantom{(}@\;\text{compile}(b, E, l_{wend})$}\\ |
|
693 \multicolumn{3}{l}{$\quad\phantom{(}@\;is$}\\ |
|
694 \multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\ |
|
695 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{wend}:, E')$}\\ |
|
696 \end{tabular}} |
|
697 \end{center} |
|
698 |
|
699 \end{frame} |
|
700 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
701 |
|
702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
703 \begin{frame}[c,fragile] |
|
704 \frametitle{Compiling Whiles} |
|
705 |
|
706 For example |
|
707 |
|
708 \begin{lstlisting}[mathescape,numbers=none,language=While] |
|
709 while x <= 10 do x := x + 1 |
|
710 \end{lstlisting} |
|
711 |
|
712 |
|
713 \begin{center} |
|
714 \begin{lstlisting}[mathescape,language=JVMIS,numbers=none] |
|
715 L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$ |
|
716 iload 0 |
|
717 ldc 10 |
|
718 if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$ |
|
719 iload 0 |
|
720 ldc 1 |
|
721 iadd |
|
722 istore 0 |
|
723 goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$ |
|
724 L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$ |
|
725 \end{lstlisting} |
|
726 \end{center} |
|
727 |
|
728 \begin{tikzpicture}[remember picture,overlay] |
|
729 \draw[->,very thick] (LA) edge [->,to path={-- ++(12mm,0mm) |
|
730 -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east); |
|
731 \draw[->,very thick] (LC) edge [->,to path={-- ++(12mm,0mm) |
|
732 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east); |
|
733 \end{tikzpicture} |
|
734 |
|
735 \end{frame} |
|
736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
737 |
|
738 |
|
739 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
740 \begin{frame}[c,fragile] |
|
741 \frametitle{Compiling Writes} |
|
742 |
|
743 \small |
|
744 \begin{lstlisting}[language=JVMIS,mathescape, |
|
745 numbers=none,xleftmargin=-6mm] |
|
746 .method public static write(I)V |
|
747 .limit locals 1 |
|
748 .limit stack 2 |
|
749 getstatic java/lang/System/out |
|
750 Ljava/io/PrintStream; |
|
751 iload 0 |
|
752 invokevirtual java/io/PrintStream/println(I)V |
|
753 return |
|
754 .end method |
|
755 |
|
756 |
|
757 |
|
758 iload $E(x)$ |
|
759 invokestatic XXX/XXX/write(I)V |
|
760 \end{lstlisting} |
|
761 |
|
762 \end{frame} |
|
763 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
764 |
|
765 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
766 \begin{frame}[c,fragile] |
|
767 \frametitle{Compiling Main} |
|
768 |
|
769 \footnotesize |
|
770 \begin{lstlisting}[language=JVMIS,mathescape, |
|
771 numbers=none,xleftmargin=-6mm] |
|
772 .class public XXX.XXX |
|
773 .super java/lang/Object |
|
774 |
|
775 .method public <init>()V |
|
776 aload_0 |
|
777 invokenonvirtual java/lang/Object/<init>()V |
|
778 return |
|
779 .end method |
|
780 |
|
781 .method public static main([Ljava/lang/String;)V |
|
782 .limit locals 200 |
|
783 .limit stack 200 |
|
784 |
|
785 $\textit{\ldots{}here comes the compiled code\ldots}$ |
|
786 |
|
787 return |
|
788 .end method |
|
789 \end{lstlisting} |
|
790 |
|
791 \end{frame} |
|
792 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
793 |
|
794 |
|
795 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
796 \mode<presentation>{ |
|
797 \begin{frame}[c] |
|
798 \frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}} |
|
799 |
|
800 \begin{itemize} |
|
801 \item assembly $\Rightarrow$ byte code (class file) |
|
802 \item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip |
|
803 \item \texttt{javap} is a disassembler for class files |
|
804 \end{itemize} |
|
805 |
500 \end{frame}} |
806 \end{frame}} |
501 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
807 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
808 |
|
809 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
810 \mode<presentation>{ |
|
811 \begin{frame}[t] |
|
812 \frametitle{\begin{tabular}{c}Compiled Code\end{tabular}} |
|
813 |
|
814 \begin{center} |
|
815 \begin{tikzpicture} |
|
816 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
|
817 \addplot+[smooth] file {compiled.data}; |
|
818 \end{axis} |
|
819 \end{tikzpicture} |
|
820 \end{center} |
|
821 |
|
822 \end{frame}} |
|
823 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
824 |
|
825 |
|
826 |
|
827 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
828 \mode<presentation>{ |
|
829 \begin{frame}[t] |
|
830 \frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}} |
|
831 |
|
832 \begin{center} |
|
833 \begin{tikzpicture} |
|
834 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
|
835 xlabel=n, |
|
836 enlargelimits=0.05, |
|
837 ybar interval=0.7, legend style=small] |
|
838 \addplot file {interpreted2.data}; |
|
839 \addplot file {compiled2.data}; |
|
840 %\legend{interpreted, compiled} |
|
841 \end{axis} |
|
842 \end{tikzpicture} |
|
843 \end{center} |
|
844 |
|
845 \end{frame}} |
|
846 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
847 |
|
848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
849 \mode<presentation>{ |
|
850 \begin{frame}[c] |
|
851 \frametitle{Backend} |
|
852 |
|
853 \begin{center} |
|
854 \begin{tikzpicture} |
|
855 \node (rexp) {\bl{\bf Lexer}}; |
|
856 \node (nfa) [right=of rexp] {\bl{\bf Parser}}; |
|
857 \node (dfa) [right=of nfa] {\bl{\begin{tabular}{c}\bf Optimizations\end{tabular}}}; |
|
858 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm] |
|
859 sequence\end{tabular}} (nfa); |
|
860 \node (final) [below=of dfa] {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Byte Code\end{tabular}}}; |
|
861 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree |
|
862 \end{tabular}}(dfa); |
|
863 \path[->, red, line width=2mm] (dfa) edge (final); |
|
864 \end{tikzpicture}\\ |
|
865 \end{center} |
|
866 |
|
867 \end{frame}} |
|
868 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
869 |
|
870 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
871 \mode<presentation>{ |
|
872 \begin{frame}[t] |
|
873 \frametitle{\begin{tabular}{c}What is Next\end{tabular}} |
|
874 |
|
875 \begin{itemize} |
|
876 \item register spilling |
|
877 \item dead code removal |
|
878 \item loop optimisations |
|
879 \item instruction selection |
|
880 \item type checking |
|
881 \item concurrency |
|
882 \item fuzzy testing |
|
883 \item verification\bigskip\\ |
|
884 |
|
885 \item GCC, LLVM, tracing JITs |
|
886 \end{itemize} |
|
887 |
|
888 \end{frame}} |
|
889 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
502 |
890 |
503 |
891 |
504 \end{document} |
892 \end{document} |
505 |
893 |
506 %%% Local Variables: |
894 %%% Local Variables: |