--- a/slides/slides06.tex	Tue Nov 02 14:40:06 2021 +0000
+++ b/slides/slides06.tex	Thu Nov 11 15:58:22 2021 +0000
@@ -60,6 +60,212 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Parser Combinators}
+
+One of the simplest ways to implement a parser, see
+{\small\url{https://vimeo.com/142341803}} (by Haoyi Li)\bigskip
+
+\begin{itemize}
+\item[$\bullet$] build-in library in Scala
+\item[$\bullet$] fastparse (2) library by Haoyi Li; is part of Ammonite
+\item[$\bullet$] possible exponential runtime behaviour  
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Parser Combinators}
+
+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 atomic parsers
+\item sequencing
+\item alternative
+\item semantic action (map-parser)
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+Atomic parsers, for example, number tokens
+
+\begin{center}
+\bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$} 
+\end{center}\bigskip
+
+\begin{itemize}
+\item you consume one or more token from the\\ 
+  input (stream)
+\item also works for characters and strings
+\end{itemize}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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:\medskip 
+\begin{center}
+((output$_1$, output$_2$), unparsed part)
+\end{center}
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+Map-parser (code \bl{$p.map(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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
+
+Addition
+
+\begin{center}
+\bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
+\end{center}\pause
+
+Multiplication
+
+\begin{center}
+\bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
+\end{center}\pause
+
+Parenthesis
+
+\begin{center}
+\bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Input Types of Parsers}
+
+\begin{itemize}
+\item input: \alert{token list}
+\item output: set of (output\_type, \alert{token list})
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Scannerless Parsers}
+
+\begin{itemize}
+\item input: \alert{string}
+\item output: set of (output\_type, \alert{string})
+\end{itemize}\bigskip\bigskip
+
+but using lexers is better because whitespaces or comments can be
+filtered out; then input is a sequence of tokens
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Abstract Parser Class}
+
+\small
+\lstinputlisting[language=Scala,xleftmargin=1mm]
+ {../progs/app7.scala}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Successful Parses}
+
+\begin{itemize}
+\item input: string
+\item output: \alert{set of} (output\_type, string)
+\end{itemize}\bigskip
+
+a parse is successful whenever the input has been fully
+``consumed'' (that is the second component is empty)
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 %%\frametitle{Test Program}
@@ -73,7 +279,6 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 \begin{frame}
 \frametitle{While-Language}
@@ -207,13 +412,8 @@
 \end{mybox3}
 \end{frame}
 
-\begin{frame}[t]
-  \begin{mybox3}{}
-  When will we have the mid-term that was originally scheduled for last week? We haven't heard anything about it for 2 weeks.  
-\end{mybox3}
-\end{frame}
 
-\begin{frame}<1-12>[c]
+\begin{frame}<1-20>[c]
 \end{frame}
 
 
@@ -998,21 +1198,6 @@
 \end{document}
 
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Parser Combinators}
-
-One of the simplest ways to implement a parser, see
-{\small\url{https://vimeo.com/142341803}} (by Haoyi Li)\bigskip
-
-\begin{itemize}
-\item[$\bullet$] build-in library in Scala
-\item[$\bullet$] fastparse (2) library by Haoyi Li; is part of Ammonite
-\item[$\bullet$] possible exponential runtime behaviour  
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]