--- a/slides/slides02.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/slides/slides02.tex Sat Aug 15 14:18:37 2020 +0100
@@ -1,5 +1,5 @@
% !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
@@ -29,26 +29,42 @@
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-1mm]
- \LARGE Formal Languages (2)\\[3mm]
+ \LARGE Formal Languages\\[3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office Hours: & Thursdays 12 -- 14\\
- Location: & N7.07 (North Wing, Bush House)\\
+ %Office Hours: & Thursdays 12 -- 14\\
+ %Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS (also homework is there)\\
\end{tabular}
\end{center}
+ \begin{center}
+ \begin{tikzpicture}
+ \node[drop shadow,fill=white,inner sep=0pt]
+ {\footnotesize\rowcolors{1}{capri!10}{white}
+ \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ 1 Introduction, Languages & 6 While-Language \\
+ \cellcolor{blue!50}
+ 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ 4 Lexing, Tokenising & 9 Optimisations \\
+ 5 Grammars, Parsing & 10 LLVM \\ \hline
+ \end{tabular}%
+ };
+ \end{tikzpicture}
+ \end{center}
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{
- Lets Implement an Efficient\\[-2mm]
+ Let's Implement an Efficient\\[-2mm]
Regular Expression Matcher}
\footnotesize
@@ -149,193 +165,7 @@
\end{center}
\vspace{\fill}
-Q: \;What about \;\bl{$r \cdot 0$} \; ?
-\end{frame}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Languages (Sets of Strings)}
-
-\begin{itemize}
-
-\item A \alert{\bf Language} is a set of strings, for example\medskip
-\begin{center}
-\bl{$\{[], hello, foobar, a, abc\}$}
-\end{center}\bigskip
-
-\item \alert{\bf Concatenation} for strings and languages
-
-\begin{center}
-\begin{tabular}{rcl}
-\bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\
-\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
-\end{tabular}
-\end{center}
-\bigskip
-
-\small
-\item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$}
-
-\[
-\bl{A \,@\, B = \{fooa, foob, bara, barb\}}
-\]
-
-\end{itemize}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
- \frametitle{Two Corner Cases}
-
- \Large
- \begin{center}
- \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\
- \bl{$A \,@\, \{\} = \;?$}
- \end{center}
-
- \end{frame}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{
- The Meaning of a\\[-2mm]
- Regular Expression}
-
- ...all the strings a regular expression can match.
-
-\begin{center}
- \begin{tabular}{rcl}
- \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
- \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
- \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
- \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
- \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
- \bl{$L(r^*)$} & \bl{$\dn$} & \\
- \end{tabular}
-\end{center}
-
-\begin{textblock}{14}(1.5,13.5)\small
-\bl{$L$} is a function from regular expressions to
-sets of strings (languages):\smallskip\\
-\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
-\end{textblock}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Power Operation}
-
-\begin{itemize}
-\item The \alert{\textbf{\boldmath$n$th Power}} of a language:
-
-\begin{center}
-\begin{tabular}{lcl}
-\bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
-\bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}
-\end{tabular}
-\end{center}\bigskip
-
-\item[] For example
-
-\begin{center}
-\begin{tabular}{lcl@{\hspace{10mm}}l}
-\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\
-\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\
-\bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
-\end{tabular}
-\end{center}
-
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
- \frametitle{Homework Question}
-
- \begin{itemize}
- \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip
-
- \item[]
- How many strings are in \bl{$A^4$}\,?
- \bigskip\medskip\pause
-
-
- \item[]
- What if \bl{$A = \{[a],[b],[c],[]\}$};\\
- how many strings are then in \bl{$A^4$}\,?
- \end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Star Operation}
-
-\begin{itemize}
-\item The \alert{\bf Kleene Star} of a \underline{language}:
-\bigskip
-
-\begin{center}
-\begin{tabular}{c}
-\bl{$A\star \dn \bigcup_{0\le n} A^n$}
-\end{tabular}
-\end{center}\bigskip
-
-\item[] This expands to
-
-\[
-\bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots}
-\]
-
-or
-
-\small
-\[
-\bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\;
- A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots}
-\]
-
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{
- The Meaning of a\\[-2mm]
- Regular Expression}
-
-...all the strings a regular expression can match.
-
-\begin{center}
- \begin{tabular}{rcl}
- \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
- \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
- \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
- \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
- \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
- \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\
- \end{tabular}
-\end{center}
-
-%\begin{textblock}{9}(6,12)\small
-%\bl{$L$} is a function from regular expressions to
-%sets of strings (languages):\smallskip\\
-%\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
-%\end{textblock}
-
+%%Q: \;What about \;\bl{$r \cdot 0$} \; ?
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -435,17 +265,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}}
-
-\bigskip
-homework (written exam 80\%)\\
-coursework (20\%; first one today)\\
-submission Fridays @ 18:00 -- accepted until Mondays
-\mbox{}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -812,9 +631,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
- \frametitle{
- Another Example\\[-2mm]
- in Java 8, Python and JavaScript}
+ \frametitle{Another Example \boldmath$(a^*)^* \cdot b$}
\bigskip
\begin{center}
@@ -1220,7 +1037,223 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}}
+
+\bigskip
+homework (written exam 80\%)\\
+coursework (20\%; first one today)\\
+submission Fridays @ 18:00 -- accepted until Mondays
+\mbox{}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Last Week}
+
+Last week I showed you a regular expression matcher
+that works provably correct in all cases (we only
+started with the proving part though)
+
+\begin{center}
+\bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}
+\end{center}\bigskip\bigskip
+
+\small
+\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Derivative of a Rexp}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
+ \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
+ \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
+ \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\
+ & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\
+ & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
+ \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\
+
+ \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
+ \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\
+ \end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Example}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
+
+\begin{center}
+\def\arraystretch{1.5}
+\begin{tabular}{@{}lcl}
+ \bl{$\der\,a\,((a \cdot b) + b)^*$}
+ & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
+ & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
+ & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
+ & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
+ & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
+ & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+Input: string \bl{$abc$} and regular expression \bl{$r$}
+
+\begin{enumerate}
+\item \bl{$der\,a\,r$}
+\item \bl{$der\,b\,(der\,a\,r)$}
+\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
+\item finally check whether the last regular expression can match the empty string
+\end{enumerate}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Simplification}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
+
+\begin{center}
+\def\arraystretch{2}
+\begin{tabular}{@{}lcl}
+ \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
+ & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
+ & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
+ & \bl{$=$} & \bl{$b \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+ \frametitle{Proofs about Rexp}
+
+ \begin{itemize}
+ \item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip
+ \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already
+ holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
+ \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already
+ holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
+ \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
+ holds for \bl{$r$}.
+ \end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+We proved
+
+\begin{center}
+\bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$}
+\end{center}
+
+by induction on the regular expression \bl{$r$}.\bigskip\pause
+
+\begin{center}
+{\huge\bf\alert{Any Questions?}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}
+
+\begin{itemize}
+\item \bl{$P$} holds for \bl{$0$} and
+\item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already
+holds for \bl{$n$}
+\end{itemize}\bigskip
+
+\begin{itemize}
+\item \bl{$P$} holds for \bl{$[]$} and
+\item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already
+holds for \bl{$s$}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+ \frametitle{Correctness Proof \\[-1mm]
+ for our Matcher}
+
+ \begin{itemize}
+ \item We started from
+
+ \begin{center}
+ \begin{tabular}{rp{4cm}}
+ & \bl{$s \in L(r)$}\medskip\\
+ \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause
+ \end{tabular}
+ \end{center}\bigskip
+
+ \item \textbf{\alert{if}} we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we
+ have\bigskip
+
+ \begin{center}
+ \begin{tabular}{rp{4cm}}
+ \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
+ \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
+ \bl{$\dn$} & \bl{$matches\,s\,r$}
+ \end{tabular}
+ \end{center}
+
+ \end{itemize}
+
+ \end{frame}
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+We need to prove
+
+\begin{center}
+\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
+\end{center}
+
+also by induction on the regular expression \bl{$r$}.
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
\end{document}