handouts/ho04.tex
author Christian Urban <christian dot urban at kcl dot ac dot uk>
Wed, 06 Apr 2016 12:18:54 +0100
changeset 400 e4afe3f46c29
parent 394 2f9fe225ecc8
child 417 e74c696821a2
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
251
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     1
\documentclass{article}
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     2
\usepackage{../style}
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     3
\usepackage{../langs}
282
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
     4
\usepackage{../graphics}
251
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     5
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     6
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     7
\begin{document}
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
     8
\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016}
251
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     9
282
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
    10
\section*{Handout 4 (Sulzmann \& Lu Algorithm)}
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
    11
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
    12
So far our algorithm based on derivatives was only able to say
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
    13
yes or no depending on whether a string was matched by regular
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
    14
expression or not. Often a more interesting question is to
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
    15
find out \emph{how} a regular expression matched a string?
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    16
Answering this question will also help us with the problem we
319
e7b110f93697 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 296
diff changeset
    17
are after, namely tokenising an input string. 
282
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
    18
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    19
The algorithm we will be looking at was designed by Sulzmann
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    20
\& Lu in a rather recent paper (from 2014). A link to it is
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    21
provided on KEATS, in case you are interested.\footnote{In my
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    22
humble opinion this is an interesting instance of the research
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    23
literature: it contains a very neat idea, but its presentation
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    24
is rather sloppy. In earlier versions of their paper, a King's
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    25
student and I found several rather annoying typos in their
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    26
examples and definitions.} In order to give an answer for
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    27
\emph{how} a regular expression matches a string, Sulzmann and
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    28
Lu introduce \emph{values}. A value will be the output of the
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    29
algorithm whenever the regular expression matches the string.
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    30
If the string does not match the string, an error will be
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    31
raised. Since the first phase of the algorithm by Sulzmann \&
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    32
Lu is identical to the derivative based matcher from the first
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
    33
coursework, the function \textit{nullable} will be used to
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
    34
decide whether as string is matched by a regular expression.
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
    35
If \textit{nullable} says yes, then values are constructed
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
    36
that reflect how the regular expression matched the string. 
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    37
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    38
The definitions for values is given below. They are shown 
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    39
together with the regular expressions $r$ to which
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    40
they correspond:
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    41
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    42
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    43
\begin{tabular}{cc}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    44
\begin{tabular}{@{}rrl@{}}
319
e7b110f93697 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 296
diff changeset
    45
\multicolumn{3}{c}{regular expressions}\medskip\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    46
  $r$ & $::=$  & $\ZERO$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    47
      & $\mid$ & $\ONE$   \\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    48
      & $\mid$ & $c$          \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    49
      & $\mid$ & $r_1 \cdot r_2$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    50
      & $\mid$ & $r_1 + r_2$   \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    51
  \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    52
      & $\mid$ & $r^*$         \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    53
\end{tabular}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    54
&
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    55
\begin{tabular}{@{\hspace{0mm}}rrl@{}}
319
e7b110f93697 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 296
diff changeset
    56
\multicolumn{3}{c}{values}\medskip\\
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    57
   $v$ & $::=$  & \\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    58
      &        & $Empty$   \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    59
      & $\mid$ & $Char(c)$          \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    60
      & $\mid$ & $Seq(v_1,v_2)$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    61
      & $\mid$ & $\Left(v)$   \\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    62
      & $\mid$ & $Right(v)$  \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    63
      & $\mid$ & $[v_1,\ldots\,v_n]$ \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    64
\end{tabular}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    65
\end{tabular}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    66
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    67
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    68
\noindent The reason is that there is a very strong
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    69
correspondence between them. There is no value for the
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    70
$\ZERO$ regular expression, since it does not match any
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    71
string. Otherwise there is exactly one value corresponding to
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    72
each regular expression with the exception of $r_1 + r_2$
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    73
where there are two values, namely $\Left(v)$ and $Right(v)$
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    74
corresponding to the two alternatives. Note that $r^*$ is
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    75
associated with a list of values, one for each copy of $r$
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    76
that was needed to match the string. This means we might also
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    77
return the empty list $[]$, if no copy was needed in case
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    78
of $r^*$. For sequence, there is exactly one value, composed 
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    79
of two component values ($v_1$ and $v_2$).
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
    80
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    81
My definition of regular expressions and values in Scala is
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    82
shown below. I have in my implementation the convention that
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    83
regular expressions are written entirely with upper-case
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    84
letters, while values just start with a single upper-case
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    85
character and the rest are lower-case letters.
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    86
 
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
    87
{\small\lstinputlisting[language=Scala,numbers=none]
352
1e1b0fe66107 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 350
diff changeset
    88
{../progs/app01.scala}}
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    89
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
    90
 
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    91
{\small\lstinputlisting[language=Scala,numbers=none]
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    92
{../progs/app02.scala}}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    93
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    94
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
    95
Graphically the algorithm by Sulzmann \& Lu can be illustrated
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    96
by the picture in Figure~\ref{Sulz} where the path from the
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    97
left to the right involving $der/nullable$ is the first phase
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    98
of the algorithm and $mkeps/inj$, the path from right to left,
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
    99
the second phase. This picture shows the steps required when a
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   100
regular expression, say $r_1$, matches the string $abc$. We
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   101
first build the three derivatives (according to $a$, $b$ and
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   102
$c$). We then use $nullable$ to find out whether the resulting
296
796b9b81ac8d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 288
diff changeset
   103
regular expression can match the empty string. If yes, we call
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   104
the function $mkeps$.
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   105
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   106
\begin{figure}[t]
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   107
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   108
\begin{tikzpicture}[scale=2,node distance=1.2cm,
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   109
                    every node/.style={minimum size=7mm}]
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   110
\node (r1)  {$r_1$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   111
\node (r2) [right=of r1]{$r_2$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   112
\draw[->,line width=1mm](r1)--(r2) node[above,midway] {$der\,a$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   113
\node (r3) [right=of r2]{$r_3$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   114
\draw[->,line width=1mm](r2)--(r3) node[above,midway] {$der\,b$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   115
\node (r4) [right=of r3]{$r_4$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   116
\draw[->,line width=1mm](r3)--(r4) node[above,midway] {$der\,c$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   117
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{$nullable$}};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   118
\node (v4) [below=of r4]{$v_4$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   119
\draw[->,line width=1mm](r4) -- (v4);
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   120
\node (v3) [left=of v4] {$v_3$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   121
\draw[->,line width=1mm](v4)--(v3) node[below,midway] {$inj\,c$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   122
\node (v2) [left=of v3]{$v_2$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   123
\draw[->,line width=1mm](v3)--(v2) node[below,midway] {$inj\,b$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   124
\node (v1) [left=of v2] {$v_1$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   125
\draw[->,line width=1mm](v2)--(v1) node[below,midway] {$inj\,a$};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   126
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{$mkeps$}};
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   127
\end{tikzpicture}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   128
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   129
\caption{The two phases of the algorithm by Sulzmann \& Lu.
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   130
\label{Sulz}}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   131
\end{figure}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   132
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   133
The $mkeps$ function calculates a value for how a regular
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   134
expression has matched the empty string. Its definition
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   135
is as follows:
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   136
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   137
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   138
\begin{tabular}{lcl}
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   139
  $mkeps(\ONE)$       & $\dn$ & $Empty$\\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   140
  $mkeps(r_1 + r_2)$      & $\dn$ & if $nullable(r_1)$  \\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   141
                          &       & then $\Left(mkeps(r_1))$\\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   142
                          &       & else $Right(mkeps(r_2))$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   143
  $mkeps(r_1 \cdot r_2)$  & $\dn$ & $Seq(mkeps(r_1),mkeps(r_2))$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   144
  $mkeps(r^*)$            & $\dn$ & $[]$  \\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   145
\end{tabular}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   146
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   147
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   148
\noindent There are no cases for $\ZERO$ and $c$, since
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   149
these regular expression cannot match the empty string. Note
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   150
also that in case of alternatives we give preference to the
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   151
regular expression on the left-hand side. This will become
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   152
important later on.
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   153
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   154
The second phase of the algorithm is organised so that it will
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   155
calculate a value for how the derivative regular expression
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   156
has matched a string. For this we need a function that
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   157
reverses this ``chopping off'' for values which we did in the
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   158
first phase for derivatives. The corresponding function is
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   159
called $inj$ for injection. This function takes three
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   160
arguments: the first one is a regular expression for which we
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   161
want to calculate the value, the second is the character we
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   162
want to inject and the third argument is the value where we
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   163
will inject the character into. The result of this function is a
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   164
new value. The definition of $inj$ is as follows: 
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   165
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   166
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   167
\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   168
  $inj\,(c)\,c\,Empty$            & $\dn$ & $Char\,c$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   169
  $inj\,(r_1 + r_2)\,c\,\Left(v)$ & $\dn$ & $\Left(inj\,r_1\,c\,v)$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   170
  $inj\,(r_1 + r_2)\,c\,Right(v)$ & $\dn$ & $Right(inj\,r_2\,c\,v)$\\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   171
  $inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$ & $\dn$  & $Seq(inj\,r_1\,c\,v_1,v_2)$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   172
  $inj\,(r_1 \cdot r_2)\,c\,\Left(Seq(v_1,v_2))$ & $\dn$  & $Seq(inj\,r_1\,c\,v_1,v_2)$\\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   173
  $inj\,(r_1 \cdot r_2)\,c\,Right(v)$ & $\dn$  & $Seq(mkeps(r_1),inj\,r_2\,c\,v)$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   174
  $inj\,(r^*)\,c\,Seq(v,vs)$         & $\dn$  & $inj\,r\,c\,v\,::\,vs$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   175
\end{tabular}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   176
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   177
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   178
\noindent This definition is by recursion on the regular
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   179
expression and by analysing the shape of the values. Therefore
296
796b9b81ac8d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 288
diff changeset
   180
there are, for example, three cases for sequence regular
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   181
expressions (for all possible shapes of the value). The last
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   182
clause for the star regular expression returns a list where
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   183
the first element is $inj\,r\,c\,v$ and the other elements are
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   184
$vs$. That means $\_\,::\,\_$ should be read as list cons.
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   185
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   186
To understand what is going on, it might be best to do some
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   187
example calculations and compare them with Figure~\ref{Sulz}.
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   188
For this note that we have not yet dealt with the need of
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   189
simplifying regular expressions (this will be a topic on its
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   190
own later). Suppose the regular expression is $a \cdot (b
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   191
\cdot c)$ and the input string is $abc$. The derivatives from
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   192
the first phase are as follows:
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   193
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   194
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   195
\begin{tabular}{ll}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   196
$r_1$: & $a \cdot (b \cdot c)$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   197
$r_2$: & $\ONE \cdot (b \cdot c)$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   198
$r_3$: & $(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   199
$r_4$: & $(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$\\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   200
\end{tabular}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   201
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   202
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   203
\noindent According to the simple algorithm, we would test
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   204
whether $r_4$ is nullable, which in this case it indeed is.
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   205
This means we can use the function $mkeps$ to calculate a
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   206
value for how $r_4$ was able to match the empty string.
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   207
Remember that this function gives preference for alternatives
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   208
on the left-hand side. However there is only $\ONE$ on the
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   209
very right-hand side of $r_4$ that matches the empty string.
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   210
Therefore $mkeps$ returns the value
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   211
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   212
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   213
$v_4:\;Right(Right(Empty))$
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   214
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   215
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   216
\noindent If there had been a $\ONE$ on the left, then
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   217
$mkeps$ would have returned something of the form
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   218
$\Left(\ldots)$. The point is that from this value we can
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   219
directly read off which part of $r_4$ matched the empty
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   220
string: take the right-alternative first, and then the
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   221
right-alternative again. Remember $r_4$ is of the form
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   222
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   223
\begin{center}
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   224
$r_4$:\;$(\ZERO \cdot (b \cdot c)) + 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   225
         ((\ZERO \cdot c) + \underline{\ONE})$\\
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   226
\end{center}
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   227
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   228
\noindent the value tells us that the underlined $\ONE$
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   229
is responsible for matching the empty string.
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   230
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   231
Next we have to ``inject'' the last character, that is $c$ in
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   232
the running example, into this value $v_4$ in order to
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   233
calculate how $r_3$ could have matched the string $c$.
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   234
According to the definition of $inj$ we obtain
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   235
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   236
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   237
$v_3:\;Right(Seq(Empty, Char(c)))$
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   238
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   239
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   240
\noindent This is the correct result, because $r_3$ needs
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   241
to use the right-hand alternative, and then $\ONE$ needs
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   242
to match the empty string and $c$ needs to match $c$.
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   243
Next we need to inject back the letter $b$ into $v_3$. This
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   244
gives
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   245
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   246
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   247
$v_2:\;Seq(Empty, Seq(Char(b), Char(c)))$
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   248
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   249
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   250
\noindent which is again the correct result for how $r_2$
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   251
matched the string $bc$. Finally we need to inject back the
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   252
letter $a$ into $v_2$ giving the final result
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   253
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   254
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   255
$v_1:\;Seq(Char(a), Seq(Char(b), Char(c)))$
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   256
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   257
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   258
\noindent This now corresponds to how the regular
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   259
expression $a \cdot (b \cdot c)$ matched the string $abc$.
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   260
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   261
There are a few auxiliary functions that are of interest
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   262
when analysing this algorithm. One is called \emph{flatten},
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   263
written $|\_|$, which extracts the string ``underlying'' a 
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   264
value. It is defined recursively as
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   265
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   266
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   267
\begin{tabular}{lcl}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   268
  $|Empty|$     & $\dn$ & $[]$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   269
  $|Char(c)|$   & $\dn$ & $[c]$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   270
  $|\Left(v)|$   & $\dn$ & $|v|$\\
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   271
  $|Right(v)|$  & $\dn$ & $|v|$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   272
  $|Seq(v_1,v_2)|$& $\dn$ & $|v_1| \,@\, |v_2|$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   273
  $|[v_1,\ldots ,v_n]|$ & $\dn$ & $|v_1| \,@\ldots @\, |v_n|$\\
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   274
\end{tabular}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   275
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   276
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   277
\noindent Using flatten we can see what are the strings behind 
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   278
the values calculated by $mkeps$ and $inj$. In our running 
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   279
example:
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   280
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   281
\begin{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   282
\begin{tabular}{ll}
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   283
$|v_4|$: & $[]$\\
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   284
$|v_3|$: & $c$\\
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   285
$|v_2|$: & $bc$\\
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   286
$|v_1|$: & $abc$
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   287
\end{tabular}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   288
\end{center}
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   289
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   290
\noindent This indicates that $inj$ indeed is injecting, or
350
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   291
adding, back a character into the value. If we continue until
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   292
all characters are injected back, we have a value that can 
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   293
indeed say how the string $abc$ was matched.
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   294
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   295
There is a problem, however, with the described algorithm
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   296
so far: it is very slow. We need to include the simplification 
c4e7caa06c74 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 326
diff changeset
   297
from Lecture 2. This is what we shall do next.
282
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
   298
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
   299
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   300
\subsubsection*{Simplification}
282
3e3b927a85cf added ho04
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 251
diff changeset
   301
283
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   302
Generally the matching algorithms based on derivatives do
c14e5ebf0c3b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 282
diff changeset
   303
poorly unless the regular expressions are simplified after
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   304
each derivative step. But this is a bit more involved in the
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   305
algorithm of Sulzmann \& Lu. So what follows might require you
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   306
to read several times before it makes sense and also might
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   307
require that you do some example calculations yourself. As a
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   308
first example consider the last derivation step in our earlier
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   309
example:
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   310
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   311
\begin{center}
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   312
$r_4 = der\,c\,r_3 = 
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   313
(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   314
\end{center}
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   315
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   316
\noindent Simplifying this regular expression would just give
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   317
us $\ONE$. Running $mkeps$ with this regular expression as
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   318
input, however, would then provide us with $Empty$ instead of
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   319
$Right(Right(Empty))$ that was obtained without the
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   320
simplification. The problem is we need to recreate this more
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   321
complicated value, rather than just return $Empty$.
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   322
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   323
This will require what I call \emph{rectification functions}.
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   324
They need to be calculated whenever a regular expression gets
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   325
simplified. Rectification functions take a value as argument
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   326
and return a (rectified) value. Let us first take a look again
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   327
at our simplification rules:
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   328
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   329
\begin{center}
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   330
\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   331
$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   332
$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   333
$r \cdot \ONE$ & $\mapsto$ & $r$\\ 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   334
$\ONE \cdot r$ & $\mapsto$ & $r$\\ 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   335
$r + \ZERO$ & $\mapsto$ & $r$\\ 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   336
$\ZERO + r$ & $\mapsto$ & $r$\\ 
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   337
$r + r$ & $\mapsto$ & $r$\\ 
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   338
\end{tabular}
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   339
\end{center}
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   340
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   341
\noindent Applying them to $r_4$ will require several nested
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   342
simplifications in order end up with just $\ONE$. However,
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   343
it is possible to apply them in a depth-first, or inside-out,
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   344
manner in order to calculate this simplified regular
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   345
expression.
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   346
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   347
The rectification we can implement by letting simp return not
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   348
just a (simplified) regular expression, but also a
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   349
rectification function. Let us consider the alternative case,
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   350
$r_1 + r_2$, first. By going depth-first, we first simplify
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   351
the component regular expressions $r_1$ and $r_2.$ This will
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   352
return simplified versions, say $r_{1s}$ and $r_{2s}$, of the
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   353
component regular expressions (if they can be simplified) but
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   354
also two rectification functions $f_{1s}$ and $f_{2s}$. We
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   355
need to assemble them in order to obtain a rectified value for
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   356
$r_1 + r_2$. In case $r_{1s}$ simplified to $\ZERO$, we
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   357
continue the derivative calculation with $r_{2s}$. The
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   358
Sulzmann \& Lu algorithm would return a corresponding value,
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   359
say $v_{2s}$. But now this value needs to be ``rectified'' to
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   360
the value 
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   361
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   362
\begin{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   363
$Right(v_{2s})$
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   364
\end{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   365
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   366
\noindent The reason is that we look for the value that tells
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   367
us how $r_1 + r_2$ could have matched the string, not just
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   368
$r_2$ or $r_{2s}$. Unfortunately, this is still not the right
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   369
value in general because there might be some simplifications
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   370
that happened inside $r_2$ and for which the simplification
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   371
function retuned also a rectification function $f_{2s}$. So in
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   372
fact we need to apply this one too which gives
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   373
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   374
\begin{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   375
$Right(f_{2s}(v_{2s}))$
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   376
\end{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   377
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   378
\noindent This is now the correct, or rectified, value. Since
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   379
the simplification will be done in the first phase of the
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   380
algorithm, but the rectification needs to be done to the
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   381
values in the second phase, it is advantageous to calculate
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   382
the rectification as a function, remember this function and
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   383
then apply the value to this function during the second phase.
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   384
So if we want to implement the rectification as function, we 
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   385
would need to return
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   386
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   387
\begin{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   388
$\lambda v.\,Right(f_{2s}(v))$
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   389
\end{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   390
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   391
\noindent which is the lambda-calculus notation for
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   392
a function that expects a value $v$ and returns everything
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   393
after the dot where $v$ is replaced by whatever value is 
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   394
given.
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   395
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   396
Let us package this idea with rectification functions
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   397
into a single function (still only considering the alternative
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   398
case):
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   399
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   400
\begin{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   401
\begin{tabular}{l}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   402
$simp(r)$:\\
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   403
\quad case $r = r_1 + r_2$\\
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   404
\qquad let $(r_{1s}, f_{1s}) = simp(r_1)$\\
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   405
\qquad \phantom{let} $(r_{2s}, f_{2s}) = simp(r_2)$\smallskip\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   406
\qquad case $r_{1s} = \ZERO$: 
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   407
       return $(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   408
\qquad case $r_{2s} = \ZERO$: 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   409
       return $(r_{1s}, \lambda v. \,\Left(f_{1s}(v)))$\\
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   410
\qquad case $r_{1s} = r_{2s}$:
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   411
       return $(r_{1s}, \lambda v. \,\Left(f_{1s}(v)))$\\
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   412
\qquad otherwise: 
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   413
       return $(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$\\
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   414
\end{tabular}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   415
\end{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   416
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   417
\noindent We first recursively call the simplification with
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   418
$r_1$ and $r_2$. This gives simplified regular expressions,
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   419
$r_{1s}$ and $r_{2s}$, as well as two rectification functions
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   420
$f_{1s}$ and $f_{2s}$. We next need to test whether the
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   421
simplified regular expressions are $\ZERO$ so as to make
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   422
further simplifications. In case $r_{1s}$ is $\ZERO$,
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   423
then we can return $r_{2s}$ (the other alternative). However
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   424
for this we need to build a corresponding rectification 
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   425
function, which as said above is
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   426
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   427
\begin{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   428
$\lambda v.\,Right(f_{2s}(v))$
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   429
\end{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   430
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   431
\noindent The case where $r_{2s} = \ZERO$ is similar:
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   432
We return $r_{1s}$ and rectify with $\Left(\_)$ and the
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   433
other calculated rectification function $f_{1s}$. This gives
284
0afe43616b6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 283
diff changeset
   434
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   435
\begin{center}
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   436
$\lambda v.\,\Left(f_{1s}(v))$
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   437
\end{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   438
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   439
\noindent The next case where $r_{1s} = r_{2s}$ can be treated
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   440
like the one where $r_{2s} = \ZERO$. We return $r_{1s}$
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   441
and rectify with $\Left(\_)$ and so on.
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   442
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   443
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   444
The otherwise-case is slightly more complicated. In this case
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   445
neither $r_{1s}$ nor $r_{2s}$ are $\ZERO$ and also
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   446
$r_{1s} \not= r_{2s}$, which means no further simplification
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   447
can be applied. Accordingly, we return $r_{1s} + r_{2s}$ as
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   448
the simplified regular expression. In principle we also do not
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   449
have to do any rectification, because no simplification was
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   450
done in this case. But this is actually not true: There might
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   451
have been simplifications inside $r_{1s}$ and $r_{2s}$. We
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   452
therefore need to take into account the calculated
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   453
rectification functions $f_{1s}$ and $f_{2s}$. We can do this
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   454
by defining a rectification function $f_{alt}$ which takes two
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   455
rectification functions as arguments and applies them
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   456
according to whether the value is of the form $\Left(\_)$ or
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   457
$Right(\_)$:
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   458
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   459
\begin{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   460
\begin{tabular}{l@{\hspace{1mm}}l}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   461
$f_{alt}(f_1, f_2) \dn$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   462
\qquad $\lambda v.\,$ case $v = \Left(v')$: 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   463
      & return $\Left(f_1(v'))$\\
285
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   464
\qquad \phantom{$\lambda v.\,$} case $v = Right(v')$: 
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   465
      & return $Right(f_2(v'))$\\      
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   466
\end{tabular}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   467
\end{center}
8a222559278f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 284
diff changeset
   468
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   469
The other interesting case with simplification is the sequence
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   470
case. In this case the main simplification function is as
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   471
follows
286
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   472
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   473
\begin{center}
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   474
\begin{tabular}{l}
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   475
$simp(r)$:\qquad\qquad (continued)\\
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   476
\quad case $r = r_1 \cdot r_2$\\
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   477
\qquad let $(r_{1s}, f_{1s}) = simp(r_1)$\\
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   478
\qquad \phantom{let} $(r_{2s}, f_{2s}) = simp(r_2)$\smallskip\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   479
\qquad case $r_{1s} = \ZERO$: 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   480
       return $(\ZERO, f_{error})$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   481
\qquad case $r_{2s} = \ZERO$: 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   482
       return $(\ZERO, f_{error})$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   483
\qquad case $r_{1s} = \ONE$: 
286
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   484
return $(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   485
\qquad case $r_{2s} = \ONE$: 
286
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   486
return $(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$\\
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   487
\qquad otherwise: 
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   488
       return $(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$\\
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   489
\end{tabular}
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   490
\end{center}
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   491
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   492
\noindent whereby in the last line $f_{seq}$ is again pushing
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   493
the two rectification functions into the two components of the
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   494
Seq-value:
286
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   495
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   496
\begin{center}
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   497
\begin{tabular}{l@{\hspace{1mm}}l}
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   498
$f_{seq}(f_1, f_2) \dn$\\
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   499
\qquad $\lambda v.\,$ case $v = Seq(v_1, v_2)$: 
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   500
      & return $Seq(f_1(v_1), f_2(v_2))$\\
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   501
\end{tabular}
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   502
\end{center}
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   503
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   504
\noindent Note that in the case of $r_{1s} = \ZERO$
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   505
(similarly $r_{2s}$) we use the function $f_{error}$ for
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   506
rectification. If you think carefully, then you will realise
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   507
that this function will actually never been called. This is
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   508
because a sequence with $\ZERO$ will never recognise any
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   509
string and therefore the second phase of the algorithm would
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   510
never been called. The simplification function still expects
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   511
us to give a function. So in my own implementation I just
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   512
returned a function that raises an error. In the case
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   513
where $r_{1s} = \ONE$ (similarly $r_{2s}$) we have
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   514
to create a sequence where the first component is a rectified
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   515
version of $Empty$. Therefore we call $f_{1s}$ with $Empty$.
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   516
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   517
Since we only simplify regular expressions of the form $r_1 +
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   518
r_2$ and $r_1 \cdot r_2$ we do not have to do anything else
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   519
in the remaining cases. The rectification function will
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   520
be just the identity, which in lambda-calculus terms is
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   521
just
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   522
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   523
\begin{center}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   524
$\lambda v.\,v$
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   525
\end{center}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   526
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   527
\noindent This completes the high-level version of the
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   528
simplification function, which is also shown again in 
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   529
Figure~\ref{simp}. This can now be used in a \emph{lexing
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   530
function} as follows:
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   531
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   532
\begin{figure}[t]
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   533
\begin{center}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   534
\begin{tabular}{l}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   535
$simp(r)$:\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   536
\quad case $r = r_1 + r_2$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   537
\qquad let $(r_{1s}, f_{1s}) = simp(r_1)$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   538
\qquad \phantom{let} $(r_{2s}, f_{2s}) = simp(r_2)$\smallskip\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   539
\qquad case $r_{1s} = \ZERO$: 
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   540
       return $(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   541
\qquad case $r_{2s} = \ZERO$: 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   542
       return $(r_{1s}, \lambda v. \,\Left(f_{1s}(v)))$\\
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   543
\qquad case $r_{1s} = r_{2s}$:
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   544
       return $(r_{1s}, \lambda v. \,\Left(f_{1s}(v)))$\\
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   545
\qquad otherwise: 
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   546
       return $(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   547
       \medskip\\
286
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   548
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   549
\quad case $r = r_1 \cdot r_2$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   550
\qquad let $(r_{1s}, f_{1s}) = simp(r_1)$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   551
\qquad \phantom{let} $(r_{2s}, f_{2s}) = simp(r_2)$\smallskip\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   552
\qquad case $r_{1s} = \ZERO$: 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   553
       return $(\ZERO, f_{error})$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   554
\qquad case $r_{2s} = \ZERO$: 
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   555
       return $(\ZERO, f_{error})$\\
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   556
\qquad case $r_{1s} = \ONE$: 
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   557
return $(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   558
\qquad case $r_{2s} = \ONE$: 
287
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   559
return $(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   560
\qquad otherwise: 
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   561
       return $(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   562
       \medskip\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   563
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   564
\quad otherwise:\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   565
\qquad return $(r, \lambda v.\,v)$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   566
\end{tabular}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   567
\end{center}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   568
\caption{The simplification function that returns a simplified 
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   569
regular expression and a rectification function.\label{simp}}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   570
\end{figure}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   571
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   572
\begin{center}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   573
\begin{tabular}{lcl}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   574
$lex\,r\,[]$ & $\dn$ & if $nullable(r)$ then $mkeps(r)$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   575
             &       & else $error$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   576
$lex\,r\,c\!::\!s$ & $\dn$ & let 
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   577
   $(r_{simp}, f_{rect}) = simp(der(c, r))$\\
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   578
& & $inj\,r\,c\,f_{rect}(lex\,r_{simp}\,s)$              
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   579
\end{tabular}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   580
\end{center}
2c50b8b5886c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 286
diff changeset
   581
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   582
\noindent This corresponds to the $matches$ function we have
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   583
seen in earlier lectures. In the first clause we are given an
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   584
empty string, $[]$, and need to test wether the regular
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   585
expression is $nullable$. If yes, we can proceed normally and
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   586
just return the value calculated by $mkeps$. The second clause
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   587
is for strings where the first character is $c$, say, and the
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   588
rest of the string is $s$. We first build the derivative of
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   589
$r$ with respect to $c$; simplify the resulting regular
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   590
expression. We continue lexing with the simplified regular
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   591
expression and the string $s$. Whatever will be returned as
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   592
value, we sill need to rectify using the $f_{rect}$ from the
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   593
simplification and finally inject $c$ back into the
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   594
(rectified) value.
286
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   595
19020b75d75e updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 285
diff changeset
   596
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   597
\subsubsection*{Records}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   598
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   599
Remember we wanted to tokenize input strings, that means
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   600
splitting strings into their ``word'' components. Furthermore
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   601
we want to classify each token as being a keyword or
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   602
identifier and so on. For this one more feature will be
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   603
required, which I call a \emph{record} regular expression.
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   604
While values encode how a regular expression matches a string,
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   605
records can be used to ``focus'' on some particular parts of
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   606
the regular expression and ``forget'' about others. 
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   607
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   608
Let us look at an example. Suppose you have the regular
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   609
expression $a\cdot b + a\cdot c$. Clearly this regular expression can only
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   610
recognise two strings. But suppose you are not interested
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   611
whether it can recognise $ab$ or $ac$, but rather if it
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   612
matched, then what was the last character of the matched
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   613
string\ldots either $b$ or $c$. You can do this by annotating
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   614
the regular expression with a record, written in general
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   615
$(x:r)$, where $x$ is just an identifier (in my implementation
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   616
a plain string) and $r$ is a regular expression. A record will
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   617
be regarded as a regular expression. The extended definition
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   618
in Scala therefore looks as follows:
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   619
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   620
{\small\lstinputlisting[language=Scala]
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   621
{../progs/app03.scala}}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   622
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   623
\noindent Since we regard records as regular expressions we
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   624
need to extend the functions $nullable$ and $der$. Similarly
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   625
$mkeps$ and $inj$ need to be extended. This means we also need
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   626
to extend the definition of values, which in Scala looks as
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   627
follows:
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   628
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   629
{\small\lstinputlisting[language=Scala]
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   630
{../progs/app04.scala}}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   631
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   632
\noindent Let us now look at the purpose of records more
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   633
closely and let us return to our question whether the string
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   634
terminated in a $b$ or $c$. We can do this as follows: we
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   635
annotate the regular expression $ab + ac$ with a record
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   636
as follows
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   637
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   638
\begin{center}
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   639
$a\cdot (x:b) + a\cdot (x:c)$
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   640
\end{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   641
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   642
\noindent This regular expression can still only recognise
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   643
the strings $ab$ and $ac$, but we can now use a function
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   644
that takes a value and returns all records. I call this
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   645
function \emph{env} for environment\ldots it builds a list
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   646
of identifiers associated with a string. This function
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   647
can be defined as follows:
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   648
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   649
\begin{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   650
\begin{tabular}{lcl}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   651
  $env(Empty)$     & $\dn$ & $[]$\\
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   652
  $env(Char(c))$   & $\dn$ & $[]$\\
400
e4afe3f46c29 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 394
diff changeset
   653
  $env(\Left(v))$   & $\dn$ & $env(v)$\\
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   654
  $env(Right(v))$  & $\dn$ & $env(v)$\\
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   655
  $env(Seq(v_1,v_2))$& $\dn$ & $env(v_1) \,@\, env(v_2)$\\
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   656
  $env([v_1,\ldots ,v_n])$ & $\dn$ & 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   657
     $env(v_1) \,@\ldots @\, env(v_n)$\\
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   658
  $env(Rec(x:v))$ & $\dn$ & $(x:|v|) :: env(v)$\\
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   659
\end{tabular}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   660
\end{center}
251
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   661
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   662
\noindent where in the last clause we use the flatten function
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   663
defined earlier. As can be seen, the function $env$ ``picks''
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   664
out all underlying strings where a record is given. Since
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   665
there can be more than one, the environment will potentially
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   666
contain many ``records''. If we now postprocess the value
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   667
calculated by $lex$ extracting all records using $env$, we can
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   668
answer the question whether the last element in the string was
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   669
an $b$ or a $c$. Lets see this in action: if we use $a\cdot b
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   670
+ a\cdot c$ and $ac$ the calculated value will be
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   671
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   672
\begin{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   673
$Right(Seq(Char(a), Char(c)))$
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   674
\end{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   675
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   676
\noindent If we use instead $a\cdot (x:b) + a\cdot (x:c)$ and
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   677
use the $env$ function to extract the recording for 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   678
$x$ we obtain
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   679
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   680
\begin{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   681
$[(x:c)]$
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   682
\end{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   683
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   684
\noindent If we had given the string $ab$ instead, then the
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   685
record would have been $[(x:b)]$. The fun starts if we 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   686
iterate this. Consider the regular expression 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   687
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   688
\begin{center}
326
94700593a2d5 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 319
diff changeset
   689
$(a\cdot (x:b) + a\cdot (y:c))^*$
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   690
\end{center}
251
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   691
288
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   692
\noindent and the string $ababacabacab$. This string is 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   693
clearly matched by the regular expression, but we are only
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   694
interested in the sequence of $b$s and $c$s. Using $env$
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   695
we obtain
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   696
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   697
\begin{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   698
$[(x:b), (x:b), (y:c), (x:b), (y:c), (x:b)]$
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   699
\end{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   700
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   701
\noindent While this feature might look silly, it is in fact
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   702
quite useful. For example if we want to match the name of
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   703
an email we might use the regular expression
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   704
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   705
\[
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   706
(name: [a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   707
(domain: [a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   708
(top\_level: [a\mbox{-}z\,.]^{\{2,6\}})
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   709
\]
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   710
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   711
\noindent Then if we match the email address
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   712
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   713
\[
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   714
\texttt{christian.urban@kcl.ac.uk}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   715
\]
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   716
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   717
\noindent we can use the $env$ function and find out
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   718
what the name, domain and top-level part of the email
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   719
address are:
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   720
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   721
\begin{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   722
$[(name:\texttt{christian.urban}), 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   723
  (domain:\texttt{kcl}), 
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   724
  (top\_level:\texttt{ac.uk})]$
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   725
\end{center}
39aeca14af8c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 287
diff changeset
   726
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   727
Recall that we want to lex a little programming language,
357
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   728
called the \emph{While}-language. A simple program in this
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   729
language is shown in Figure~\ref{while}. The main keywords in
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   730
this language are \pcode{while}, \pcode{if}, \pcode{then} and
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   731
\pcode{else}. As usual we have syntactic categories for
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   732
identifiers, operators, numbers and so on. For this we would
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   733
need to design the corresponding regular expressions to
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   734
recognise these syntactic categories. I let you do this design
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   735
task. Having these regular expressions at our disposal, we can
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   736
form the regular expression
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   737
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   738
\begin{figure}[t]
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   739
\begin{center}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   740
\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   741
\end{center}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   742
\caption{The Fibonacci program in the While-language.\label{while}}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   743
\end{figure}
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   744
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   745
\begin{center}
357
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   746
$\textit{WhileRegs} \;\dn\; 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   747
\left(\begin{array}{l}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   748
       (k, KeyWords)\; +\\
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   749
       (i, Ids)\;+\\
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   750
       (o, Ops)\;+ \\
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   751
       (n, Nums)\;+ \\
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   752
       (s, Semis)\;+ \\
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   753
       (p, (LParens + RParens))\;+\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   754
       (b, (Begin + End))\;+ \\
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   755
       (w, WhiteSpacess)
394
2f9fe225ecc8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 357
diff changeset
   756
      \end{array}\right)^{\mbox{\LARGE{}*}}$
357
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   757
\end{center}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   758
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   759
\noindent and ask the algorithm by Sulzmann \& Lu to lex, say
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   760
the following string
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   761
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   762
\begin{center}\large
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   763
\code{"if true then then 42 else +"}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   764
\end{center}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   765
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   766
\noindent
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   767
By using the records and extracting the environment, the 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   768
result is the following list:
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   769
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   770
\begin{center}\tt
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   771
\begin{tabular}{l}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   772
KEYWORD(if),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   773
WHITESPACE,\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   774
IDENT(true),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   775
WHITESPACE,\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   776
KEYWORD(then),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   777
WHITESPACE,\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   778
KEYWORD(then),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   779
WHITESPACE,\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   780
NUM(42),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   781
WHITESPACE,\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   782
KEYWORD(else),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   783
WHITESPACE,\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   784
OP(+)
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   785
\end{tabular}
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   786
\end{center}
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   787
357
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   788
\noindent Typically we are not interested in the whitespaces 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   789
and comments and would filter them out: this gives
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   790
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   791
\begin{center}\tt
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   792
\begin{tabular}{l}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   793
KEYWORD(if),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   794
IDENT(true),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   795
KEYWORD(then),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   796
KEYWORD(then),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   797
NUM(42),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   798
KEYWORD(else),\\ 
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   799
OP(+)
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   800
\end{tabular}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   801
\end{center}
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   802
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   803
\noindent
603e171a7b48 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 356
diff changeset
   804
which will be the input for the next phase of our compiler.
356
d9c784c71305 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 352
diff changeset
   805
251
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   806
\end{document}
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   807
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   808
%%% Local Variables: 
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   809
%%% mode: latex
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   810
%%% TeX-master: t
5b5a68df6d16 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   811
%%% End: