# HG changeset patch # User Christian Urban # Date 1600385583 -3600 # Node ID ea0be0662be04b0ee0881b7aa8903427f4a38e7a # Parent f7c7a75e05836f4a651d30c72065d6dfdbdf32e8 updated diff -r f7c7a75e0583 -r ea0be0662be0 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r f7c7a75e0583 -r ea0be0662be0 handouts/ho02.tex --- a/handouts/ho02.tex Tue Sep 15 23:13:45 2020 +0100 +++ b/handouts/ho02.tex Fri Sep 18 00:33:03 2020 +0100 @@ -13,15 +13,15 @@ \section*{Handout 2 (Regular Expression Matching)} -\noindent -{\bf Checklist} - -\begin{itemize} - \item You have understood the derivative-based matching algorithm. - \item You know how the derivative is related to the meaning of regular - expressions. - \item You can extend the algorithm to non-basic regular expressions. -\end{itemize}\bigskip\bigskip\bigskip +%\noindent +%{\bf Checklist} +% +%\begin{itemize} +% \item You have understood the derivative-based matching algorithm. +% \item You know how the derivative is related to the meaning of regular +% expressions. +% \item You can extend the algorithm to non-basic regular expressions. +%\end{itemize}\bigskip\bigskip\bigskip \noindent This lecture is about implementing a more efficient regular expression diff -r f7c7a75e0583 -r ea0be0662be0 progs/lexer/lexer.sc --- a/progs/lexer/lexer.sc Tue Sep 15 23:13:45 2020 +0100 +++ b/progs/lexer/lexer.sc Fri Sep 18 00:33:03 2020 +0100 @@ -32,8 +32,6 @@ case class Rec(x: String, v: Val) extends Val // some convenience for typing in regular expressions -import scala.language.implicitConversions -import scala.language.reflectiveCalls def charlist2rexp(s : List[Char]): Rexp = s match { case Nil => ONE diff -r f7c7a75e0583 -r ea0be0662be0 progs/while-compiler-arrays/compile_arrays.sc --- a/progs/while-compiler-arrays/compile_arrays.sc Tue Sep 15 23:13:45 2020 +0100 +++ b/progs/while-compiler-arrays/compile_arrays.sc Fri Sep 18 00:33:03 2020 +0100 @@ -87,8 +87,6 @@ // convenient string interpolations // for generating instructions and labels -import scala.language.implicitConversions -import scala.language.reflectiveCalls implicit def sring_inters(sc: StringContext) = new { def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" diff -r f7c7a75e0583 -r ea0be0662be0 progs/while-compiler-arrays/compile_bfc.sc --- a/progs/while-compiler-arrays/compile_bfc.sc Tue Sep 15 23:13:45 2020 +0100 +++ b/progs/while-compiler-arrays/compile_bfc.sc Fri Sep 18 00:33:03 2020 +0100 @@ -292,7 +292,7 @@ @doc(" Mandelbrot set.") @main -def bfc4() = bf_run(read(pwd / "mandelbrot.bf"), "mand") +def bfc4() = bf_run(read(pwd / "mandelbrot.bf"), "mandelbrot") // this unfortunately hits the capacity of the JVM, even with optimisations diff -r f7c7a75e0583 -r ea0be0662be0 slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r f7c7a75e0583 -r ea0be0662be0 slides/slides01.tex --- a/slides/slides01.tex Tue Sep 15 23:13:45 2020 +0100 +++ b/slides/slides01.tex Fri Sep 18 00:33:03 2020 +0100 @@ -369,7 +369,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] - \frametitle{A ``Compiler'' for BF*** to C} + \frametitle{Another~``Compiler''~for~BF~to~C} \begin{center} \begin{tabular}{rcl} @@ -389,26 +389,7 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Recap} - - \begin{itemize} - \item interpreter \bl{\texttt{bfi.sc}} \\$\Rightarrow$ 11 mins\pause - \item simple compiler \bl{\texttt{bfi0.sc}}, no optimisations \\$\Rightarrow$ 20 secs\pause - \item ``advanced'' compiler \bl{\texttt{bfi1.sc}}, no optimisations \\$\Rightarrow$ 5 secs\bigskip\pause - - \item simple compiler \bl{\texttt{bfi0.sc}}, - \alert{\textbf{full optimisations}} \\$\Rightarrow$ 7 secs - \end{itemize}\bigskip\pause - - \hspace{4cm}all programs on KEATS - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{A Brief Compiler History} @@ -439,6 +420,73 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] +\frametitle{Some Housekeeping} + +\textbf{Exams will be online:}\bigskip + +\begin{itemize} +\item final exam in January (30\%) +\item mid-term shortly after Reading Week (10\%)\bigskip + +\item weekly engagement (10\%) +\end{itemize}\bigskip\bigskip\pause + + +\textbf{Weekly Homework (optional):} +\begin{itemize} +\item uploaded on KEATS, send answers via email, responded individually +\item \alert{\bf all} questions in the exam and mid-term will be from the HW!! +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Some Housekeeping} + +\textbf{Coursework (5 accounting for 45\%):}\bigskip + +\begin{itemize} +\item matcher (5\%) +\item lexer (8\%) +\item parser / interpreter (10\%) +\item JVM compiler (10\%) +\item LLVM compiler (12\%) +\end{itemize}\bigskip\pause + +you can use any programming language you like (Haskell, Rust)\\\pause +you can use any code I showed you and uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!}\pause + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Lectures 1 - 5} + +transforming strings into structured data\\[10mm] + +{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\ +\hspace{5mm}(recognising ``words'')\\[6mm] + +{\LARGE\bf Parsing}\medskip\\ +\hspace{5mm}(recognising ``sentences'') + +\begin{textblock}{1}(10,9.1) +\begin{tabular}{c} +\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm] +\footnotesize Stone of Rosetta +\end{tabular} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] \frametitle{Lectures 1 - 5} transforming strings into structured data\\[10mm] @@ -479,13 +527,13 @@ \end{textblock} \end{frame} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{Familiar Regular Expr.} +\frametitle{Familiar Regular Expresssions} \small \begin{center} \texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}} @@ -509,11 +557,35 @@ \end{tabular} \end{center} +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Some ``innocent'' examples} + +Let's try two examples + +\begin{center} + \bl{\texttt{(a*)*b}} + \hspace{2cm} + \bl{\texttt{[a?]\{n\}[a]\{n\}}} +\end{center}\bigskip\pause + +and match them with strings of the form + +\begin{center} + \bl{\texttt{a}}, + \bl{\texttt{aa}}, + \bl{\texttt{aaa}}, + \bl{\texttt{aaaa}}, + \bl{\texttt{aaaaa}}, + \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$} +\end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Why Bother with Regexes?} @@ -804,26 +876,26 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{A Regular Expression} - -\begin{itemize} -\item \ldots{} is a pattern or template for specifying strings -\end{itemize}\bigskip - -\begin{center} -\only<1>{\scode{"https?://[^"]*"}}% -\only<2>{\scode{""""https?://[^"]*"""".r}} -\end{center}\bigskip\bigskip - -matches for example\smallskip\\ -\hspace{2mm}\code{"http://www.foobar.com"}\\ -\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\ - -but not\smallskip\\ -\hspace{2mm}\code{"http://www."foo"bar.com"}\\ - -\end{frame} +%\begin{frame}[t] +%\frametitle{A Regular Expression} +% +%\begin{itemize} +%\item \ldots{} is a pattern or template for specifying strings +%\end{itemize}\bigskip +% +%\begin{center} +%\only<1>{\scode{"https?://[^"]*"}}% +%\only<2>{\scode{""""https?://[^"]*"""".r}} +%\end{center}\bigskip\bigskip +% +%matches for example\smallskip\\ +%\hspace{2mm}\code{"http://www.foobar.com"}\\ +%\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\ +% +%but not\smallskip\\ +%\hspace{2mm}\code{"http://www."foo"bar.com"}\\ +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -887,7 +959,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{Regular Expressions} +\frametitle{(Basic) Regular Expressions} Their inductive definition: