--- a/slides/slides01.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/slides/slides01.tex Sat Aug 15 14:18:37 2020 +0100
@@ -1,10 +1,12 @@
% !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t,xelatex]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
\usepackage{../data}
+
+
\hfuzz=220pt
\lstset{language=Scala,
@@ -24,13 +26,15 @@
\begin{document}
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-1mm]
- \LARGE Formal Languages (1)\\[-3mm]
+ \LARGE Formal Languages\\[-3mm]
\end{tabular}}
\begin{center}
@@ -43,12 +47,28 @@
\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\\
\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
+ \cellcolor{blue!50}
+ 1 Introduction, Languages & 6 While-Language \\
+ 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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -56,7 +76,10 @@
\begin{frame}[t]
\frametitle{Why Study Compilers?}
-John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}\smallskip\\
+
+John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}
+\here{https://blog.regehr.org/archives/1419}
+\smallskip\\
\begin{bubble}[10.5cm]
\bf ``\ldots{}It’s effectively a perpetual
@@ -104,12 +127,12 @@
\node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}};
\draw [->,line width=4mm, red] (0) -- (1);
\node (2) [below=25mm] at (0) {\LARGE\bf``source''};
- \node (3) [right=35mm] at (2) {\LARGE\bf``binary''};
+ \node (3) [right=40mm] at (2) {\LARGE\bf``binary''};
\draw [->,line width=1mm] (2) -- (3);
\end{tikzpicture}
\end{center}
-\begin{textblock}{10}(1,13.5)
+\begin{textblock}{12}(1,14.5)
Compiler explorers, e.g.: \url{https://gcc.godbolt.org}
\end{textblock}
@@ -296,7 +319,7 @@
node/.style={
rectangle,rounded corners=3mm,
very thick,draw=black!50,minimum height=18mm, minimum width=20mm,
- top color=white,bottom color=black!20}]
+ top color=white,bottom color=black!20,drop shadow}]
\node at (3.05, 1.8) {\Large\bf write a compiler};
@@ -473,7 +496,7 @@
\end{tabular}
\end{center}\bigskip
- \texttt{char field[30000]\\ char *ptr = &field[15000]}
+ \texttt{char field[30000]\\ char *ptr = \&field[15000]}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -956,6 +979,110 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{The Star Operation}
\begin{itemize}