--- a/slides08.tex	Tue Nov 20 22:06:05 2012 +0000
+++ b/slides08.tex	Wed Nov 21 02:20:16 2012 +0000
@@ -151,6 +151,360 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+\frametitle{\begin{tabular}{c}Building a Web Browser\end{tabular}}
+
+Using a lexer: assume the following regular expressions
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\
+$W\!O\!RD$ & $\dn$ & $SY\!M^+$\\
+$BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\
+$ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\
+$W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Interpreting a List of Token\end{tabular}}
+
+\begin{itemize}
+\item text should be formatted consistently up to a specified width, say 60 characters 
+\item potential linebreaks are inserted by the formatter
+\item repeated whitespaces are ``condensed'' to a single whitepace
+\item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$}  start/end paragraph
+\item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$}  start/end bold
+\item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$}  start/end red (cyan, etc)
+
+
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Interpreting a List of Token\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 \bl{$p$} first producing a set of pairs
+\item then apply \bl{$q$} to the unparsed parts
+\item the combine the results:\\ \mbox{}\;\;((input$_1$, input$_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 fist 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}
+
+
+\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]
+{\lstset{language=Scala}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{app7.scala}}}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+{\lstset{language=Scala}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{app7.scala}}}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+{\lstset{language=Scala}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{app8.scala}}}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 \frametitle{\begin{tabular}{c}Two Grammars\end{tabular}}
 
 Which languages are recognised by the following two grammars?