# HG changeset patch # User Christian Urban # Date 1443211164 -3600 # Node ID 4755ad4b457b5e2ca18e324b1c6dbce8181304f2 # Parent a2c18456c6b7236997e41301082734df49d3b238 updated diff -r a2c18456c6b7 -r 4755ad4b457b coursework/cw01.pdf Binary file coursework/cw01.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b coursework/cw02.pdf Binary file coursework/cw02.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b coursework/cw03.pdf Binary file coursework/cw03.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b coursework/cw04.pdf Binary file coursework/cw04.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b coursework/cw05.pdf Binary file coursework/cw05.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b handouts/ho01.tex --- a/handouts/ho01.tex Fri Sep 25 17:39:02 2015 +0100 +++ b/handouts/ho01.tex Fri Sep 25 20:59:24 2015 +0100 @@ -119,8 +119,8 @@ \ref{crawler3}.\footnote{There is an interesting twist in the web-scraper where \pcode{re*?} is used instead of \pcode{re*}.} Note, however, the regular expression for -http-addresses in web-pages in Figure~\ref{crawler1}, Line 15, is -intended to be +http-addresses in web-pages in Figure~\ref{crawler1}, Line 15, +is intended to be \[ \pcode{"https?://[^"]*"} @@ -128,11 +128,12 @@ \noindent It specifies that web-addresses need to start with a double quote, then comes \texttt{http} followed by an optional -\texttt{s} and so on. Usually we would have to escape the -double quotes in order to make sure we interpret the double -quote as character, not as double quote for a string. But -Scala's trick with triple quotes allows us to omit this kind -of escaping. As a result we can just write: +\texttt{s} and so on until the closing double quote comes. +Usually we would have to escape the double quotes in order to +make sure we interpret the double quote as character, not as +double quote for a string. But Scala's trick with triple +quotes allows us to omit this kind of escaping. As a result we +can just write: \[ \pcode{""""https?://[^"]*"""".r} @@ -228,7 +229,7 @@ \subsection*{Basic Regular Expressions} -The regular expressions shown above, for example for Scala, we +The regular expressions shown above for Scala, we will call \emph{extended regular expressions}. The ones we will mainly study in this module are \emph{basic regular expressions}, which by convention we will just call @@ -521,7 +522,7 @@ specification and that the corresponding implementations do not contain any bugs. We are close, but not yet quite there. -My fascination non withstanding, I am also happy to admit that regular +Notwithstanding my fascination, I am also happy to admit that regular expressions have their shortcomings. There are some well-known ``theoretical'' shortcomings, for example recognising strings of the form $a^{n}b^{n}$. I am not so bothered by them. What I @@ -570,7 +571,7 @@ in ``my'' domain---since these are the ones I am interested in to fix. It uses the regular expression \texttt{my\_urls} in Line~16 to check for my name in the links. The main change is -in Lines~26--29 where there is a test whether URL is in ``my'' +in Lines~24--28 where there is a test whether URL is in ``my'' domain or not.\label{crawler2}} \end{figure} @@ -581,8 +582,8 @@ \caption{A small email harvester---whenever we download a web-page, we also check whether it contains any email addresses. For this we use the regular expression -\texttt{email\_pattern} in Line~16. The main change is in Line -32 where all email addresses that can be found in a page are +\texttt{email\_pattern} in Line~15. The main change is in Line +30 where all email addresses that can be found in a page are printed.\label{crawler3}} \end{figure} diff -r a2c18456c6b7 -r 4755ad4b457b handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b handouts/ho02.tex --- a/handouts/ho02.tex Fri Sep 25 17:39:02 2015 +0100 +++ b/handouts/ho02.tex Fri Sep 25 20:59:24 2015 +0100 @@ -233,7 +233,7 @@ The other function of our matching algorithm calculates a \emph{derivative} of a regular expression. This is a function which will take a regular expression, say $r$, and a -character, say $c$, as argument and return a new regular +character, say $c$, as argument and returns a new regular expression. Be careful that the intuition behind this function is not so easy to grasp on first reading. Essentially this function solves the following problem: if $r$ can match a @@ -271,7 +271,7 @@ straightforward: all strings of the form $c\!::\!s$ are either matched by the regular expression $r_1$ or $r_2$. So we just have to recursively call $der$ with these two regular -expressions and compose the results again with $+$. Yes, makes +expressions and compose the results again with $+$. Makes sense? The $\cdot$-case is more complicated: if $r_1\cdot r_2$ matches a string of the form $c\!::\!s$, then the first part must be matched by $r_1$. Consequently, it makes sense to @@ -332,7 +332,7 @@ Step 4: & the string is exhausted; test & ($nullable(r_4)$)\\ & whether $r_4$ can recognise the\\ & empty string\smallskip\\ -Output: & result of the test $\Rightarrow true \,\text{or}\, \textit{false}$\\ +Output: & result of this test $\Rightarrow true \,\text{or}\, \textit{false}$\\ \end{tabular} \end{center} diff -r a2c18456c6b7 -r 4755ad4b457b handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b handouts/notation.tex --- a/handouts/notation.tex Fri Sep 25 17:39:02 2015 +0100 +++ b/handouts/notation.tex Fri Sep 25 20:59:24 2015 +0100 @@ -19,7 +19,7 @@ are composed of \defn{characters}. While characters are surely a familiar concept, we will make one subtle distinction in this module. If we want to refer to concrete characters, like -\code{a}, \code{b} and so on, we use a typewriter font. +\code{a}, \code{b}, \code{c} and so on, we use a typewriter font. Accordingly if we want to refer to the concrete characters of my email address we shall write @@ -37,7 +37,7 @@ \noindent But often we do not care which particular characters we use. In such cases we use the italic font and write $a$, -$b$ and so on for characters. Therefore if we need a +$b$, $c$ and so on for characters. Therefore if we need a representative string, we might write \begin{equation}\label{abracadabra} @@ -67,7 +67,7 @@ write this string as \[ -[\text{\it h, e, l, l, o}] +[\text{\it h, e, l, l, o}] \;\;\text{or simply}\;\; \textit{hello} \] \noindent The important point is that we can always decompose diff -r a2c18456c6b7 -r 4755ad4b457b handouts/scala-ho.pdf Binary file handouts/scala-ho.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw06.pdf Binary file hws/hw06.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw07.pdf Binary file hws/hw07.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/hw09.pdf Binary file hws/hw09.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b hws/proof.pdf Binary file hws/proof.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b mk --- a/mk Fri Sep 25 17:39:02 2015 +0100 +++ b/mk Fri Sep 25 20:59:24 2015 +0100 @@ -1,7 +1,7 @@ #!/bin/sh set -e -subdirs="slides handouts hws coursework" +subdirs=${1:-"slides handouts hws coursework"} for sd in $subdirs; do cd $sd diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides01.tex --- a/slides/slides01.tex Fri Sep 25 17:39:02 2015 +0100 +++ b/slides/slides01.tex Fri Sep 25 20:59:24 2015 +0100 @@ -296,8 +296,8 @@ \frametitle{Today} \begin{itemize} -\item the ultimate goal is to implement a small compiler -(a really small one for the JVM)\bigskip +\item While the ultimate goal is to implement a small compiler +(a really small one for the JVM)\ldots\bigskip \end{itemize} Let's start with: @@ -305,7 +305,7 @@ \begin{itemize} \item a web-crawler \item an email harvester -\item \textcolor{gray}{a web-scraper} +\item \textcolor{gray}{(a web-scraper)} \end{itemize} \end{frame} @@ -637,7 +637,7 @@ \bl{$\{[], hello, \textit{foobar}, a, abc\}$} \end{center}\bigskip -\item \alert{\bf Concatenation} of strings and sets +\item \alert{\bf Concatenation} of strings and languages \begin{center} \begin{tabular}{rcl} diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides02.tex --- a/slides/slides02.tex Fri Sep 25 17:39:02 2015 +0100 +++ b/slides/slides02.tex Fri Sep 25 20:59:24 2015 +0100 @@ -117,7 +117,7 @@ \bl{$\{[], hello, \textit{foobar}, a, abc\}$} \end{center}\bigskip -\item \alert{\bf Concatenation} of strings and sets +\item \alert{\bf Concatenation} of strings and languages \begin{center} \begin{tabular}{rcl} @@ -152,14 +152,7 @@ \end{tabular} \end{textblock} - -\only<2->{\footnotesize -\begin{textblock}{9}(2,0.5) -\begin{bubble}[9.8cm] -\lstinputlisting{../progs/app01.scala} -\end{bubble} -\end{textblock}} - + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -204,6 +197,19 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c} + When Are Two Regular\\ + Expressions Equivalent?\end{tabular}} +\large +\begin{center} +\bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{\begin{tabular}{c}Concrete Equivalences\end{tabular}} diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides07.pdf Binary file slides/slides07.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides08.pdf Binary file slides/slides08.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r a2c18456c6b7 -r 4755ad4b457b slides/slides10.pdf Binary file slides/slides10.pdf has changed