5 \usepackage{../graphics}

     6 

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

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

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

    36 

    35 \begin{frame}[c]

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

    36 \frametitle{Bird's Eye View}

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

    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.

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

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

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

    70 

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

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

    43  {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Java Byte Code\end{tabular}}};

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

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

    73 \draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};

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

    74 \draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};

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

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

    47 \end{tikzpicture}\\

    76 \end{tikzpicture}

    48 \end{center}

    77 

    49 

    78 \end{center}

    50 \end{frame}

    79 

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

    80 \end{frame}}

    52  

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

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

    82 

    54 \begin{frame}[c]

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

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

    84 \mode<presentation>{

    56   \LARGE

    85 \begin{frame}[c]

    57   \fontspec{Hoefler Text Black}

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

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

    87 

    59 \end{textblock}

    88 A grammar for arithmetic expressions and numbers:

    60 \fontsize{8}{10}\selectfont

    89 

    61 %\footnotesize

    90 \begin{center}

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

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

    63 

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

    64 \begin{columns}

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

    65 \begin{column}{2cm} 

    94 \end{tabular}}

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

    95 \end{center}

    67 \end{column}

    96 

    68 

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

    69 \begin{column}{2cm} 

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

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

    99 \bigskip\pause

    71 \end{column}

   100 

    72 

   101 \end{frame}}

    73 \end{columns}

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

    74 

   103 

    75 \end{frame}

   104 

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

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

    77  

   106 \mode<presentation>{

    78  

   107 \begin{frame}[t]

    79  

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

   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 

   101 

   373 \end{frame}}

   102 

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

   103 \end{frame}}

   375 

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

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

   105 

   377 \mode<presentation>{

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

   378 \begin{frame}[c]

   107 \begin{frame}[c]

   379 

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

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

   109 

   381 

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

   382 \end{frame}}

   111 

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

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

   384 

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

   385 

   114 

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

   115 \end{frame}

   387 \mode<presentation>{

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

   388 \begin{frame}[c]

   117 

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

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

   390 

   119 \begin{frame}[c]

   391 \begin{center}

   120 \frametitle{Interpreter}

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

   393 $\{$\\

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

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

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

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

   398 $\}$

   399 \end{tabular}}

   400 \end{center}

   401 

   402 \begin{itemize}

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

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

   405 \end{itemize}

   406 

   407 

   408 \end{frame}}

   409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   410 

   411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   412 \mode<presentation>{

   413 \begin{frame}[c]

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

   135 \end{frame}

   429 \end{frame}}

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

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

   137 

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

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

   432 \mode<presentation>{

   139 \begin{frame}[c]

   433 \begin{frame}[c]

   140 \frametitle{Interpreter (2)}

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

   159 \end{frame}

   453 \end{frame}}

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

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

   161 

   455 

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

   456 

   163 \begin{frame}[c]

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

   164 \frametitle{Test Program}

   458 \mode<presentation>{

   459 \begin{frame}[c]

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

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

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

   171 \end{frame}

   467 \end{frame}}

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

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

   173 

   469 

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

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

   175 \begin{frame}[c]

   471 \mode<presentation>{

   176 \fontsize{7}{9}\selectfont

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

   194 \frametitle{Interpreted Code}

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

   204 \end{frame}

   483 \end{frame}}

   208 \begin{frame}[c]

   487 \mode<presentation>{

   209 \frametitle{Java Virtual Machine}

   488 \begin{frame}[c]

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

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

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

   220 \end{frame}

   500 \end{frame}}

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

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

   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 \begin{frame}[t]

   285 \frametitle{Compiling AExps}

   286 

   287 \begin{center}

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

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

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

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

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

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

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

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

   296 \end{tabular}}

   297 \end{center}

   298 

   299 \end{frame}

   300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   301 

   302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   303 \mode<presentation>{

   304 \begin{frame}[t]

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

   306 

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

   308 

   309 \begin{center}

   310 \bl{\begin{tabular}{l}

   311 ldc 1\\

   312 ldc 2\\

   313 ldc 3\\

   314 imul\\

   315 ldc 4\\

   316 ldc 3\\

   317 isub\\

   318 iadd\\

   319 iadd\\

   320 \end{tabular}}

   321 \end{center}

   322 

   323 \end{frame}}

   324 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   325 

   326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   327 \begin{frame}[t]

   328 \frametitle{Variables}

   329 

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

   331 

   332 \begin{itemize}

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

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

   335 \end{itemize}\bigskip\pause

   336 

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

   338 Java bytecode indices

   339 

   340 \begin{center}

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

   342 \end{center}

   343 

   344 \end{frame}

   345 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   346 

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

   348 \begin{frame}[t]

   349 \frametitle{Compiling AExps}

   350 

   351 \begin{center}

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

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

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

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

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

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

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

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

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

   361 \end{tabular}}

   362 \end{center}

   363 

   364 \end{frame}

   365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   366 

   367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   368 \begin{frame}[c, fragile]

   369 \frametitle{Mathematical Functions}

   370 

   371 Compilation of some mathematical functions:

   372 

   373 \begin{center}

   374 \begin{tabular}{lcl}

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

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

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

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

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

   380 \end{tabular}

   381 \end{center}

   382 

   383 \end{frame}

   384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   385 

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

   387 \begin{frame}[t]

   388 \frametitle{Compiling Statements}

   389 

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

   391 variables

   392 

   393 \begin{center}

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

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

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

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

   398 \end{tabular}}

   399 \end{center}\medskip

   400 

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

   402 or if it is not, then the largest index not yet seen

   403 

   404 \end{frame}

   405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   406 

   407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   408 \begin{frame}[c]

   409 \frametitle{Compiling Assignments}

   410 

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

   412 

   413 \begin{center}

   414 \bl{\begin{tabular}{l}

   415 iload $n_x$\\

   416 ldc 1\\

   417 iadd\\

   418 istore $n_x$\\

   419 \end{tabular}}

   420 \end{center}

   421 

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

   423 

   424 \end{frame}

   425 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   426 

   427 

   428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   429 \begin{frame}[t]

   430 \frametitle{Compiling Ifs}

   431 

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

   433 

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

   435 

   436 \begin{center}

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

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

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

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

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

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

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

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

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

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

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

   448 

   449 \only<2>{

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

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

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

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

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

   455 \only<3>{

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

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

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

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

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

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

   462 \end{tikzpicture}

   463 \end{center}

   464 

   465 \end{frame}

   466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   467 

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

   469 \begin{frame}[t]

   470 \frametitle{Conditional Jumps}

   471 

   472 \begin{minipage}{1.1\textwidth}

   473 \begin{itemize}

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

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

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

   477 \item[]\ldots

   478 \end{itemize}

   479 \end{minipage}\pause

   480 

   481 

   482 \begin{center}

   483 \bl{\begin{tabular}{l}

   484 $L_1$:\\

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

   486 \hspace{5mm}iload 1\\

   487 \hspace{5mm}ldc 1\\

   488 \hspace{5mm}iadd\\

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

   490 $L_2$:

   491 \end{tabular}}

   492 \end{center}

   493 

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

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

   496 \end{textblock}

   497 \end{frame}

   498 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   499 

   500 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   501 \begin{frame}[t]

   502 \frametitle{Compiling BExps}

   503 

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

   505 

   506 \begin{center}

   507 \bl{\begin{tabular}{lcl}

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

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

   510 \end{tabular}}

   511 \end{center}

   512 

   513 \end{frame}

   514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   515 

   516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   517 \begin{frame}[c, fragile]

   518 \frametitle{Boolean Expressions}

   519 

   520 Compilation of boolean expressions:

   521 

   522 \begin{center}

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

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

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

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

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

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

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

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

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

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

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

   534 

   535 \only<1>{

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

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

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

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

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

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

   542 \end{tikzpicture}

   543 \end{center}

   544 

   545 \begin{center}

   546 \begin{tabular}{lcl}

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

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

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

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

   551 \end{tabular}

   552 \end{center}

   553 

   554 \end{frame}

   555 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   556 

   557 

   558 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   559 \begin{frame}[t]

   560 \frametitle{Compiling Ifs}

   561 

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

   563 

   564 \begin{center}

   565 \bl{\begin{tabular}{lcl}

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

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

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

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

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

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

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

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

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

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

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

   577 \end{tabular}}

   578 \end{center}

   579 

   580 \end{frame}

   581 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   582 

   583 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   584 \begin{frame}[t]

   585 \frametitle{Compiling Whiles}

   586 

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

   588 

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

   590 

   591 \begin{center}

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

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

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

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

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

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

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

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

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

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

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

   603 

   604 \only<2>{

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

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

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

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

   609 \only<3>{

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

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

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

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

   614 \end{tikzpicture}

   615 \end{center}

   616 

   617 \end{frame}

   618 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   619 

   620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   621 \begin{frame}[t]

   622 \frametitle{Compiling Whiles}

   623 

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

   625 

   626 \begin{center}

   627 \bl{\begin{tabular}{lcl}

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

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

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

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

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

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

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

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

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

   637 \end{tabular}}

   638 \end{center}

   639 

   640 \end{frame}

   641 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   642 

   643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   644 \begin{frame}[t]

   645 \frametitle{Compiling Writes}

   646 

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

   648 

   649 \begin{center}

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

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

   652 \;\;    .limit locals 5 \\

   653 \;\;    .limit stack 5 \\

   654 \;\;    iload 0 \\

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

   656 \;\;    swap \\

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

   658 \;\;    return \\

   659 .end method\bigskip\bigskip\\

   660 %

   661 \normalsize

   662 iload $E(x)$\\

   663 invokestatic write(I)V\\

   664 \end{tabular}}

   665 \end{center}

   666 

   667 \end{frame}

   668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   669 

   670 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   671 \begin{frame}[c]

   672 

   673 \begin{center}

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

   675 .class public XXX.XXX\\

   676 .super java/lang/Object\\

   677 \\

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

   679 \;\;     aload\_0\\

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

   681  \;\;    return\\

   682 .end method\\

   683 \\

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

   685 \;\;   .limit locals 200\\

   686 \;\;     .limit stack 200\\

   687 \\

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

   689 \\

   690 \;\;     return\\

   691 .end method\\

   692 \end{tabular}}

   693 \end{center}

   694 

   695 \end{frame}

   696 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   697 

   698 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   699 \mode<presentation>{

   700 \begin{frame}[c]

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

   702 

   703 \begin{itemize}

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

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

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

   707 \end{itemize}

   708 

   709 \end{frame}}

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

   711 

   712 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   713 \mode<presentation>{

   714 \begin{frame}[t]

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

   716 

   717 \begin{center}

   718 \begin{tikzpicture}

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

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

   721 \end{axis}

   722 \end{tikzpicture}

   723 \end{center}

   724 

   725 \end{frame}}

   726 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   727 

   728 

   729 

   730 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   731 \mode<presentation>{

   732 \begin{frame}[t]

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

   734 

   735 \begin{center}

   736 \begin{tikzpicture}

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

   738     xlabel=n,

   739     enlargelimits=0.05,

   740     ybar interval=0.7, legend style=small]

   741 \addplot file {interpreted2.data};

   742 \addplot file {compiled2.data};

   743 %\legend{interpreted, compiled}

   744 \end{axis}

   745 \end{tikzpicture}

   746 \end{center}

   747 

   748 \end{frame}}

   749 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   750 

   751 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   752 \mode<presentation>{

   753 \begin{frame}[c]

   754 \frametitle{Backend}

   755 

   756 \begin{center}

   757 \begin{tikzpicture}

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

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

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

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

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

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

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

   765 \end{tabular}}(dfa);

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

   767 \end{tikzpicture}\\

   768 \end{center}

   769 

   770 \end{frame}}

   771 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   772 

   773 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   774 \mode<presentation>{

   775 \begin{frame}[t]

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

   777 

   778 \begin{itemize}

   779 \item register spilling

   780 \item dead code removal

   781 \item loop optimisations

   782 \item instruction selection

   783 \item type checking

   784 \item concurrency

   785 \item fuzzy testing

   786 \item verification\bigskip\\

   787 

   788 \item GCC, LLVM, tracing JITs

   789 \end{itemize}

   790 

   791 \end{frame}}

   792 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%