717 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   718 \begin{frame}[c]

   719 \frametitle{Simplification}

   720 

   721 \begin{itemize}

   722 \item If we simplify after the derivative, then we ar builing the

   723 value for the simplified regular expression, but \emph{not} for the original

   724 regular expression.

   725 \end{itemize}

   726 

   727 \begin{center}

   728 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]

   729 \node (r1)  {\bl{$r_1$}};

   730 \node (r2) [right=of r1] {\bl{$r_2$}};

   731 \draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};

   732 \node (r3) [right=of r2] {\bl{$r_3$}};

   733 \draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};

   734 \node (r4) [right=of r3] {\bl{$r_4$}};

   735 \draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};

   736 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};

   737 \node (v4) [below=of r4] {\bl{$v_4$}};

   738 \draw[->,line width=1mm]  (r4) -- (v4);

   739 \node (v3) [left=of v4] {\bl{$v_3$}};

   740 \draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};

   741 \node (v2) [left=of v3] {\bl{$v_2$}};

   742 \draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};

   743 \node (v1) [left=of v2] {\bl{$v_1$}};

   744 \draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};

   745 \draw[->,line width=0.5mm]  (r3) -- (v3);

   746 \draw[->,line width=0.5mm]  (r2) -- (v2);

   747 \draw[->,line width=0.5mm]  (r1) -- (v1);

   748 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};

   749 \end{tikzpicture}

   750 \end{center}

   751 

   752 \end{frame}

   753 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   754 

   755 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   756 \begin{frame}[c]

   757 \frametitle{Rectification}

   758 

   759 \def\arraystretch{1.05}

   760 \begin{center}

   761 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{5mm}}l}

   762 & & & \hspace{5mm}rectification \\

   763 & & & \hspace{5mm}functions:\\

   764 \bl{$r \cdot \varnothing$} & $\mapsto$ & \bl{$\varnothing$} & \\ 

   765 \bl{$\varnothing \cdot r$} & $\mapsto$ & \bl{$\varnothing$} & \\ 

   766 \bl{$r \cdot \epsilon$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\ 

   767 \bl{$\epsilon \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\ 

   768 \bl{$r + \varnothing$} & $\mapsto$ & \bl{$r$}   & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\ 

   769 \bl{$\varnothing + r$} & $\mapsto$ & \bl{$r$}   & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\

   770 \bl{$r + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}

   771 \end{tabular}

   772 \end{center}\medskip\pause

   773 

   774 \small

   775 old \bl{$simp$} returns a rexp;\\

   776 new \bl{$simp$} returns a rexp and a rectification~fun.

   777 \end{frame}

   778 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   779 

   780 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   781 \begin{frame}[c]

   782 \frametitle{Lexing with Simplification}

   783 

   784 \begin{center}

   785 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}

   786   \bl{$lex\,r\,[]$} & \bl{$\dn$}  & \bl{if $nullable(r)$ then $mkeps(r)$ else $error$}\\

   787   \bl{$lex\,r\,c::s$} & \bl{$\dn$}  & \bl{let $(r', frect) = simp(der(c, r))$}\smallskip\\

   788                       & & \bl{$inj\,r\,c\,(frect(lex(r', s)))$}\\

   789 \end{tabular}

   790 \end{center}\bigskip

   791 

   792 \begin{center}\small

   793 \begin{tikzpicture}[node distance=1.1cm,every node/.style={minimum size=7mm}]

   794 \node (r1)  {\bl{$r_1$}};

   795 \node (r2) [right=of r1] {\bl{$r_2$}};

   796 \draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};

   797 \node (r3) [right=of r2] {\bl{$r_3$}};

   798 \draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};

   799 \node (r4) [right=of r3] {\bl{$r_4$}};

   800 \draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};

   801 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};

   802 \node (v4) [below=of r4] {\bl{$v_4$}};

   803 \draw[->,line width=1mm]  (r4) -- (v4);

   804 \node (v3) [left=of v4] {\bl{$v_3$}};

   805 \draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};

   806 \node (v2) [left=of v3] {\bl{$v_2$}};

   807 \draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};

   808 \node (v1) [left=of v2] {\bl{$v_1$}};

   809 \draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};

   810 \draw[->,line width=0.5mm]  (r3) -- (v3);

   811 \draw[->,line width=0.5mm]  (r2) -- (v2);

   812 \draw[->,line width=0.5mm]  (r1) -- (v1);

   813 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};

   814 \end{tikzpicture}

   815 \end{center}

   816 

   817 

   818 \end{frame}

   819 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   820