666
+ − 1 % !TEX program = xelatex
744
+ − 2 \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 3 \usepackage{../slides}
871
+ − 4 \usepackage{../graphicss}
215
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 5 \usepackage{../langs}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 6 \usepackage{../data}
597
+ − 7 \usepackage{../grammar}
49
+ − 8
+ − 9 % beamer stuff
445
+ − 10 \renewcommand{\slidecaption}{CFL 06, King's College London}
+ − 11
+ − 12
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 13 \newcommand{\bl}[1]{\textcolor{blue}{#1}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 14 %\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 15 \newcommand{\qq}{\mbox{\texttt{"}}}
49
+ − 16
809
+ − 17 \usepackage{tcolorbox}
+ − 18 \newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
+ − 19 \newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
+ − 20 \newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
+ − 21
+ − 22
+ − 23
49
+ − 24 \begin{document}
+ − 25
+ − 26 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 27 \begin{frame}[t]
49
+ − 28 \frametitle{%
+ − 29 \begin{tabular}{@ {}c@ {}}
+ − 30 \\[-3mm]
895
+ − 31 \LARGE Compilers and \\[-1mm]
+ − 32 \LARGE Formal Languages\\[-5mm]
49
+ − 33 \end{tabular}}
+ − 34
+ − 35 \normalsize
+ − 36 \begin{center}
+ − 37 \begin{tabular}{ll}
895
+ − 38 Email: & christian.urban at kcl.ac.uk\\
+ − 39 Office Hour: & Fridays 11 -- 12\\
+ − 40 Location: & N7.07 (North Wing, Bush House)\\
+ − 41 Slides \& Progs: & KEATS\\
+ − 42 Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
49
+ − 43 \end{tabular}
+ − 44 \end{center}
+ − 45
744
+ − 46 \begin{center}
+ − 47 \begin{tikzpicture}
+ − 48 \node[drop shadow,fill=white,inner sep=0pt]
+ − 49 {\footnotesize\rowcolors{1}{capri!10}{white}
+ − 50 \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ − 51 1 Introduction, Languages & \cellcolor{blue!50} 6 While-Language \\
+ − 52 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ − 53 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ − 54 4 Lexing, Tokenising & 9 Optimisations \\
+ − 55 5 Grammars, Parsing & 10 LLVM \\ \hline
+ − 56 \end{tabular}%
+ − 57 };
+ − 58 \end{tikzpicture}
+ − 59 \end{center}
+ − 60
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 61 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
49
+ − 63
849
+ − 64
+ − 65 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 66 \begin{frame}[c]
+ − 67 \frametitle{Parser Combinators}
+ − 68
+ − 69 One of the simplest ways to implement a parser, see
+ − 70 {\small\url{https://vimeo.com/142341803}} (by Haoyi Li)\bigskip
+ − 71
+ − 72 \begin{itemize}
895
+ − 73 \item[$\bullet$] built-in library in Scala
849
+ − 74 \item[$\bullet$] fastparse (2) library by Haoyi Li; is part of Ammonite
+ − 75 \item[$\bullet$] possible exponential runtime behaviour
+ − 76 \end{itemize}
+ − 77
+ − 78 \end{frame}
+ − 79 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 80
+ − 81 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 82 \begin{frame}[c]
+ − 83 \frametitle{Parser Combinators}
+ − 84
+ − 85 Parser combinators: \bigskip
+ − 86
+ − 87 \begin{minipage}{1.1\textwidth}
+ − 88 \begin{center}
+ − 89 \mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$}
+ − 90 $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$
+ − 91 \end{center}
+ − 92 \end{minipage}\bigskip
+ − 93
+ − 94 \begin{itemize}
+ − 95 \item atomic parsers
+ − 96 \item sequencing
+ − 97 \item alternative
+ − 98 \item semantic action (map-parser)
+ − 99 \end{itemize}
+ − 100
+ − 101 \end{frame}
+ − 102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 103
+ − 104 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 105 \begin{frame}[c]
+ − 106
+ − 107 Atomic parsers, for example, number tokens
+ − 108
+ − 109 \begin{center}
+ − 110 \bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$}
+ − 111 \end{center}\bigskip
+ − 112
+ − 113 \begin{itemize}
+ − 114 \item you consume one or more token from the\\
+ − 115 input (stream)
+ − 116 \item also works for characters and strings
+ − 117 \end{itemize}
+ − 118 \end{frame}
+ − 119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 120
+ − 121
+ − 122
+ − 123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 124 \begin{frame}[c]
+ − 125
+ − 126 Alternative parser (code \bl{$p\;||\;q$})\bigskip
+ − 127
+ − 128 \begin{itemize}
+ − 129 \item apply \bl{$p$} and also \bl{$q$}; then combine
+ − 130 the outputs
+ − 131 \end{itemize}
+ − 132
+ − 133 \begin{center}
+ − 134 \large \bl{$p(\text{input}) \cup q(\text{input})$}
+ − 135 \end{center}
+ − 136
+ − 137 \end{frame}
+ − 138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 139
+ − 140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 141 \begin{frame}[c]
+ − 142
+ − 143 Sequence parser (code \bl{$p\sim q$})\bigskip
+ − 144
+ − 145 \begin{itemize}
+ − 146 \item apply first \bl{$p$} producing a set of pairs
+ − 147 \item then apply \bl{$q$} to the unparsed parts
+ − 148 \item then combine the results:\medskip
+ − 149 \begin{center}
+ − 150 ((output$_1$, output$_2$), unparsed part)
+ − 151 \end{center}
+ − 152 \end{itemize}
+ − 153
+ − 154 \begin{center}
+ − 155 \begin{tabular}{l}
+ − 156 \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm]
+ − 157 \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
+ − 158 \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
+ − 159 \end{tabular}
+ − 160 \end{center}
+ − 161
+ − 162
+ − 163 \end{frame}
+ − 164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 165
+ − 166 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 167 \begin{frame}[c]
+ − 168
+ − 169 Map-parser (code \bl{$p.map(f)\;$})\bigskip
+ − 170
+ − 171 \begin{itemize}
+ − 172 \item apply \bl{$p$} producing a set of pairs
+ − 173 \item then apply the function \bl{$f$} to each first component
+ − 174 \end{itemize}
+ − 175
+ − 176 \begin{center}
+ − 177 \begin{tabular}{l}
+ − 178 \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
+ − 179 \end{tabular}
+ − 180 \end{center}\bigskip\bigskip\pause
+ − 181
+ − 182 \bl{$f$} is the semantic action (``what to do with the parsed input'')
+ − 183
+ − 184 \end{frame}
+ − 185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 186
+ − 187 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 188 \begin{frame}[c]
+ − 189 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
+ − 190
+ − 191 Addition
+ − 192
+ − 193 \begin{center}
+ − 194 \bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
+ − 195 \end{center}\pause
+ − 196
+ − 197 Multiplication
+ − 198
+ − 199 \begin{center}
+ − 200 \bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
+ − 201 \end{center}\pause
+ − 202
+ − 203 Parenthesis
+ − 204
+ − 205 \begin{center}
+ − 206 \bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
+ − 207 \end{center}
+ − 208
+ − 209 \end{frame}
+ − 210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 211
+ − 212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 213 \begin{frame}[c]
+ − 214 \frametitle{Input Types of Parsers}
+ − 215
+ − 216 \begin{itemize}
+ − 217 \item input: \alert{token list}
+ − 218 \item output: set of (output\_type, \alert{token list})
+ − 219 \end{itemize}\bigskip\pause
+ − 220
+ − 221 actually it can be any input type as long as it is a kind of
+ − 222 sequence (for example a string)
+ − 223
+ − 224 \end{frame}
+ − 225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 226
+ − 227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 228 \begin{frame}[c]
+ − 229 \frametitle{Scannerless Parsers}
+ − 230
+ − 231 \begin{itemize}
+ − 232 \item input: \alert{string}
+ − 233 \item output: set of (output\_type, \alert{string})
+ − 234 \end{itemize}\bigskip\bigskip
+ − 235
+ − 236 but using lexers is better because whitespaces or comments can be
+ − 237 filtered out; then input is a sequence of tokens
+ − 238
+ − 239 \end{frame}
+ − 240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 241
+ − 242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 243 \begin{frame}[c]
+ − 244 \frametitle{Abstract Parser Class}
+ − 245
+ − 246 \small
+ − 247 \lstinputlisting[language=Scala,xleftmargin=1mm]
+ − 248 {../progs/app7.scala}
+ − 249 \end{frame}
+ − 250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 251
+ − 252
+ − 253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 254 \begin{frame}[c]
+ − 255 \frametitle{Successful Parses}
+ − 256
+ − 257 \begin{itemize}
+ − 258 \item input: string
+ − 259 \item output: \alert{set of} (output\_type, string)
+ − 260 \end{itemize}\bigskip
+ − 261
+ − 262 a parse is successful whenever the input has been fully
+ − 263 ``consumed'' (that is the second component is empty)
+ − 264
+ − 265 \end{frame}
+ − 266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 267
+ − 268
+ − 269
799
+ − 270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 271 \begin{frame}[c]
803
+ − 272 %%\frametitle{Test Program}
799
+ − 273
803
+ − 274 \mbox{}\\[-18mm]\mbox{}
799
+ − 275
803
+ − 276 {\lstset{language=While}%%\fontsize{10}{12}\selectfont
+ − 277 \texttt{\lstinputlisting{../progs/while-tests/loops.while}}}
799
+ − 278
+ − 279 \end{frame}
+ − 280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 281
+ − 282
+ − 283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 284 \begin{frame}
+ − 285 \frametitle{While-Language}
+ − 286 \mbox{}\\[-23mm]\mbox{}
+ − 287
+ − 288 \bl{\begin{plstx}[rhs style=,one per line]: \meta{Stmt} ::= skip
+ − 289 | \meta{Id} := \meta{AExp}
+ − 290 | if \meta{BExp} then \meta{Block} else \meta{Block}
+ − 291 | while \meta{BExp} do \meta{Block}\\
+ − 292 : \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}
+ − 293 | \meta{Stmt}\\
+ − 294 : \meta{Block} ::= \{ \meta{Stmts} \}
+ − 295 | \meta{Stmt}\\
+ − 296 : \meta{AExp} ::= \ldots\\
+ − 297 : \meta{BExp} ::= \ldots\\\end{plstx}}
+ − 298
+ − 299 \end{frame}
+ − 300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 301
+ − 302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
803
+ − 303 \mode<presentation>{
799
+ − 304 \begin{frame}[c]
803
+ − 305 \frametitle{\begin{tabular}{c}Aexps\end{tabular}}
799
+ − 306
+ − 307 \begin{center}
803
+ − 308 \bl{\begin{tabular}{@{}lcl@{}}
+ − 309 $\text{eval}(n)$ & $\dn$ & $n$\\
+ − 310 $\text{eval}(a_1 + a_2)$ & $\dn$ & $\text{eval}(a_1) + \text{eval}(a_2)$\\
+ − 311 $\text{eval}(a_1 - a_2)$ & $\dn$ & $\text{eval}(a_1) - \text{eval}(a_2)$\\
+ − 312 $\text{eval}(a_1 * a_2)$ & $\dn$ & $\text{eval}(a_1) * \text{eval}(a_2)$\bigskip\\
+ − 313 $\text{eval}(x)$ & $\dn$ & $???$\\
799
+ − 314 \end{tabular}}
+ − 315 \end{center}
+ − 316
803
+ − 317 \end{frame}}
+ − 318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
799
+ − 319
+ − 320
+ − 321
+ − 322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 323 \mode<presentation>{
+ − 324 \begin{frame}[c]
+ − 325 \frametitle{\begin{tabular}{c}Interpreter\end{tabular}}
+ − 326
+ − 327 \begin{center}
+ − 328 \bl{\begin{tabular}{@{}lcl@{}}
+ − 329 $\text{eval}(n, E)$ & $\dn$ & $n$\\
+ − 330 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\
+ − 331 $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\
+ − 332 $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\
+ − 333 $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\
+ − 334 $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\
+ − 335 $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\
+ − 336 $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\
+ − 337 \end{tabular}}
+ − 338 \end{center}
+ − 339
+ − 340 \end{frame}}
803
+ − 341 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 342
+ − 343
+ − 344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 345 \begin{frame}[c]
+ − 346 \frametitle{An Interpreter (1)}
+ − 347
+ − 348 \begin{center}
+ − 349 \bl{\begin{tabular}{l}
+ − 350 $\{$\\
+ − 351 \;\;$x := 5 \text{;}$\\
+ − 352 \;\;$y := x * 3\text{;}$\\
+ − 353 \;\;$y := x * 4\text{;}$\\
+ − 354 \;\;$x := u * 3$\\
+ − 355 $\}$
+ − 356 \end{tabular}}
+ − 357 \end{center}
+ − 358
+ − 359 \begin{itemize}
+ − 360 \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
+ − 361 \item \bl{\texttt{eval(stmt, env)}}
+ − 362 \end{itemize}
+ − 363
+ − 364 \end{frame}
799
+ − 365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
803
+ − 366
799
+ − 367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 368 \mode<presentation>{
+ − 369 \begin{frame}[c]
+ − 370 \frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}
+ − 371
+ − 372 \begin{center}
+ − 373 \bl{\begin{tabular}{@{}lcl@{}}
+ − 374 $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\
+ − 375 $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\
+ − 376 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\
+ − 377 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;
+ − 378 \text{eval}(cs_1,E)$}\\
+ − 379 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\
+ − 380 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\
+ − 381 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\
+ − 382 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;
+ − 383 \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\
+ − 384 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\
+ − 385 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\
+ − 386 \end{tabular}}
+ − 387 \end{center}
+ − 388
+ − 389 \end{frame}}
+ − 390 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 391
+ − 392
+ − 393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 394 \mode<presentation>{
+ − 395 \begin{frame}[t]
+ − 396 \frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}
+ − 397
+ − 398 \begin{center}
+ − 399 \begin{tikzpicture}
+ − 400 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
+ − 401 \addplot+[smooth] file {interpreted.data};
+ − 402 \end{axis}
+ − 403 \end{tikzpicture}
+ − 404 \end{center}
+ − 405
+ − 406 \end{frame}}
+ − 407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 408
809
+ − 409
+ − 410 \begin{frame}[t,fragile]
+ − 411 \begin{mybox3}{}
+ − 412 In CW3, in the collatz program there is the line write "$\backslash$n" Should this print "/n" or perform the new line command /n ? Also should write be print() or println() ?
+ − 413 \end{mybox3}
+ − 414 \end{frame}
+ − 415
+ − 416
895
+ − 417 \begin{frame}<1-30>[c]
809
+ − 418 \end{frame}
+ − 419
+ − 420
803
+ − 421 \end{document}
+ − 422
+ − 423
799
+ − 424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 425 \mode<presentation>{
+ − 426 \begin{frame}[c]
+ − 427 \frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}
+ − 428
+ − 429 \begin{itemize}
+ − 430 \item introduced in 1995
+ − 431 \item is a stack-based VM (like Postscript, CLR of .Net)
+ − 432 \item contains a JIT compiler
+ − 433 \item many languages take advantage of JVM's infrastructure (JRE)
+ − 434 \item is garbage collected $\Rightarrow$ no buffer overflows
+ − 435 \item some languages compile to the JVM: Scala, Clojure\ldots
+ − 436 \end{itemize}
+ − 437
+ − 438 \end{frame}}
+ − 439 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 440
+ − 441
+ − 442
803
+ − 443 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 444 % \begin{frame}[t]
+ − 445 % \frametitle{%
+ − 446 % \begin{tabular}{@ {}c@ {}}
+ − 447 % \\[-3mm]
+ − 448 % \LARGE Compilers and \\[-2mm]
+ − 449 % \LARGE Formal Languages\\[3mm]
+ − 450 % \end{tabular}}
799
+ − 451
803
+ − 452 % \normalsize
+ − 453 % \begin{center}
+ − 454 % \begin{tabular}{ll}
+ − 455 % Email: & christian.urban at kcl.ac.uk\\
+ − 456 % %Office Hours: & Thursdays 12 -- 14\\
+ − 457 % %Location: & N7.07 (North Wing, Bush House)\\
+ − 458 % Slides \& Progs: & KEATS (also homework is there)\\
+ − 459 % \end{tabular}
+ − 460 % \end{center}
799
+ − 461
803
+ − 462 % \begin{center}
+ − 463 % \begin{tikzpicture}
+ − 464 % \node[drop shadow,fill=white,inner sep=0pt]
+ − 465 % {\footnotesize\rowcolors{1}{capri!10}{white}
+ − 466 % \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ − 467 % 1 Introduction, Languages & \cellcolor{blue!50} 6 While-Language \\
+ − 468 % 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ − 469 % 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ − 470 % 4 Lexing, Tokenising & 9 Optimisations \\
+ − 471 % 5 Grammars, Parsing & 10 LLVM \\ \hline
+ − 472 % \end{tabular}%
+ − 473 % };
+ − 474 % \end{tikzpicture}
+ − 475 % \end{center}
799
+ − 476
803
+ − 477 % \end{frame}
+ − 478 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
799
+ − 479
+ − 480
+ − 481 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
531
+ − 482 % \begin{frame}[c]
+ − 483 % \small
+ − 484 % \mbox{}\\[5mm]
+ − 485 % %\begin{textblock}{10}(3,5)
+ − 486 % \begin{tikzpicture}[scale=1.5,
+ − 487 % node distance=1cm,
+ − 488 % every node/.style={minimum size=7mm}]
+ − 489 % \node (r1) {\bl{$r_1$}};
+ − 490 % \node (r2) [right=of r1] {\bl{$r_2$}};
+ − 491 % \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+ − 492 % \node (r3) [right=of r2] {\bl{$r_3$}};
+ − 493 % \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+ − 494 % \node (r4) [right=of r3] {\bl{$r_4$}};
+ − 495 % \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+ − 496 % \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+ − 497 % \node (v4) [below=of r4] {\bl{$v_4$}};
+ − 498 % \draw[->,line width=1mm] (r4) -- (v4);
+ − 499 % \node (v3) [left=of v4] {\bl{$v_3$}};
+ − 500 % \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+ − 501 % \node (v2) [left=of v3] {\bl{$v_2$}};
+ − 502 % \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+ − 503 % \node (v1) [left=of v2] {\bl{$v_1$}};
+ − 504 % \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+ − 505 % \draw[->,line width=0.5mm] (r3) -- (v3);
+ − 506 % \draw[->,line width=0.5mm] (r2) -- (v2);
+ − 507 % \draw[->,line width=0.5mm] (r1) -- (v1);
+ − 508 % \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+ − 509 % \end{tikzpicture}
+ − 510 % %\end{textblock}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 511
531
+ − 512 % \begin{center}
+ − 513 % \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+ − 514 % \\[-10mm]
+ − 515 % \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\
+ − 516 % \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
+ − 517 % \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
+ − 518 % \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+ − 519 % \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+ − 520 % \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
+ − 521 % \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\
+ − 522 % \end{tabular}
+ − 523 % \end{center}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 524
531
+ − 525 % \end{frame}
+ − 526 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 527
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 528 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
683
+ − 529 \begin{frame}[t]
+ − 530 \frametitle{Starting Symbol}
+ − 531
+ − 532 \bl{\begin{plstx}[margin=1cm]
+ − 533 : \meta{S} ::= \meta{A}\cdot\meta{S}\cdot\meta{B} |
+ − 534 \meta{B}\cdot\meta{S}\cdot\meta{A} | \epsilon\\
+ − 535 : \meta{A} ::= a | \epsilon\\
+ − 536 : \meta{B} ::= b\\
+ − 537 \end{plstx}}
+ − 538
750
+ − 539
+ − 540 TODO: Testcases for math expressions
+ − 541 \url{https://github.com/ArashPartow/math-parser-benchmark-project}
+ − 542
683
+ − 543 \end{frame}
+ − 544 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 545
+ − 546
+ − 547 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 548 \begin{frame}[c]
683
+ − 549 \frametitle{Hierarchy of Languages}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 550
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 551 Recall that languages are sets of strings.
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 552
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 553 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 554 \begin{tikzpicture}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 555 [rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 556
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 557 \draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 558 \draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 559 \draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 560 \draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 561 \draw (0,-1.4) node [rect] {regular languages};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 562 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 563
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 564 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 565
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 566 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 567 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 568
531
+ − 569
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 570
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 571 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 572 \begin{frame}[c]
598
+ − 573 \frametitle{Parser Combinators}
+ − 574
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 575 Atomic parsers, for example
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 576
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 577 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 578 \bl{$1::rest \;\Rightarrow\; \{(1, rest)\}$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 579 \end{center}\bigskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 580
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 581 \begin{itemize}
597
+ − 582 \item you consume one or more tokens from the\\
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 583 input (stream)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 584 \item also works for characters and strings
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 585 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 586 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 587 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 588
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 589 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 590 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 591
686
+ − 592 Alternative parser (code \bl{$p\;|\;q$})\bigskip
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 593
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 594 \begin{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 595 \item apply \bl{$p$} and also \bl{$q$}; then combine
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 596 the outputs
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 597 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 598
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 599 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 600 \large \bl{$p(\text{input}) \cup q(\text{input})$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 601 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 602
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 603 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 604 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 605
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 606 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 607 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 608
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 609 Sequence parser (code \bl{$p\sim q$})\bigskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 610
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 611 \begin{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 612 \item apply first \bl{$p$} producing a set of pairs
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 613 \item then apply \bl{$q$} to the unparsed parts
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 614 \item then combine the results:\medskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 615 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 616 ((output$_1$, output$_2$), unparsed part)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 617 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 618 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 619
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 620 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 621 \begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 622 \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 623 \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 624 \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 625 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 626 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 627
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 628
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 629 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 630 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 631
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 632 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 633 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 634
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 635 Function parser (code \bl{$p \Rightarrow f\;$})\bigskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 636
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 637 \begin{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 638 \item apply \bl{$p$} producing a set of pairs
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 639 \item then apply the function \bl{$f$} to each first component
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 640 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 641
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 642 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 643 \begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 644 \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 645 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 646 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 647
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 648 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 650
531
+ − 651 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 652 \begin{frame}[c]
+ − 653 \frametitle{Types of Parsers}
+ − 654
+ − 655 \begin{itemize}
+ − 656 \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
+ − 657 then \bl{$p \sim q$} returns results of type
+ − 658
+ − 659 \begin{center}
+ − 660 \bl{$T \times S$}
+ − 661 \end{center}\pause
+ − 662
+ − 663 \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then \bl{$q$} \alert{must} also have results of type \bl{$T$},
686
+ − 664 and \bl{$p \;|\; q$} returns results of type
531
+ − 665
+ − 666 \begin{center}
+ − 667 \bl{$T$}
+ − 668 \end{center}\pause
+ − 669
+ − 670 \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
+ − 671 \bl{$T$} to \bl{$S$}, then
+ − 672 \bl{$p \Rightarrow f$} returns results of type
+ − 673
+ − 674 \begin{center}
+ − 675 \bl{$S$}
+ − 676 \end{center}
+ − 677
+ − 678 \end{itemize}
+ − 679
+ − 680 \end{frame}
+ − 681 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 682
+ − 683
+ − 684
+ − 685 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 686 \begin{frame}[c]
+ − 687 \frametitle{Two Grammars}
+ − 688
+ − 689 Which languages are recognised by the following two grammars?
+ − 690
597
+ − 691 \bl{\begin{plstx}[margin=3cm]
+ − 692 : \meta{S} ::= \liningnums{1}\cdot\meta{S}\cdot \meta{S} | \epsilon\\
+ − 693 \end{plstx}}
531
+ − 694
597
+ − 695 \bl{\begin{plstx}[margin=3cm]
+ − 696 : \meta{U} ::= \liningnums{1}\cdot\meta{U} | \epsilon\\
+ − 697 \end{plstx}}
531
+ − 698
+ − 699 \end{frame}
+ − 700 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 701
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 703 \begin{frame}[t]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 704 \frametitle{Ambiguous Grammars}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 705
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 706 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 707 \begin{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 708 \begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 709 enlargelimits=false,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 710 xtick={0,100,...,1000},
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 711 xmax=1050,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 712 ymax=33,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 713 ytick={0,5,...,30},
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 714 scaled ticks=false,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 715 axis lines=left,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 716 width=11cm,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 717 height=7cm,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 718 legend entries={unambiguous,ambiguous},
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 719 legend pos=north east,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 720 legend cell align=left,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 721 x tick label style={font=\small,/pgf/number format/1000 sep={}}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 722 \addplot[blue,mark=*, mark options={fill=white}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 723 table {s-grammar1.data};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 724 \only<2>{
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 725 \addplot[red,mark=triangle*, mark options={fill=white}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 726 table {s-grammar2.data};}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 727 \end{axis}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 728 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 729 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 730
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 731 \end{frame}
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 732 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 733
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 734 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 735 \begin{frame}[c]
597
+ − 736 \frametitle{Arithmetic Expressions}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 737
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 738 A grammar for arithmetic expressions and numbers:
50
+ − 739
597
+ − 740 \bl{\begin{plstx}[margin=1cm]
+ − 741 : \meta{E} ::= \meta{E} \cdot + \cdot \meta{E}
+ − 742 | \meta{E} \cdot * \cdot \meta{E}
+ − 743 | ( \cdot \meta{E} \cdot ) | \meta{N}\\
+ − 744 : \meta{N} ::= \meta{N} \cdot \meta{N} |
+ − 745 0 | 1 | \ldots | 9\\
+ − 746 \end{plstx}}
49
+ − 747
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 748 Unfortunately it is left-recursive (and ambiguous).\medskip\\
597
+ − 749 A problem for \alert{recursive descent parsers} (e.g.~parser
+ − 750 combinators). \bigskip\pause
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 751
597
+ − 752 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 753 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 754
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 755
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 756 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 757 \begin{frame}[t]
597
+ − 758 \frametitle{Numbers}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 759
597
+ − 760 \bl{\begin{plstx}[margin=1cm]
+ − 761 : \meta{N} ::= \meta{N} \cdot \meta{N} |
+ − 762 0 | 1 | \ldots | 9\\
+ − 763 \end{plstx}}
49
+ − 764
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 765 A non-left-recursive, non-ambiguous grammar for numbers:
49
+ − 766
597
+ − 767 \bl{\begin{plstx}[margin=1cm]
+ − 768 : \meta{N} ::= 0 \cdot \meta{N} | 1 \cdot \meta{N} | \ldots |
+ − 769 0 | 1 | \ldots | 9\\
+ − 770 \end{plstx}}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 771
597
+ − 772 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 773 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 774
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 775 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 776 \begin{frame}[c]
597
+ − 777 \frametitle{Removing Left-Recursion}
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 778
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 779 The rule for numbers is directly left-recursive:
49
+ − 780
+ − 781 \begin{center}
50
+ − 782 \bl{\begin{tabular}{lcl}
597
+ − 783 $\meta{N}$ & $::=$ & $\meta{N} \cdot \meta{N} \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 784 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 785 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 786
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 787 Translate
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 788
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 789 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 790 \begin{tabular}{ccc}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 791 \bl{\begin{tabular}{lcl}
597
+ − 792 $\meta{N}$ & $::=$ & $\meta{N} \cdot \alpha$\\
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 793 & $\;|\;$ & $\beta$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 794 \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 795 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 796 & {\Large$\Rightarrow$} &
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 797 \bl{\begin{tabular}{lcl}
597
+ − 798 $\meta{N}$ & $::=$ & $\beta \cdot \meta{N}'$\\
+ − 799 $\meta{N}'$ & $::=$ & $\alpha \cdot \meta{N}'$\\
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 800 & $\;|\;$ & $\epsilon$
50
+ − 801 \end{tabular}}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 802 \end{tabular}
50
+ − 803 \end{center}\pause
+ − 804
597
+ − 805 Which means in this case:
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 806
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 807 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 808 \bl{\begin{tabular}{lcl}
597
+ − 809 $\meta{N}$ & $\rightarrow$ & $0 \cdot \meta{N}' \;|\; 1 \cdot \meta{N}'$\\
+ − 810 $\meta{N}'$ & $\rightarrow$ & $\meta{N} \cdot \meta{N}' \;|\; \epsilon$\\
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 811 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 812 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 813
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 814
597
+ − 815 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 816 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 817
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 818 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
685
+ − 819 %\begin{frame}[c]
+ − 820 %\frametitle{Operator Precedences}
+ − 821 %
+ − 822 %
+ − 823 %To disambiguate
+ − 824 %
+ − 825 %\begin{center}
+ − 826 %\bl{\begin{tabular}{lcl}
+ − 827 %$\meta{E}$ & $::=$ & $\meta{E} \cdot + \cdot \meta{E} \;|\;\meta{E} \cdot * \cdot \meta{E} \;|\;( \cdot \meta{E} \cdot ) \;|\;\meta{N}$ \\
+ − 828 %\end{tabular}}
+ − 829 %\end{center}
+ − 830 %
+ − 831 %Decide on how many precedence levels, say\medskip\\
+ − 832 %highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
+ − 833 %
+ − 834 %\begin{center}
+ − 835 %\bl{\begin{tabular}{lcl}
+ − 836 %$\meta{E}_{low}$ & $::=$ & $\meta{E}_{med} \cdot + \cdot \meta{E}_{low} \;|\; \meta{E}_{med}$ \\
+ − 837 %$\meta{E}_{med}$ & $::=$ & $\meta{E}_{hi} \cdot * \cdot \meta{E}_{med} \;|\; \meta{E}_{hi}$\\
+ − 838 %$\meta{E}_{hi}$ & $::=$ & $( \cdot \meta{E}_{low} \cdot ) \;|\;\meta{N}$ \\
+ − 839 %\end{tabular}}
+ − 840 %\end{center}\pause
+ − 841 %
+ − 842 %\small What happens with \bl{$1 + 3 + 4$}?
+ − 843 %\end{frame}
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 844 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 845
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 846 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 847 \begin{frame}[c]
597
+ − 848 \frametitle{Chomsky Normal Form}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 849
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 850 All rules must be of the form
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 851
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 852 \begin{center}
597
+ − 853 \bl{$\meta{A} ::= a$}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 854 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 855
50
+ − 856 or
+ − 857
+ − 858 \begin{center}
597
+ − 859 \bl{$\meta{A} ::= \meta{B}\cdot \meta{C}$}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 860 \end{center}
49
+ − 861
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 862 No rule can contain \bl{$\epsilon$}.
49
+ − 863
597
+ − 864 \end{frame}
49
+ − 865 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 866
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 867 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 868 \begin{frame}[c]
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 869 \frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}}
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 870
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 871 \begin{enumerate}
597
+ − 872 \item If \bl{$A::= \alpha \cdot B \cdot \beta$} and \bl{$B ::= \epsilon$} are in the grammar,
+ − 873 then add \bl{$A::= \alpha \cdot \beta$} (iterate if necessary).
+ − 874 \item Throw out all \bl{$B ::= \epsilon$}.
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 875 \end{enumerate}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 876
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 877 \small
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 878 \begin{center}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 879 \begin{tabular}{ccc}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 880 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
597
+ − 881 $N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'$\\
+ − 882 $N'$ & $::=$ & $N \cdot N'\;|\;\epsilon$\\
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 883 \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 884 \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 885 \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 886 \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 887 \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 888 \end{tabular}} &
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 889 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 890 \\
597
+ − 891 $N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
+ − 892 $N'$ & $::=$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 893 \\
597
+ − 894 $N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
+ − 895 $N'$ & $::=$ & $N \cdot N'\;|\;N$\\
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 896 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 897 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 898 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 899
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 900 \pause\normalsize
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 901 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 902 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
597
+ − 903 $N$ & $::=$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 904 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 905
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 906 \end{center}
368
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 907 \end{frame}
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 908 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 909
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 910
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 911
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 912 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 913 \begin{frame}[c]
597
+ − 914 \frametitle{CYK Algorithm}
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 915
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 916 If grammar is in Chomsky normalform \ldots
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 917
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 918 \begin{center}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 919 \bl{\begin{tabular}{@ {}lcl@ {}}
597
+ − 920 $\meta{S}$ & $::=$ & $\meta{N}\cdot \meta{P}$ \\
+ − 921 $\meta{P}$ & $::=$ & $\meta{V}\cdot \meta{N}$ \\
+ − 922 $\meta{N}$ & $::=$ & $\meta{N}\cdot \meta{N}$ \\
+ − 923 $\meta{N}$ & $::=$ & $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
+ − 924 $\meta{V}$ & $::=$ & $\texttt{trains}$
49
+ − 925 \end{tabular}}
+ − 926 \end{center}
+ − 927
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 928 \bl{\texttt{Jeff trains geometry students}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 929
597
+ − 930 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 931 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
597
+ − 932
+ − 933 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 934 \begin{frame}[c]
597
+ − 935 \frametitle{CYK Algorithm}
49
+ − 936
+ − 937
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 938 \begin{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 939 \item fastest possible algorithm for recognition problem
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 940 \item runtime is \bl{$O(n^3)$}\bigskip
597
+ − 941 \item grammars need to be transformed into CNF
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 942 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 943
597
+ − 944 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 945 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 946
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 947 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 948 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 949 \frametitle{The Goal of this Course}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 950 \mbox{}\\[-26mm]\mbox{}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 951
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 952 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 953 \begin{tikzpicture}[scale=1,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 954 node/.style={
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 955 rectangle,rounded corners=3mm,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 956 very thick,draw=black!50,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 957 minimum height=18mm, minimum width=20mm,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 958 top color=white,bottom color=black!20}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 959
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 960 \node at (3.05, 1.8) {\Large\bf Write a Compiler};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 961
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 962 \node (0) at (-2.3,0) {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 963
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 964 \node (A) at (0,0) [node] {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 965 \node [below right] at (A.north west) {lexer};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 966
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 967 \node (B) at (3,0) [node] {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 968 \node [below right=1mm] at (B.north west)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 969 {\mbox{}\hspace{-1mm}parser};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 970
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 971 \node (C) at (6,0) [node] {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 972 \node [below right] at (C.north west)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 973 {\mbox{}\hspace{-1mm}code gen};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 974
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 975 \node (1) at (8.4,0) {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 976
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 977 \draw [->,line width=4mm] (0) -- (A);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 978 \draw [->,line width=4mm] (A) -- (B);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 979 \draw [->,line width=4mm] (B) -- (C);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 980 \draw [->,line width=4mm] (C) -- (1);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 981 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 982 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 983
598
+ − 984 We have a lexer and a parser\ldots
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 985
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 986 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 987
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 988 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 989 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 990
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 991 \begin{center}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 992 \bl{\begin{tabular}{@{}lcl@{}}
598
+ − 993 \meta{Stmt} & $::=$ & $\texttt{skip}$\\
+ − 994 & $|$ & \textit{Id}\;\texttt{:=}\;\meta{AExp}\\
+ − 995 & $|$ & \texttt{if}\; \meta{BExp} \;\texttt{then}\; \meta{Block} \;\texttt{else}\; \meta{Block}\\
+ − 996 & $|$ & \texttt{while}\; \meta{BExp} \;\texttt{do}\; \meta{Block}\\
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 997 & $|$ & \texttt{read}\;\textit{Id}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 998 & $|$ & \texttt{write}\;\textit{Id}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 999 & $|$ & \texttt{write}\;\textit{String}\medskip\\
598
+ − 1000 \meta{Stmts} & $::=$ & \meta{Stmt} \;\texttt{;}\; \meta{Stmts}\\
+ − 1001 & $|$ & \meta{Stmt}\medskip\\
+ − 1002 \meta{Block} & $::=$ & \texttt{\{}\,\meta{Stmts}\,\texttt{\}}\\
+ − 1003 & $|$ & \meta{Stmt}\medskip\\
+ − 1004 \meta{AExp} & $::=$ & \ldots\\
+ − 1005 \meta{BExp} & $::=$ & \ldots\\
50
+ − 1006 \end{tabular}}
+ − 1007 \end{center}
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1008 \end{frame}
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1009 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1010
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1011 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1012 \mode<presentation>{
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1013 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1014
744
+ − 1015 ??%%\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1016
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1017 \end{frame}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1018 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1019
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1020
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1021 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1022 \begin{frame}[c]
598
+ − 1023 \frametitle{An Interpreter}
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1024
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1025 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1026 \bl{\begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1027 $\{$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1028 \;\;$x := 5 \text{;}$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1029 \;\;$y := x * 3\text{;}$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1030 \;\;$y := x * 4\text{;}$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1031 \;\;$x := u * 3$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1032 $\}$
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1033 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1034 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1035
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1036 \begin{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1037 \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1038 \item \bl{\text{eval}(stmt, env)}
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1039 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1040
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1041
598
+ − 1042 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1043 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1044
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1045 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1046 \begin{frame}[c]
598
+ − 1047 \frametitle{An Interpreter}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1048
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1049 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1050 \bl{\begin{tabular}{@{}lcl@{}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1051 $\text{eval}(n, E)$ & $\dn$ & $n$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1052 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1053 $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1054 $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1055 $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1056 $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1057 $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1058 $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1059 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1060 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1061
598
+ − 1062 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1063 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
598
+ − 1064
+ − 1065 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1066 \begin{frame}[c]
598
+ − 1067 \frametitle{An Interpreter (2)}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1068
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1069 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1070 \bl{\begin{tabular}{@{}lcl@{}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1071 $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1072 $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1073 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1074 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1075 \text{eval}(cs_1,E)$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1076 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1077 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1078 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1079 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1080 \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1081 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1082 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1083 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1084 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1085
598
+ − 1086 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1087 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1088
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1089 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1090 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1091 \frametitle{\begin{tabular}{c}Test Program\end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1092
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1093 \mbox{}\\[-18mm]\mbox{}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1094
744
+ − 1095 ??
+ − 1096 %{\lstset{language=While}%%\fontsize{10}{12}\selectfont
+ − 1097 %\texttt{\lstinputlisting{../progs/loops.while}}}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1098
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1099 \end{frame}
169
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1101
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1103 \mode<presentation>{
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1104 \begin{frame}[t]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1105 \frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1106
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1107 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1108 \begin{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1109 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1110 \addplot+[smooth] file {interpreted.data};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1111 \end{axis}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1112 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1113 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1114
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1115 \end{frame}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1117
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1119 \begin{frame}[c]
685
+ − 1120 \frametitle{Java Virtual Machine}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1121
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1122 \begin{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1123 \item introduced in 1995
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1124 \item is a stack-based VM (like Postscript, CLR of .Net)
685
+ − 1125 \item contains a JIT compiler\\
+ − 1126 \begin{itemize}
+ − 1127 \item From the Cradle to the Holy Graal - the JDK Story
+ − 1128 \item \url{https://www.youtube.com/watch?v=h419kfbLhUI}
+ − 1129 \end{itemize}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1130 \item is garbage collected $\Rightarrow$ no buffer overflows
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1131 \item some languages compile to the JVM: Scala, Clojure\ldots
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1132 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1133
685
+ − 1134 \end{frame}
365
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1135 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1136
685
+ − 1137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1138 \begin{frame}[c]
+ − 1139 \frametitle{LLVM}
+ − 1140
+ − 1141 \begin{itemize}
+ − 1142 \item LLVM started by academics in 2000 (University of Illinois in
+ − 1143 Urbana-Champaign)
+ − 1144 \item suite of compiler tools
+ − 1145 \item SSA-based intermediate language
+ − 1146 \item no need to allocate registers
686
+ − 1147 \item source languages: C, C++, Rust, Go, Swift
+ − 1148 \item target CPUs: x86, ARM, PowerPC, \ldots
685
+ − 1149 \end{itemize}
+ − 1150 \end{frame}
+ − 1151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
702
+ − 1152
598
+ − 1153 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
666
+ − 1154 %\begin{frame}[c]
+ − 1155 % \frametitle{Coursework: MkEps}
+ − 1156 %
+ − 1157 %\begin{center}
+ − 1158 %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+ − 1159 % \bl{$mkeps([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $\bl{undefined}$\\
+ − 1160 % \bl{$mkeps(r^*)$} & \bl{$\dn$} & $\bl{Stars\,[]}$\\
+ − 1161 % \bl{$mkeps(r^{\{n\}})$} & \bl{$\dn$} & $\bl{Stars\,(mkeps(r))^n}$\\
+ − 1162 % \bl{$mkeps(r^{\{n..\}})$} & \bl{$\dn$} & $\bl{Stars\,(mkeps(r))^n}$\\
+ − 1163 % \bl{$mkeps(r^{\{..n\}})$} & \bl{$\dn$} & $\bl{Stars\,[]}$\\
+ − 1164 % \bl{$mkeps(r^{\{n..m\}})$} & \bl{$\dn$} & $\bl{Stars\,(mkeps(r))^n}$\medskip\\
+ − 1165 %
+ − 1166 % \bl{$mkeps(r^+)$} & \bl{$\dn$} & \bl{$mkeps(r^{\{1..\}})$}\\
+ − 1167 % \bl{$mkeps(r^?)$} & \bl{$\dn$} & \bl{$mkeps(r^{\{..1\}})$}\\
+ − 1168 %\end{tabular}
+ − 1169 %\end{center}
+ − 1170 %
+ − 1171 %\end{frame}
+ − 1172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1173 %
+ − 1174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1175 %\begin{frame}[c]
+ − 1176 % \frametitle{Coursework: Inj}
+ − 1177 %
+ − 1178 %\begin{center}
+ − 1179 %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+ − 1180 % \bl{$inj([c_1 c_2 \ldots c_n])\,c\,Empty$} & \bl{$\dn$} & $\bl{Chr\,c}$\\
+ − 1181 % \bl{$inj(r^*)\,c\;(Seq\,v\,(Stars\,vs))$} & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\\
+ − 1182 % \bl{$inj(r^{\{n\}})\,c\;(Seq\,v\,(Stars\,vs))$} & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\\
+ − 1183 % \bl{$inj(r^{\{n..\}})\,c\;(Seq\,v\,(Stars\,vs))$} & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\\
+ − 1184 % \bl{$inj(r^{\{..n\}})\,c\;(Seq\,v\,(Stars\,vs))$} & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\\
+ − 1185 % \bl{$inj(r^{\{n..m\}})\,c\;(Seq\,v\,(Stars\,vs))$} & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\medskip\\
+ − 1186 %
+ − 1187 % \bl{$inj(r^+)\,c\,v$} & \bl{$\dn$} & \bl{$inj(r^{\{1..\}})\,c\,v$}\\
+ − 1188 % \bl{$inj(r^?)\,c\,v$} & \bl{$\dn$} & \bl{$inj(r^{\{..1\}})\,c\,v$}\\
+ − 1189 %\end{tabular}
+ − 1190 %\end{center}
+ − 1191 %
+ − 1192 %\end{frame}
+ − 1193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
702
+ − 1194 %
598
+ − 1195
809
+ − 1196
+ − 1197
+ − 1198
49
+ − 1199 \end{document}
+ − 1200
803
+ − 1201
+ − 1202
+ − 1203 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1204 \begin{frame}[c]
+ − 1205 \frametitle{Parser Combinators}
+ − 1206
+ − 1207 Parser combinators: \bigskip
+ − 1208
+ − 1209 \begin{minipage}{1.1\textwidth}
+ − 1210 \begin{center}
+ − 1211 \mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$}
+ − 1212 $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$
+ − 1213 \end{center}
+ − 1214 \end{minipage}\bigskip
+ − 1215
+ − 1216 \begin{itemize}
+ − 1217 \item atomic parsers
+ − 1218 \item sequencing
+ − 1219 \item alternative
+ − 1220 \item semantic action (map-parser)
+ − 1221 \end{itemize}
+ − 1222
+ − 1223 \end{frame}
+ − 1224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1225
+ − 1226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1227 \begin{frame}[c]
+ − 1228
+ − 1229 Atomic parsers, for example, number tokens
+ − 1230
+ − 1231 \begin{center}
+ − 1232 \bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$}
+ − 1233 \end{center}\bigskip
+ − 1234
+ − 1235 \begin{itemize}
+ − 1236 \item you consume one or more token from the\\
+ − 1237 input (stream)
+ − 1238 \item also works for characters and strings
+ − 1239 \end{itemize}
+ − 1240 \end{frame}
+ − 1241 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1242
+ − 1243 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1244 \begin{frame}[c]
+ − 1245
+ − 1246 Alternative parser (code \bl{$p\;||\;q$})\bigskip
+ − 1247
+ − 1248 \begin{itemize}
+ − 1249 \item apply \bl{$p$} and also \bl{$q$}; then combine
+ − 1250 the outputs
+ − 1251 \end{itemize}
+ − 1252
+ − 1253 \begin{center}
+ − 1254 \large \bl{$p(\text{input}) \cup q(\text{input})$}
+ − 1255 \end{center}
+ − 1256
+ − 1257 \end{frame}
+ − 1258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1259
+ − 1260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1261 \begin{frame}[c]
+ − 1262
+ − 1263 Sequence parser (code \bl{$p\sim q$})\bigskip
+ − 1264
+ − 1265 \begin{itemize}
+ − 1266 \item apply first \bl{$p$} producing a set of pairs
+ − 1267 \item then apply \bl{$q$} to the unparsed part
+ − 1268 \item then combine the results:\medskip
+ − 1269 \begin{center}
+ − 1270 ((output$_1$, output$_2$), unparsed part)
+ − 1271 \end{center}
+ − 1272 \end{itemize}
+ − 1273
+ − 1274 \begin{center}
+ − 1275 \begin{tabular}{l}
+ − 1276 \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm]
+ − 1277 \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
+ − 1278 \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
+ − 1279 \end{tabular}
+ − 1280 \end{center}
+ − 1281
+ − 1282
+ − 1283 \end{frame}
+ − 1284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1285
+ − 1286 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1287 \begin{frame}[c]
+ − 1288
+ − 1289 Map-parser (code \bl{$p.map(f)\;$})\bigskip
+ − 1290
+ − 1291 \begin{itemize}
+ − 1292 \item apply \bl{$p$} producing a set of pairs
+ − 1293 \item then apply the function \bl{$f$} to each first component
+ − 1294 \end{itemize}
+ − 1295
+ − 1296 \begin{center}
+ − 1297 \begin{tabular}{l}
+ − 1298 \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
+ − 1299 \end{tabular}
+ − 1300 \end{center}\bigskip\bigskip\pause
+ − 1301
+ − 1302 \bl{$f$} is the semantic action (``what to do with the parsed input'')
+ − 1303
+ − 1304 \end{frame}
+ − 1305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1306
+ − 1307
+ − 1308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1309 \mode<presentation>{
+ − 1310 \begin{frame}[c]
+ − 1311 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
+ − 1312
+ − 1313 Addition
+ − 1314
+ − 1315 \begin{center}
+ − 1316 \bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
+ − 1317 \end{center}\pause
+ − 1318
+ − 1319 Multiplication
+ − 1320
+ − 1321 \begin{center}
+ − 1322 \bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
+ − 1323 \end{center}\pause
+ − 1324
+ − 1325 Parenthesis
+ − 1326
+ − 1327 \begin{center}
+ − 1328 \bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
+ − 1329 \end{center}
+ − 1330
+ − 1331 \end{frame}}
+ − 1332 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1333
+ − 1334 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1335 \begin{frame}[c]
+ − 1336 \frametitle{Types of Parsers}
+ − 1337
+ − 1338 \begin{itemize}
+ − 1339 \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
+ − 1340 then \bl{$p \sim q$} returns results of type
+ − 1341
+ − 1342 \begin{center}
+ − 1343 \bl{$T \times S$}
+ − 1344 \end{center}\pause
+ − 1345
+ − 1346 \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then \bl{$q$} \alert{must} also have results of type \bl{$T$},
+ − 1347 and \bl{$p \;||\; q$} returns results of type
+ − 1348
+ − 1349 \begin{center}
+ − 1350 \bl{$T$}
+ − 1351 \end{center}\pause
+ − 1352
+ − 1353 \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
+ − 1354 \bl{$T$} to \bl{$S$}, then
+ − 1355 \bl{$p \Rightarrow f$} returns results of type
+ − 1356
+ − 1357 \begin{center}
+ − 1358 \bl{$S$}
+ − 1359 \end{center}
+ − 1360
+ − 1361 \end{itemize}
+ − 1362
+ − 1363 \end{frame}
+ − 1364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1365
+ − 1366 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1367 \begin{frame}[c]
+ − 1368 \frametitle{Input Types of Parsers}
+ − 1369
+ − 1370 \begin{itemize}
+ − 1371 \item input: \alert{token list}
+ − 1372 \item output: set of (output\_type, \alert{token list})
+ − 1373 \end{itemize}\bigskip\pause
+ − 1374
+ − 1375 actually it can be any input type as long as it is a kind of
+ − 1376 sequence (for example a string)
+ − 1377
+ − 1378 \end{frame}
+ − 1379 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1380
+ − 1381 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1382 \begin{frame}[c]
+ − 1383 \frametitle{Scannerless Parsers}
+ − 1384
+ − 1385 \begin{itemize}
+ − 1386 \item input: \alert{string}
+ − 1387 \item output: set of (output\_type, \alert{string})
+ − 1388 \end{itemize}\bigskip\bigskip
+ − 1389
+ − 1390 but using lexers is better because whitespaces or comments can be
+ − 1391 filtered out; then input is a sequence of tokens
+ − 1392
+ − 1393 \end{frame}
+ − 1394 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1395
+ − 1396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1397 \begin{frame}[c]
+ − 1398 \frametitle{Successful Parses}
+ − 1399
+ − 1400 \begin{itemize}
+ − 1401 \item input: string
+ − 1402 \item output: \alert{set of} (output\_type, string)
+ − 1403 \end{itemize}\bigskip
+ − 1404
+ − 1405 a parse is successful whenever the input has been fully
+ − 1406 ``consumed'' (that is the second component is empty)
+ − 1407
+ − 1408 \end{frame}
+ − 1409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1410
+ − 1411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1412 \begin{frame}[c]
+ − 1413 \frametitle{Abstract Parser Class}
+ − 1414
+ − 1415 \small
+ − 1416 \lstinputlisting[language=Scala,xleftmargin=1mm]
+ − 1417 {../progs/app7.scala}
+ − 1418 \end{frame}
+ − 1419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1420
+ − 1421 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1422 \begin{frame}[c]
+ − 1423
+ − 1424 \small
+ − 1425 \fontsize{10}{12}\selectfont
+ − 1426 \lstinputlisting[language=Scala,xleftmargin=1mm]
+ − 1427 {../progs/app8.scala}
+ − 1428 \end{frame}
+ − 1429 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1430
+ − 1431
+ − 1432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1433 \begin{frame}[c]
+ − 1434 \frametitle{Two Grammars}
+ − 1435
+ − 1436 Which languages are recognised by the following two grammars?
+ − 1437
+ − 1438 \begin{center}
+ − 1439 \bl{\begin{tabular}{lcl}
+ − 1440 $\meta{S}$ & $\rightarrow$ & $1 \cdot \meta{S} \cdot \meta{S}$\\
+ − 1441 & $|$ & $\epsilon$
+ − 1442 \end{tabular}}
+ − 1443 \end{center}\bigskip
+ − 1444
+ − 1445 \begin{center}
+ − 1446 \bl{\begin{tabular}{lcl}
+ − 1447 $\meta{U}$ & $\rightarrow$ & $1 \cdot \meta{U}$\\
+ − 1448 & $|$ & $\epsilon$
+ − 1449 \end{tabular}}
+ − 1450 \end{center}
+ − 1451
+ − 1452 \end{frame}
+ − 1453 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1454
+ − 1455 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1456 \begin{frame}[t]
+ − 1457 \frametitle{Ambiguous Grammars}
+ − 1458
+ − 1459 \begin{center}
+ − 1460 \begin{tikzpicture}
+ − 1461 \begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
+ − 1462 enlargelimits=false,
+ − 1463 xtick={0,100,...,1000},
+ − 1464 xmax=1050,
+ − 1465 ymax=33,
+ − 1466 ytick={0,5,...,30},
+ − 1467 scaled ticks=false,
+ − 1468 axis lines=left,
+ − 1469 width=11cm,
+ − 1470 height=7cm,
+ − 1471 legend entries={unambiguous,ambiguous},
+ − 1472 legend pos=north east,
+ − 1473 legend cell align=left,
+ − 1474 x tick label style={font=\small,/pgf/number format/1000 sep={}}]
+ − 1475 \addplot[blue,mark=*, mark options={fill=white}]
+ − 1476 table {s-grammar1.data};
+ − 1477 \only<2>{
+ − 1478 \addplot[red,mark=triangle*, mark options={fill=white}]
+ − 1479 table {s-grammar2.data};}
+ − 1480 \end{axis}
+ − 1481 \end{tikzpicture}
+ − 1482 \end{center}
+ − 1483
+ − 1484 \end{frame}
+ − 1485 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1486
809
+ − 1487 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1488
803
+ − 1489
+ − 1490
+ − 1491
49
+ − 1492 %%% Local Variables:
+ − 1493 %%% mode: latex
+ − 1494 %%% TeX-master: t
+ − 1495 %%% End:
+ − 1496