diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides01.tex --- 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}