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