18 

    19 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    20 \begin{frame}[t]

    21 \frametitle{%

    22   \begin{tabular}{@ {}c@ {}}

    23   \\[-3mm]

    24   \LARGE Compilers and \\[-2mm] 

    25   \LARGE Formal Languages\\[3mm] 

    26   \end{tabular}}

    27 

    28   \normalsize

    29   \begin{center}

    30   \begin{tabular}{ll}

    31     Email:  & christian.urban at kcl.ac.uk\\

    32     %Office Hours: & Thursdays 12 -- 14\\

    33     %Location: & N7.07 (North Wing, Bush House)\\

    34     Slides \& Progs: & KEATS (also homework is there)\\  

    35   \end{tabular}

    36   \end{center}

    37 

    38   \begin{center}

    39     \begin{tikzpicture}

    40       \node[drop shadow,fill=white,inner sep=0pt] 

    41       {\footnotesize\rowcolors{1}{capri!10}{white}

    42         \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline

    43           1 Introduction, Languages          & \cellcolor{blue!50} 6 While-Language \\

    44           2 Regular Expressions, Derivatives & 7 Compilation, JVM \\

    45           3 Automata, Regular Languages      & 8 Compiling Functional Languages \\

    46           4 Lexing, Tokenising               & 9 Optimisations \\

    47           5 Grammars, Parsing                & 10 LLVM \\ \hline

    48         \end{tabular}%

    49       };

    50     \end{tikzpicture}

    51   \end{center}

    52   

    53 \end{frame}

    54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

    55 

    56 

    57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    58 \begin{frame}[c]

    59 \frametitle{Parser Combinators}

    60 

    61 One of the simplest ways to implement a parser, see

    62 {\small\url{https://vimeo.com/142341803}} (by Haoyi Li)\bigskip

    63 

    64 \begin{itemize}

    65 \item[$\bullet$] build-in library in Scala

    66 \item[$\bullet$] fastparse (2) library by Haoyi Li; is part of Ammonite

    67 \item[$\bullet$] possible exponential runtime behaviour  

    68 \end{itemize}

    69 

    70 \end{frame}

    71 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    72 

    73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    74 \begin{frame}[c]

    75 \frametitle{Parser Combinators}

    76 

    77 Parser combinators: \bigskip

    78 

    79 \begin{minipage}{1.1\textwidth}

    80 \begin{center}

    81 \mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} 

    82 $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$

    83 \end{center}

    84 \end{minipage}\bigskip

    85 

    86 \begin{itemize}

    87 \item atomic parsers

    88 \item sequencing

    89 \item alternative

    90 \item semantic action (map-parser)

    91 \end{itemize}

    92 

    93 \end{frame}

    94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

    95 

    96 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    97 \begin{frame}[c]

    98 

    99 Atomic parsers, for example, number tokens

   100 

   101 \begin{center}

   102 \bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$} 

   103 \end{center}\bigskip

   104 

   105 \begin{itemize}

   106 \item you consume one or more token from the\\ 

   107   input (stream)

   108 \item also works for characters and strings

   109 \end{itemize}

   110 \end{frame}

   111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   112 

   113 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   114 \begin{frame}[c]

   115 

   116 Alternative parser (code \bl{$p\;||\;q$})\bigskip

   117 

   118 \begin{itemize}

   119 \item apply \bl{$p$} and also \bl{$q$}; then combine 

   120   the outputs

   121 \end{itemize}

   122 

   123 \begin{center}

   124 \large \bl{$p(\text{input}) \cup q(\text{input})$}

   125 \end{center}

   126 

   127 \end{frame}

   128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   129 

   130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   131 \begin{frame}[c]

   132 

   133 Sequence parser (code \bl{$p\sim q$})\bigskip

   134 

   135 \begin{itemize}

   136 \item apply first \bl{$p$} producing a set of pairs

   137 \item then apply \bl{$q$} to the unparsed part

   138 \item then combine the results:\medskip 

   139 \begin{center}

   140 ((output$_1$, output$_2$), unparsed part)

   141 \end{center}

   142 \end{itemize}

   143 

   144 \begin{center}

   145 \begin{tabular}{l}

   146 \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 

   147 \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]

   148 \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}

   149 \end{tabular}

   150 \end{center}

   151 

   152 

   153 \end{frame}

   154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   155 

   156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   157 \begin{frame}[c]

   158 

   159 Map-parser (code \bl{$p.map(f)\;$})\bigskip

   160 

   161 \begin{itemize}

   162 \item apply \bl{$p$} producing a set of pairs

   163 \item then apply the function \bl{$f$} to each first component

   164 \end{itemize}

   165 

   166 \begin{center}

   167 \begin{tabular}{l}

   168 \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}

   169 \end{tabular}

   170 \end{center}\bigskip\bigskip\pause

   171 

   172 \bl{$f$} is the semantic action (``what to do with the parsed input'')

   173 

   174 \end{frame}

   175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   176 

   177 

   178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   179 \mode<presentation>{

   180 \begin{frame}[c]

   181 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}

   182 

   183 Addition

   184 

   185 \begin{center}

   186 \bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}

   187 \end{center}\pause

   188 

   189 Multiplication

   190 

   191 \begin{center}

   192 \bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}

   193 \end{center}\pause

   194 

   195 Parenthesis

   196 

   197 \begin{center}

   198 \bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}

   199 \end{center}

   200 

   201 \end{frame}}

   202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   203 

   204 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   205 \begin{frame}[c]

   206 \frametitle{Types of Parsers}

   207 

   208 \begin{itemize}

   209 \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},

   210 then \bl{$p \sim q$} returns results of type

   211 

   212 \begin{center}

   213 \bl{$T \times S$}

   214 \end{center}\pause

   215 

   216 \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then  \bl{$q$} \alert{must} also have results of type \bl{$T$},

   217 and \bl{$p \;||\; q$} returns results of type

   218 

   219 \begin{center}

   220 \bl{$T$}

   221 \end{center}\pause

   222 

   223 \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from

   224 \bl{$T$} to \bl{$S$}, then

   225 \bl{$p \Rightarrow f$} returns results of type

   226 

   227 \begin{center}

   228 \bl{$S$}

   229 \end{center}

   230 

   231 \end{itemize}

   232 

   233 \end{frame}

   234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   235 

   236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   237 \begin{frame}[c]

   238 \frametitle{Input Types of Parsers}

   239 

   240 \begin{itemize}

   241 \item input: \alert{token list}

   242 \item output: set of (output\_type, \alert{token list})

   243 \end{itemize}\bigskip\pause

   244 

   245 actually it can be any input type as long as it is a kind of

   246 sequence (for example a string)

   247 

   248 \end{frame}

   249 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   250 

   251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   252 \begin{frame}[c]

   253 \frametitle{Scannerless Parsers}

   254 

   255 \begin{itemize}

   256 \item input: \alert{string}

   257 \item output: set of (output\_type, \alert{string})

   258 \end{itemize}\bigskip\bigskip

   259 

   260 but using lexers is better because whitespaces or comments can be

   261 filtered out; then input is a sequence of tokens

   262 

   263 \end{frame}

   264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   265 

   266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   267 \begin{frame}[c]

   268 \frametitle{Successful Parses}

   269 

   270 \begin{itemize}

   271 \item input: string

   272 \item output: \alert{set of} (output\_type, string)

   273 \end{itemize}\bigskip

   274 

   275 a parse is successful whenever the input has been fully

   276 ``consumed'' (that is the second component is empty)

   277 

   278 \end{frame}

   279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   280 

   281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   282 \begin{frame}[c]

   283 \frametitle{Abstract Parser Class}

   284 

   285 \small

   286 \lstinputlisting[language=Scala,xleftmargin=1mm]

   287  {../progs/app7.scala}

   288 \end{frame}

   289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   290 

   291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   292 \begin{frame}[c]

   293 

   294 \small

   295 \fontsize{10}{12}\selectfont

   296 \lstinputlisting[language=Scala,xleftmargin=1mm]

   297   {../progs/app8.scala}

   298 \end{frame}

   299 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   300 

   301 

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

   303 \begin{frame}[c]

   304 \frametitle{Two Grammars}

   305 

   306 Which languages are recognised by the following two grammars?

   307 

   308 \begin{center}

   309 \bl{\begin{tabular}{lcl}

   310 $\meta{S}$ & $\rightarrow$ &  $1 \cdot \meta{S} \cdot \meta{S}$\\

   311         & $|$ & $\epsilon$

   312 \end{tabular}}

   313 \end{center}\bigskip

   314 

   315 \begin{center}

   316 \bl{\begin{tabular}{lcl}

   317 $\meta{U}$ & $\rightarrow$ &  $1 \cdot \meta{U}$\\

   318         & $|$ & $\epsilon$

   319 \end{tabular}}

   320 \end{center}

   321 

   322 \end{frame}

   323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   324 

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

   326 \begin{frame}[t]

   327 \frametitle{Ambiguous Grammars}

   328 

   329 \begin{center}

   330 \begin{tikzpicture}

   331 \begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},

   332     enlargelimits=false,

   333     xtick={0,100,...,1000},

   334     xmax=1050,

   335     ymax=33,

   336     ytick={0,5,...,30},

   337     scaled ticks=false,

   338     axis lines=left,

   339     width=11cm,

   340     height=7cm, 

   341     legend entries={unambiguous,ambiguous},  

   342     legend pos=north east,

   343     legend cell align=left,

   344     x tick label style={font=\small,/pgf/number format/1000 sep={}}]

   345 \addplot[blue,mark=*, mark options={fill=white}] 

   346   table {s-grammar1.data};

   347 \only<2>{

   348   \addplot[red,mark=triangle*, mark options={fill=white}] 

   349   table {s-grammar2.data};}  

   350 \end{axis}

   351 \end{tikzpicture}

   352 \end{center}

   353 

   354 \end{frame}

   355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   356 

   357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   358 \begin{frame}

   359 \frametitle{While-Language}

   360 \mbox{}\\[-23mm]\mbox{}

   361 

   362 \bl{\begin{plstx}[rhs style=,one per line]: \meta{Stmt} ::= skip

   363          | \meta{Id} := \meta{AExp}

   364          | if \meta{BExp} then \meta{Block} else \meta{Block}

   365          | while \meta{BExp} do \meta{Block}\\

   366 : \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}

   367           | \meta{Stmt}\\

   368 : \meta{Block} ::= \{ \meta{Stmts} \}

   369           | \meta{Stmt}\\

   370 : \meta{AExp} ::= \ldots\\

   371 : \meta{BExp} ::= \ldots\\\end{plstx}}

   372 

   373 \end{frame}

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

   375 

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

   377 \begin{frame}[c]

   378 \frametitle{An Interpreter}

   379 

   380 \begin{center}

   381 \bl{\begin{tabular}{l}

   382 $\{$\\

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

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

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

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

   387 $\}$

   388 \end{tabular}}

   389 \end{center}

   390 

   391 \begin{itemize}

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

   393 \item \bl{\texttt{eval(stmt, env)}}

   394 \end{itemize}

   395 

   396 \end{frame}

   397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   398 

   399 

   400 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   401 \mode<presentation>{

   402 \begin{frame}[c]

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

   404 

   405 \begin{center}

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

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

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

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

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

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

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

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

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

   415 \end{tabular}}

   416 \end{center}

   417 

   418 \end{frame}}

   419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   421 \mode<presentation>{

   422 \begin{frame}[c]

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

   424 

   425 \begin{center}

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

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

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

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

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

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

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

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

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

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

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

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

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

   439 \end{tabular}}

   440 \end{center}

   441 

   442 \end{frame}}

   443 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   444 

   445 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   446 \begin{frame}[c]

   447 \frametitle{Test Program}

   448 

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

   450 

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

   452 %\texttt{\lstinputlisting{../progs/loops.while}}}

   453 

   454 \end{frame}

   455 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   456 

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

   458 \mode<presentation>{

   459 \begin{frame}[t]

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

   461 

   462 \begin{center}

   463 \begin{tikzpicture}

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

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

   466 \end{axis}

   467 \end{tikzpicture}

   468 \end{center}

   469 

   470 \end{frame}}

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

   472 

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

   474 \mode<presentation>{

   475 \begin{frame}[c]

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

   477 

   478 \begin{itemize}

   479 \item introduced in 1995

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

   481 \item contains a JIT compiler

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

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

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

   485 \end{itemize}

   486 

   487 \end{frame}}

   488 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   489 

   490