6 

     5 \usepackage{../graphics}

    21   \LARGE Formal Languages (7)\\[3mm] 

    19   \LARGE Formal Languages (8)\\[3mm] 

    36 

    34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    37 \newcommand{\qq}{\mbox{\texttt{"}}}

    35 \begin{frame}[c]

    38 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    36 \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.

    69 [rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]

    40 \node (rexp)  {\bl{\bf Lexer}};

    70 

    41 \node (nfa) [right=of rexp] {\bl{\bf Parser}};

    71 \draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};

    42 \node (dfa) [right=of nfa] 

    72 \draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};

    43  {\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};

    44 \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};

    45 sequence\end{tabular}} (nfa);

    75 \draw (0,-1.4) node [rect] {regular languages};

    46 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree\end{tabular}}(dfa);

    76 \end{tikzpicture}

    47 \end{tikzpicture}\\

    77 

    48 \end{center}

    78 \end{center}

    49 

    79 

    50 \end{frame}

    80 \end{frame}}

    51 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

    81 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

    52  

    82 

    53 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    54 \begin{frame}[c]

    84 \mode<presentation>{

    55 \begin{textblock}{10}(0.5,0.5)

    85 \begin{frame}[c]

    56   \LARGE

    86 \frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}

    57   \fontspec{Hoefler Text Black}

    87 

    58   \textcolor{ProcessBlue}{JVM\\ Code}

    88 A grammar for arithmetic expressions and numbers:

    59 \end{textblock}

    89 

    60 \fontsize{8}{10}\selectfont

    90 \begin{center}

    61 %\footnotesize

    91 \bl{\begin{tabular}{lcl}

    62 \mbox{}\\[-8mm]\mbox{}

    92 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\

    63 

    93 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ 

    64 \begin{columns}

    94 \end{tabular}}

    65 \begin{column}{2cm} 

    95 \end{center}

    66 \lstinputlisting[numbers=none]{../progs/appHa.j}

    96 

    67 \end{column}

    97 Unfortunately it is left-recursive (and ambiguous).\medskip\\

    68 

    98 A problem for \alert{recursive descent parsers} (e.g.~parser combinators).

    69 \begin{column}{2cm} 

    99 \bigskip\pause

    70 \lstinputlisting[numbers=none]{../progs/appHb.j}

   100 

    71 \end{column}

   101 \end{frame}}

    72 

   102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

    73 \end{columns}

   103 

    74 

   104 

    75 \end{frame}

   105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    76 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   106 \mode<presentation>{

    77  

   107 \begin{frame}[t]

    78  

   108 \frametitle{\begin{tabular}{c}Numbers\end{tabular}}

    79  

   109 

   110 

   111 

   112 \begin{center}

   113 \bl{\begin{tabular}{lcl}

   114 $N$ & $\rightarrow$ &  $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   115 \end{tabular}}

   116 \end{center}

   117 

   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 

   373 \end{frame}}

   101 

   374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   102 

   375 

   103 \end{frame}}

   376 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   104 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   377 \mode<presentation>{

   105 

   378 \begin{frame}[c]

   106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   379 

   107 \begin{frame}[c]

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

   108 \frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}}

   381 

   109 

   382 \end{frame}}

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

   383 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   111 

   384 

   112 {\lstset{language=While}\fontsize{10}{12}\selectfont

   385 

   113 \texttt{\lstinputlisting{../progs/fib.while}}}

   386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   114 

   387 \mode<presentation>{

   115 \end{frame}

   388 \begin{frame}[c]

   116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

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

   117 

   390 

   118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   391 \begin{center}

   119 \begin{frame}[c]

   392 \bl{\begin{tabular}{l}

   120 \frametitle{Interpreter}

   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}}

   429 \end{frame}}

   135 \end{frame}

   430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   137 

   432 \mode<presentation>{

   138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   433 \begin{frame}[c]

   139 \begin{frame}[c]

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

   140 \frametitle{Interpreter (2)}

   453 \end{frame}}

   159 \end{frame}

   454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   160 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   455 

   161 

   456 

   162 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   163 \begin{frame}[c]

   458 \mode<presentation>{

   164 \frametitle{Test Program}

   459 \begin{frame}[c]

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

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

   168 {\lstset{language=While}\fontsize{10}{12}\selectfont

   467 \end{frame}}

   171 \end{frame}

   468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   469 

   173 

   470 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   471 \mode<presentation>{

   175 \begin{frame}[c]

   472 \begin{frame}[t]

   176 \fontsize{7}{9}\selectfont

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

   177 

   178 

   179 \begin{columns}

   180 \begin{column}{7cm} 

   181 \lstinputlisting[numbers=none]{../progs/appHa.j}

   182 \end{column}

   183 

   184 \begin{column}{7cm} 

   185 \lstinputlisting[numbers=none]{../progs/appHb.j}

   186 \end{column}

   187 \end{columns}

   188 

   189 \end{frame}

   190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   191  

   192 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   193 \begin{frame}[t]

   194 \frametitle{Interpreted Code}

   483 \end{frame}}

   204 \end{frame}

   487 \mode<presentation>{

   208 \begin{frame}[c]

   488 \begin{frame}[c]

   209 \frametitle{Java Virtual Machine}

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

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

   217 \item some languages compiled to the JVM: Scala, Clojure\ldots

   500 \end{frame}}

   220 \end{frame}

   501 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   222 

   223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   224 \begin{frame}[t]

   225 \frametitle{Compiling AExps}

   226 

   227 {\Large\bl{1 + 2}}

   228 

   229 \begin{center}

   230 \bl{\begin{tabular}{l}

   231 ldc 1\\

   232 ldc 2\\

   233 iadd\\

   234 \end{tabular}}

   235 \end{center}

   236 \end{frame}

   237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   238 

   239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   240 \mode<presentation>{

   241 \begin{frame}[t]

   242 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}

   243 

   244 {\Large\bl{1 + 2 + 3}}

   245 

   246 \begin{center}

   247 \bl{\begin{tabular}{l}

   248 ldc 1\\

   249 ldc 2\\

   250 iadd\\

   251 ldc 3\\

   252 iadd\\

   253 \end{tabular}}

   254 \end{center}

   255 

   256 \end{frame}}

   257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   258 

   259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   260 \mode<presentation>{

   261 \begin{frame}[t]

   262 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}

   263 

   264 {\Large\bl{1 + (2 + 3)}}

   265 

   266 \begin{center}

   267 \bl{\begin{tabular}{l}

   268 ldc 1\\

   269 ldc 2\\

   270 ldc 3\\

   271 iadd\\

   272 iadd\\

   273 \end{tabular}}

   274 \end{center}\bigskip\pause

   275 \vfill

   276 

   277 \bl{dadd, fadd, ladd, \ldots}

   278 

   279 \end{frame}}

   280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   281 

   282 

   283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   284 \mode<presentation>{

   285 \begin{frame}[t]

   286 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}

   287 

   288 \begin{center}

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

   290 $\text{compile}(n)$ & $\dn$ & $\text{ldc}\;n$\\

   291 $\text{compile}(a_1 + a_2)$ & $\dn$\\ 

   292 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\;\text{compile}(a_2)\;@\; \text{iadd}$}\smallskip\\

   293 $\text{compile}(a_1 - a_2)$ & $\dn$\\ 

   294 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{isub}$}\smallskip\\

   295 $\text{compile}(a_1 * a_2)$ & $\dn$\\ 

   296 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{imul}$}\smallskip\\

   297 \end{tabular}}

   298 \end{center}\pause

   299 

   300 \end{frame}}

   301 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   302 

   303 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   304 \mode<presentation>{

   305 \begin{frame}[t]

   306 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}

   307 

   308 {\Large\bl{1 + 2 * 3 + (4 - 3)}}

   309 

   310 \begin{center}

   311 \bl{\begin{tabular}{l}

   312 ldc 1\\

   313 ldc 2\\

   314 ldc 3\\

   315 imul\\

   316 ldc 4\\

   317 ldc 3\\

   318 isub\\

   319 iadd\\

   320 iadd\\

   321 \end{tabular}}

   322 \end{center}

   323 

   324 \end{frame}}

   325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   326 

   327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   328 \mode<presentation>{

   329 \begin{frame}[t]

   330 \frametitle{\begin{tabular}{c}Variables\end{tabular}}

   331 

   332 {\Large\bl{$x := 5 + y * 2$}}\bigskip\pause   

   333 

   334 \begin{itemize}

   335 \item lookup: \bl{$\text{iload}\; index$}

   336 \item store: \bl{$\text{istore}\; index$}

   337 \end{itemize}\bigskip\pause

   338 

   339 while compilating we have to maintain a map between our identifiers and the

   340 Java bytecode indices

   341 

   342 \begin{center}

   343 \bl{$\text{compile}(a, E)$}

   344 \end{center}

   345 

   346 \end{frame}}

   347 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   348 

   349 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   350 \mode<presentation>{

   351 \begin{frame}[t]

   352 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}

   353 

   354 \begin{center}

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

   356 $\text{compile}(n, E)$ & $\dn$ & $\text{ldc}\;n$\\

   357 $\text{compile}(a_1 + a_2, E)$ & $\dn$\\ 

   358 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\;\text{compile}(a_2. E)\;@\; \text{iadd}$}\smallskip\\

   359 $\text{compile}(a_1 - a_2, E)$ & $\dn$\\ 

   360 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{isub}$}\smallskip\\

   361 $\text{compile}(a_1 * a_2, E)$ & $\dn$\\ 

   362 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{imul}$}\bigskip\\

   363 $\text{compile}(x, E)$ & $\dn$ & $\text{iload}\;E(x)$\\

   364 \end{tabular}}

   365 \end{center}\pause

   366 

   367 \end{frame}}

   368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   369 

   370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   371 \begin{frame}[t]

   372 \frametitle{Compiling Statements}

   373 

   374 We return a list of instructions and an environment for the

   375 variables

   376 

   377 \begin{center}

   378 \bl{\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}

   379 $\text{compile}(\text{skip}, E)$ & $\dn$ & $(\textit{Nil}, E)$\bigskip\\

   380 $\text{compile}(x := a, E)$ & $\dn$\\

   381 \multicolumn{3}{l}{$(\text{compile}(a, E) \;@\;\text{istore}\;index, E(x\mapsto index))$}\\

   382 \end{tabular}}

   383 \end{center}\medskip

   384 

   385 where \bl{$index$} is \bl{$E(x)$} if it is already defined, 

   386 or if it is not then the largest index not yet seen

   387 

   388 \end{frame}

   389 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   390 

   391 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   392 \mode<presentation>{

   393 \begin{frame}[t]

   394 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}

   395 

   396 {\Large\bl{$x := x + 1$}}

   397 

   398 \begin{center}

   399 \bl{\begin{tabular}{l}

   400 iload $n_x$\\

   401 ldc 1\\

   402 iadd\\

   403 istore $n_x$\\

   404 \end{tabular}}

   405 \end{center}

   406 

   407 where \bl{$n_x$} is the index corresponding to the variable \bl{$x$}

   408 

   409 \end{frame}}

   410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   411 

   412 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   413 \begin{frame}[c, fragile]

   414 \frametitle{Mathematical Functions}

   415 

   416 Compilation of some mathematical functions:

   417 

   418 \begin{center}

   419 \begin{tabular}{lcl}

   420 \texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\

   421 \texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\

   422 \texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\

   423 \texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\

   424 \texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\

   425 \end{tabular}

   426 \end{center}

   427 

   428 \end{frame}

   429 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   430 

   431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   432 \mode<presentation>{

   433 \begin{frame}[t]

   434 \frametitle{\begin{tabular}{c}Compiling Ifs\end{tabular}}

   435 

   436 {\Large\bl{$\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2$}}\bigskip\bigskip

   437 

   438 \onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:}

   439 

   440 \begin{center}

   441 \begin{tikzpicture}[node distance=2mm and 4mm,

   442  block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},

   443  point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},

   444  skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]

   445 \node (A1) [point] {};

   446 \node (b) [block, right=of A1] {code of \bl{$b$}};

   447 \node (A2) [point, right=of b] {};

   448 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};

   449 \node (A3) [point, right=of cs1] {};

   450 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};

   451 \node (A4) [point, right=of cs2] {};

   452 

   453 \only<2>{

   454 \draw (A1) edge [->, red, line width=1mm] (b);

   455 \draw (b) edge [->, red, line width=1mm] (cs1);

   456 \draw (cs1) edge [->, red, line width=1mm] (A3);

   457 \draw (A3) edge [->,skip loop] (A4);

   458 \node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};}

   459 \only<3>{

   460 \draw (A1) edge [->, red, line width=1mm] (b);

   461 \draw (b) edge [->, red, line width=1mm] (A2);

   462 \draw (A2) edge [skip loop] (A3);

   463 \draw (A3) edge [->, red, line width=1mm] (cs2);

   464 \draw (cs2) edge [->,red, line width=1mm] (A4);

   465 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}

   466 \end{tikzpicture}

   467 \end{center}

   468 

   469 

   470 \end{frame}}

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

   472 

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

   474 \begin{frame}[t]

   475 \frametitle{Conditional Jumps}

   476 

   477 \begin{minipage}{1.1\textwidth}

   478 \begin{itemize}

   479 \item \bl{if\_icmpeq $label$} if two ints are equal, then jump\medskip

   480 \item \bl{if\_icmpne $label$} if two ints aren't equal, then jump\medskip

   481 \item \bl{if\_icmpge $label$} if one int is greater or equal then another, then jump

   482 \item[]\ldots

   483 \end{itemize}

   484 \end{minipage}\pause

   485 

   486 

   487 \begin{center}

   488 \bl{\begin{tabular}{l}

   489 $L_1$:\\

   490 \hspace{5mm}if\_icmpeq\;$L_2$\\

   491 \hspace{5mm}iload 1\\

   492 \hspace{5mm}ldc 1\\

   493 \hspace{5mm}iadd\\

   494 \hspace{5mm}if\_icmpeq\;$L_1$\\

   495 $L_2$:

   496 \end{tabular}}

   497 \end{center}

   498 

   499 \begin{textblock}{3.5}(11,12)

   500 \only<3>{labels must be unique}

   501 \end{textblock}

   502 \end{frame}

   503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   504 

   505 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   506 \mode<presentation>{

   507 \begin{frame}[t]

   508 \frametitle{\begin{tabular}{c}Compiling BExps\end{tabular}}

   509 

   510 {\Large\bl{$a_1 = a_2$}}

   511 

   512 \begin{center}

   513 \bl{\begin{tabular}{lcl}

   514 $\text{compile}(a_1 = a_2, E, lab)$ & $\dn$\\ 

   515 \multicolumn{3}{l}{$\quad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{if\_icmpne}\;lab$}

   516 \end{tabular}}

   517 \end{center}

   518 

   519 \end{frame}}

   520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   521 

   522 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   523 \begin{frame}[c, fragile]

   524 \frametitle{Boolean Expressions}

   525 

   526 Compilation of boolean expressions:

   527 

   528 \begin{center}

   529 \begin{tikzpicture}[node distance=2mm and 4mm,

   530  block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},

   531  point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},

   532  skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]

   533 \node (A1) [point] {};

   534 \node (b) [block, right=of A1] {code of \bl{$b$}};

   535 \node (A2) [point, right=of b] {};

   536 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};

   537 \node (A3) [point, right=of cs1] {};

   538 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};

   539 \node (A4) [point, right=of cs2] {};

   540 

   541 \only<1>{

   542 \draw (A1) edge [->, red, line width=1mm] (b);

   543 \draw (b) edge [->, red, line width=1mm] (A2);

   544 \draw (A2) edge [skip loop] (A3);

   545 \draw (A3) edge [->, red, line width=1mm] (cs2);

   546 \draw (cs2) edge [->,red, line width=1mm] (A4);

   547 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}

   548 \end{tikzpicture}

   549 \end{center}

   550 

   551 \begin{center}

   552 \begin{tabular}{lcl}

   553 \texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\

   554 \texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\

   555 \texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\

   556 \texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\

   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}Compiling Ifs\end{tabular}}

   568 

   569 {\Large\bl{if $b$ then $cs_1$ else $cs_2$}}

   570 

   571 \begin{center}

   572 \bl{\begin{tabular}{lcl}

   573 $\text{compile}(\text{if}\;b\;\text{then}\; cs_1\;\text{else}\; cs_2, E)$ & $\dn$\\ 

   574 \multicolumn{3}{l}{$\quad l_{ifelse}\;$ \textcolor{black}{(fresh label)}}\\

   575 \multicolumn{3}{l}{$\quad l_{ifend}\;$ \textcolor{black}{(fresh label)}}\\

   576 \multicolumn{3}{l}{$\quad (is_1, E') = \text{compile}(cs_1, E)$}\\

   577 \multicolumn{3}{l}{$\quad (is_2, E'') = \text{compile}(cs_2, E')$}\\

   578 \multicolumn{3}{l}{$\quad(\text{compile}(b, E, l_{ifelse})$}\\

   579 \multicolumn{3}{l}{$\quad\phantom{(}@\;is_1$}\\

   580 \multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{ifend}$}\\

   581 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifelse}:$}\\

   582 \multicolumn{3}{l}{$\quad\phantom{(}@\;is_2$}\\

   583 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifend}:, E'')$}\\

   584 \end{tabular}}

   585 \end{center}

   586 

   587 \end{frame}}

   588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   589 

   590 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   591 \mode<presentation>{

   592 \begin{frame}[t]

   593 \frametitle{\begin{tabular}{c}Compiling Whiles\end{tabular}}

   594 

   595 {\Large\bl{$\text{while}\;b\;\text{do}\;cs$}}\bigskip\bigskip

   596 

   597 \onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:}

   598 

   599 \begin{center}

   600 \begin{tikzpicture}[node distance=2mm and 4mm,

   601  block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},

   602  point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},

   603  skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]

   604 \node (A0) [point, left=of A1] {};

   605 \node (A1) [point] {};

   606 \node (b) [block, right=of A1] {code of \bl{$b$}};

   607 \node (A2) [point, right=of b] {};

   608 \node (cs1) [block, right=of A2] {code of \bl{$cs$}};

   609 \node (A3) [point, right=of cs1] {};

   610 \node (A4) [point, right=of A3] {};

   611 

   612 \only<2>{

   613 \draw (A0) edge [->, red, line width=1mm] (b);

   614 \draw (b) edge [->, red, line width=1mm] (cs1);

   615 \draw (cs1) edge [->, red, line width=1mm] (A3);

   616 \draw (A3) edge [->,skip loop] (A1);}

   617 \only<3>{

   618 \draw (A0) edge [->, red, line width=1mm] (b);

   619 \draw (b) edge [->, red, line width=1mm] (A2);

   620 \draw (A2) edge [skip loop] (A3);

   621 \draw (A3) edge [->, red, line width=1mm] (A4);}

   622 \end{tikzpicture}

   623 \end{center}

   624 

   625 

   626 \end{frame}}

   627 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   628 

   629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   630 \mode<presentation>{

   631 \begin{frame}[t]

   632 \frametitle{\begin{tabular}{c}Compiling Whiles\end{tabular}}

   633 

   634 {\Large\bl{while $b$ do $cs$}}

   635 

   636 \begin{center}

   637 \bl{\begin{tabular}{lcl}

   638 $\text{compile}(\text{while}\; b\; \text{do} \;cs, E)$ & $\dn$\\ 

   639 \multicolumn{3}{l}{$\quad l_{wbegin}\;$ \textcolor{black}{(fresh label)}}\\

   640 \multicolumn{3}{l}{$\quad l_{wend}\;$ \textcolor{black}{(fresh label)}}\\

   641 \multicolumn{3}{l}{$\quad (is, E') = \text{compile}(cs_1, E)$}\\

   642 \multicolumn{3}{l}{$\quad(l_{wbegin}:$}\\

   643 \multicolumn{3}{l}{$\quad\phantom{(}@\;\text{compile}(b, E, l_{wend})$}\\

   644 \multicolumn{3}{l}{$\quad\phantom{(}@\;is$}\\

   645 \multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\

   646 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{wend}:, E')$}\\

   647 \end{tabular}}

   648 \end{center}

   649 

   650 \end{frame}}

   651 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   652 

   653 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   654 \mode<presentation>{

   655 \begin{frame}[t]

   656 \frametitle{\begin{tabular}{c}Compiling Writes\end{tabular}}

   657 

   658 {\Large\bl{write $x$}}

   659 

   660 \begin{center}

   661 \small\bl{\begin{tabular}{l}

   662 .method public static write(I)V\hspace{1cm}\textcolor{black}{(library function)}\\ 

   663 \;\;    .limit locals 5 \\

   664 \;\;    .limit stack 5 \\

   665 \;\;    iload 0 \\

   666 \;\;    getstatic java/lang/System/out Ljava/io/PrintStream;\\ 

   667 \;\;    swap \\

   668 \;\;    invokevirtual java/io/PrintStream/println(I)V \\

   669 \;\;    return \\

   670 .end method\bigskip\bigskip\\

   671 %

   672 \normalsize

   673 iload $E(x)$\\

   674 invokestatic write(I)V\\

   675 \end{tabular}}

   676 \end{center}

   677 

   678 \end{frame}}

   679 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   680 

   681 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   682 \mode<presentation>{

   683 \begin{frame}[c]

   684 

   685 \begin{center}

   686 \small\bl{\begin{tabular}{l}

   687 .class public XXX.XXX\\

   688 .super java/lang/Object\\

   689 \\

   690 .method public <init>()V\\

   691 \;\;     aload\_0\\

   692 \;\;     invokenonvirtual java/lang/Object/<init>()V\\

   693  \;\;    return\\

   694 .end method\\

   695 \\

   696 .method public static main([Ljava/lang/String;)V\\

   697 \;\;   .limit locals 200\\

   698 \;\;     .limit stack 200\\

   699 \\

   700    \textcolor{black}{(here comes the compiled code)}\\

   701 \\

   702 \;\;     return\\

   703 .end method\\

   704 \end{tabular}}

   705 \end{center}

   706 

   707 \end{frame}}

   708 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   709 

   710 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   711 \mode<presentation>{

   712 \begin{frame}[c]

   713 \frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}}

   714 

   715 \begin{itemize}

   716 \item assembly $\Rightarrow$ byte code (class file)

   717 \item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip

   718 \item \texttt{javap} is a disassembler for class files

   719 \end{itemize}

   720 

   721 \end{frame}}

   722 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   723 

   724 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   725 \mode<presentation>{

   726 \begin{frame}[t]

   727 \frametitle{\begin{tabular}{c}Compiled Code\end{tabular}}

   728 

   729 \begin{center}

   730 \begin{tikzpicture}

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

   732 \addplot+[smooth] file {compiled.data};

   733 \end{axis}

   734 \end{tikzpicture}

   735 \end{center}

   736 

   737 \end{frame}}

   738 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   739 

   740 

   741 

   742 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   743 \mode<presentation>{

   744 \begin{frame}[t]

   745 \frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}}

   746 

   747 \begin{center}

   748 \begin{tikzpicture}

   749 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,

   750     xlabel=n,

   751     enlargelimits=0.05,

   752     ybar interval=0.7, legend style=small]

   753 \addplot file {interpreted2.data};

   754 \addplot file {compiled2.data};

   755 %\legend{interpreted, compiled}

   756 \end{axis}

   757 \end{tikzpicture}

   758 \end{center}

   759 

   760 \end{frame}}

   761 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   762 

   763 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   764 \mode<presentation>{

   765 \begin{frame}[c]

   766 \frametitle{Backend}

   767 

   768 \begin{center}

   769 \begin{tikzpicture}

   770 \node (rexp)  {\bl{\bf Lexer}};

   771 \node (nfa) [right=of rexp] {\bl{\bf Parser}};

   772 \node (dfa) [right=of nfa] {\bl{\begin{tabular}{c}\bf Optimizations\end{tabular}}};

   773 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm]

   774 sequence\end{tabular}} (nfa);

   775 \node (final) [below=of dfa] {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Byte Code\end{tabular}}};

   776 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree

   777 \end{tabular}}(dfa);

   778 \path[->, red, line width=2mm] (dfa) edge (final);

   779 \end{tikzpicture}\\

   780 \end{center}

   781 

   782 \end{frame}}

   783 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   784 

   785 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   786 \mode<presentation>{

   787 \begin{frame}[t]

   788 \frametitle{\begin{tabular}{c}What Next\end{tabular}}

   789 

   790 \begin{itemize}

   791 \item register spilling

   792 \item dead code removal

   793 \item loop optimisations

   794 \item instruction selection

   795 \item type checking

   796 \item concurrency

   797 \item fuzzy testing

   798 \item verification\bigskip\\

   799 

   800 \item GCC, LLVM, tracing JITs

   801 \end{itemize}

   802 

   803 \end{frame}}

   804 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%