--- a/slides09.tex Sat Nov 24 14:58:41 2012 +0000
+++ b/slides09.tex Sat Nov 24 15:10:43 2012 +0000
@@ -192,313 +192,6 @@
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}
-
-The lexer cannot prevent errors like
-
-\begin{center}
-\bl{$<\!b\!>$} \ldots \bl{$<\!p\!>$} \ldots \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!\slash{}p\!>$}
-\end{center}
-
-or
-
-\begin{center}
-\bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!b\!>$}
-\end{center}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}}
-
-Parser combinators: \bigskip
-
-\begin{minipage}{1.1\textwidth}
-\begin{center}
-\mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$}
-$\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$
-\end{center}
-\end{minipage}\bigskip
-
-\begin{itemize}
-\item sequencing
-\item alternative
-\item semantic action
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-Alternative parser (code \bl{$p\;||\;q$})\bigskip
-
-\begin{itemize}
-\item apply \bl{$p$} and also \bl{$q$}; then combine the outputs
-\end{itemize}
-
-\begin{center}
-\large \bl{$p(\text{input}) \cup q(\text{input})$}
-\end{center}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-Sequence parser (code \bl{$p\sim q$})\bigskip
-
-\begin{itemize}
-\item apply first \bl{$p$} producing a set of pairs
-\item then apply \bl{$q$} to the unparsed parts
-\item then combine the results:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part)
-\end{itemize}
-
-\begin{center}
-\begin{tabular}{l}
-\large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm]
-\large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
-\large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
-\end{tabular}
-\end{center}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-Function parser (code \bl{$p \Longrightarrow f$})\bigskip
-
-\begin{itemize}
-\item apply \bl{$p$} producing a set of pairs
-\item then apply the function \bl{$f$} to each first component
-\end{itemize}
-
-\begin{center}
-\begin{tabular}{l}
-\large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
-\end{tabular}
-\end{center}\bigskip\bigskip\pause
-
-\bl{$f$} is the semantic action (``what to do with the parsed input'')
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-Token parser:\bigskip
-
-\begin{itemize}
-\item if the input is
-
-\begin{center}
-\large \bl{$tok_1:: tok_2 :: \ldots :: tok_n$}
-\end{center}
-
-then return
-
-\begin{center}
-\large \bl{$\{(tok_1,\; tok_2 :: \ldots :: tok_n)\}$}
-\end{center}
-
-or
-
-\begin{center}
-\large \bl{$\{\}$}
-\end{center}
-
-if \bl{$tok_1$} is not the right token we are looking for
-\end{itemize}
-
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-Number-Token parser:\bigskip
-
-\begin{itemize}
-\item if the input is
-
-\begin{center}
-\large \bl{$num\_tok(42):: tok_2 :: \ldots :: tok_n$}
-\end{center}
-
-then return
-
-\begin{center}
-\large \bl{$\{(42,\; tok_2 :: \ldots :: tok_n)\}$}
-\end{center}
-
-or
-
-\begin{center}
-\large \bl{$\{\}$}
-\end{center}
-
-if \bl{$tok_1$} is not the right token we are looking for
-\end{itemize}\pause
-
-\begin{center}
-list of tokens \bl{$\Rightarrow$} set of (\alert{int}, list of tokens)
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{itemize}
-\item if the input is
-
-\begin{center}
-\begin{tabular}{l}
-\large \bl{$num\_tok(42)::$}\\
-\hspace{7mm}\large \bl{$num\_tok(3) ::$}\\
-\hspace{14mm}\large \bl{$tok_3 :: \ldots :: tok_n$}
-\end{tabular}
-\end{center}
-
-and the parser is
-
-\begin{center}
-\bl{$ntp \sim ntp$}
-\end{center}
-
-the successful output will be
-
-\begin{center}
-\large \bl{$\{((42, 3),\; tok_2 :: \ldots :: tok_n)\}$}
-\end{center}\pause
-
-Now we can form
-\begin{center}
-\bl{$(ntp \sim ntp) \Longrightarrow f$}
-\end{center}
-
-where \bl{$f$} is the semantic action (``what to do with the pair'')
-
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
-
-Addition
-
-\begin{center}
-\bl{$T \sim + \sim E \Longrightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
-\end{center}\pause
-
-Multiplication
-
-\begin{center}
-\bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$}
-\end{center}\pause
-
-Parenthesis
-
-\begin{center}
-\bl{$\text{(} \sim E \sim \text{)} \Longrightarrow f((x,y), z) \Rightarrow y$}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}}
-
-\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 \Longrightarrow f$} returns results of type
-
-\begin{center}
-\bl{$S$}
-\end{center}
-
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}}
-
-\begin{itemize}
-\item input: \alert{list of tokens}
-\item output: set of (output\_type, \alert{list of tokens})
-\end{itemize}\bigskip\pause
-
-actually it can be any input type as long as it is a kind of sequence
-(for example a string)
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}}
-
-\begin{itemize}
-\item input: \alert{string}
-\item output: set of (output\_type, \alert{string})
-\end{itemize}\bigskip
-
-but lexers are better when whitespaces or comments need to be filtered out
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{