# HG changeset patch # User Christian Urban # Date 1597497517 -3600 # Node ID 6acabeecdf75290ddc289e85426a49f8f8eddbc9 # Parent b5b5583a3a08f8c7deb76bc85aacdb3c44676788 updated diff -r b5b5583a3a08 -r 6acabeecdf75 graphics.sty --- a/graphics.sty Thu Jul 30 13:50:54 2020 +0100 +++ b/graphics.sty Sat Aug 15 14:18:37 2020 +0100 @@ -6,16 +6,19 @@ \usetikzlibrary{arrows} \usetikzlibrary{backgrounds} \usetikzlibrary{fit} +\usetikzlibrary{shadows} \usepackage{tikz-qtree} \usepackage{graphicx} \usepackage{pgfplots} + + \pgfplotsset{compat=1.15} \newenvironment{bubble}[1][]{% \addtolength{\leftmargini}{4mm}% \begin{tikzpicture}[baseline=(current bounding box.north)]% -\draw (0,0) node[inner sep=2mm,fill=cream,ultra thick,draw=red,rounded corners=2mm]% +\draw (0,0) node[drop shadow,inner sep=2mm,fill=cream,ultra thick,draw=red,rounded corners=2mm]% \bgroup\begin{minipage}{#1}\raggedright{}} {\end{minipage}\egroup;% \end{tikzpicture}\bigskip} diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/graphs.pdf Binary file handouts/graphs.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho01.tex --- a/handouts/ho01.tex Thu Jul 30 13:50:54 2020 +0100 +++ b/handouts/ho01.tex Sat Aug 15 14:18:37 2020 +0100 @@ -51,10 +51,10 @@ write into code the machine can run as fast as possible. Developing a compiler is an old craft going back to 1952 with the first compiler written by Grace Hopper.\footnote{Who many years ago was invited on a -talk show hosted by David Letterman, see -\url{https://youtu.be/3N_ywhx6_K0?t=31}.} Why studying compilers +talk show hosted by David Letterman. +\here{https://youtu.be/3N_ywhx6_K0?t=31}.} Why studying compilers nowadays? An interesting answer is given by John Regher in his compiler -blog:\footnote{\url{http://blog.regehr.org/archives/1419}} +blog:\here{http://blog.regehr.org/archives/1419} \begin{quote}\it{}``We can start off with a couple of observations about the role of compilers. First, hardware is getting weirder @@ -107,7 +107,7 @@ program (crashing it or making it go into an infinite loop, if not worse). This kind of ``inspecting'' mechanism is also implemented in popular network security tools such as Snort and -Bro.\footnote{\url{www.snort.org}, \url{www.bro.org}} They scan incoming +Bro.\here{www.snort.org}\here{www.bro.org} They scan incoming network traffic for computer viruses or malicious packets. Similarly filtering out spam usually involves looking for some signature (essentially a string pattern). The point is that the fast diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho07.pdf Binary file handouts/ho07.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho08.pdf Binary file handouts/ho08.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho09.pdf Binary file handouts/ho09.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/ho10.pdf Binary file handouts/ho10.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 handouts/scala-ho.pdf Binary file handouts/scala-ho.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw01.tex --- a/hws/hw01.tex Thu Jul 30 13:50:54 2020 +0100 +++ b/hws/hw01.tex Sat Aug 15 14:18:37 2020 +0100 @@ -14,9 +14,15 @@ in the lectures, install the Scala programming language available (for free) from -\begin{center} -\url{http://www.scala-lang.org} -\end{center} + \begin{center} + \url{http://www.scala-lang.org} + \end{center} + + and the Ammonite REPL from + + \begin{center} + \url{https://ammonite.io} + \end{center} If you want to follow the code I present during the lectures, read the handout about Scala. diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw06.pdf Binary file hws/hw06.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw07.pdf Binary file hws/hw07.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/hw09.pdf Binary file hws/hw09.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 hws/proof.pdf Binary file hws/proof.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 progs/bf/bfi.sc --- a/progs/bf/bfi.sc Thu Jul 30 13:50:54 2020 +0100 +++ b/progs/bf/bfi.sc Sat Aug 15 14:18:37 2020 +0100 @@ -47,7 +47,7 @@ case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } - case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) + case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) //scala.io.StdIn.readLine() case '[' => if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) diff -r b5b5583a3a08 -r 6acabeecdf75 slides.sty --- a/slides.sty Thu Jul 30 13:50:54 2020 +0100 +++ b/slides.sty Sat Aug 15 14:18:37 2020 +0100 @@ -1,6 +1,8 @@ \usepackage[absolute,overlay]{textpos} \usepackage{xcolor} \usepackage[no-math]{fontspec} +%%\usepackage{marginnote} +\usepackage{fontawesome5} %%%%% CODE FONT %\setmonofont[Scale=.95]{Consolas} @@ -24,6 +26,8 @@ \defaultfontfeatures{Ligatures=TeX} \defaultfontfeatures{Mapping=tex-text} +%% for recording slides +\setbeamersize{text margin right=5cm} % <- like this %%%% Colours @@ -46,6 +50,12 @@ \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% \newcommand{\slidecaption}{} +%%% url pointers +\newcommand{\here}[1]{\href{#1}{\small\textcolor{ProcessBlue}{\faHandPointRight[regular]}}} +\newcommand{\video}[1]{\href{#1}{\small\textcolor{ProcessBlue}{\faFilm}}} +%%\newcommand{\alert}{\reversemarginpar\marginpar{\mbox{}\hfill\textcolor{red}{\faExclamationTriangle}}} + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Frametitles diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides01.pdf Binary file slides/slides01.pdf has changed 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} diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides02.tex --- 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} diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides03.tex --- a/slides/slides03.tex Thu Jul 30 13:50:54 2020 +0100 +++ b/slides/slides03.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} @@ -22,17 +22,33 @@ \begin{tabular}{@ {}c@ {}} \\[-3mm] \LARGE Compilers and \\[-2mm] - \LARGE Formal Languages (3)\\[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 \\ + 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ + \cellcolor{blue!50} + 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} @@ -55,206 +71,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\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} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{(Basic) Regular Expressions} @@ -1329,6 +1145,360 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{center} +\begin{tikzpicture}[scale=2,>=stealth',very thick, + every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] + \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};} + \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};} + \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};} + \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};} + \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$}; + \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) + (q1) edge[bend left] node[above] {\alert{$b$}} (q0) + (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) + (q1) edge node[above] {\alert{$a$}} (q2) + (q2) edge [loop right] node {\alert{$a$}} () + (q0) edge [loop below] node {\alert{$b$}} () + ; +\end{tikzpicture} +\end{center}\bigskip + +\begin{center} +\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\ +\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\ +\end{tabular} +\end{center} + + +Arden's Lemma: +\begin{center} +If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} +\end{center} + +\only<2-6>{\small +\begin{textblock}{6}(1,0.8) +\begin{bubble}[6.7cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} +\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<3-6>{\small +\begin{textblock}{6}(2,4.15) +\begin{bubble}[6.7cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} +\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<4-6>{\small +\begin{textblock}{6}(3,7.55) +\begin{bubble}[6.7cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} + \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$} +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<5-6>{\small +\begin{textblock}{6}(4,10.9) +\begin{bubble}[7.5cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} + \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\ +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<6>{\small +\begin{textblock}{6}(5,13.4) +\begin{bubble}[7.5cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} + \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ +\end{tabular} +\end{bubble} +\end{textblock}} + + +\only<7->{\small +\begin{textblock}{6}(6,11.5) +\begin{bubble}[6.7cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} +\multicolumn{3}{@{}l}{Finally:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ +\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\ +\end{tabular} +\end{bubble} +\end{textblock}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Regexps and Automata} + +\begin{center} +\begin{tikzpicture} +\node (rexp) {\bl{\bf Regexps}}; +\node (nfa) [right=of rexp] {\bl{\bf NFAs}}; +\node (dfa) [right=of nfa] {\bl{\bf DFAs}}; +\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}}; +\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] + {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); +\path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] + {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); +\path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); +%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); +\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp); + +\end{tikzpicture}\\ +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} + +\begin{tikzpicture} +\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=30, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=10cm, + height=7cm, + legend entries={Python,Ruby,my NFA}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; +\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; +\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; +\end{axis} +\end{tikzpicture} + +The punchline is that many existing libraries do depth-first search +in NFAs (backtracking). + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{DFA to Rexp} + +% \begin{center} +% \begin{tikzpicture}[scale=2,>=stealth',very thick, +% every state/.style={minimum size=0pt, +% draw=blue!50,very thick,fill=blue!20},] +% \node[state, initial] (q0) at ( 0,1) {$q_0$}; +% \node[state] (q1) at ( 1,1) {$q_1$}; +% \node[state, accepting] (q2) at ( 2,1) {$q_2$}; +% \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) +% (q1) edge[bend left] node[above] {\alert{$b$}} (q0) +% (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) +% (q1) edge node[above] {\alert{$a$}} (q2) +% (q2) edge [loop right] node {\alert{$a$}} () +% (q0) edge [loop below] node {\alert{$b$}} (); +% \end{tikzpicture} +% \end{center}\bigskip + +% \begin{center} +% \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} +% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ +% \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ +% \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ + +% \end{tabular} +% \end{center} + +% Arden's Lemma: +% \begin{center} +% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} +% \end{center} + + +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{DFA Minimisation} + +% \begin{enumerate} +% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} +% \item Mark all pairs that accepting and non-accepting states +% \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether +% \begin{center} +% \bl{$(\delta(q, c), \delta(p,c))$} +% \end{center} +% are marked. If yes, then also mark \bl{$(q, p)$}. +% \item Repeat last step until no change. +% \item All unmarked pairs can be merged. +% \end{enumerate} + +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] + +% \begin{center} +% \begin{tabular}{@{\hspace{-8mm}}cc@{}} +% \begin{tikzpicture}[>=stealth',very thick,auto, +% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] +% \node[state,initial] (q_0) {$q_0$}; +% \node[state] (q_1) [right=of q_0] {$q_1$}; +% \node[state] (q_2) [below right=of q_0] {$q_2$}; +% \node[state] (q_3) [right=of q_2] {$q_3$}; +% \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; +% \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); +% \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); +% \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); +% \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); +% \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); +% \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); +% \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); +% \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); +% \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); +% \end{tikzpicture} +% & +% \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] +% \draw (0,0) -- (4,0); +% \draw (0,1) -- (4,1); +% \draw (0,2) -- (3,2); +% \draw (0,3) -- (2,3); +% \draw (0,4) -- (1,4); + +% \draw (0,0) -- (0, 4); +% \draw (1,0) -- (1, 4); +% \draw (2,0) -- (2, 3); +% \draw (3,0) -- (3, 2); +% \draw (4,0) -- (4, 1); + +% \draw (0.5,-0.5) node {$q_0$}; +% \draw (1.5,-0.5) node {$q_1$}; +% \draw (2.5,-0.5) node {$q_2$}; +% \draw (3.5,-0.5) node {$q_3$}; + +% \draw (-0.5, 3.5) node {$q_1$}; +% \draw (-0.5, 2.5) node {$q_2$}; +% \draw (-0.5, 1.5) node {$q_3$}; +% \draw (-0.5, 0.5) node {$q_4$}; + +% \draw (0.5,0.5) node {\large$\star$}; +% \draw (1.5,0.5) node {\large$\star$}; +% \draw (2.5,0.5) node {\large$\star$}; +% \draw (3.5,0.5) node {\large$\star$}; +% \draw (0.5,1.5) node {\large$\star$}; +% \draw (2.5,1.5) node {\large$\star$}; +% \draw (0.5,3.5) node {\large$\star$}; +% \draw (1.5,2.5) node {\large$\star$}; +% \end{tikzpicture}} +% \end{tabular} +% \end{center} + + +% \mbox{}\\[-20mm]\mbox{} + +% \begin{center} +% \begin{tikzpicture}[>=stealth',very thick,auto, +% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] +% \node[state,initial] (q_02) {$q_{0, 2}$}; +% \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; +% \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; +% \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); +% \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); +% \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); +% \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); +% \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); +% \end{tikzpicture}\\ +% minimal automaton +% \end{center} + +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Regular Languages} + +Two equivalent definitions:\bigskip + +\begin{quote}\rm A language is \alert{regular} iff there exists a +regular expression that recognises all its strings. +\end{quote} + +\begin{quote}\rm A language is \alert{regular} iff there exists an +automaton that recognises all its strings. +\end{quote}\bigskip\bigskip + + +\small +for example \bl{$a^nb^n$} is not regular +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Negation} + +Regular languages are closed under negation:\bigskip + +\begin{center} +\begin{tikzpicture}[scale=2,>=stealth',very thick, + every state/.style={minimum size=0pt, + draw=blue!50,very thick,fill=blue!20}] + \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};} + \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};} + \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} + \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} + \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} + \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};} + \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) + (q1) edge[bend left] node[above] {\alert{$b$}} (q0) + (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) + (q1) edge node[above] {\alert{$a$}} (q2) + (q2) edge [loop right] node {\alert{$a$}} () + (q0) edge [loop below] node {\alert{$b$}} (); +\end{tikzpicture} +\end{center}\bigskip\bigskip + +But requires that the automaton is \alert{completed}! + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \end{document} %%% Local Variables: diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides04.tex --- a/slides/slides04.tex Thu Jul 30 13:50:54 2020 +0100 +++ b/slides/slides04.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} @@ -27,126 +27,38 @@ \begin{tabular}{@ {}c@ {}} \\[-3mm] \LARGE Compilers and \\[-2mm] - \LARGE Formal Languages (4)\\[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 \\ + 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ + 3 Automata, Regular Languages & 8 Compiling Functional Languages \\ + \cellcolor{blue!50} + 4 Lexing, Tokenising & 9 Optimisations \\ + 5 Grammars, Parsing & 10 LLVM \\ \hline + \end{tabular}% + }; + \end{tikzpicture} + \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\begin{center} -\begin{tikzpicture}[scale=2,>=stealth',very thick, - every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] - \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};} - \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};} - \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};} - \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};} - \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$}; - \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) - (q1) edge[bend left] node[above] {\alert{$b$}} (q0) - (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) - (q1) edge node[above] {\alert{$a$}} (q2) - (q2) edge [loop right] node {\alert{$a$}} () - (q0) edge [loop below] node {\alert{$b$}} () - ; -\end{tikzpicture} -\end{center}\bigskip - -\begin{center} -\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\ -\end{tabular} -\end{center} - - -Arden's Lemma: -\begin{center} -If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} -\end{center} - -\only<2-6>{\small -\begin{textblock}{6}(1,0.8) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<3-6>{\small -\begin{textblock}{6}(2,4.15) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<4-6>{\small -\begin{textblock}{6}(3,7.55) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<5-6>{\small -\begin{textblock}{6}(4,10.9) -\begin{bubble}[7.5cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<6>{\small -\begin{textblock}{6}(5,13.4) -\begin{bubble}[7.5cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - - -\only<7->{\small -\begin{textblock}{6}(6,11.5) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{Finally:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ -\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -192,251 +104,7 @@ \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Regexps and Automata} - -\begin{center} -\begin{tikzpicture} -\node (rexp) {\bl{\bf Regexps}}; -\node (nfa) [right=of rexp] {\bl{\bf NFAs}}; -\node (dfa) [right=of nfa] {\bl{\bf DFAs}}; -\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}}; -\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] - {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); -\path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] - {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); -\path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); -%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); -\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp); - -\end{tikzpicture}\\ -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} - -\begin{tikzpicture} -\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, - enlargelimits=false, - xtick={0,5,...,30}, - xmax=30, - ymax=35, - ytick={0,5,...,30}, - scaled ticks=false, - axis lines=left, - width=10cm, - height=7cm, - legend entries={Python,Ruby,my NFA}, - legend pos=north west, - legend cell align=left] -\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; -\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; -\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; -\end{axis} -\end{tikzpicture} - -The punchline is that many existing libraries do depth-first search -in NFAs (backtracking). - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{DFA to Rexp} - -% \begin{center} -% \begin{tikzpicture}[scale=2,>=stealth',very thick, -% every state/.style={minimum size=0pt, -% draw=blue!50,very thick,fill=blue!20},] -% \node[state, initial] (q0) at ( 0,1) {$q_0$}; -% \node[state] (q1) at ( 1,1) {$q_1$}; -% \node[state, accepting] (q2) at ( 2,1) {$q_2$}; -% \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) -% (q1) edge[bend left] node[above] {\alert{$b$}} (q0) -% (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) -% (q1) edge node[above] {\alert{$a$}} (q2) -% (q2) edge [loop right] node {\alert{$a$}} () -% (q0) edge [loop below] node {\alert{$b$}} (); -% \end{tikzpicture} -% \end{center}\bigskip - -% \begin{center} -% \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} -% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ -% \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ -% \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ - -% \end{tabular} -% \end{center} - -% Arden's Lemma: -% \begin{center} -% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} -% \end{center} - - -% \end{frame} -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{DFA Minimisation} - -% \begin{enumerate} -% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} -% \item Mark all pairs that accepting and non-accepting states -% \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether -% \begin{center} -% \bl{$(\delta(q, c), \delta(p,c))$} -% \end{center} -% are marked. If yes, then also mark \bl{$(q, p)$}. -% \item Repeat last step until no change. -% \item All unmarked pairs can be merged. -% \end{enumerate} - -% \end{frame} -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] - -% \begin{center} -% \begin{tabular}{@{\hspace{-8mm}}cc@{}} -% \begin{tikzpicture}[>=stealth',very thick,auto, -% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] -% \node[state,initial] (q_0) {$q_0$}; -% \node[state] (q_1) [right=of q_0] {$q_1$}; -% \node[state] (q_2) [below right=of q_0] {$q_2$}; -% \node[state] (q_3) [right=of q_2] {$q_3$}; -% \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; -% \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); -% \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); -% \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); -% \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); -% \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); -% \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); -% \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); -% \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); -% \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); -% \end{tikzpicture} -% & -% \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] -% \draw (0,0) -- (4,0); -% \draw (0,1) -- (4,1); -% \draw (0,2) -- (3,2); -% \draw (0,3) -- (2,3); -% \draw (0,4) -- (1,4); - -% \draw (0,0) -- (0, 4); -% \draw (1,0) -- (1, 4); -% \draw (2,0) -- (2, 3); -% \draw (3,0) -- (3, 2); -% \draw (4,0) -- (4, 1); - -% \draw (0.5,-0.5) node {$q_0$}; -% \draw (1.5,-0.5) node {$q_1$}; -% \draw (2.5,-0.5) node {$q_2$}; -% \draw (3.5,-0.5) node {$q_3$}; - -% \draw (-0.5, 3.5) node {$q_1$}; -% \draw (-0.5, 2.5) node {$q_2$}; -% \draw (-0.5, 1.5) node {$q_3$}; -% \draw (-0.5, 0.5) node {$q_4$}; - -% \draw (0.5,0.5) node {\large$\star$}; -% \draw (1.5,0.5) node {\large$\star$}; -% \draw (2.5,0.5) node {\large$\star$}; -% \draw (3.5,0.5) node {\large$\star$}; -% \draw (0.5,1.5) node {\large$\star$}; -% \draw (2.5,1.5) node {\large$\star$}; -% \draw (0.5,3.5) node {\large$\star$}; -% \draw (1.5,2.5) node {\large$\star$}; -% \end{tikzpicture}} -% \end{tabular} -% \end{center} - - -% \mbox{}\\[-20mm]\mbox{} - -% \begin{center} -% \begin{tikzpicture}[>=stealth',very thick,auto, -% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] -% \node[state,initial] (q_02) {$q_{0, 2}$}; -% \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; -% \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; -% \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); -% \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); -% \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); -% \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); -% \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); -% \end{tikzpicture}\\ -% minimal automaton -% \end{center} - -% \end{frame} -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Regular Languages} - -Two equivalent definitions:\bigskip - -\begin{quote}\rm A language is \alert{regular} iff there exists a -regular expression that recognises all its strings. -\end{quote} - -\begin{quote}\rm A language is \alert{regular} iff there exists an -automaton that recognises all its strings. -\end{quote}\bigskip\bigskip - - -\small -for example \bl{$a^nb^n$} is not regular -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Negation} - -Regular languages are closed under negation:\bigskip - -\begin{center} -\begin{tikzpicture}[scale=2,>=stealth',very thick, - every state/.style={minimum size=0pt, - draw=blue!50,very thick,fill=blue!20}] - \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};} - \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};} - \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} - \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} - \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} - \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};} - \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) - (q1) edge[bend left] node[above] {\alert{$b$}} (q0) - (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) - (q1) edge node[above] {\alert{$a$}} (q2) - (q2) edge [loop right] node {\alert{$a$}} () - (q0) edge [loop below] node {\alert{$b$}} (); -\end{tikzpicture} -\end{center}\bigskip\bigskip - -But requires that the automaton is \alert{completed}! - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -449,7 +117,7 @@ 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}; @@ -509,7 +177,7 @@ \begin{frame}[c] \frametitle{Lexing: Test Case} -\mbox{\lstinputlisting[language=While]{../progs/fib.while}} +??%\mbox{\lstinputlisting[language=While]{../progs/fib.while}} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -1474,6 +1142,416 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Last Week\\[-2mm] + Regexes and Values\end{tabular}} + +Regular expressions and their corresponding values: + +\begin{center} +\begin{columns} +\begin{column}{3cm} +\begin{tabular}{@{}rrl@{}} + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\ + & \bl{$\mid$} & \bl{$\ONE$} \\ + & \bl{$\mid$} & \bl{$c$} \\ + & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ + & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ + \\ + & \bl{$\mid$} & \bl{$r^*$} \\ + \end{tabular} +\end{column} +\begin{column}{3cm} +\begin{tabular}{@{\hspace{-7mm}}rrl@{}} + \bl{$v$} & \bl{$::=$} & \\ + & & \bl{$Empty$} \\ + & \bl{$\mid$} & \bl{$Char(c)$} \\ + & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ + & \bl{$\mid$} & \bl{$Left(v)$} \\ + & \bl{$\mid$} & \bl{$Right(v)$} \\ + & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\ + \end{tabular} +\end{column} +\end{columns} +\end{center} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{textblock}{10}(3,5) +\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] +\node (r1) {\bl{$r_1$}}; +\node (r2) [right=of r1] {\bl{$r_2$}}; +\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; +\node (r3) [right=of r2] {\bl{$r_3$}}; +\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; +\node (r4) [right=of r3] {\bl{$r_4$}}; +\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; +\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; +\node (v4) [below=of r4] {\bl{$v_4$}}; +\draw[->,line width=1mm] (r4) -- (v4); +\node (v3) [left=of v4] {\bl{$v_3$}}; +\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; +\node (v2) [left=of v3] {\bl{$v_2$}}; +\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; +\node (v1) [left=of v2] {\bl{$v_1$}}; +\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; +\draw[->,line width=0.5mm] (r3) -- (v3); +\draw[->,line width=0.5mm] (r2) -- (v2); +\draw[->,line width=0.5mm] (r1) -- (v1); +\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; +\end{tikzpicture} +\end{textblock} + +\begin{textblock}{6}(1,0.8) +\begin{bubble}[6cm] +\small +\begin{tabular}{ll} +\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ +\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\ +\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\ +\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\ +\end{tabular} +\end{bubble} +\end{textblock} + +\begin{textblock}{6}(1,11.4) +\begin{bubble}[7.6cm] +\small +\begin{tabular}{ll} +\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ +\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ +\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ +\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ +\end{tabular} +\end{bubble} +\end{textblock} + +\begin{textblock}{6}(12,11.4) +\begin{bubble}[2cm] +\small +\begin{tabular}{ll} +\bl{$|v_1|$}: & \bl{$abc$}\\ +\bl{$|v_2|$}: & \bl{$bc$}\\ +\bl{$|v_3|$}: & \bl{$c$}\\ +\bl{$|v_4|$}: & \bl{$[]$} +\end{tabular} +\end{bubble} +\end{textblock} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Simplification} + +\begin{itemize} +\item If we simplify after the derivative, then we are builing the +value for the simplified regular expression, but \emph{not} for the original +regular expression. +\end{itemize} + +\begin{center} +\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] +\node (r1) {\bl{$r_1$}}; +\node (r2) [right=of r1] {\bl{$r_2$}}; +\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; +\node (r3) [right=of r2] {\bl{$r_3$}}; +\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; +\node (r4) [right=of r3] {\bl{$r_4$}}; +\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; +\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; +\node (v4) [below=of r4] {\bl{$v_4$}}; +\draw[->,line width=1mm] (r4) -- (v4); +\node (v3) [left=of v4] {\bl{$v_3$}}; +\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; +\node (v2) [left=of v3] {\bl{$v_2$}}; +\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; +\node (v1) [left=of v2] {\bl{$v_1$}}; +\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; +\draw[->,line width=0.5mm] (r3) -- (v3); +\draw[->,line width=0.5mm] (r2) -- (v2); +\draw[->,line width=0.5mm] (r1) -- (v1); +\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; +\end{tikzpicture} +\end{center} + +\small +\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$} +$\mapsto$ +\bl{$(b \cdot c) + \ONE$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[t] + +% \begin{center} +% \bl{$\only<1>{(b \cdot c)}% +% \only<2-3>{(\underline{b \cdot c})}% +% \only<1-3>{+}% +% \only<1>{(\ZERO + \ONE)}% +% \only<2-3>{(\underline{\ZERO + \ONE})}$}% +% \only<4->{% +% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}% +% } +% $\mapsto$ +% \bl{$(b \cdot c) + \ONE$} +% \end{center}\bigskip + +% \onslide<3->{% +% \begin{center} +% \begin{tabular}{lcl} +% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\ +% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$} +% \end{tabular} +% \end{center}} + +% \only<4>{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} +% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\ +% \quad \bl{$\lambda v.\,$} +% case \bl{$v = Left(v')$}: +% & return \bl{$Left(f_{s1}(v'))$}\\ +% \quad \phantom{$\lambda v.\,$} +% case \bl{$v = Right(v')$}: +% & return \bl{$Right(f_{s2}(v'))$}\\ +% \end{tabular} +% \end{center}}% +% \only<5->{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} +% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\ +% \quad \bl{$\lambda v.\,$} +% case \bl{$v = Left(v')$}: +% & return \bl{$Left(v')$}\\ +% \quad \phantom{$\lambda v.\,$} +% case \bl{$v = Right(v')$}: +% & return \bl{$Right(Right(v'))$}\\ +% \end{tabular} +% \end{center}}% + +% \only<6->{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}} +% \bl{$\textit{mkeps}$} simplified case: & +% \bl{$\textit{Right}(\textit{Empty})$}\\ +% rectified case: & +% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$} +% \end{tabular} +% \end{center}}% + +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Records} + +\begin{itemize} +\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause + +\item \bl{$nullable(x:r) \dn nullable(r)$} +\item \bl{$der\,c\,(x:r) \dn der\,c\,r$} +\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} +\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} +\end{itemize}\bigskip\bigskip\pause + +\small +for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Environments} + +Obtaining the ``recorded'' parts of a value: + +\begin{center} +\begin{tabular}{lcl} + \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\ + \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\ + \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ + \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ + \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\ + \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} & + \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\ + \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{While Tokens} + +\begin{center} +\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}} +\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ + & & \phantom{(}\pcode{("i" : ID)} +\\ + & & \phantom{(}\pcode{("o" : OP)} + \\ + & & \phantom{(}\pcode{("n" : NUM)} + \\ + & & \phantom{(}\pcode{("s" : SEMI)} +\\ + & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ + & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ + & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$} +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] + +\consolas +\begin{center} +\code{"if true then then 42 else +"} +\end{center} + +\only<1>{ +\small\begin{tabular}{l} +KEYWORD(if),\\ +WHITESPACE,\\ +IDENT(true),\\ +WHITESPACE,\\ +KEYWORD(then),\\ +WHITESPACE,\\ +KEYWORD(then),\\ +WHITESPACE,\\ +NUM(42),\\ +WHITESPACE,\\ +KEYWORD(else),\\ +WHITESPACE,\\ +OP(+) +\end{tabular}} + +\only<2>{ +\small\begin{tabular}{l} +KEYWORD(if),\\ +IDENT(true),\\ +KEYWORD(then),\\ +KEYWORD(then),\\ +NUM(42),\\ +KEYWORD(else),\\ +OP(+) +\end{tabular}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Coursework: PLs (16)} +% +%\begin{itemize} +%\item Java (16) +%\item C++, C, C\# (14) +%\item JavaScript (10) +%\item Scala (9) +%\item Python (9) +%\item PHP (6) +%\item Haskell (3) +%\item Ruby (4) +%\item Bash, Perl, Powershell (2) +%\item TypeScript (1) +%\item R (1) +%\item Coconut (1) +%\item Pascal (1) +%\end{itemize} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Coursework: Nullable} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +% \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\ +% +%\end{tabular} +%\end{center} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%%%\frametitle{Coursework: der} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}} +% \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\ +% \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\ +% & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\ +% \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\ +% +% \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & +% \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\ +% \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\ +% \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else +% \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\ +% \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\ +%\end{tabular} +%\end{center} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Coursework: CFUN} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +% \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\ +% \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} & +% \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\ +% \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\ +% \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\ +% \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\ +%\end{tabular} +%\end{center} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + \end{document} %%% Local Variables: diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides05.tex --- a/slides/slides05.tex Thu Jul 30 13:50:54 2020 +0100 +++ b/slides/slides05.tex Sat Aug 15 14:18:37 2020 +0100 @@ -1,6 +1,6 @@ % !TEX program = xelatex -\documentclass[dvipsnames,14pt,t]{beamer} +\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} \usepackage{../graphics} \usepackage{../langs} @@ -25,448 +25,55 @@ \begin{tabular}{@ {}c@ {}} \\[-3mm] \LARGE Compilers and \\[-2mm] - \LARGE Formal Languages (5)\\[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 \\ + 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ + 3 Automata, Regular Languages & 8 Compiling Functional Languages \\ + 4 Lexing, Tokenising & 9 Optimisations \\ + \cellcolor{blue!50} + 5 Grammars, Parsing & 10 LLVM \\ \hline + \end{tabular}% + }; + \end{tikzpicture} \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Coursework 1: Submissions} - - \begin{itemize} - \item Scala (29) - \item Haskell (1) - \item Kotlin (1) - \item Rust (1) - \end{itemize}\bigskip\bigskip - - \small - Please get in contact if you intend to do CW Strand 2. No zips please. - Give definitions also on paper if asked. BTW, simp - can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}! - \end{frame} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Last Week\\[-2mm] - Regexes and Values\end{tabular}} - -Regular expressions and their corresponding values: - -\begin{center} -\begin{columns} -\begin{column}{3cm} -\begin{tabular}{@{}rrl@{}} - \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\ - & \bl{$\mid$} & \bl{$\ONE$} \\ - & \bl{$\mid$} & \bl{$c$} \\ - & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ - & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ - \\ - & \bl{$\mid$} & \bl{$r^*$} \\ - \end{tabular} -\end{column} -\begin{column}{3cm} -\begin{tabular}{@{\hspace{-7mm}}rrl@{}} - \bl{$v$} & \bl{$::=$} & \\ - & & \bl{$Empty$} \\ - & \bl{$\mid$} & \bl{$Char(c)$} \\ - & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ - & \bl{$\mid$} & \bl{$Left(v)$} \\ - & \bl{$\mid$} & \bl{$Right(v)$} \\ - & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\ - \end{tabular} -\end{column} -\end{columns} -\end{center} - - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\begin{textblock}{10}(3,5) -\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] -\node (r1) {\bl{$r_1$}}; -\node (r2) [right=of r1] {\bl{$r_2$}}; -\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; -\node (r3) [right=of r2] {\bl{$r_3$}}; -\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; -\node (r4) [right=of r3] {\bl{$r_4$}}; -\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; -\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; -\node (v4) [below=of r4] {\bl{$v_4$}}; -\draw[->,line width=1mm] (r4) -- (v4); -\node (v3) [left=of v4] {\bl{$v_3$}}; -\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; -\node (v2) [left=of v3] {\bl{$v_2$}}; -\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; -\node (v1) [left=of v2] {\bl{$v_1$}}; -\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; -\draw[->,line width=0.5mm] (r3) -- (v3); -\draw[->,line width=0.5mm] (r2) -- (v2); -\draw[->,line width=0.5mm] (r1) -- (v1); -\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; -\end{tikzpicture} -\end{textblock} - -\begin{textblock}{6}(1,0.8) -\begin{bubble}[6cm] -\small -\begin{tabular}{ll} -\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ -\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\ -\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\ -\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\ -\end{tabular} -\end{bubble} -\end{textblock} - -\begin{textblock}{6}(1,11.4) -\begin{bubble}[7.6cm] -\small -\begin{tabular}{ll} -\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ -\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ -\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ -\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ -\end{tabular} -\end{bubble} -\end{textblock} - -\begin{textblock}{6}(12,11.4) -\begin{bubble}[2cm] -\small -\begin{tabular}{ll} -\bl{$|v_1|$}: & \bl{$abc$}\\ -\bl{$|v_2|$}: & \bl{$bc$}\\ -\bl{$|v_3|$}: & \bl{$c$}\\ -\bl{$|v_4|$}: & \bl{$[]$} -\end{tabular} -\end{bubble} -\end{textblock} - - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - +%\begin{frame}[c] +% \frametitle{Coursework 1: Submissions} +% +% \begin{itemize} +% \item Scala (29) +% \item Haskell (1) +% \item Kotlin (1) +% \item Rust (1) +% \end{itemize}\bigskip\bigskip +% +% \small +% Please get in contact if you intend to do CW Strand 2. No zips please. +% Give definitions also on paper if asked. BTW, simp +% can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}! +% \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Simplification} - -\begin{itemize} -\item If we simplify after the derivative, then we are builing the -value for the simplified regular expression, but \emph{not} for the original -regular expression. -\end{itemize} - -\begin{center} -\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] -\node (r1) {\bl{$r_1$}}; -\node (r2) [right=of r1] {\bl{$r_2$}}; -\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; -\node (r3) [right=of r2] {\bl{$r_3$}}; -\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; -\node (r4) [right=of r3] {\bl{$r_4$}}; -\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; -\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; -\node (v4) [below=of r4] {\bl{$v_4$}}; -\draw[->,line width=1mm] (r4) -- (v4); -\node (v3) [left=of v4] {\bl{$v_3$}}; -\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; -\node (v2) [left=of v3] {\bl{$v_2$}}; -\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; -\node (v1) [left=of v2] {\bl{$v_1$}}; -\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; -\draw[->,line width=0.5mm] (r3) -- (v3); -\draw[->,line width=0.5mm] (r2) -- (v2); -\draw[->,line width=0.5mm] (r1) -- (v1); -\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; -\end{tikzpicture} -\end{center} - -\small -\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$} -$\mapsto$ -\bl{$(b \cdot c) + \ONE$} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[t] - -% \begin{center} -% \bl{$\only<1>{(b \cdot c)}% -% \only<2-3>{(\underline{b \cdot c})}% -% \only<1-3>{+}% -% \only<1>{(\ZERO + \ONE)}% -% \only<2-3>{(\underline{\ZERO + \ONE})}$}% -% \only<4->{% -% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}% -% } -% $\mapsto$ -% \bl{$(b \cdot c) + \ONE$} -% \end{center}\bigskip - -% \onslide<3->{% -% \begin{center} -% \begin{tabular}{lcl} -% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\ -% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$} -% \end{tabular} -% \end{center}} - -% \only<4>{% -% \begin{center} -% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} -% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\ -% \quad \bl{$\lambda v.\,$} -% case \bl{$v = Left(v')$}: -% & return \bl{$Left(f_{s1}(v'))$}\\ -% \quad \phantom{$\lambda v.\,$} -% case \bl{$v = Right(v')$}: -% & return \bl{$Right(f_{s2}(v'))$}\\ -% \end{tabular} -% \end{center}}% -% \only<5->{% -% \begin{center} -% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} -% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\ -% \quad \bl{$\lambda v.\,$} -% case \bl{$v = Left(v')$}: -% & return \bl{$Left(v')$}\\ -% \quad \phantom{$\lambda v.\,$} -% case \bl{$v = Right(v')$}: -% & return \bl{$Right(Right(v'))$}\\ -% \end{tabular} -% \end{center}}% - -% \only<6->{% -% \begin{center} -% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}} -% \bl{$\textit{mkeps}$} simplified case: & -% \bl{$\textit{Right}(\textit{Empty})$}\\ -% rectified case: & -% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$} -% \end{tabular} -% \end{center}}% - -% \end{frame} -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Records} - -\begin{itemize} -\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause - -\item \bl{$nullable(x:r) \dn nullable(r)$} -\item \bl{$der\,c\,(x:r) \dn der\,c\,r$} -\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} -\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} -\end{itemize}\bigskip\bigskip\pause - -\small -for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Environments} - -Obtaining the ``recorded'' parts of a value: - -\begin{center} -\begin{tabular}{lcl} - \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\ - \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\ - \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ - \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ - \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\ - \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} & - \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\ - \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\ -\end{tabular} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{While Tokens} - -\begin{center} -\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}} -\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ - & & \phantom{(}\pcode{("i" : ID)} +\\ - & & \phantom{(}\pcode{("o" : OP)} + \\ - & & \phantom{(}\pcode{("n" : NUM)} + \\ - & & \phantom{(}\pcode{("s" : SEMI)} +\\ - & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ - & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ - & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$} -\end{tabular} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] - -\consolas -\begin{center} -\code{"if true then then 42 else +"} -\end{center} - -\only<1>{ -\small\begin{tabular}{l} -KEYWORD(if),\\ -WHITESPACE,\\ -IDENT(true),\\ -WHITESPACE,\\ -KEYWORD(then),\\ -WHITESPACE,\\ -KEYWORD(then),\\ -WHITESPACE,\\ -NUM(42),\\ -WHITESPACE,\\ -KEYWORD(else),\\ -WHITESPACE,\\ -OP(+) -\end{tabular}} - -\only<2>{ -\small\begin{tabular}{l} -KEYWORD(if),\\ -IDENT(true),\\ -KEYWORD(then),\\ -KEYWORD(then),\\ -NUM(42),\\ -KEYWORD(else),\\ -OP(+) -\end{tabular}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%\frametitle{Coursework: PLs (16)} -% -%\begin{itemize} -%\item Java (16) -%\item C++, C, C\# (14) -%\item JavaScript (10) -%\item Scala (9) -%\item Python (9) -%\item PHP (6) -%\item Haskell (3) -%\item Ruby (4) -%\item Bash, Perl, Powershell (2) -%\item TypeScript (1) -%\item R (1) -%\item Coconut (1) -%\item Pascal (1) -%\end{itemize} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%\frametitle{Coursework: Nullable} -% -%\begin{center} -%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -% \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ -% \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\ -% \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\ -% \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\ -% \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\ -% \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\ -% \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\ -% \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\ -% -%\end{tabular} -%\end{center} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%%%\frametitle{Coursework: der} -% -%\begin{center} -%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}} -% \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ -% \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\ -% \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\ -% \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & -% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\ -% \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & -% \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\ -% & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\ -% \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & -% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\ -% -% \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & -% \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\ -% \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\ -% \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else -% \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\ -% \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\ -%\end{tabular} -%\end{center} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%\frametitle{Coursework: CFUN} -% -%\begin{center} -%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -% \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\ -% \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} & -% \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\ -% \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\ -% \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\ -% \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\ -%\end{tabular} -%\end{center} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{Lexer, Parser} @@ -478,7 +85,7 @@ 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 (0) at (-2.3,0) {}; \node (A) at (0,0) [node] {}; @@ -1239,8 +846,8 @@ \mbox{}\\[-18mm]\mbox{} -{\lstset{language=While}%%\fontsize{10}{12}\selectfont -\texttt{\lstinputlisting{../progs/loops.while}}} +??%{\lstset{language=While}%%\fontsize{10}{12}\selectfont +%\texttt{\lstinputlisting{../progs/loops.while}}} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% diff -r b5b5583a3a08 -r 6acabeecdf75 style.sty --- a/style.sty Thu Jul 30 13:50:54 2020 +0100 +++ b/style.sty Sat Aug 15 14:18:37 2020 +0100 @@ -9,6 +9,8 @@ \definecolor{darkblue}{rgb}{0,0,0.6} \usepackage[colorlinks=true,urlcolor=darkblue,linkcolor=darkblue]{hyperref} \usepackage{soul} +\usepackage{marginnote} +\usepackage{fontawesome5} %%% for regular expressions and values \newcommand{\ZERO}{\mbox{\bf 0}} @@ -49,6 +51,12 @@ \def\VS{\Vspace[0.6em]} +%%% url pointers +\newcommand{\here}[1]{\marginnote{\href{#1}{\faHandPointRight[regular]}}} +\newcommand{\video}[1]{\marginnote{\href{#1}{\faFilm}}} +\newcommand{\alert}{\reversemarginpar\marginpar{\mbox{}\hfill\textcolor{red}{\faExclamationTriangle}}} + + \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}} \newcommand{\defn}[1]{\textit{\textbf{#1}}} \newcommand{\dq}[1]{\mbox{\tt{"}}#1\mbox{\tt{"}}} @@ -60,7 +68,7 @@ \makeatother \newcommand{\HEADER}{{\bf Please submit your solutions via email. Please submit -only ASCII text or PDFs. Every solution should be preceeded by the corresponding +only PDFs! Every solution should be preceeded by the corresponding question text, like: \begin{center} @@ -82,7 +90,10 @@ parts in this lecture? Any problems with my Scala code? Please feel free to share any other questions or concerns. Also, all my material is \st{crap} imperfect. If you have any suggestions for -improvement, I am very grateful to hear.} +improvement, I am very grateful to hear.\medskip + +If *you* want to share anything (code, videos, links), you are +encouraged to do so. Just drop me an email.} % CW deadlines