| author | Christian Urban <urbanc@in.tum.de> | 
| Wed, 23 Oct 2019 22:23:10 +0100 | |
| changeset 665 | 81bb2db5e658 | 
| parent 664 | 44a1b8906b31 | 
| child 666 | 7612f066e832 | 
| permissions | -rw-r--r-- | 
| 582 | 1 | |
| 664 | 2 | % !TEX program = xelatex | 
| 44 | 3 | \documentclass[dvipsnames,14pt,t]{beamer}
 | 
| 270 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 4 | \usepackage{../slides}
 | 
| 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 5 | \usepackage{../graphics}
 | 
| 215 
828303e8e4af
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
169diff
changeset | 6 | \usepackage{../langs}
 | 
| 
828303e8e4af
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
169diff
changeset | 7 | \usepackage{../data}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 8 | \usepackage{../grammar}
 | 
| 44 | 9 | |
| 270 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 10 | \hfuzz=220pt | 
| 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 11 | |
| 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 12 | \pgfplotsset{compat=1.11}
 | 
| 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 13 | |
| 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 14 | \newcommand{\bl}[1]{\textcolor{blue}{#1}}  
 | 
| 44 | 15 | |
| 16 | % beamer stuff | |
| 445 | 17 | \renewcommand{\slidecaption}{CFL 05, King's College London}
 | 
| 270 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 18 | |
| 44 | 19 | |
| 20 | \begin{document}
 | |
| 21 | ||
| 22 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 270 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 23 | \begin{frame}[t]
 | 
| 44 | 24 | \frametitle{%
 | 
| 25 |   \begin{tabular}{@ {}c@ {}}
 | |
| 26 | \\[-3mm] | |
| 445 | 27 | \LARGE Compilers and \\[-2mm] | 
| 44 | 28 | \LARGE Formal Languages (5)\\[3mm] | 
| 29 |   \end{tabular}}
 | |
| 30 | ||
| 31 | \normalsize | |
| 32 |   \begin{center}
 | |
| 33 |   \begin{tabular}{ll}
 | |
| 664 | 34 | Email: & christian.urban at kcl.ac.uk\\ | 
| 35 | Office Hours: & Thursdays 12 -- 14\\ | |
| 36 | Location: & N7.07 (North Wing, Bush House)\\ | |
| 37 | Slides \& Progs: & KEATS (also homework is there)\\ | |
| 44 | 38 |   \end{tabular}
 | 
| 39 |   \end{center}
 | |
| 270 
4dbeaf43031d
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
215diff
changeset | 40 | \end{frame}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 41 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 44 | 42 | |
| 462 | 43 | |
| 44 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 45 | \begin{frame}[c]
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 46 | \frametitle{\begin{tabular}{c}Last Week\\[-1mm] 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 47 |             Regexes and Values\end{tabular}}
 | 
| 44 | 48 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 49 | Regular expressions and their corresponding values: | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 50 | |
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 51 | \begin{center}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 52 | \begin{columns}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 53 | \begin{column}{3cm}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 54 | \begin{tabular}{@{}rrl@{}}
 | 
| 445 | 55 |   \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}\\
 | 
| 56 |            & \bl{$\mid$} & \bl{$\ONE$}   \\
 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 57 |            & \bl{$\mid$} & \bl{$c$}          \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 58 |            & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 59 |            & \bl{$\mid$} & \bl{$r_1 + r_2$}   \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 60 | \\ | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 61 |            & \bl{$\mid$} & \bl{$r^*$}         \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 62 |   \end{tabular}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 63 | \end{column}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 64 | \begin{column}{3cm}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 65 | \begin{tabular}{@{\hspace{-7mm}}rrl@{}}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 66 |   \bl{$v$} & \bl{$::=$}  & \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 67 |            &             & \bl{$Empty$}   \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 68 |            & \bl{$\mid$} & \bl{$Char(c)$}          \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 69 |            & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 70 |            & \bl{$\mid$} & \bl{$Left(v)$}   \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 71 |            & \bl{$\mid$} & \bl{$Right(v)$}  \\
 | 
| 664 | 72 |            & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 73 |   \end{tabular}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 74 | \end{column}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 75 | \end{columns}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 76 | \end{center}
 | 
| 44 | 77 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 78 | |
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 79 | \end{frame}
 | 
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 80 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 81 | |
| 44 | 82 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 272 
1446bc47a294
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
270diff
changeset | 83 | \begin{frame}[c]
 | 
| 44 | 84 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 85 | \begin{textblock}{10}(3,5)
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 86 | \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 87 | \node (r1)  {\bl{$r_1$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 88 | \node (r2) [right=of r1] {\bl{$r_2$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 89 | \draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 90 | \node (r3) [right=of r2] {\bl{$r_3$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 91 | \draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 92 | \node (r4) [right=of r3] {\bl{$r_4$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 93 | \draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 94 | \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 95 | \node (v4) [below=of r4] {\bl{$v_4$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 96 | \draw[->,line width=1mm] (r4) -- (v4); | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 97 | \node (v3) [left=of v4] {\bl{$v_3$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 98 | \draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 99 | \node (v2) [left=of v3] {\bl{$v_2$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 100 | \draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 101 | \node (v1) [left=of v2] {\bl{$v_1$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 102 | \draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 103 | \draw[->,line width=0.5mm] (r3) -- (v3); | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 104 | \draw[->,line width=0.5mm] (r2) -- (v2); | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 105 | \draw[->,line width=0.5mm] (r1) -- (v1); | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 106 | \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
 | 
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 107 | \end{tikzpicture}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 108 | \end{textblock}
 | 
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 109 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 110 | \begin{textblock}{6}(1,0.8)
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 111 | \begin{bubble}[6cm]
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 112 | \small | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 113 | \begin{tabular}{ll}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 114 | \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
 | 
| 445 | 115 | \bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
 | 
| 116 | \bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
 | |
| 117 | \bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
 | |
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 118 | \end{tabular}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 119 | \end{bubble}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 120 | \end{textblock}
 | 
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 121 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 122 | \begin{textblock}{6}(1,11.4)
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 123 | \begin{bubble}[7.6cm]
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 124 | \small | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 125 | \begin{tabular}{ll}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 126 | \bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 127 | \bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 128 | \bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 129 | \bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 130 | \end{tabular}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 131 | \end{bubble}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 132 | \end{textblock}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 133 | |
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 134 | \begin{textblock}{6}(12,11.4)
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 135 | \begin{bubble}[2cm]
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 136 | \small | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 137 | \begin{tabular}{ll}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 138 | \bl{$|v_1|$}: & \bl{$abc$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 139 | \bl{$|v_2|$}: & \bl{$bc$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 140 | \bl{$|v_3|$}: & \bl{$c$}\\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 141 | \bl{$|v_4|$}: & \bl{$[]$}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 142 | \end{tabular}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 143 | \end{bubble}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 144 | \end{textblock}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 145 | |
| 44 | 146 | |
| 272 
1446bc47a294
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
270diff
changeset | 147 | \end{frame}
 | 
| 44 | 148 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 149 | ||
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 150 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 151 | \begin{frame}[c]
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 152 | \frametitle{Simplification}
 | 
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 153 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 154 | \begin{itemize}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 155 | \item If we simplify after the derivative, then we are builing the | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 156 | value for the simplified regular expression, but \emph{not} for the original
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 157 | regular expression. | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 158 | \end{itemize}
 | 
| 44 | 159 | |
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 160 | \begin{center}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 161 | \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 162 | \node (r1)  {\bl{$r_1$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 163 | \node (r2) [right=of r1] {\bl{$r_2$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 164 | \draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 165 | \node (r3) [right=of r2] {\bl{$r_3$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 166 | \draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 167 | \node (r4) [right=of r3] {\bl{$r_4$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 168 | \draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 169 | \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 170 | \node (v4) [below=of r4] {\bl{$v_4$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 171 | \draw[->,line width=1mm] (r4) -- (v4); | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 172 | \node (v3) [left=of v4] {\bl{$v_3$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 173 | \draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 174 | \node (v2) [left=of v3] {\bl{$v_2$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 175 | \draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 176 | \node (v1) [left=of v2] {\bl{$v_1$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 177 | \draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 178 | \draw[->,line width=0.5mm] (r3) -- (v3); | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 179 | \draw[->,line width=0.5mm] (r2) -- (v2); | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 180 | \draw[->,line width=0.5mm] (r1) -- (v1); | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 181 | \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
 | 
| 147 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 182 | \end{tikzpicture}
 | 
| 
4725bba8ef26
added slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
93diff
changeset | 183 | \end{center}
 | 
| 44 | 184 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 185 | \small | 
| 445 | 186 | \hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 187 | $\mapsto$ | 
| 445 | 188 | \bl{$(b \cdot c) + \ONE$}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 189 | |
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 190 | \end{frame}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 191 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 192 | |
| 528 | 193 | % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 194 | % \begin{frame}[t]
 | |
| 361 
9c7eb266594c
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
360diff
changeset | 195 | |
| 528 | 196 | % \begin{center}
 | 
| 197 | % \bl{$\only<1>{(b \cdot c)}%
 | |
| 198 | %      \only<2-3>{(\underline{b \cdot c})}%
 | |
| 199 | %      \only<1-3>{+}% 
 | |
| 200 | %      \only<1>{(\ZERO + \ONE)}%
 | |
| 201 | %      \only<2-3>{(\underline{\ZERO + \ONE})}$}%
 | |
| 202 | % \only<4->{%
 | |
| 203 | % \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
 | |
| 204 | % } | |
| 205 | % $\mapsto$ | |
| 206 | % \bl{$(b \cdot c) + \ONE$}
 | |
| 207 | % \end{center}\bigskip
 | |
| 361 
9c7eb266594c
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
360diff
changeset | 208 | |
| 528 | 209 | % \onslide<3->{%
 | 
| 210 | % \begin{center}
 | |
| 211 | % \begin{tabular}{lcl}
 | |
| 212 | % \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
 | |
| 213 | % \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
 | |
| 214 | % \end{tabular}
 | |
| 215 | % \end{center}}
 | |
| 361 
9c7eb266594c
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
360diff
changeset | 216 | |
| 528 | 217 | % \only<4>{%
 | 
| 218 | % \begin{center}
 | |
| 219 | % \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
 | |
| 220 | % \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
 | |
| 221 | % \quad \bl{$\lambda v.\,$} 
 | |
| 222 | %         case \bl{$v = Left(v')$}: 
 | |
| 223 | %       & return \bl{$Left(f_{s1}(v'))$}\\
 | |
| 224 | % \quad \phantom{$\lambda v.\,$} 
 | |
| 225 | %         case \bl{$v = Right(v')$}: 
 | |
| 226 | %       & return \bl{$Right(f_{s2}(v'))$}\\ 
 | |
| 227 | % \end{tabular}
 | |
| 228 | % \end{center}}%
 | |
| 229 | % \only<5->{%
 | |
| 230 | % \begin{center}
 | |
| 231 | % \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
 | |
| 232 | % \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
 | |
| 233 | % \quad \bl{$\lambda v.\,$} 
 | |
| 234 | %         case \bl{$v = Left(v')$}: 
 | |
| 235 | %       & return \bl{$Left(v')$}\\
 | |
| 236 | % \quad \phantom{$\lambda v.\,$} 
 | |
| 237 | %         case \bl{$v = Right(v')$}: 
 | |
| 238 | %       & return \bl{$Right(Right(v'))$}\\ 
 | |
| 239 | % \end{tabular}
 | |
| 240 | % \end{center}}%
 | |
| 361 
9c7eb266594c
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
360diff
changeset | 241 | |
| 528 | 242 | % \only<6->{%
 | 
| 243 | % \begin{center}
 | |
| 244 | % \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
 | |
| 245 | % \bl{$\textit{mkeps}$} simplified case: &
 | |
| 246 | % \bl{$\textit{Right}(\textit{Empty})$}\\
 | |
| 247 | % rectified case: & | |
| 248 | % \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
 | |
| 249 | % \end{tabular}
 | |
| 250 | % \end{center}}%
 | |
| 361 
9c7eb266594c
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
360diff
changeset | 251 | |
| 528 | 252 | % \end{frame}
 | 
| 253 | % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 361 
9c7eb266594c
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
360diff
changeset | 254 | |
| 
9c7eb266594c
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
360diff
changeset | 255 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 256 | \begin{frame}[c]
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 257 | \frametitle{Records}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 258 | |
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 259 | \begin{itemize}
 | 
| 583 | 260 | \item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
 | 
| 44 | 261 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 262 | \item \bl{$nullable(x:r) \dn nullable(r)$}
 | 
| 583 | 263 | \item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 264 | \item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
 | 
| 583 | 265 | \item \bl{$inj\,(x:r)\,c\,Rec(x, v) \dn Rec(x, inj\,r\,c\,v)$}
 | 
| 266 | \end{itemize}\bigskip\bigskip\pause
 | |
| 44 | 267 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 268 | \small | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 269 | for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
 | 
| 44 | 270 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 271 | \end{frame}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 272 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 46 | 273 | |
| 583 | 274 | |
| 148 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 275 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 276 | \begin{frame}[c]
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 277 | \frametitle{Environments}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 278 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 279 | Obtaining the ``recorded'' parts of a value: | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 280 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 281 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 282 | \begin{tabular}{lcl}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 283 |   \bl{$env(Empty)$}     & \bl{$\dn$} & \bl{$[]$}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 284 |   \bl{$env(Char(c))$}   & \bl{$\dn$} & \bl{$[]$}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 285 |   \bl{$env(Left(v))$}   & \bl{$\dn$} & \bl{$env(v)$}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 286 |   \bl{$env(Right(v))$}  & \bl{$\dn$} & \bl{$env(v)$}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 287 |   \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
 | 
| 664 | 288 |   \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} & 
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 289 |      \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 290 |   \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 291 | \end{tabular}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 292 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 293 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 294 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 295 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 296 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 297 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 298 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 299 | \begin{frame}[c]
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 300 | \frametitle{While Tokens}
 | 
| 150 
a2d792ed768e
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
149diff
changeset | 301 | |
| 148 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 302 | \begin{center}
 | 
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 303 | \begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 304 | \pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ 
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 305 |                   &       & \phantom{(}\pcode{("i" : ID)} +\\ 
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 306 |                   &       & \phantom{(}\pcode{("o" : OP)} + \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 307 |                   &       & \phantom{(}\pcode{("n" : NUM)} + \\
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 308 |                   &       & \phantom{(}\pcode{("s" : SEMI)} +\\ 
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 309 |                   &       & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ 
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 310 |                   &       & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ 
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 311 |                   &       & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 312 | \end{tabular}
 | 
| 148 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 313 | \end{center}
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 314 | |
| 289 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 315 | \end{frame}
 | 
| 
c22c8baff491
updated slides
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
272diff
changeset | 316 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 148 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 317 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 318 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 319 | |
| 148 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 320 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 321 | \begin{frame}[t]
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 322 | |
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 323 | \consolas | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 324 | \begin{center}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 325 | \code{"if true then then 42 else +"}
 | 
| 148 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 326 | \end{center}
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 327 | |
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 328 | \only<1>{
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 329 | \small\begin{tabular}{l}
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 330 | KEYWORD(if),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 331 | WHITESPACE,\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 332 | IDENT(true),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 333 | WHITESPACE,\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 334 | KEYWORD(then),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 335 | WHITESPACE,\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 336 | KEYWORD(then),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 337 | WHITESPACE,\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 338 | NUM(42),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 339 | WHITESPACE,\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 340 | KEYWORD(else),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 341 | WHITESPACE,\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 342 | OP(+) | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 343 | \end{tabular}}
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 344 | |
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 345 | \only<2>{
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 346 | \small\begin{tabular}{l}
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 347 | KEYWORD(if),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 348 | IDENT(true),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 349 | KEYWORD(then),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 350 | KEYWORD(then),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 351 | NUM(42),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 352 | KEYWORD(else),\\ | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 353 | OP(+) | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 354 | \end{tabular}}
 | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 355 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 356 | \end{frame}
 | 
| 148 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 357 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 358 | |
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 359 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
36eb7bfb0e63
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
147diff
changeset | 360 | \begin{frame}[c]
 | 
| 664 | 361 | \frametitle{Coursework: Submissions}
 | 
| 582 | 362 | |
| 363 | \begin{itemize}
 | |
| 664 | 364 | \item Scala (29) | 
| 365 | \item Haskell (1) | |
| 366 | \item Kotlin (1) | |
| 367 | \item Rust (1) | |
| 368 | \end{itemize}\bigskip  
 | |
| 582 | 369 | |
| 664 | 370 | Please get in contact if you intend to do CW Strand 2. | 
| 582 | 371 | \end{frame}
 | 
| 372 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 664 | 373 | |
| 374 | ||
| 582 | 375 | |
| 376 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 664 | 377 | %\begin{frame}[c]
 | 
| 378 | %\frametitle{Coursework: PLs (16)}
 | |
| 379 | % | |
| 380 | %\begin{itemize}
 | |
| 381 | %\item Java (16) | |
| 382 | %\item C++, C, C\# (14) | |
| 383 | %\item JavaScript (10) | |
| 384 | %\item Scala (9) | |
| 385 | %\item Python (9) | |
| 386 | %\item PHP (6) | |
| 387 | %\item Haskell (3) | |
| 388 | %\item Ruby (4) | |
| 389 | %\item Bash, Perl, Powershell (2) | |
| 390 | %\item TypeScript (1) | |
| 391 | %\item R (1) | |
| 392 | %\item Coconut (1) | |
| 393 | %\item Pascal (1) | |
| 394 | %\end{itemize}  
 | |
| 395 | % | |
| 396 | %\end{frame}
 | |
| 528 | 397 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 150 
a2d792ed768e
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
149diff
changeset | 398 | |
| 290 
3a2fa69ea675
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
289diff
changeset | 399 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 664 | 400 | %\begin{frame}[c]
 | 
| 401 | %\frametitle{Coursework: Nullable}
 | |
| 402 | % | |
| 403 | %\begin{center}
 | |
| 404 | %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
 | |
| 405 | %  \bl{$nullable([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\
 | |
| 406 | %  \bl{$nullable(r^+)$}                   & \bl{$\dn$} & $?$\\
 | |
| 407 | %  \bl{$nullable(r^?)$}                   & \bl{$\dn$} & $?$\\
 | |
| 408 | %  \bl{$nullable(r^{\{n\}})$}              & \bl{$\dn$} & $?$\\
 | |
| 409 | %  \bl{$nullable(r^{\{n..\}})$}            & \bl{$\dn$} & $?$\\
 | |
| 410 | %  \bl{$nullable(r^{\{..n\}})$}            & \bl{$\dn$} & $?$\\
 | |
| 411 | %  \bl{$nullable(r^{\{n..m\}})$}           & \bl{$\dn$} & $?$\\
 | |
| 412 | %  \bl{$nullable(\sim{}r)$}               & \bl{$\dn$} & $?$\\
 | |
| 413 | % | |
| 414 | %\end{tabular}
 | |
| 415 | %\end{center}
 | |
| 416 | % | |
| 417 | %\end{frame}
 | |
| 290 
3a2fa69ea675
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
289diff
changeset | 418 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 150 
a2d792ed768e
added
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
149diff
changeset | 419 | |
| 528 | 420 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 664 | 421 | %\begin{frame}[c]
 | 
| 422 | %%%\frametitle{Coursework: der}
 | |
| 423 | % | |
| 424 | %\begin{center}
 | |
| 425 | %\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
 | |
| 426 | %  \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\
 | |
| 427 | %  \bl{$der\, c\, (r^+)$}                   & \bl{$\dn$} & $?$\\
 | |
| 428 | %  \bl{$der\, c\, (r^?)$}                   & \bl{$\dn$} & $?$\\
 | |
| 429 | %  \bl{$der\, c\, (r^{\{n\}})$}              & \bl{$\dn$} &
 | |
| 430 | %     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
 | |
| 431 | %  \bl{$der\, c\, (r^{\{n..\}})$}            & \bl{$\dn$} &
 | |
| 432 | %     \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
 | |
| 433 | %  & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
 | |
| 434 | %  \bl{$der\, c\, (r^{\{..n\}})$}            & \bl{$\dn$} &
 | |
| 435 | %     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
 | |
| 436 | % | |
| 437 | %  \bl{$der\, c\, (r^{\{n..m\}})$}          & \bl{$\dn$} &
 | |
| 438 | %     \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
 | |
| 439 | %  \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
 | |
| 440 | %  \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
 | |
| 441 | %          \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
 | |
| 442 | %  \bl{$der\, c\, (\sim{}r)$}              & \bl{$\dn$} & $?$\\
 | |
| 443 | %\end{tabular}
 | |
| 444 | %\end{center}
 | |
| 445 | % | |
| 446 | %\end{frame}
 | |
| 447 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 528 | 448 | |
| 664 | 449 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 450 | %\begin{frame}[c]
 | |
| 451 | %\frametitle{Coursework: CFUN}
 | |
| 452 | % | |
| 453 | %\begin{center}
 | |
| 454 | %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
 | |
| 455 | %  \bl{$nullable(CFUN(\_))$}  & \bl{$\dn$} & \bl{$false$}\\
 | |
| 456 | %  \bl{$der\,c\,(CFUN(f))$}   & \bl{$\dn$} &
 | |
| 457 | %     \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\
 | |
| 458 | %  \bl{$CHAR(c)$}                   & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\
 | |
| 459 | %  \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\
 | |
| 460 | %  \bl{$ALL$}                   & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\                                                      
 | |
| 461 | %\end{tabular}
 | |
| 462 | %\end{center}
 | |
| 463 | % | |
| 464 | %\end{frame}
 | |
| 528 | 465 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 582 | 466 | |
| 528 | 467 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 468 | \begin{frame}[t]
 | |
| 469 | \frametitle{Lexer, Parser}
 | |
| 470 | \mbox{}\\[-16mm]\mbox{}
 | |
| 471 | ||
| 472 | \begin{center}
 | |
| 473 |   \begin{tikzpicture}[scale=1,
 | |
| 474 |                       node/.style={
 | |
| 475 | rectangle,rounded corners=3mm, | |
| 476 | very thick,draw=black!50, | |
| 477 | minimum height=18mm, minimum width=20mm, | |
| 478 | top color=white,bottom color=black!20}] | |
| 479 |   \node (0) at (-2.3,0) {}; 
 | |
| 480 | ||
| 481 |   \node (A) at (0,0)  [node] {};
 | |
| 482 |   \node [below right] at (A.north west) {lexer};
 | |
| 483 | ||
| 484 |   \node (B) at (3,0)  [node] {};
 | |
| 485 | \node [below right=1mm] at (B.north west) | |
| 486 |     {\mbox{}\hspace{-1mm}parser};
 | |
| 487 | ||
| 488 |   \node (C) at (6,0)  [node] {};
 | |
| 489 | \node [below right] at (C.north west) | |
| 490 |     {\mbox{}\hspace{-1mm}code gen};
 | |
| 491 | ||
| 492 |   \node (1) at (8.4,0) {}; 
 | |
| 493 | ||
| 494 | \draw [->,line width=4mm] (0) -- (A); | |
| 495 | \draw [->,line width=4mm] (A) -- (B); | |
| 496 | \draw [->,line width=4mm] (B) -- (C); | |
| 497 | \draw [->,line width=4mm] (C) -- (1); | |
| 498 |   \end{tikzpicture}
 | |
| 499 |   \end{center}
 | |
| 500 | ||
| 501 | Today a parser. | |
| 502 | ||
| 503 | \end{frame}
 | |
| 504 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 505 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 506 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 507 | \begin{frame}[c]
 | 
| 550 | 508 | \frametitle{What Parsing is Not}
 | 
| 509 | ||
| 510 | Usually parsing does not check semantic correctness, e.g. | |
| 511 | ||
| 512 | \begin{itemize}
 | |
| 513 | \item whether a function is not used before it | |
| 514 | is defined | |
| 515 | \item whether a function has the correct number of arguments | |
| 516 | or are of correct type | |
| 517 | \item whether a variable can be declared twice in a scope | |
| 518 | \end{itemize}  
 | |
| 519 | ||
| 520 | \end{frame}
 | |
| 521 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 522 | ||
| 523 | ||
| 524 | ||
| 525 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 526 | \begin{frame}[c]
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 527 | \frametitle{Regular Languages}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 528 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 529 | While regular expressions are very useful for lexing, there is | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 530 | no regular expression that can recognise the language | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 531 | \bl{$a^nb^n$}.\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 532 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 533 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 534 | \bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 535 | \end{center}\bigskip\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 536 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 537 | \small | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 538 | \noindent So we cannot find out with regular expressions | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 539 | whether parentheses are matched or unmatched. Also regular | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 540 | expressions are not recursive, e.g.~\bl{$(1 + 2) + 3$}.
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 541 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 542 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 543 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 544 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 545 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 546 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 547 | \frametitle{Hierarchy of Languages}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 548 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 549 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 550 | \begin{tikzpicture}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 551 | [rect/.style={draw=black!50, 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 552 | top color=white, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 553 | bottom color=black!20, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 554 | rectangle, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 555 | very thick, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 556 | rounded corners}, scale=1.2] | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 557 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 558 | \draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 559 | \draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 560 | \draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 561 | \draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 562 | \draw (0,-1.4) node [rect] {regular languages};
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 563 | \end{tikzpicture}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 564 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 565 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 566 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 567 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 568 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 569 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 570 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 571 | \begin{frame}[c]
 | 
| 360 
c6c574d2ca0c
update
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
358diff
changeset | 572 | \frametitle{CF Grammars}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 573 | |
| 360 
c6c574d2ca0c
update
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
358diff
changeset | 574 | A \alert{\bf context-free grammar} \bl{$G$} consists of
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 575 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 576 | \begin{itemize}
 | 
| 664 | 577 | \item a finite set of nonterminal symbols (e.g.~$\meta{A}$ upper case)
 | 
| 578 | \item a finite set terminal symbols or tokens (lower case) | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 579 | \item a start symbol (which must be a nonterminal) | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 580 | \item a set of rules | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 581 | \begin{center}
 | 
| 451 | 582 | \bl{$\meta{A} ::= \textit{rhs}$}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 583 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 584 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 585 | where \bl{\textit{rhs}} are sequences involving terminals and nonterminals,
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 586 | including the empty sequence \bl{$\epsilon$}.\medskip\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 587 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 588 | We also allow rules | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 589 | \begin{center}
 | 
| 451 | 590 | \bl{$\meta{A} ::= \textit{rhs}_1 | \textit{rhs}_2 | \ldots$}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 591 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 592 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 593 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 594 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 595 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 596 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 597 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 582 | 598 | \begin{frame}[t]
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 599 | \frametitle{Palindromes}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 600 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 601 | A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 602 | |
| 451 | 603 | \bl{\begin{plstx}[margin=3cm]
 | 
| 604 | : \meta{S} ::= a\cdot\meta{S}\cdot a\\
 | |
| 605 | : \meta{S} ::= b\cdot\meta{S}\cdot b\\
 | |
| 588 | 606 | : \meta{S} ::= a\\
 | 
| 607 | : \meta{S} ::= b\\
 | |
| 608 | : \meta{S} ::= \epsilon\\
 | |
| 451 | 609 | \end{plstx}}\pause
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 610 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 611 | or | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 612 | |
| 451 | 613 | \bl{\begin{plstx}[margin=2cm]
 | 
| 588 | 614 | : \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\
 | 
| 451 | 615 | \end{plstx}}\pause\bigskip
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 616 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 617 | \small | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 618 | Can you find the grammar rules for matched parentheses? | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 619 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 620 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 621 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 622 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 623 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 624 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 625 | \frametitle{Arithmetic Expressions}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 626 | |
| 451 | 627 | \bl{\begin{plstx}[margin=3cm,one per line]
 | 
| 628 | : \meta{E} ::=  num\_token 
 | |
| 629 |    | \meta{E} \cdot + \cdot \meta{E} 
 | |
| 630 |    | \meta{E} \cdot - \cdot \meta{E} 
 | |
| 631 |    | \meta{E} \cdot * \cdot \meta{E} 
 | |
| 632 |    | ( \cdot \meta{E} \cdot ) \\
 | |
| 633 | \end{plstx}}\pause
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 634 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 635 | \bl{\texttt{1 + 2 * 3 + 4}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 636 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 637 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 638 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 639 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 640 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 641 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 642 | \frametitle{A CFG Derivation}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 643 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 644 | \begin{enumerate}
 | 
| 451 | 645 | \item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip
 | 
| 646 | \item Replace any nonterminal \bl{\meta{X}} in the string by the
 | |
| 647 | right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip
 | |
| 582 | 648 | \item Repeat 2 until there are no nonterminals left | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 649 | \end{enumerate}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 650 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 651 | \begin{center}
 | 
| 451 | 652 | \bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 653 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 654 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 655 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 656 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 657 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 658 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 451 | 659 | \begin{frame}[t]
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 660 | \frametitle{Example Derivation}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 661 | |
| 451 | 662 | \bl{\begin{plstx}[margin=2cm]
 | 
| 663 | : \meta{S} ::=  \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\
 | |
| 664 | \end{plstx}}\bigskip
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 665 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 666 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 667 | \begin{tabular}{lcl}
 | 
| 451 | 668 | \bl{\meta{S}} & \bl{$\rightarrow$} & \bl{$a\meta{S}a$}\\
 | 
| 669 |               & \bl{$\rightarrow$} & \bl{$ab\meta{S}ba$}\\
 | |
| 670 |               & \bl{$\rightarrow$} & \bl{$aba\meta{S}aba$}\\
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 671 |               & \bl{$\rightarrow$} & \bl{$abaaba$}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 672 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 673 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 674 | \end{tabular}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 675 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 676 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 677 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 678 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 679 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 680 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 451 | 681 | \begin{frame}[t]
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 682 | \frametitle{Example Derivation}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 683 | |
| 451 | 684 | \bl{\begin{plstx}[margin=3cm,one per line]
 | 
| 685 | : \meta{E} ::=  num\_token 
 | |
| 686 |    | \meta{E} \cdot + \cdot \meta{E} 
 | |
| 687 |    | \meta{E} \cdot - \cdot \meta{E} 
 | |
| 688 |    | \meta{E} \cdot * \cdot \meta{E} 
 | |
| 689 |    | ( \cdot \meta{E} \cdot ) \\
 | |
| 690 | \end{plstx}}
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 691 | |
| 451 | 692 | \small | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 693 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 694 | \begin{tabular}{@{}c@{}c@{}}
 | 
| 451 | 695 | \begin{tabular}{@{\hspace{-2mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{4mm}}}
 | 
| 696 | \bl{\meta{E}} & \bl{$\rightarrow$} & \bl{$\meta{E}*\meta{E}$}\\
 | |
| 697 |               & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}$}\\
 | |
| 698 |               & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 699 |               & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 700 | \end{tabular} &\pause
 | 
| 451 | 701 | \begin{tabular}{@{}l@{\hspace{0mm}}l@{\hspace{1mm}}l}
 | 
| 702 | \bl{$\meta{E}$} & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}$}\\
 | |
| 703 |                 & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}+\meta{E}$}\\
 | |
| 704 |                 & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
 | |
| 705 |                 & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 706 | \end{tabular}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 707 | \end{tabular}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 708 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 709 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 710 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 711 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 712 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 713 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 714 | \begin{frame}[c]
 | 
| 664 | 715 | \frametitle{Context Sensitive Grammars}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 716 | |
| 360 
c6c574d2ca0c
update
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
358diff
changeset | 717 | It is much harder to find out whether a string is parsed | 
| 
c6c574d2ca0c
update
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
358diff
changeset | 718 | by a context sensitive grammar: | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 719 | |
| 451 | 720 | \bl{\begin{plstx}[margin=2cm]
 | 
| 721 | : \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\
 | |
| 722 | : \meta{A} ::= a\\
 | |
| 723 | : b\meta{A} ::= \meta{A}b\\
 | |
| 724 | \end{plstx}}\pause
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 725 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 726 | \begin{center}
 | 
| 451 | 727 | \bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$}
 | 
| 665 | 728 | \end{center}\pause
 | 
| 729 | ||
| 730 | \begin{center}
 | |
| 731 | \tt Time flies like an arrow;\\ | |
| 732 | fruit flies like bananas. | |
| 733 |   \end{center}  
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 734 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 735 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 736 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 737 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 738 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 739 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 740 | \frametitle{Language of a CFG}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 741 | |
| 451 | 742 | Let \bl{$G$} be a context-free grammar with start symbol \bl{\meta{S}}. 
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 743 | Then the language \bl{$L(G)$} is:
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 744 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 745 | \begin{center}
 | 
| 451 | 746 | \bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge \meta{S} \rightarrow^* c_1\ldots c_n \}$}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 747 | \end{center}\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 748 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 749 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 750 | \item Terminals, because there are no rules for replacing them. | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 751 | \item Once generated, terminals are ``permanent''. | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 752 | \item Terminals ought to be tokens of the language\\ | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 753 | (but can also be strings). | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 754 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 755 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 756 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 757 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 758 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 759 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 451 | 760 | \begin{frame}[t]
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 761 | \frametitle{Parse Trees}
 | 
| 582 | 762 | \mbox{}\\[-12mm]
 | 
| 451 | 763 | |
| 593 | 764 | \bl{\begin{plstx}: \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} |  \meta{T} \cdot - \cdot \meta{E}\\
 | 
| 529 | 765 | : \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\
 | 
| 766 | : \meta{F} ::= num\_token | ( \cdot \meta{E} \cdot )\\
 | |
| 451 | 767 | \end{plstx}}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 768 | |
| 451 | 769 | \begin{center}\small
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 770 | \begin{tikzpicture}[level distance=8mm, blue]
 | 
| 451 | 771 |   \node {$\meta{E}$}
 | 
| 529 | 772 |     child {node {$\meta{T}$} 
 | 
| 451 | 773 |      child {node {$\meta{T}$} 
 | 
| 774 |                  child {node {(\,$\meta{E}$\,)}
 | |
| 775 |                             child {node{$\meta{F}$ *{} $\meta{F}$}
 | |
| 776 |                                   child {node {$\meta{T}$} child {node {2}}}
 | |
| 777 |                                   child {node {$\meta{T}$} child {node {3}}} 
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 778 | } | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 779 | } | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 780 | } | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 781 |      child {node {+}}
 | 
| 451 | 782 |      child {node {$\meta{T}$}
 | 
| 783 |        child {node {(\,$\meta{E}$\,)} 
 | |
| 784 |        child {node {$\meta{F}$}
 | |
| 785 |        child {node {$\meta{T}$ +{} $\meta{T}$}
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 786 |                     child {node {3}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 787 |                     child {node {4}} 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 788 | } | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 789 | }} | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 790 | }}; | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 791 | \end{tikzpicture}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 792 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 793 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 794 | \begin{textblock}{5}(1, 6.5)
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 795 | \bl{\texttt{(2*3)+(3+4)}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 796 | \end{textblock}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 797 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 798 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 799 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 800 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 801 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 451 | 802 | \begin{frame}[t]
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 803 | \frametitle{Arithmetic Expressions}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 804 | |
| 451 | 805 | \bl{\begin{plstx}[margin=3cm,one per line]
 | 
| 806 | : \meta{E} ::=  num\_token 
 | |
| 807 |    | \meta{E} \cdot + \cdot \meta{E} 
 | |
| 808 |    | \meta{E} \cdot - \cdot \meta{E} 
 | |
| 809 |    | \meta{E} \cdot * \cdot \meta{E} 
 | |
| 810 |    | ( \cdot \meta{E} \cdot ) \\
 | |
| 811 | \end{plstx}}\pause\bigskip
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 812 | |
| 451 | 813 | A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} such
 | 
| 814 | that \bl{$\meta{E} \rightarrow^+ \meta{E}\cdot \ldots$}
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 815 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 816 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 817 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 818 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 819 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 451 | 820 | \begin{frame}[t]
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 821 | \frametitle{Ambiguous Grammars}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 822 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 823 | A grammar is \alert{\bf ambiguous} if there is a string that
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 824 | has at least two different parse trees. | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 825 | |
| 451 | 826 | \bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::=  num\_token 
 | 
| 827 |    | \meta{E} \cdot + \cdot \meta{E} 
 | |
| 828 |    | \meta{E} \cdot - \cdot \meta{E} 
 | |
| 829 |    | \meta{E} \cdot * \cdot \meta{E} 
 | |
| 830 |    | ( \cdot \meta{E} \cdot ) \\
 | |
| 831 | \end{plstx}}
 | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 832 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 833 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 834 | \bl{\texttt{1 + 2 * 3 + 4}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 835 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 836 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 837 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 838 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 839 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 840 | \begin{frame}[c]
 | 
| 582 | 841 | \frametitle{`Dangling' Else}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 842 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 843 | Another ambiguous grammar:\bigskip | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 844 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 845 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 846 | \bl{\begin{tabular}{lcl}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 847 | $E$ & $\rightarrow$ & if $E$ then $E$\\ | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 848 | & $|$ & if $E$ then $E$ else $E$ \\ | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 849 | & $|$ & \ldots | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 850 | \end{tabular}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 851 | \end{center}\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 852 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 853 | \bl{\texttt{if a then if x then y else c}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 854 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 855 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 856 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 857 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 858 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 859 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 860 | \frametitle{Parser Combinators}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 861 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 862 | One of the simplest ways to implement a parser, see | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 863 | {\small\url{https://vimeo.com/142341803}}\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 864 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 865 | Parser combinators: \bigskip | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 866 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 867 | \begin{minipage}{1.1\textwidth}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 868 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 869 | \mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 870 | $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 871 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 872 | \end{minipage}\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 873 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 874 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 875 | \item atomic parsers | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 876 | \item sequencing | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 877 | \item alternative | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 878 | \item semantic action | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 879 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 880 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 881 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 882 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 883 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 884 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 885 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 886 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 887 | Atomic parsers, for example, number tokens | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 888 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 889 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 890 | \bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$} 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 891 | \end{center}\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 892 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 893 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 894 | \item you consume one or more token from the\\ | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 895 | input (stream) | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 896 | \item also works for characters and strings | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 897 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 898 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 899 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 900 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 901 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 902 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 903 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 904 | Alternative parser (code \bl{$p\;||\;q$})\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 905 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 906 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 907 | \item apply \bl{$p$} and also \bl{$q$}; then combine 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 908 | the outputs | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 909 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 910 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 911 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 912 | \large \bl{$p(\text{input}) \cup q(\text{input})$}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 913 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 914 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 915 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 916 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 917 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 918 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 919 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 920 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 921 | Sequence parser (code \bl{$p\sim q$})\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 922 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 923 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 924 | \item apply first \bl{$p$} producing a set of pairs
 | 
| 528 | 925 | \item then apply \bl{$q$} to the unparsed part
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 926 | \item then combine the results:\medskip | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 927 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 928 | ((output$_1$, output$_2$), unparsed part) | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 929 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 930 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 931 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 932 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 933 | \begin{tabular}{l}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 934 | \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 935 | \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 936 | \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 937 | \end{tabular}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 938 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 939 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 940 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 941 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 942 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 943 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 944 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 945 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 946 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 947 | Function parser (code \bl{$p \Rightarrow f\;$})\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 948 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 949 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 950 | \item apply \bl{$p$} producing a set of pairs
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 951 | \item then apply the function \bl{$f$} to each first component
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 952 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 953 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 954 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 955 | \begin{tabular}{l}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 956 | \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 957 | \end{tabular}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 958 | \end{center}\bigskip\bigskip\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 959 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 960 | \bl{$f$} is the semantic action (``what to do with the parsed input'')
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 961 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 962 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 963 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 964 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 965 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 966 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 967 | \mode<presentation>{
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 968 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 969 | \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 970 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 971 | Addition | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 972 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 973 | \begin{center}
 | 
| 582 | 974 | \bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 975 | \end{center}\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 976 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 977 | Multiplication | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 978 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 979 | \begin{center}
 | 
| 582 | 980 | \bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 981 | \end{center}\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 982 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 983 | Parenthesis | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 984 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 985 | \begin{center}
 | 
| 582 | 986 | \bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 987 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 988 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 989 | \end{frame}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 990 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 991 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 992 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 993 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 994 | \frametitle{Types of Parsers}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 995 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 996 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 997 | \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 998 | then \bl{$p \sim q$} returns results of type
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 999 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1000 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1001 | \bl{$T \times S$}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1002 | \end{center}\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1003 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1004 | \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then  \bl{$q$} \alert{must} also have results of type \bl{$T$},
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1005 | and \bl{$p \;||\; q$} returns results of type
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1006 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1007 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1008 | \bl{$T$}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1009 | \end{center}\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1010 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1011 | \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1012 | \bl{$T$} to \bl{$S$}, then
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1013 | \bl{$p \Rightarrow f$} returns results of type
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1014 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1015 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1016 | \bl{$S$}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1017 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1018 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1019 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1020 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1021 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1022 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1023 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1024 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1025 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1026 | \frametitle{Input Types of Parsers}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1027 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1028 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1029 | \item input: \alert{token list}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1030 | \item output: set of (output\_type, \alert{token list})
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1031 | \end{itemize}\bigskip\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1032 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1033 | actually it can be any input type as long as it is a kind of | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1034 | sequence (for example a string) | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1035 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1036 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1037 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1038 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1039 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1040 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1041 | \frametitle{Scannerless Parsers}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1042 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1043 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1044 | \item input: \alert{string}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1045 | \item output: set of (output\_type, \alert{string})
 | 
| 664 | 1046 | \end{itemize}\bigskip\bigskip
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1047 | |
| 664 | 1048 | but using lexers is better because whitespaces or comments can be | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1049 | filtered out; then input is a sequence of tokens | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1050 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1051 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1052 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1053 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1054 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1055 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1056 | \frametitle{Successful Parses}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1057 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1058 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1059 | \item input: string | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1060 | \item output: \alert{set of} (output\_type, string)
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1061 | \end{itemize}\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1062 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1063 | a parse is successful whenever the input has been fully | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1064 | ``consumed'' (that is the second component is empty) | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1065 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1066 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1067 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1068 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1069 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1070 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1071 | \frametitle{Abstract Parser Class}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1072 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1073 | \small | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1074 | \lstinputlisting[language=Scala,xleftmargin=1mm] | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1075 |  {../progs/app7.scala}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1076 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1077 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1078 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1079 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1080 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1081 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1082 | \small | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1083 | \fontsize{10}{12}\selectfont
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1084 | \lstinputlisting[language=Scala,xleftmargin=1mm] | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1085 |   {../progs/app8.scala}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1086 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1087 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1088 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1089 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1090 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1091 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1092 | \frametitle{Two Grammars}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1093 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1094 | Which languages are recognised by the following two grammars? | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1095 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1096 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1097 | \bl{\begin{tabular}{lcl}
 | 
| 582 | 1098 | $\meta{S}$ & $\rightarrow$ &  $1 \cdot \meta{S} \cdot \meta{S}$\\
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1099 | & $|$ & $\epsilon$ | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1100 | \end{tabular}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1101 | \end{center}\bigskip
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1102 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1103 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1104 | \bl{\begin{tabular}{lcl}
 | 
| 582 | 1105 | $\meta{U}$ & $\rightarrow$ &  $1 \cdot \meta{U}$\\
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1106 | & $|$ & $\epsilon$ | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1107 | \end{tabular}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1108 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1109 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1110 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1111 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1112 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1113 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1114 | \begin{frame}[t]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1115 | \frametitle{Ambiguous Grammars}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1116 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1117 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1118 | \begin{tikzpicture}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1119 | \begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1120 | enlargelimits=false, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1121 |     xtick={0,100,...,1000},
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1122 | xmax=1050, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1123 | ymax=33, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1124 |     ytick={0,5,...,30},
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1125 | scaled ticks=false, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1126 | axis lines=left, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1127 | width=11cm, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1128 | height=7cm, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1129 |     legend entries={unambiguous,ambiguous},  
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1130 | legend pos=north east, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1131 | legend cell align=left, | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1132 |     x tick label style={font=\small,/pgf/number format/1000 sep={}}]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1133 | \addplot[blue,mark=*, mark options={fill=white}] 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1134 |   table {s-grammar1.data};
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1135 | \only<2>{
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1136 |   \addplot[red,mark=triangle*, mark options={fill=white}] 
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1137 |   table {s-grammar2.data};}  
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1138 | \end{axis}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1139 | \end{tikzpicture}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1140 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1141 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1142 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1143 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1144 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1145 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1146 | \begin{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1147 | \frametitle{While-Language}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1148 | \mbox{}\\[-23mm]\mbox{}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1149 | |
| 370 
a65767fe5d71
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
361diff
changeset | 1150 | \bl{\begin{plstx}[rhs style=,one per line]: \meta{Stmt} ::= skip
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1151 |          | \meta{Id} := \meta{AExp}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1152 |          | if \meta{BExp} then \meta{Block} else \meta{Block}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1153 |          | while \meta{BExp} do \meta{Block}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1154 | : \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1155 |           | \meta{Stmt}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1156 | : \meta{Block} ::= \{ \meta{Stmts} \}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1157 |           | \meta{Stmt}\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1158 | : \meta{AExp} ::= \ldots\\
 | 
| 370 
a65767fe5d71
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
361diff
changeset | 1159 | : \meta{BExp} ::= \ldots\\\end{plstx}}
 | 
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1160 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1161 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1162 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1163 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1164 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1165 | \begin{frame}[c]
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1166 | \frametitle{An Interpreter}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1167 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1168 | \begin{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1169 | \bl{\begin{tabular}{l}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1170 | $\{$\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1171 | \;\;$x := 5 \text{;}$\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1172 | \;\;$y := x * 3\text{;}$\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1173 | \;\;$y := x * 4\text{;}$\\
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1174 | \;\;$x := u * 3$\\ | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1175 | $\}$ | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1176 | \end{tabular}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1177 | \end{center}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1178 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1179 | \begin{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1180 | \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1181 | \item \bl{\texttt{eval(stmt, env)}}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1182 | \end{itemize}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1183 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1184 | \end{frame}
 | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1185 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | 
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1186 | |
| 465 | 1187 | |
| 1188 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1189 | \mode<presentation>{
 | |
| 1190 | \begin{frame}[c]
 | |
| 1191 | \frametitle{\begin{tabular}{c}Interpreter\end{tabular}}
 | |
| 1192 | ||
| 1193 | \begin{center}
 | |
| 1194 | \bl{\begin{tabular}{@{}lcl@{}}
 | |
| 1195 | $\text{eval}(n, E)$ & $\dn$ & $n$\\
 | |
| 1196 | $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\
 | |
| 1197 | $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\
 | |
| 1198 | $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\
 | |
| 1199 | $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\
 | |
| 1200 | $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\
 | |
| 1201 | $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\
 | |
| 1202 | $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\
 | |
| 1203 | \end{tabular}}
 | |
| 1204 | \end{center}
 | |
| 1205 | ||
| 1206 | \end{frame}}
 | |
| 1207 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1208 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1209 | \mode<presentation>{
 | |
| 1210 | \begin{frame}[c]
 | |
| 1211 | \frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}
 | |
| 1212 | ||
| 1213 | \begin{center}
 | |
| 1214 | \bl{\begin{tabular}{@{}lcl@{}}
 | |
| 1215 | $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\
 | |
| 1216 | $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\
 | |
| 1217 | \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\
 | |
| 1218 | \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;
 | |
| 1219 | \text{eval}(cs_1,E)$}\\
 | |
| 1220 | \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\
 | |
| 1221 | \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\
 | |
| 1222 | \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\
 | |
| 1223 | \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;
 | |
| 1224 | \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\
 | |
| 1225 | \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\
 | |
| 1226 | $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\
 | |
| 1227 | \end{tabular}}
 | |
| 1228 | \end{center}
 | |
| 1229 | ||
| 1230 | \end{frame}}
 | |
| 1231 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1232 | ||
| 1233 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1234 | \begin{frame}[c]
 | |
| 582 | 1235 | \frametitle{Test Program}
 | 
| 465 | 1236 | |
| 1237 | \mbox{}\\[-18mm]\mbox{}
 | |
| 1238 | ||
| 1239 | {\lstset{language=While}%%\fontsize{10}{12}\selectfont
 | |
| 1240 | \texttt{\lstinputlisting{../progs/loops.while}}}
 | |
| 1241 | ||
| 1242 | \end{frame}
 | |
| 1243 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1244 | ||
| 1245 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1246 | \mode<presentation>{
 | |
| 1247 | \begin{frame}[t]
 | |
| 1248 | \frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}
 | |
| 1249 | ||
| 1250 | \begin{center}
 | |
| 1251 | \begin{tikzpicture}
 | |
| 1252 | \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
 | |
| 1253 | \addplot+[smooth] file {interpreted.data};
 | |
| 1254 | \end{axis}
 | |
| 1255 | \end{tikzpicture}
 | |
| 1256 | \end{center}
 | |
| 1257 | ||
| 1258 | \end{frame}}
 | |
| 1259 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1260 | ||
| 1261 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 1262 | \mode<presentation>{
 | |
| 1263 | \begin{frame}[c]
 | |
| 1264 | \frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}
 | |
| 1265 | ||
| 1266 | \begin{itemize}
 | |
| 1267 | \item introduced in 1995 | |
| 1268 | \item is a stack-based VM (like Postscript, CLR of .Net) | |
| 1269 | \item contains a JIT compiler | |
| 1270 | \item many languages take advantage of JVM's infrastructure (JRE) | |
| 1271 | \item is garbage collected $\Rightarrow$ no buffer overflows | |
| 1272 | \item some languages compile to the JVM: Scala, Clojure\ldots | |
| 1273 | \end{itemize}
 | |
| 1274 | ||
| 1275 | \end{frame}}
 | |
| 1276 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 358 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1277 | |
| 
b3129cff41e9
updated
 Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 
290diff
changeset | 1278 | |
| 44 | 1279 | \end{document}
 | 
| 1280 | ||
| 1281 | %%% Local Variables: | |
| 1282 | %%% mode: latex | |
| 1283 | %%% TeX-master: t | |
| 1284 | %%% End: | |
| 1285 |