--- a/slides/slides06.tex Wed Nov 01 11:44:23 2017 +0000
+++ b/slides/slides06.tex Wed Nov 08 12:54:39 2017 +0000
@@ -38,51 +38,51 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\small
-\mbox{}\\[5mm]
-%\begin{textblock}{10}(3,5)
-\begin{tikzpicture}[scale=1.5,
- node distance=1cm,
- every node/.style={minimum size=7mm}]
-\node (r1) {\bl{$r_1$}};
-\node (r2) [right=of r1] {\bl{$r_2$}};
-\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
-\node (r3) [right=of r2] {\bl{$r_3$}};
-\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
-\node (r4) [right=of r3] {\bl{$r_4$}};
-\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
-\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
-\node (v4) [below=of r4] {\bl{$v_4$}};
-\draw[->,line width=1mm] (r4) -- (v4);
-\node (v3) [left=of v4] {\bl{$v_3$}};
-\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
-\node (v2) [left=of v3] {\bl{$v_2$}};
-\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
-\node (v1) [left=of v2] {\bl{$v_1$}};
-\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
-\draw[->,line width=0.5mm] (r3) -- (v3);
-\draw[->,line width=0.5mm] (r2) -- (v2);
-\draw[->,line width=0.5mm] (r1) -- (v1);
-\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
-\end{tikzpicture}
-%\end{textblock}
+% \begin{frame}[c]
+% \small
+% \mbox{}\\[5mm]
+% %\begin{textblock}{10}(3,5)
+% \begin{tikzpicture}[scale=1.5,
+% node distance=1cm,
+% every node/.style={minimum size=7mm}]
+% \node (r1) {\bl{$r_1$}};
+% \node (r2) [right=of r1] {\bl{$r_2$}};
+% \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+% \node (r3) [right=of r2] {\bl{$r_3$}};
+% \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+% \node (r4) [right=of r3] {\bl{$r_4$}};
+% \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+% \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+% \node (v4) [below=of r4] {\bl{$v_4$}};
+% \draw[->,line width=1mm] (r4) -- (v4);
+% \node (v3) [left=of v4] {\bl{$v_3$}};
+% \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+% \node (v2) [left=of v3] {\bl{$v_2$}};
+% \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+% \node (v1) [left=of v2] {\bl{$v_1$}};
+% \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+% \draw[->,line width=0.5mm] (r3) -- (v3);
+% \draw[->,line width=0.5mm] (r2) -- (v2);
+% \draw[->,line width=0.5mm] (r1) -- (v1);
+% \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+% \end{tikzpicture}
+% %\end{textblock}
-\begin{center}
-\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
- \\[-10mm]
- \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\
- \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
- \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
- \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\
-\end{tabular}
-\end{center}
+% \begin{center}
+% \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+% \\[-10mm]
+% \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\
+% \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
+% \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
+% \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+% \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+% \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
+% \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\
+% \end{tabular}
+% \end{center}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \end{frame}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -106,28 +106,7 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Two Grammars}
-
-Which languages are recognised by the following two grammars?
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\
- & $|$ & $\epsilon$
-\end{tabular}}
-\end{center}\bigskip
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$U$ & $\rightarrow$ & $1 \cdot U$\\
- & $|$ & $\epsilon$
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -208,6 +187,62 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Types of Parsers}
+
+\begin{itemize}
+\item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
+then \bl{$p \sim q$} returns results of type
+
+\begin{center}
+\bl{$T \times S$}
+\end{center}\pause
+
+\item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then \bl{$q$} \alert{must} also have results of type \bl{$T$},
+and \bl{$p \;||\; q$} returns results of type
+
+\begin{center}
+\bl{$T$}
+\end{center}\pause
+
+\item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
+\bl{$T$} to \bl{$S$}, then
+\bl{$p \Rightarrow f$} returns results of type
+
+\begin{center}
+\bl{$S$}
+\end{center}
+
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Two Grammars}
+
+Which languages are recognised by the following two grammars?
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\
+ & $|$ & $\epsilon$
+\end{tabular}}
+\end{center}\bigskip
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$U$ & $\rightarrow$ & $1 \cdot U$\\
+ & $|$ & $\epsilon$
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]