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