updated
authorChristian Urban <christian dot urban at kcl dot ac dot uk>
Sat, 06 Dec 2014 18:50:58 +0000
changeset 319 e7b110f93697
parent 318 7975e4f0d4de
child 320 0c43ef11e086
updated
handouts/ho04.pdf
handouts/ho04.tex
Binary file handouts/ho04.pdf has changed
--- a/handouts/ho04.tex	Fri Dec 05 17:13:33 2014 +0000
+++ b/handouts/ho04.tex	Sat Dec 06 18:50:58 2014 +0000
@@ -13,33 +13,31 @@
 expression or not. Often a more interesting question is to
 find out \emph{how} a regular expression matched a string?
 Answering this question will also help us with the problem we
-are after, namely tokenising an input string. The algorithm we
-will be looking at for this was designed by Sulzmann \& Lu in
-a rather recent paper. A link to it is provided on KEATS, in
-case you are interested.\footnote{In my humble opinion this is
-an interesting instance of the research literature: it
-contains a very neat idea, but its presentation is rather
-sloppy. In earlier versions of their paper, students and I
-found several rather annoying typos in their examples and
-definitions.}
+are after, namely tokenising an input string. 
 
-In order to give an answer for how a regular expression
-matched a string, Sulzmann and Lu introduce \emph{values}. A
-value will be the output of the algorithm whenever the regular
-expression matches the string. If not, an error will be
-raised. Since the first phase of the algorithm by Sulzmann \&
-Lu is identical to the derivative based matcher from the first
-coursework, the function $nullable$ will be used to decide
-whether as string is matched by a regular expression. If
-$nullable$ says yes, then values are constructed that reflect
-how the regular expression matched the string. The definitions
-for regular expressions $r$ and values $v$ is shown next to
-each other below:
+The algorithm we will be looking at was designed by Sulzmann \& Lu in
+a rather recent paper. A link to it is provided on KEATS, in case you
+are interested.\footnote{In my humble opinion this is an interesting
+  instance of the research literature: it contains a very neat idea,
+  but its presentation is rather sloppy. In earlier versions of their
+  paper, students and I found several rather annoying typos in their
+  examples and definitions.}  In order to give an answer for how a
+regular expression matched a string, Sulzmann and Lu introduce
+\emph{values}. A value will be the output of the algorithm whenever
+the regular expression matches the string. If the string does not
+match the string, an error will be raised. Since the first phase of
+the algorithm by Sulzmann \& Lu is identical to the derivative based
+matcher from the first coursework, the function $nullable$ will be
+used to decide whether as string is matched by a regular
+expression. If $nullable$ says yes, then values are constructed that
+reflect how the regular expression matched the string. The definitions
+for regular expressions $r$ and values $v$ is shown next to each other
+below:
 
 \begin{center}
 \begin{tabular}{cc}
 \begin{tabular}{@{}rrl@{}}
-\multicolumn{3}{c}{regular expressions}\\
+\multicolumn{3}{c}{regular expressions}\medskip\\
   $r$ & $::=$  & $\varnothing$\\
       & $\mid$ & $\epsilon$   \\
       & $\mid$ & $c$          \\
@@ -50,7 +48,7 @@
 \end{tabular}
 &
 \begin{tabular}{@{\hspace{0mm}}rrl@{}}
-\multicolumn{3}{c}{values}\\
+\multicolumn{3}{c}{values}\medskip\\
    $v$ & $::=$  & \\
       &        & $Empty$   \\
       & $\mid$ & $Char(c)$          \\