# HG changeset patch # User Christian Urban # Date 1539646930 -3600 # Node ID 6e5e3adc9eb1d67a20786a5fab9d208d350531c8 # Parent 7a437f1f689d6d3fd46b26312078b35b795abf7e updated diff -r 7a437f1f689d -r 6e5e3adc9eb1 coursework/cw02.pdf Binary file coursework/cw02.pdf has changed diff -r 7a437f1f689d -r 6e5e3adc9eb1 coursework/cw02.tex --- a/coursework/cw02.tex Sat Oct 13 13:51:28 2018 +0100 +++ b/coursework/cw02.tex Tue Oct 16 00:42:10 2018 +0100 @@ -172,18 +172,18 @@ after each derivation step and rectify the computed values after each injection. Use this lexer to tokenize the programs in Figure~\ref{fib} and \ref{loop}. Give the tokens of these -programs where whitespaces are filtered out. +programs where whitespaces are filtered out.\bigskip -\begin{figure}[p] -\mbox{\lstinputlisting[language=while]{../progs/fib.while}} +\begin{figure}[h] +\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../progs/fib.while}} \caption{Fibonacci program in the WHILE language.\label{fib}} \end{figure} -\begin{figure}[p] -\mbox{\lstinputlisting[language=while]{../progs/loops.while}} +\begin{figure}[h] +\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../progs/loops.while}} \caption{The three-nested-loops program in the WHILE language. -Usually used for timing measurements.\label{loop}} +(Usually used for timing measurements.)\label{loop}} \end{figure} \end{document} diff -r 7a437f1f689d -r 6e5e3adc9eb1 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 7a437f1f689d -r 6e5e3adc9eb1 handouts/ho03.tex --- a/handouts/ho03.tex Sat Oct 13 13:51:28 2018 +0100 +++ b/handouts/ho03.tex Tue Oct 16 00:42:10 2018 +0100 @@ -1355,15 +1355,15 @@ \end{eqnarray} \noindent Unfortunately we cannot make any more progress with -substituting equations, because both (6) and (7) contain the +substituting equations, because both (8) and (9) contain the variable on the left-hand side also on the right-hand side. Here we need to now use a law that is different from the usual laws about linear equations. It is called \emph{Arden's rule}. It states that if an equation is of the form $q = q\,r + s$ then it can be transformed to $q = s\, r^*$. Since we can -assume $+$ is symmetric, Equation (7) is of that form: $s$ is +assume $+$ is symmetric, Equation (9) is of that form: $s$ is $Q_0\,a\,a$ and $r$ is $a$. That means we can transform -(7) to obtain the two new equations +(9) to obtain the two new equations \begin{eqnarray} Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_2\,b\\ diff -r 7a437f1f689d -r 6e5e3adc9eb1 pics/s1.png Binary file pics/s1.png has changed diff -r 7a437f1f689d -r 6e5e3adc9eb1 pics/s2.png Binary file pics/s2.png has changed diff -r 7a437f1f689d -r 6e5e3adc9eb1 pics/s3.png Binary file pics/s3.png has changed diff -r 7a437f1f689d -r 6e5e3adc9eb1 pics/s4.png Binary file pics/s4.png has changed diff -r 7a437f1f689d -r 6e5e3adc9eb1 pics/stickman.jpg Binary file pics/stickman.jpg has changed diff -r 7a437f1f689d -r 6e5e3adc9eb1 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 7a437f1f689d -r 6e5e3adc9eb1 slides/slides04.tex --- a/slides/slides04.tex Sat Oct 13 13:51:28 2018 +0100 +++ b/slides/slides04.tex Tue Oct 16 00:42:10 2018 +0100 @@ -27,28 +27,164 @@ \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ - Office: & N7.07 (North Wing, Bush House)\\ - Slides: & KEATS (also home work is there)\\ + Office: & N\liningnums{7.07} (North Wing, Bush House)\\ + Slides: & KEATS (also homework is there)\\ \end{tabular} \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Survey: Thanks!} +\small + +\hspace{9mm}{\it``\ldots Thanks a million! Thanks without end!''} + +\begin{textblock}{3}(12,1.7) +\includegraphics[scale=0.1]{../pics/stickman.jpg} +\end{textblock}\pause + +\begin{textblock}{6}(1,4.15) +\begin{bubble}[6.7cm] + \it ``Urban is a very talented lecturer: thorough, concise, + clear, and cares to make sure that we are learning!'' +\end{bubble} +\end{textblock} + +\only<3>{ +\begin{textblock}{6}(0.6,8.5) +\includegraphics[scale=0.2]{../pics/s1.png} +\end{textblock} +\begin{textblock}{6}(8,8.5) +\includegraphics[scale=0.2]{../pics/s2.png} +\end{textblock}} + +\only<4>{ +\begin{textblock}{6}(0.6,8.5) +\includegraphics[scale=0.2]{../pics/s3.png} +\end{textblock} +\begin{textblock}{6}(8,8.5) +\includegraphics[scale=0.2]{../pics/s4.png} +\end{textblock}} + +% \begin{itemize} +% \item {\bf My Voice} ``lecturer speaks in a low voice and +% is hard to hear him'' ``please use mic'' ``please use mic +% \& lecture recording'' +% \item {\bf Pace} ``faster pace'' ``a bit quick for me +% personally'' +% \item {\bf Recording} ``please use recording class'' +% \item {\bf Module Name} ``misleading'' +% \item {\bf Examples} ``more examples'' +% \item {\bf Assessment} ``really appreciate extension of +% first coursework'' +% \end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Regular Expressions} -In programming languages they are often used to recognise:\medskip +\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{itemize} -\item symbols, digits -\item identifiers -\item numbers (non-leading zeros) -\item keywords -\item comments -\end{itemize}\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}} -\mbox{}\hfill\bl{\url{http://www.regexper.com}} +\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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -98,10 +234,12 @@ 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}; +\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; \end{axis} \end{tikzpicture} +The punchline is that existing libraries do depth-first search in NFAs. + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -261,6 +399,7 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -305,7 +444,7 @@ minimum height=18mm, minimum width=20mm, top color=white,bottom color=black!20}] - \node at (3.05, 1.8) {\Large\bf Write A Compiler}; + \node at (3.05, 1.8) {\Large\bf Write a compiler}; \node (0) at (-2.3,0) {}; @@ -335,24 +474,21 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Survey: Thanks!} -\small +\frametitle{Regular Expressions} + +In programming languages they are often used to recognise:\medskip -% \begin{itemize} -% \item {\bf My Voice} ``lecturer speaks in a low voice and -% is hard to hear him'' ``please use mic'' ``please use mic -% \& lecture recording'' -% \item {\bf Pace} ``faster pace'' ``a bit quick for me -% personally'' -% \item {\bf Recording} ``please use recording class'' -% \item {\bf Module Name} ``misleading'' -% \item {\bf Examples} ``more examples'' -% \item {\bf Assessment} ``really appreciate extension of -% first coursework'' -% \end{itemize} - +\begin{itemize} +\item symbols, digits +\item identifiers +\item numbers (non-leading zeros) +\item keywords +\item comments +\end{itemize}\bigskip + +\mbox{}\hfill\bl{\url{http://www.regexper.com}} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -364,13 +500,13 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{?? Test Case} - -\mbox{\lstinputlisting[language=While]{../progs/collatz.while}} - -\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{?? Test Case} +% +%\mbox{\lstinputlisting[language=While]{../progs/collatz.while}} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -444,7 +580,7 @@ There is one small problem with the tokenizer. How should we -tokenize: +tokenize\ldots? \begin{center} \large\code{"x-3"} @@ -478,7 +614,7 @@ letters followed by ``letters + numbers + \_''$^*$ \[ -\bl{iffoo} +\bl{if}\qquad\bl{iffoo} \] \end{frame} @@ -576,8 +712,8 @@ & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ & \bl{$\mid$} & \bl{$Left(v)$} \\ & \bl{$\mid$} & \bl{$Right(v)$} \\ - & \bl{$\mid$} & \bl{$[]$} \\ - & \bl{$\mid$} & \bl{$[v_1,\ldots\,v_n]$} \\ + & \bl{$\mid$} & \bl{$Stars\,[]$} \\ + & \bl{$\mid$} & \bl{$Stars\,[v_1,\ldots\,v_n]$} \\ \end{tabular} \end{column} \end{columns} @@ -610,7 +746,7 @@ & & \bl{then $Left(mkeps(r_1))$}\\ & & \bl{else $Right(mkeps(r_2))$}\\ \bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ - \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$[]$} \\ + \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$Stars\,[]$} \\ \end{tabular} \end{center} @@ -624,14 +760,14 @@ Injecting (``Adding'') a character to a value\\[-12mm]\mbox{} \begin{center} -\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} - \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\ - \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ - \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ - \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ - \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ - \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ - \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\ +\begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} + \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\ + \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ + \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ + \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ + \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ + \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ + \bl{$inj\,(r^*)\,c\,(Seq(v,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\ \end{tabular} \end{center}\bigskip @@ -909,7 +1045,7 @@ \begin{itemize} \item If we simplify after the derivative, then we are building the -value for the simplified regular expression, but \emph{not} for the original +value for the simplified regular expression, but \alert{\textbf{not}} for the original regular expression. \end{itemize} @@ -956,12 +1092,13 @@ \end{center} and answer how this regular expression matches the empty string + with the value \begin{center} \bl{$Right(Right(Empty))$} \end{center}\bigskip - But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$}. + But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$} (see \textit{mkeps}). \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -1199,7 +1336,7 @@ \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([v_1,\ldots ,v_n])$} & \bl{$\dn$} & + \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} @@ -1301,8 +1438,8 @@ \begin{frame}[c] \begin{center} \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -\bl{$zeroable(\varnothing)$} & \bl{$\dn$} & \bl{$true$}\\ -\bl{$zeroable(\epsilon)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ +\bl{$zeroable(\ZERO)$} & \bl{$\dn$} & \bl{$true$}\\ +\bl{$zeroable(\ONE)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ \bl{$zeroable(c)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ \bl{$zeroable(r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\ \bl{$zeroable(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\