# HG changeset patch # User Christian Urban # Date 1474702264 -3600 # Node ID a47c4227a0c6715cff85d0b494b137d3066161ee # Parent 546f2090ce1201a40d6424e63b7cadb2f4aac6a4 updated diff -r 546f2090ce12 -r a47c4227a0c6 coursework/cw01.pdf Binary file coursework/cw01.pdf has changed diff -r 546f2090ce12 -r a47c4227a0c6 coursework/cw02.pdf Binary file coursework/cw02.pdf has changed diff -r 546f2090ce12 -r a47c4227a0c6 coursework/cw02.tex --- a/coursework/cw02.tex Fri Sep 23 15:22:33 2016 +0100 +++ b/coursework/cw02.tex Sat Sep 24 08:31:04 2016 +0100 @@ -6,7 +6,7 @@ \section*{Coursework 2 (Strand 1)} -\noindent This coursework is worth 4\% and is due on 3 +\noindent This coursework is worth 5\% and is due on 3 November at 16:00. You are asked to implement the Sulzmann \& Lu lexer for the WHILE language. You can do the implementation in any programming language you like, but you diff -r 546f2090ce12 -r a47c4227a0c6 coursework/cw03.pdf Binary file coursework/cw03.pdf has changed diff -r 546f2090ce12 -r a47c4227a0c6 coursework/cw04.pdf Binary file coursework/cw04.pdf has changed diff -r 546f2090ce12 -r a47c4227a0c6 coursework/cw04.tex --- a/coursework/cw04.tex Fri Sep 23 15:22:33 2016 +0100 +++ b/coursework/cw04.tex Sat Sep 24 08:31:04 2016 +0100 @@ -9,7 +9,7 @@ \section*{Coursework 4 (Strand 1)} -\noindent This coursework is worth 5\% and is due on 13 +\noindent This coursework is worth 6\% and is due on 13 December at 16:00. You are asked to implement a compiler for the WHILE language that targets the assembler language provided by Jasmin or Krakatau (both have very similar diff -r 546f2090ce12 -r a47c4227a0c6 coursework/cw05.pdf Binary file coursework/cw05.pdf has changed diff -r 546f2090ce12 -r a47c4227a0c6 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 546f2090ce12 -r a47c4227a0c6 progs/app1.scala --- a/progs/app1.scala Fri Sep 23 15:22:33 2016 +0100 +++ b/progs/app1.scala Sat Sep 24 08:31:04 2016 +0100 @@ -1,4 +1,4 @@ def get_page(url: String) : String = { - Try(Source.fromURL(url).take(10000).mkString) getOrElse - { println(s" Problem with: $url"); ""} + Try(Source.fromURL(url).take(10000).mkString). + getOrElse { println(s" Problem with: $url"); ""} } diff -r 546f2090ce12 -r a47c4227a0c6 progs/crawler1.scala --- a/progs/crawler1.scala Fri Sep 23 15:22:33 2016 +0100 +++ b/progs/crawler1.scala Sat Sep 24 08:31:04 2016 +0100 @@ -7,8 +7,8 @@ // gets the first 10K of a web-page def get_page(url: String) : String = { - Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString) getOrElse - { println(s" Problem with: $url"); ""} + Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString). + getOrElse { println(s" Problem with: $url"); ""} } // regex for URLs @@ -32,9 +32,8 @@ } // some starting URLs for the crawler -//val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc""" +val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc""" //val startURL = """http://www.inf.kcl.ac.uk/staff/mcburney""" -val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc/bsc-projects-16.html""" crawl(startURL, 2) diff -r 546f2090ce12 -r a47c4227a0c6 progs/crawler2.scala --- a/progs/crawler2.scala Fri Sep 23 15:22:33 2016 +0100 +++ b/progs/crawler2.scala Sat Sep 24 08:31:04 2016 +0100 @@ -7,8 +7,8 @@ // gets the first 10K of a web-page def get_page(url: String) : String = { - Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString) getOrElse - { println(s" Problem with: $url"); ""} + Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString). + getOrElse { println(s" Problem with: $url"); ""} } // regexes for URLs and "my" domain diff -r 546f2090ce12 -r a47c4227a0c6 progs/crawler3.scala --- a/progs/crawler3.scala Fri Sep 23 15:22:33 2016 +0100 +++ b/progs/crawler3.scala Sat Sep 24 08:31:04 2016 +0100 @@ -6,8 +6,8 @@ import scala.util._ def get_page(url: String) : String = { - Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString) getOrElse - { println(s" Problem with: $url"); ""} + Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString). + getOrElse { println(s" Problem with: $url"); ""} } // regexes for URLs, for "my" domain and for email addresses diff -r 546f2090ce12 -r a47c4227a0c6 slides.sty --- a/slides.sty Fri Sep 23 15:22:33 2016 +0100 +++ b/slides.sty Sat Sep 24 08:31:04 2016 +0100 @@ -16,6 +16,8 @@ \newcommand{\tttext}[1]{{\consolas{#1}}} +\newcommand{\ZERO}{\mbox{\bf 0}} +\newcommand{\ONE}{\mbox{\bf 1}} \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% \newcommand{\slidecaption}{} diff -r 546f2090ce12 -r a47c4227a0c6 slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 546f2090ce12 -r a47c4227a0c6 slides/slides01.tex --- a/slides/slides01.tex Fri Sep 23 15:22:33 2016 +0100 +++ b/slides/slides01.tex Sat Sep 24 08:31:04 2016 +0100 @@ -18,7 +18,7 @@ \newcommand{\bl}[1]{\textcolor{blue}{#1}} % beamer stuff -\renewcommand{\slidecaption}{AFL 01, King's College London} +\renewcommand{\slidecaption}{CFL 01, King's College London} \begin{document} @@ -28,7 +28,7 @@ \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] - \LARGE Automata and \\[-2mm] + \LARGE Compilers and \\[-1mm] \LARGE Formal Languages (1)\\[-3mm] \end{tabular}} @@ -179,66 +179,98 @@ \begin{frame}[c] \frametitle{Why Bother?} -\begin{columns}[b] +\begin{columns}[t] \begin{column}{.5\textwidth} -Ruby, Python\\ and Others\bigskip\\ -\begin{tikzpicture}[y=.08cm, x=.10cm] - %axis - \draw (0,0) -- coordinate (x axis mid) (30,0); - \draw (0,0) -- coordinate (y axis mid) (0,30); - %ticks - \foreach \x in {0,5,...,30} - \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\footnotesize\x}; - \foreach \y in {0,5,...,30} - \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\footnotesize\y}; - %labels - \node[below=0.6cm] at (x axis mid) {\footnotesize number of \texttt{a}s}; - \node[rotate=90,left=1cm] at (y axis mid) {\footnotesize time in secs}; - %plots - \draw[color=blue] plot[mark=*] - file {re-python.data}; - \draw[color=brown] plot[mark=triangle*] - file {re-ruby.data}; - %legend - \begin{scope}[shift={(4,20)}] - \draw[color=blue] (0,0) -- - plot[mark=*] (0.25,0) -- (0.5,0) - node[right]{\small Python}; - \draw[yshift=-\baselineskip, color=brown] (0,0) -- - plot[mark=triangle*] (0.25,0) -- (0.5,0) - node[right]{\small Ruby}; - \end{scope} +Ruby, Python, Java\medskip\\ +\begin{tikzpicture}\footnotesize +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=33, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=5.5cm, + height=4cm, + legend entries={Python,Ruby}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=*] table {re-python.data}; +\addplot[brown,mark=triangle*] table {re-ruby.data}; +\end{axis} +\end{tikzpicture} +\begin{tikzpicture}\footnotesize +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=33, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=5.5cm, + height=4cm, + legend entries={Java}, + legend pos=north west, + legend cell align=left] +\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; +\end{axis} +\end{tikzpicture} + +\end{column} +\begin{column}{.5\textwidth} +Us (after next lecture)\medskip\\ +\begin{tikzpicture}\footnotesize +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.07,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,4000,...,12000}, + xmax=13000, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=5.5cm, + height=4cm] +\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; +\addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; +\end{axis} +\end{tikzpicture} +\begin{tikzpicture}\footnotesize +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.07,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=5.5cm, + height=4cm] +\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; +\end{axis} \end{tikzpicture} \end{column} -\begin{column}{.5\textwidth} -Us (after next lecture)\\\mbox{}\bigskip\\ -\begin{tikzpicture}[y=.08cm, x=.0003cm] - %axis - \draw (0,0) -- coordinate (x axis mid) (12000,0); - \draw (0,0) -- coordinate (y axis mid) (0,30); - %ticks - \foreach \x in {0,4000,...,12000} - \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\footnotesize\x}; - \foreach \y in {0,5,...,30} - \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\footnotesize\y}; - %labels - \node[below=0.6cm] at (x axis mid) {\footnotesize number of \texttt{a}s}; - \node[rotate=90, left=1cm] at (y axis mid) {\footnotesize time in secs}; +\end{columns}\bigskip - %plots - \draw[color=green] plot[mark=square*, mark options={fill=white} ] - file {re2b.data}; - \draw[color=black] plot[mark=square*, mark options={fill=white} ] - file {re3.data}; -\end{tikzpicture} -\end{column} -\end{columns}\bigskip\medskip - -\hspace{2cm}matching \texttt{[a?]\{n\}[a]\{n\}} against -$\underbrace{\texttt{a}...\texttt{a}}_n$ +\small\centering +matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{[a*]*b} +against $\underbrace{\texttt{a}...\texttt{a}}_n$ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Lectures 1 - 5} @@ -402,7 +434,7 @@ \bigskip\medskip\pause -\small A slightly more complicated version for handling errors properly: +\small A slightly more complicated version for handling errors: \smallskip \footnotesize @@ -564,8 +596,8 @@ \begin{textblock}{6}(2,7.5) \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} - \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ - & \bl{$\mid$} & \bl{$\epsilon$} & empty string / \pcode{""} / $[]$\\ + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & null\\ + & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ & \bl{$\mid$} & \bl{$c$} & character\\ & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ @@ -662,12 +694,12 @@ \begin{textblock}{15}(1,4) \begin{tabular}{rcl} - \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\ - \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \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{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ - \bl{$L(r^*)$} & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{n \ge 0} L(r)^n$}}\\ + \bl{$L(r^*)$} & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\ \end{tabular}\bigskip \onslide<2->{ @@ -696,7 +728,7 @@ \ldots and the point of the next lecture is to decide this problem as fast as possible (unlike Python, -Ruby) +Ruby, Java) \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -707,7 +739,7 @@ \frametitle{Written Exam} \begin{itemize} -\item Accounts for 75\%.\bigskip +\item Accounts for 80\%.\bigskip \item You will understand the question ``\textit{Is this relevant for the exam?}'' is very demotivating for the lecturer!\bigskip\\ @@ -727,19 +759,19 @@ \frametitle{Coursework} \begin{itemize} -\item Accounts for 25\%. Two strands. Choose \alert{\bf one}!\bigskip +\item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip \end{itemize} \begin{columns}[t] \begin{column}{.5\textwidth} \underline{\bf Strand 1}\medskip \begin{itemize} -\item four programming subtasks: +\item four programming tasks: \begin{itemize} -\item matcher (5\%, 16.10.) -\item lexer (5\%, 06.11.) -\item parser (5\%, 27.11.) -\item compiler (10\%, 11.12.) +\item matcher (4\%, 20.10.) +\item lexer (5\%, 03.11.) +\item parser (5\%, 24.11.) +\item compiler (6\%, 13.12.) \end{itemize} \end{itemize} \end{column} @@ -749,7 +781,7 @@ \underline{\bf Strand 2}\smallskip\begin{itemize} \item one task: prove the correctness of a regular expression matcher in the Isabelle theorem prover -\item 25\%, submission 11.12. +\item 20\%, submission 13.12. \end{itemize} \end{column} \end{columns}\medskip