427 \frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}

   452 

   428 \begin{center}

   453 \begin{center}

   429 \begin{tabular}{@{}lcl@{}}

   454 \bl{\begin{tabular}{@{}lcl@{}}

   443 \end{tabular}

   468 \end{tabular}}

   444 \end{center}

   469 \end{center}

   445 \end{frame}}

   470 \end{frame}}

   446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   471 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   447 

   472 

   448 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   449 \mode<presentation>{

   474 \mode<presentation>{

   450 \begin{frame}[c]

   475 \begin{frame}[c]

   451 \frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}

   476 

   452 

   477 \mbox{\lstinputlisting[language=while]{../progs/fib.while}}

   453 \begin{center}

   478 

   454 \bl{\begin{tabular}{lcl}

   479 \end{frame}}

   455 $E$ & $\rightarrow$ &  $F \;|\; F \cdot * \cdot F$\\

   480 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   456 $F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\

   481 

   457 $T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\

   482 

   458 \end{tabular}}

   483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   459 \end{center}

   484 \mode<presentation>{

   460 

   485 \begin{frame}[c]

   461 \begin{center}

   486 \frametitle{\begin{tabular}{c}An Interpreter\end{tabular}}

   462 \begin{tikzpicture}[level distance=8mm, blue]

   487 

   463   \node {$E$}

   488 \begin{center}

   464     child {node {$F$} 

   489 \bl{\begin{tabular}{l}

   465      child {node {$T$} 

   490 $\{$\\

   466                  child {node {(\,$E$\,)}

   491 \;\;$x := 5 \text{;}$\\

   467                             child {node{$F$ *{} $F$}

   492 \;\;$y := x * 3\text{;}$\\

   468                                   child {node {$T$} child {node {2}}}

   493 \;\;$y := x * 4\text{;}$\\

   469                                   child {node {$T$} child {node {3}}} 

   494 \;\;$x := u * 3$\\

   470                                }

   495 $\}$

   471                           }

   496 \end{tabular}}

   472               }

   497 \end{center}

   473      child {node {+}}

   498 

   474      child {node {$T$}

   499 \begin{itemize}

   475        child {node {(\,$E$\,)} 

   500 \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause

   476        child {node {$F$}

   501 \item \bl{\text{eval}(stmt, env)}

   477        child {node {$T$ +{} $T$}

   502 \end{itemize}

   478                     child {node {3}}

   503 

   479                     child {node {4}} 

   504 

   480                  }

   505 \end{frame}}

   481                  }}

   506 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   482     }};

   507 

   508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   509 \mode<presentation>{

   510 \begin{frame}[c]

   511 \frametitle{\begin{tabular}{c}Interpreter\end{tabular}}

   512 

   513 \begin{center}

   514 \bl{\begin{tabular}{@{}lcl@{}}

   515 $\text{eval}(n, E)$ & $\dn$ & $n$\\

   516 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\

   517 $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\

   518 $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\

   519 $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\

   520 $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\

   521 $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\

   522 $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\

   523 \end{tabular}}

   524 \end{center}

   525 

   526 \end{frame}}

   527 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   528 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   529 \mode<presentation>{

   530 \begin{frame}[c]

   531 \frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}

   532 

   533 \begin{center}

   534 \bl{\begin{tabular}{@{}lcl@{}}

   535 $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\

   536 $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\

   537 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\

   538 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;

   539 \text{eval}(cs_1,E)$}\\

   540 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\

   541 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\

   542 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\

   543 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;

   544 \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\

   545 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\

   546 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\

   547 \end{tabular}}

   548 \end{center}

   549 

   550 \end{frame}}

   551 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   552 

   553 

   554 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   555 \mode<presentation>{

   556 \begin{frame}[c]

   557 \frametitle{\begin{tabular}{c}Test Program\end{tabular}}

   558 

   559 \mbox{}\\[-18mm]\mbox{}

   560 

   561 {\lstset{language=While}%%\fontsize{10}{12}\selectfont

   562 \texttt{\lstinputlisting{../progs/loops.while}}}

   563 

   564 \end{frame}}

   565 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   566 

   567 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   568 \mode<presentation>{

   569 \begin{frame}[t]

   570 \frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}

   571 

   572 \begin{center}

   573 \begin{tikzpicture}

   574 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]

   575 \addplot+[smooth] file {interpreted.data};

   576 \end{axis}

   538 \frametitle{\begin{tabular}{c}A CFG Derivation\end{tabular}}

   586 \frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}

   539 

   587 

   540 \begin{enumerate}

   588 \begin{itemize}

   541 \item Begin with a string with only the start symbol \bl{$S$}\bigskip

   589 \item introduced in 1995

   542 \item Replace any non-terminal \bl{$X$} in the string by the

   590 \item is a stack-based VM (like Postscript, CLR of .Net)

   543 right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip

   591 \item contains a JIT compiler

   544 \item Repeat 2 until there are no non-terminals

   592 \item many languages take advantage of JVM's infrastructure (JRE)

   545 \end{enumerate}

   593 \item is garbage collected $\Rightarrow$ no buffer overflows

   546 

   594 \item some languages compile to the JVM: Scala, Clojure\ldots

   547 \begin{center}

   595 \end{itemize}

   548 \bl{$S \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}

   549 \end{center}