137 |
163 |
138 \normalsize |
164 \normalsize |
139 \begin{center} |
165 \begin{center} |
140 \begin{tabular}{ll} |
166 \begin{tabular}{ll} |
141 Email: & christian.urban at kcl.ac.uk\\ |
167 Email: & christian.urban at kcl.ac.uk\\ |
142 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
168 Office: & S1.27 (1st floor Strand Building)\\ |
143 Slides: & KEATS (also home work is there)\\ |
169 Slides: & KEATS (also home work is there)\\ |
144 \end{tabular} |
170 \end{tabular} |
145 \end{center} |
171 \end{center} |
146 |
172 |
147 |
173 \end{frame}} |
148 \end{frame}} |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
175 |
150 |
176 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
177 \mode<presentation>{ |
152 \mode<presentation>{ |
178 \begin{frame}[c] |
153 \begin{frame}[c] |
179 |
154 \frametitle{\begin{tabular}{c}Building a ``Web Browser''\end{tabular}} |
180 Imagine the following situation: You talk to somebody |
155 |
181 and you find out that she/he has implemented a compiler.\smallskip |
156 Using a lexer: assume the following regular expressions |
182 |
|
183 What is your reaction? \pause Check all that apply.\bigskip |
|
184 |
|
185 \begin{itemize} |
|
186 \item[$\Box$] You think she/he is God |
|
187 \item[$\Box$] \"Uberhacker |
|
188 \item[$\Box$] superhuman |
|
189 \item[$\Box$] wizard |
|
190 \item[$\Box$] supremo |
|
191 \end{itemize} |
|
192 |
|
193 \end{frame}} |
|
194 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
195 |
|
196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
197 \mode<presentation>{ |
|
198 \begin{frame}[c] |
|
199 \frametitle{Bird's Eye View} |
|
200 |
|
201 \begin{center} |
|
202 \begin{tikzpicture} |
|
203 \node (rexp) {\bl{\bf Lexer}}; |
|
204 \node (nfa) [right=of rexp] {\bl{\bf Parser}}; |
|
205 \node (dfa) [right=of nfa] {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Byte Code\end{tabular}}}; |
|
206 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm] |
|
207 sequence\end{tabular}} (nfa); |
|
208 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree\end{tabular}}(dfa); |
|
209 \end{tikzpicture}\\ |
|
210 \end{center} |
|
211 |
|
212 \end{frame}} |
|
213 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
214 |
|
215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
216 \mode<presentation>{ |
|
217 \begin{frame}[c] |
|
218 |
|
219 \begin{center} |
|
220 \includegraphics[scale=0.7]{../pics/machine_code.jpg} |
|
221 \end{center} |
|
222 |
|
223 \end{frame}} |
|
224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
225 |
|
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
227 \mode<presentation>{ |
|
228 \begin{frame}[c] |
|
229 \frametitle{Assembly Code} |
|
230 \mbox{}\\[-20mm]\mbox{} |
|
231 |
|
232 \begin{center} |
|
233 \includegraphics[scale=0.7]{../pics/assembly.jpg} |
|
234 \end{center} |
|
235 |
|
236 \end{frame}} |
|
237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
238 |
|
239 |
|
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
241 \mode<presentation>{ |
|
242 \begin{frame}[c] |
|
243 |
|
244 \begin{center} |
|
245 \bl{\begin{tabular}{@{}lcl@{}} |
|
246 \textit{Stmt} & $\rightarrow$ & $\texttt{skip}$\\ |
|
247 & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\ |
|
248 & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\ |
|
249 & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\ |
|
250 & $|$ & \texttt{read}\;\textit{Id}\\ |
|
251 & $|$ & \texttt{write}\;\textit{Id}\\ |
|
252 & $|$ & \texttt{write}\;\textit{String}\medskip\\ |
|
253 \textit{Stmts} & $\rightarrow$ & \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\ |
|
254 & $|$ & \textit{Stmt}\medskip\\ |
|
255 \textit{Block} & $\rightarrow$ & \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\ |
|
256 & $|$ & \textit{Stmt}\medskip\\ |
|
257 \textit{AExp} & $\rightarrow$ & \ldots\\ |
|
258 \textit{BExp} & $\rightarrow$ & \ldots\\ |
|
259 \end{tabular}} |
|
260 \end{center} |
|
261 |
|
262 |
|
263 \end{frame}} |
|
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
265 |
|
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
267 \mode<presentation>{ |
|
268 \begin{frame}[c] |
|
269 \frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}} |
|
270 |
|
271 \mbox{}\\[-18mm]\mbox{} |
|
272 |
|
273 {\lstset{language=While}\fontsize{10}{12}\selectfont |
|
274 \texttt{\lstinputlisting{../progs/fib.while}}} |
|
275 |
|
276 \end{frame}} |
|
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
278 |
|
279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
280 \mode<presentation>{ |
|
281 \begin{frame}[c] |
|
282 \frametitle{\begin{tabular}{c}Interpreter\end{tabular}} |
|
283 |
|
284 \begin{center} |
|
285 \bl{\begin{tabular}{@{}lcl@{}} |
|
286 $\text{eval}(n, E)$ & $\dn$ & $n$\\ |
|
287 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\ |
|
288 $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\ |
|
289 $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\ |
|
290 $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\ |
|
291 $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\ |
|
292 $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\ |
|
293 $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\ |
|
294 \end{tabular}} |
|
295 \end{center} |
|
296 |
|
297 \end{frame}} |
|
298 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
299 |
|
300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
301 \mode<presentation>{ |
|
302 \begin{frame}[c] |
|
303 \frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}} |
|
304 |
|
305 \begin{center} |
|
306 \bl{\begin{tabular}{@{}lcl@{}} |
|
307 $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\ |
|
308 $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\ |
|
309 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\ |
|
310 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\; |
|
311 \text{eval}(cs_1,E)$}\\ |
|
312 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\ |
|
313 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\ |
|
314 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\ |
|
315 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\; |
|
316 \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\ |
|
317 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\ |
|
318 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\ |
|
319 \end{tabular}} |
|
320 \end{center} |
|
321 |
|
322 \end{frame}} |
|
323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
324 |
|
325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
326 \mode<presentation>{ |
|
327 \begin{frame}[c] |
|
328 \frametitle{\begin{tabular}{c}Test Program\end{tabular}} |
|
329 |
|
330 \mbox{}\\[-18mm]\mbox{} |
|
331 |
|
332 {\lstset{language=While}\fontsize{10}{12}\selectfont |
|
333 \texttt{\lstinputlisting{../progs/loops.while}}} |
|
334 |
|
335 \end{frame}} |
|
336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
337 |
|
338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
339 \mode<presentation>{ |
|
340 \begin{frame}[t] |
|
341 \frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}} |
|
342 |
|
343 \begin{center} |
|
344 \begin{tikzpicture} |
|
345 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
|
346 \addplot+[smooth] file {interpreted.data}; |
|
347 \end{axis} |
|
348 \end{tikzpicture} |
|
349 \end{center} |
|
350 |
|
351 \end{frame}} |
|
352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
353 |
|
354 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
355 \mode<presentation>{ |
|
356 \begin{frame}[c] |
|
357 \frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}} |
|
358 |
|
359 \begin{itemize} |
|
360 \item introduced in 1995 |
|
361 \item is a stack-based VM (like Postscript, CLR of .Net) |
|
362 \item contains a JIT compiler |
|
363 \item many languages take advantage of JVM's infrastructure (JRE) |
|
364 \item is garbage collected $\Rightarrow$ no buffer overflows |
|
365 \item some languages compiled to the JVM: Scala, Clojure\ldots |
|
366 \end{itemize} |
|
367 |
|
368 \end{frame}} |
|
369 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
370 |
|
371 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
372 \mode<presentation>{ |
|
373 \begin{frame}[t] |
|
374 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
375 |
|
376 {\Large\bl{1 + 2}} |
|
377 |
|
378 \begin{center} |
|
379 \bl{\begin{tabular}{l} |
|
380 ldc 1\\ |
|
381 ldc 2\\ |
|
382 iadd\\ |
|
383 \end{tabular}} |
|
384 \end{center}\end{frame}} |
|
385 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
386 |
|
387 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
388 \mode<presentation>{ |
|
389 \begin{frame}[t] |
|
390 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
391 |
|
392 {\Large\bl{1 + 2 + 3}} |
|
393 |
|
394 \begin{center} |
|
395 \bl{\begin{tabular}{l} |
|
396 ldc 1\\ |
|
397 ldc 2\\ |
|
398 iadd\\ |
|
399 ldc 3\\ |
|
400 iadd\\ |
|
401 \end{tabular}} |
|
402 \end{center} |
|
403 |
|
404 \end{frame}} |
|
405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
406 |
|
407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
408 \mode<presentation>{ |
|
409 \begin{frame}[t] |
|
410 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
411 |
|
412 {\Large\bl{1 + (2 + 3)}} |
|
413 |
|
414 \begin{center} |
|
415 \bl{\begin{tabular}{l} |
|
416 ldc 1\\ |
|
417 ldc 2\\ |
|
418 ldc 3\\ |
|
419 iadd\\ |
|
420 iadd\\ |
|
421 \end{tabular}} |
|
422 \end{center}\bigskip\pause |
|
423 \vfill |
|
424 |
|
425 \bl{dadd, fadd, ladd, \ldots} |
|
426 |
|
427 \end{frame}} |
|
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
429 |
|
430 |
|
431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
432 \mode<presentation>{ |
|
433 \begin{frame}[t] |
|
434 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
435 |
|
436 \begin{center} |
|
437 \bl{\begin{tabular}{@{}lcl@{}} |
|
438 $\text{compile}(n)$ & $\dn$ & $\text{ldc}\;n$\\ |
|
439 $\text{compile}(a_1 + a_2)$ & $\dn$\\ |
|
440 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\;\text{compile}(a_2)\;@\; \text{iadd}$}\smallskip\\ |
|
441 $\text{compile}(a_1 - a_2)$ & $\dn$\\ |
|
442 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{isub}$}\smallskip\\ |
|
443 $\text{compile}(a_1 * a_2)$ & $\dn$\\ |
|
444 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{imul}$}\smallskip\\ |
|
445 \end{tabular}} |
|
446 \end{center}\pause |
|
447 |
|
448 \end{frame}} |
|
449 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
450 |
|
451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
452 \mode<presentation>{ |
|
453 \begin{frame}[t] |
|
454 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
455 |
|
456 {\Large\bl{1 + 2 * 3 + (4 - 3)}} |
|
457 |
|
458 \begin{center} |
|
459 \bl{\begin{tabular}{l} |
|
460 ldc 1\\ |
|
461 ldc 2\\ |
|
462 ldc 3\\ |
|
463 imul\\ |
|
464 ldc 4\\ |
|
465 ldc 3\\ |
|
466 isub\\ |
|
467 iadd\\ |
|
468 iadd\\ |
|
469 \end{tabular}} |
|
470 \end{center} |
|
471 |
|
472 \end{frame}} |
|
473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
474 |
|
475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
476 \mode<presentation>{ |
|
477 \begin{frame}[t] |
|
478 \frametitle{\begin{tabular}{c}Variables\end{tabular}} |
|
479 |
|
480 {\Large\bl{$x := 5 + y * 2$}}\bigskip\pause |
|
481 |
|
482 \begin{itemize} |
|
483 \item lookup: \bl{$\text{iload}\; index$} |
|
484 \item store: \bl{$\text{istore}\; index$} |
|
485 \end{itemize}\bigskip\pause |
|
486 |
|
487 while compilating we have to maintain a map between our identifiers and the |
|
488 Java bytecode indices |
|
489 |
|
490 \begin{center} |
|
491 \bl{$\text{compile}(a, E)$} |
|
492 \end{center} |
|
493 |
|
494 \end{frame}} |
|
495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
496 |
|
497 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
498 \mode<presentation>{ |
|
499 \begin{frame}[t] |
|
500 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
501 |
|
502 \begin{center} |
|
503 \bl{\begin{tabular}{@{}lcl@{}} |
|
504 $\text{compile}(n, E)$ & $\dn$ & $\text{ldc}\;n$\\ |
|
505 $\text{compile}(a_1 + a_2, E)$ & $\dn$\\ |
|
506 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\;\text{compile}(a_2. E)\;@\; \text{iadd}$}\smallskip\\ |
|
507 $\text{compile}(a_1 - a_2, E)$ & $\dn$\\ |
|
508 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{isub}$}\smallskip\\ |
|
509 $\text{compile}(a_1 * a_2, E)$ & $\dn$\\ |
|
510 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{imul}$}\bigskip\\ |
|
511 $\text{compile}(x, E)$ & $\dn$ & $\text{iload}\;E(x)$\\ |
|
512 \end{tabular}} |
|
513 \end{center}\pause |
|
514 |
|
515 \end{frame}} |
|
516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
517 |
|
518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
519 \mode<presentation>{ |
|
520 \begin{frame}[t] |
|
521 \frametitle{\begin{tabular}{c}Compiling Statements\end{tabular}} |
|
522 |
|
523 We return a list of instructions and an environment for the variables |
|
524 |
|
525 \begin{center} |
|
526 \bl{\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} |
|
527 $\text{compile}(\text{skip}, E)$ & $\dn$ & $(N\!il, E)$\bigskip\\ |
|
528 $\text{compile}(x := a, E)$ & $\dn$\\ |
|
529 \multicolumn{3}{l}{$(\text{compile}(a, E) \;@\;\text{istore}\;index, E(x\mapsto index))$}\\ |
|
530 \end{tabular}} |
|
531 \end{center}\medskip |
|
532 |
|
533 where \bl{$index$} is \bl{$E(x)$} if it is already defined, or if it is not then the largest index not yet seen |
|
534 |
|
535 \end{frame}} |
|
536 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
537 |
|
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
539 \mode<presentation>{ |
|
540 \begin{frame}[t] |
|
541 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
542 |
|
543 {\Large\bl{$x := x + 1$}} |
|
544 |
|
545 \begin{center} |
|
546 \bl{\begin{tabular}{l} |
|
547 iload $n_x$\\ |
|
548 ldc 1\\ |
|
549 iadd\\ |
|
550 istore $n_x$\\ |
|
551 \end{tabular}} |
|
552 \end{center} |
|
553 |
|
554 where \bl{$n_x$} is the index corresponding to the variable \bl{$x$} |
|
555 |
|
556 \end{frame}} |
|
557 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
558 |
|
559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
560 \mode<presentation>{ |
|
561 \begin{frame}[t] |
|
562 \frametitle{\begin{tabular}{c}Compiling Ifs\end{tabular}} |
|
563 |
|
564 {\Large\bl{$\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2$}}\bigskip\bigskip |
|
565 |
|
566 \onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:} |
|
567 |
|
568 \begin{center} |
|
569 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
570 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
571 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
572 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
573 \node (A1) [point] {}; |
|
574 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
575 \node (A2) [point, right=of b] {}; |
|
576 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; |
|
577 \node (A3) [point, right=of cs1] {}; |
|
578 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; |
|
579 \node (A4) [point, right=of cs2] {}; |
|
580 |
|
581 \only<2>{ |
|
582 \draw (A1) edge [->, red, line width=1mm] (b); |
|
583 \draw (b) edge [->, red, line width=1mm] (cs1); |
|
584 \draw (cs1) edge [->, red, line width=1mm] (A3); |
|
585 \draw (A3) edge [->,skip loop] (A4); |
|
586 \node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};} |
|
587 \only<3>{ |
|
588 \draw (A1) edge [->, red, line width=1mm] (b); |
|
589 \draw (b) edge [->, red, line width=1mm] (A2); |
|
590 \draw (A2) edge [skip loop] (A3); |
|
591 \draw (A3) edge [->, red, line width=1mm] (cs2); |
|
592 \draw (cs2) edge [->,red, line width=1mm] (A4); |
|
593 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} |
|
594 \end{tikzpicture} |
|
595 \end{center} |
|
596 |
|
597 |
|
598 \end{frame}} |
|
599 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
600 |
|
601 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
602 \mode<presentation>{ |
|
603 \begin{frame}[c] |
|
604 \frametitle{\begin{tabular}{c}Conditional Jumps\end{tabular}} |
|
605 |
|
606 \begin{minipage}{1.1\textwidth} |
|
607 \begin{itemize} |
|
608 \item \bl{if\_icmpeq $label$} if two ints are equal, then jump\medskip |
|
609 \item \bl{if\_icmpne $label$} if two ints aren't equal, then jump\medskip |
|
610 \item \bl{if\_icmpge $label$} if one int is greater or equal then another, then jump |
|
611 \item[]\ldots |
|
612 \end{itemize} |
|
613 \end{minipage}\pause |
|
614 |
|
615 |
|
616 \begin{center} |
|
617 \bl{\begin{tabular}{l} |
|
618 $L_1$:\\ |
|
619 \hspace{5mm}if\_icmpeq\;$L_2$\\ |
|
620 \hspace{5mm}iload 1\\ |
|
621 \hspace{5mm}ldc 1\\ |
|
622 \hspace{5mm}iadd\\ |
|
623 \hspace{5mm}if\_icmpeq\;$L_1$\\ |
|
624 $L_2$: |
|
625 \end{tabular}} |
|
626 \end{center} |
|
627 |
|
628 \begin{textblock}{3.5}(11,12) |
|
629 \only<3>{labels must be unique} |
|
630 \end{textblock} |
|
631 \end{frame}} |
|
632 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
633 |
|
634 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
635 \mode<presentation>{ |
|
636 \begin{frame}[t] |
|
637 \frametitle{\begin{tabular}{c}Compiling BExps\end{tabular}} |
|
638 |
|
639 {\Large\bl{$a_1 = a_2$}} |
157 |
640 |
158 \begin{center} |
641 \begin{center} |
159 \bl{\begin{tabular}{lcl} |
642 \bl{\begin{tabular}{lcl} |
160 $SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\ |
643 $\text{compile}(a_1 = a_2, E, lab)$ & $\dn$\\ |
161 $W\!O\!RD$ & $\dn$ & $SY\!M^+$\\ |
644 \multicolumn{3}{l}{$\quad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{if\_icmpne}\;lab$} |
162 $BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\ |
645 \end{tabular}} |
163 $ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\ |
646 \end{center} |
164 $W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\ |
647 |
165 \end{tabular}} |
648 \end{frame}} |
166 \end{center} |
649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
167 |
650 |
168 \end{frame}} |
651 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
652 \mode<presentation>{ |
170 |
653 \begin{frame}[t] |
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
654 \frametitle{\begin{tabular}{c}Compiling Ifs\end{tabular}} |
172 \mode<presentation>{ |
655 |
173 \begin{frame}[c] |
656 {\Large\bl{if $b$ then $cs_1$ else $cs_2$}} |
174 \frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}} |
657 |
|
658 \begin{center} |
|
659 \bl{\begin{tabular}{lcl} |
|
660 $\text{compile}(\text{if}\;b\;\text{then}\; cs_1\;\text{else}\; cs_2, E)$ & $\dn$\\ |
|
661 \multicolumn{3}{l}{$\quad l_{ifelse}\;$ \textcolor{black}{(fresh label)}}\\ |
|
662 \multicolumn{3}{l}{$\quad l_{ifend}\;$ \textcolor{black}{(fresh label)}}\\ |
|
663 \multicolumn{3}{l}{$\quad (is_1, E') = \text{compile}(cs_1, E)$}\\ |
|
664 \multicolumn{3}{l}{$\quad (is_2, E'') = \text{compile}(cs_2, E')$}\\ |
|
665 \multicolumn{3}{l}{$\quad(\text{compile}(b, E, l_{ifelse})$}\\ |
|
666 \multicolumn{3}{l}{$\quad\phantom{(}@\;is_1$}\\ |
|
667 \multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{ifend}$}\\ |
|
668 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifelse}:$}\\ |
|
669 \multicolumn{3}{l}{$\quad\phantom{(}@\;is_2$}\\ |
|
670 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifend}:, E'')$}\\ |
|
671 \end{tabular}} |
|
672 \end{center} |
|
673 |
|
674 \end{frame}} |
|
675 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
676 |
|
677 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
678 \mode<presentation>{ |
|
679 \begin{frame}[t] |
|
680 \frametitle{\begin{tabular}{c}Compiling Whiles\end{tabular}} |
|
681 |
|
682 {\Large\bl{$\text{while}\;b\;\text{do}\;cs$}}\bigskip\bigskip |
|
683 |
|
684 \onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:} |
|
685 |
|
686 \begin{center} |
|
687 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
688 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
689 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
690 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
691 \node (A0) [point, left=of A1] {}; |
|
692 \node (A1) [point] {}; |
|
693 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
694 \node (A2) [point, right=of b] {}; |
|
695 \node (cs1) [block, right=of A2] {code of \bl{$cs$}}; |
|
696 \node (A3) [point, right=of cs1] {}; |
|
697 \node (A4) [point, right=of A3] {}; |
|
698 |
|
699 \only<2>{ |
|
700 \draw (A0) edge [->, red, line width=1mm] (b); |
|
701 \draw (b) edge [->, red, line width=1mm] (cs1); |
|
702 \draw (cs1) edge [->, red, line width=1mm] (A3); |
|
703 \draw (A3) edge [->,skip loop] (A1);} |
|
704 \only<3>{ |
|
705 \draw (A0) edge [->, red, line width=1mm] (b); |
|
706 \draw (b) edge [->, red, line width=1mm] (A2); |
|
707 \draw (A2) edge [skip loop] (A3); |
|
708 \draw (A3) edge [->, red, line width=1mm] (A4);} |
|
709 \end{tikzpicture} |
|
710 \end{center} |
|
711 |
|
712 |
|
713 \end{frame}} |
|
714 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
715 |
|
716 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
717 \mode<presentation>{ |
|
718 \begin{frame}[t] |
|
719 \frametitle{\begin{tabular}{c}Compiling Whiles\end{tabular}} |
|
720 |
|
721 {\Large\bl{while $b$ do $cs$}} |
|
722 |
|
723 \begin{center} |
|
724 \bl{\begin{tabular}{lcl} |
|
725 $\text{compile}(\text{while}\; b\; \text{do} \;cs, E)$ & $\dn$\\ |
|
726 \multicolumn{3}{l}{$\quad l_{wbegin}\;$ \textcolor{black}{(fresh label)}}\\ |
|
727 \multicolumn{3}{l}{$\quad l_{wend}\;$ \textcolor{black}{(fresh label)}}\\ |
|
728 \multicolumn{3}{l}{$\quad (is, E') = \text{compile}(cs_1, E)$}\\ |
|
729 \multicolumn{3}{l}{$\quad(l_{wbegin}:$}\\ |
|
730 \multicolumn{3}{l}{$\quad\phantom{(}@\;\text{compile}(b, E, l_{wend})$}\\ |
|
731 \multicolumn{3}{l}{$\quad\phantom{(}@\;is$}\\ |
|
732 \multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\ |
|
733 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{wend}:, E')$}\\ |
|
734 \end{tabular}} |
|
735 \end{center} |
|
736 |
|
737 \end{frame}} |
|
738 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
739 |
|
740 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
741 \mode<presentation>{ |
|
742 \begin{frame}[t] |
|
743 \frametitle{\begin{tabular}{c}Compiling Writes\end{tabular}} |
|
744 |
|
745 {\Large\bl{write $x$}} |
|
746 |
|
747 \begin{center} |
|
748 \small\bl{\begin{tabular}{l} |
|
749 .method public static write(I)V\hspace{1cm}\textcolor{black}{(library function)}\\ |
|
750 \;\; .limit locals 5 \\ |
|
751 \;\; .limit stack 5 \\ |
|
752 \;\; iload 0 \\ |
|
753 \;\; getstatic java/lang/System/out Ljava/io/PrintStream;\\ |
|
754 \;\; swap \\ |
|
755 \;\; invokevirtual java/io/PrintStream/println(I)V \\ |
|
756 \;\; return \\ |
|
757 .end method\bigskip\bigskip\\ |
|
758 % |
|
759 \normalsize |
|
760 iload $E(x)$\\ |
|
761 invokestatic write(I)V\\ |
|
762 \end{tabular}} |
|
763 \end{center} |
|
764 |
|
765 \end{frame}} |
|
766 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
767 |
|
768 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
769 \mode<presentation>{ |
|
770 \begin{frame}[c] |
|
771 |
|
772 \begin{center} |
|
773 \small\bl{\begin{tabular}{l} |
|
774 .class public XXX.XXX\\ |
|
775 .super java/lang/Object\\ |
|
776 \\ |
|
777 .method public <init>()V\\ |
|
778 \;\; aload\_0\\ |
|
779 \;\; invokenonvirtual java/lang/Object/<init>()V\\ |
|
780 \;\; return\\ |
|
781 .end method\\ |
|
782 \\ |
|
783 .method public static main([Ljava/lang/String;)V\\ |
|
784 \;\; .limit locals 200\\ |
|
785 \;\; .limit stack 200\\ |
|
786 \\ |
|
787 \textcolor{black}{(here comes the compiled code)}\\ |
|
788 \\ |
|
789 \;\; return\\ |
|
790 .end method\\ |
|
791 \end{tabular}} |
|
792 \end{center} |
|
793 |
|
794 \end{frame}} |
|
795 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
796 |
|
797 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
798 \mode<presentation>{ |
|
799 \begin{frame}[c] |
|
800 \frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}} |
175 |
801 |
176 \begin{itemize} |
802 \begin{itemize} |
177 \item the text should be formatted consistently up to a specified width, say 60 characters |
803 \item assembly $\Rightarrow$ byte code (class file) |
178 \item potential linebreaks are inserted by the formatter (not the input) |
804 \item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip |
179 \item repeated whitespaces are ``condensed'' to a single whitepace |
805 \item \texttt{javap} is a disassembler for class files |
180 \item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$} start/end paragraph |
|
181 \item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$} start/end bold |
|
182 \item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$} start/end red (cyan, etc) |
|
183 |
|
184 |
|
185 \end{itemize} |
806 \end{itemize} |
186 |
807 |
187 \end{frame}} |
808 \end{frame}} |
188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
809 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
189 |
810 |
190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
811 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
191 \mode<presentation>{ |
812 \mode<presentation>{ |
192 \begin{frame}[c] |
813 \begin{frame}[t] |
193 \frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}} |
814 \frametitle{\begin{tabular}{c}Compiled Code\end{tabular}} |
194 |
815 |
195 The lexer cannot prevent errors like |
816 \begin{center} |
196 |
817 \begin{tikzpicture} |
197 \begin{center} |
818 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
198 \bl{$<\!b\!>$} \ldots \bl{$<\!p\!>$} \ldots \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!\slash{}p\!>$} |
819 \addplot+[smooth] file {compiled.data}; |
199 \end{center} |
820 \end{axis} |
200 |
821 \end{tikzpicture} |
201 or |
822 \end{center} |
202 |
823 |
203 \begin{center} |
824 \end{frame}} |
204 \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!b\!>$} |
825 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
205 \end{center} |
826 |
206 |
827 |
207 |
828 |
208 \end{frame}} |
829 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
830 \mode<presentation>{ |
210 |
831 \begin{frame}[t] |
211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
832 \frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}} |
212 \mode<presentation>{ |
833 |
213 \begin{frame}[c] |
834 \begin{center} |
214 \frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}} |
835 \begin{tikzpicture} |
215 |
836 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
216 Parser combinators: \bigskip |
837 xlabel=n, |
217 |
838 enlargelimits=0.05, |
218 \begin{minipage}{1.1\textwidth} |
839 ybar interval=0.7, legend style=small] |
219 \begin{center} |
840 \addplot file {interpreted2.data}; |
220 \mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} |
841 \addplot file {compiled2.data}; |
221 $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$ |
842 %\legend{interpreted, compiled} |
222 \end{center} |
843 \end{axis} |
223 \end{minipage}\bigskip |
844 \end{tikzpicture} |
|
845 \end{center} |
|
846 |
|
847 \end{frame}} |
|
848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
849 |
|
850 |
|
851 |
|
852 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
853 \mode<presentation>{ |
|
854 \begin{frame}[t] |
|
855 \frametitle{\begin{tabular}{c}What Next\end{tabular}} |
224 |
856 |
225 \begin{itemize} |
857 \begin{itemize} |
226 \item sequencing |
858 \item register spilling |
227 \item alternative |
859 \item dead code removal |
228 \item semantic action |
860 \item loop optimisations |
|
861 \item instruction selection |
|
862 \item type checking |
|
863 \item concurrency |
|
864 \item fuzzy testing |
|
865 \item verification\bigskip\\ |
|
866 |
|
867 \item GCC, LLVM, tracing JITs |
229 \end{itemize} |
868 \end{itemize} |
230 |
869 |
231 \end{frame}} |
870 \end{frame}} |
232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
233 |
|
234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
235 \mode<presentation>{ |
|
236 \begin{frame}[c] |
|
237 |
|
238 Alternative parser (code \bl{$p\;||\;q$})\bigskip |
|
239 |
|
240 \begin{itemize} |
|
241 \item apply \bl{$p$} and also \bl{$q$}; then combine the outputs |
|
242 \end{itemize} |
|
243 |
|
244 \begin{center} |
|
245 \large \bl{$p(\text{input}) \cup q(\text{input})$} |
|
246 \end{center} |
|
247 |
|
248 |
|
249 \end{frame}} |
|
250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
251 |
|
252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
253 \mode<presentation>{ |
|
254 \begin{frame}[c] |
|
255 |
|
256 Sequence parser (code \bl{$p\sim q$})\bigskip |
|
257 |
|
258 \begin{itemize} |
|
259 \item apply first \bl{$p$} producing a set of pairs |
|
260 \item then apply \bl{$q$} to the unparsed parts |
|
261 \item then combine the results:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part) |
|
262 \end{itemize} |
|
263 |
|
264 \begin{center} |
|
265 \begin{tabular}{l} |
|
266 \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] |
|
267 \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm] |
|
268 \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$} |
|
269 \end{tabular} |
|
270 \end{center} |
|
271 |
|
272 |
|
273 \end{frame}} |
|
274 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
275 |
|
276 |
|
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
278 \mode<presentation>{ |
|
279 \begin{frame}[c] |
|
280 |
|
281 Function parser (code \bl{$p \Longrightarrow f$})\bigskip |
|
282 |
|
283 \begin{itemize} |
|
284 \item apply \bl{$p$} producing a set of pairs |
|
285 \item then apply the function \bl{$f$} to each first component |
|
286 \end{itemize} |
|
287 |
|
288 \begin{center} |
|
289 \begin{tabular}{l} |
|
290 \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$} |
|
291 \end{tabular} |
|
292 \end{center}\bigskip\bigskip\pause |
|
293 |
|
294 \bl{$f$} is the semantic action (``what to do with the parsed input'') |
|
295 |
|
296 \end{frame}} |
|
297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
298 |
|
299 |
|
300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
301 \mode<presentation>{ |
|
302 \begin{frame}[c] |
|
303 |
|
304 Token parser:\bigskip |
|
305 |
|
306 \begin{itemize} |
|
307 \item if the input is |
|
308 |
|
309 \begin{center} |
|
310 \large \bl{$tok_1:: tok_2 :: \ldots :: tok_n$} |
|
311 \end{center} |
|
312 |
|
313 then return |
|
314 |
|
315 \begin{center} |
|
316 \large \bl{$\{(tok_1,\; tok_2 :: \ldots :: tok_n)\}$} |
|
317 \end{center} |
|
318 |
|
319 or |
|
320 |
|
321 \begin{center} |
|
322 \large \bl{$\{\}$} |
|
323 \end{center} |
|
324 |
|
325 if \bl{$tok_1$} is not the right token we are looking for |
|
326 \end{itemize} |
|
327 |
|
328 |
|
329 |
|
330 \end{frame}} |
|
331 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
332 |
|
333 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
334 \mode<presentation>{ |
|
335 \begin{frame}[c] |
|
336 |
|
337 Number-Token parser:\bigskip |
|
338 |
|
339 \begin{itemize} |
|
340 \item if the input is |
|
341 |
|
342 \begin{center} |
|
343 \large \bl{$num\_tok(42):: tok_2 :: \ldots :: tok_n$} |
|
344 \end{center} |
|
345 |
|
346 then return |
|
347 |
|
348 \begin{center} |
|
349 \large \bl{$\{(42,\; tok_2 :: \ldots :: tok_n)\}$} |
|
350 \end{center} |
|
351 |
|
352 or |
|
353 |
|
354 \begin{center} |
|
355 \large \bl{$\{\}$} |
|
356 \end{center} |
|
357 |
|
358 if \bl{$tok_1$} is not the right token we are looking for |
|
359 \end{itemize}\pause |
|
360 |
|
361 \begin{center} |
|
362 list of tokens \bl{$\Rightarrow$} set of (\alert{int}, list of tokens) |
|
363 \end{center} |
|
364 |
|
365 \end{frame}} |
|
366 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
367 |
|
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
369 \mode<presentation>{ |
|
370 \begin{frame}[c] |
|
371 |
|
372 \begin{itemize} |
|
373 \item if the input is |
|
374 |
|
375 \begin{center} |
|
376 \begin{tabular}{l} |
|
377 \large \bl{$num\_tok(42)::$}\\ |
|
378 \hspace{7mm}\large \bl{$num\_tok(3) ::$}\\ |
|
379 \hspace{14mm}\large \bl{$tok_3 :: \ldots :: tok_n$} |
|
380 \end{tabular} |
|
381 \end{center} |
|
382 |
|
383 and the parser is |
|
384 |
|
385 \begin{center} |
|
386 \bl{$ntp \sim ntp$} |
|
387 \end{center} |
|
388 |
|
389 the successful output will be |
|
390 |
|
391 \begin{center} |
|
392 \large \bl{$\{((42, 3),\; tok_2 :: \ldots :: tok_n)\}$} |
|
393 \end{center}\pause |
|
394 |
|
395 Now we can form |
|
396 \begin{center} |
|
397 \bl{$(ntp \sim ntp) \Longrightarrow f$} |
|
398 \end{center} |
|
399 |
|
400 where \bl{$f$} is the semantic action (``what to do with the pair'') |
|
401 |
|
402 \end{itemize} |
|
403 |
|
404 \end{frame}} |
|
405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
406 |
|
407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
408 \mode<presentation>{ |
|
409 \begin{frame}[c] |
|
410 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}} |
|
411 |
|
412 Addition |
|
413 |
|
414 \begin{center} |
|
415 \bl{$T \sim + \sim E \Longrightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$} |
|
416 \end{center}\pause |
|
417 |
|
418 Multiplication |
|
419 |
|
420 \begin{center} |
|
421 \bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$} |
|
422 \end{center}\pause |
|
423 |
|
424 Parenthesis |
|
425 |
|
426 \begin{center} |
|
427 \bl{$\text{(} \sim E \sim \text{)} \Longrightarrow f((x,y), z) \Rightarrow y$} |
|
428 \end{center} |
|
429 |
|
430 \end{frame}} |
|
431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
432 |
|
433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
434 \mode<presentation>{ |
|
435 \begin{frame}[c] |
|
436 \frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}} |
|
437 |
|
438 \begin{itemize} |
|
439 \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$}, |
|
440 then \bl{$p \sim q$} returns results of type |
|
441 |
|
442 \begin{center} |
|
443 \bl{$T \times S$} |
|
444 \end{center}\pause |
|
445 |
|
446 \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then \bl{$q$} \alert{must} also have results of type \bl{$T$}, |
|
447 and \bl{$p \;||\; q$} returns results of type |
|
448 |
|
449 \begin{center} |
|
450 \bl{$T$} |
|
451 \end{center}\pause |
|
452 |
|
453 \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from |
|
454 \bl{$T$} to \bl{$S$}, then |
|
455 \bl{$p \Longrightarrow f$} returns results of type |
|
456 |
|
457 \begin{center} |
|
458 \bl{$S$} |
|
459 \end{center} |
|
460 |
|
461 \end{itemize} |
|
462 |
|
463 \end{frame}} |
|
464 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
871 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
465 |
872 |
466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
467 \mode<presentation>{ |
|
468 \begin{frame}[c] |
|
469 \frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}} |
|
470 |
|
471 \begin{itemize} |
|
472 \item input: \alert{list of tokens} |
|
473 \item output: set of (output\_type, \alert{list of tokens}) |
|
474 \end{itemize}\bigskip\pause |
|
475 |
|
476 actually it can be any input type as long as it is a kind of sequence |
|
477 (for example a string) |
|
478 |
|
479 \end{frame}} |
|
480 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
481 |
|
482 |
|
483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
484 \mode<presentation>{ |
|
485 \begin{frame}[c] |
|
486 \frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}} |
|
487 |
|
488 \begin{itemize} |
|
489 \item input: \alert{string} |
|
490 \item output: set of (output\_type, \alert{string}) |
|
491 \end{itemize}\bigskip |
|
492 |
|
493 but lexers are better when whitespaces or comments need to be filtered out |
|
494 |
|
495 \end{frame}} |
|
496 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
497 |
|
498 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
499 \mode<presentation>{ |
|
500 \begin{frame}[c] |
|
501 \frametitle{\begin{tabular}{c}Successful Parses\end{tabular}} |
|
502 |
|
503 \begin{itemize} |
|
504 \item input: string |
|
505 \item output: \alert{set of} (output\_type, string) |
|
506 \end{itemize}\bigskip |
|
507 |
|
508 a parse is successful whenever the input has been |
|
509 fully ``consumed'' (that is the second component is empty) |
|
510 |
|
511 |
|
512 \end{frame}} |
|
513 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
514 |
|
515 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
516 \mode<presentation>{ |
|
517 \begin{frame}[c] |
|
518 {\lstset{language=Scala}\fontsize{10}{12}\selectfont |
|
519 \texttt{\lstinputlisting{app7.scala}}} |
|
520 \end{frame}} |
|
521 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
522 |
|
523 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
524 \mode<presentation>{ |
|
525 \begin{frame}[c] |
|
526 {\lstset{language=Scala}\fontsize{10}{12}\selectfont |
|
527 \texttt{\lstinputlisting{app7.scala}}} |
|
528 \end{frame}} |
|
529 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
530 |
|
531 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
532 \mode<presentation>{ |
|
533 \begin{frame}[c] |
|
534 {\lstset{language=Scala}\fontsize{10}{12}\selectfont |
|
535 \texttt{\lstinputlisting{app8.scala}}} |
|
536 \end{frame}} |
|
537 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
538 |
|
539 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
540 \mode<presentation>{ |
|
541 \begin{frame}[c] |
|
542 \frametitle{\begin{tabular}{c}Two Grammars\end{tabular}} |
|
543 |
|
544 Which languages are recognised by the following two grammars? |
|
545 |
|
546 \begin{center} |
|
547 \bl{\begin{tabular}{lcl} |
|
548 $S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\ |
|
549 & $|$ & $\epsilon$ |
|
550 \end{tabular}} |
|
551 \end{center}\bigskip |
|
552 |
|
553 \begin{center} |
|
554 \bl{\begin{tabular}{lcl} |
|
555 $U$ & $\rightarrow$ & $1 \cdot U$\\ |
|
556 & $|$ & $\epsilon$ |
|
557 \end{tabular}} |
|
558 \end{center} |
|
559 |
|
560 \end{frame}} |
|
561 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
562 |
|
563 |
|
564 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
565 \mode<presentation>{ |
|
566 \begin{frame}[t] |
|
567 \frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} |
|
568 |
|
569 \mbox{}\\[-25mm]\mbox{} |
|
570 |
|
571 \begin{center} |
|
572 \begin{tikzpicture}[y=.2cm, x=.009cm] |
|
573 %axis |
|
574 \draw (0,0) -- coordinate (x axis mid) (1000,0); |
|
575 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
576 %ticks |
|
577 \foreach \x in {0, 20, 100, 200,...,1000} |
|
578 \draw (\x,1pt) -- (\x,-3pt) |
|
579 node[anchor=north] {\small \x}; |
|
580 \foreach \y in {0,5,...,30} |
|
581 \draw (1pt,\y) -- (-3pt,\y) |
|
582 node[anchor=east] {\small\y}; |
|
583 %labels |
|
584 \node[below=0.6cm] at (x axis mid) {\bl{1}s}; |
|
585 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
586 |
|
587 %plots |
|
588 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
589 file {s-grammar1.data}; |
|
590 \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
591 file {s-grammar2.data};} |
|
592 %legend |
|
593 \begin{scope}[shift={(400,20)}] |
|
594 \draw[color=blue] (0,0) -- |
|
595 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
596 node[right]{\small unambiguous}; |
|
597 \only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- |
|
598 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
599 node[right]{\small ambiguous};} |
|
600 \end{scope} |
|
601 \end{tikzpicture} |
|
602 \end{center} |
|
603 |
|
604 \end{frame}} |
|
605 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
606 |
|
607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
608 \mode<presentation>{ |
|
609 \begin{frame}[c] |
|
610 \frametitle{\begin{tabular}{c}What about Left-Recursion?\end{tabular}} |
|
611 |
|
612 \begin{itemize} |
|
613 \item we record when we recursively called a parser\bigskip |
|
614 \item whenever the is a recursion, the parser must have consumed something --- so |
|
615 we can decrease the input string/list of token by one (at the end) |
|
616 \end{itemize} |
|
617 \end{frame}} |
|
618 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
619 |
|
620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
621 \mode<presentation>{ |
|
622 \begin{frame}[c] |
|
623 \frametitle{\begin{tabular}{c}While-Language\end{tabular}} |
|
624 |
|
625 |
|
626 \begin{center} |
|
627 \bl{\begin{tabular}{@{}lcl@{}} |
|
628 $Stmt$ & $\rightarrow$ & $\text{skip}$\\ |
|
629 & $|$ & $Id := AExp$\\ |
|
630 & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ |
|
631 & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\ |
|
632 $Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ |
|
633 & $|$ & $Stmt$\medskip\\ |
|
634 $Block$ & $\rightarrow$ & $\{ Stmts \}$\\ |
|
635 & $|$ & $Stmt$\medskip\\ |
|
636 $AExp$ & $\rightarrow$ & \ldots\\ |
|
637 $BExp$ & $\rightarrow$ & \ldots\\ |
|
638 \end{tabular}} |
|
639 \end{center} |
|
640 |
|
641 |
|
642 \end{frame}} |
|
643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
644 |
|
645 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
646 \mode<presentation>{ |
|
647 \begin{frame}[c] |
|
648 \frametitle{\begin{tabular}{c}An Interpreter\end{tabular}} |
|
649 |
|
650 \begin{center} |
|
651 \bl{\begin{tabular}{l} |
|
652 $\{$\\ |
|
653 \;\;$x := 5 \text{;}$\\ |
|
654 \;\;$y := x * 3\text{;}$\\ |
|
655 \;\;$y := x * 4\text{;}$\\ |
|
656 \;\;$x := u * 3$\\ |
|
657 $\}$ |
|
658 \end{tabular}} |
|
659 \end{center} |
|
660 |
|
661 \begin{itemize} |
|
662 \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause |
|
663 \item \bl{\text{eval}(stmt, env)} |
|
664 \end{itemize} |
|
665 |
|
666 |
|
667 \end{frame}} |
|
668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
669 |
873 |
670 \end{document} |
874 \end{document} |
671 |
875 |
672 %%% Local Variables: |
876 %%% Local Variables: |
673 %%% mode: latex |
877 %%% mode: latex |