diff -r 7975e4f0d4de -r e7b110f93697 handouts/ho04.tex --- 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)$ \\