% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../grammar}
\hfuzz=220pt
\pgfplotsset{compat=1.11}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
% beamer stuff
\renewcommand{\slidecaption}{CFL 05, King's College London}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-2mm]
\LARGE Formal Languages (5)\\[3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
Office Hours: & Thursdays 12 -- 14\\
Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS (also homework is there)\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Last Week\\[-2mm]
Regexes and Values\end{tabular}}
Regular expressions and their corresponding values:
\begin{center}
\begin{columns}
\begin{column}{3cm}
\begin{tabular}{@{}rrl@{}}
\bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
& \bl{$\mid$} & \bl{$\ONE$} \\
& \bl{$\mid$} & \bl{$c$} \\
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
& \bl{$\mid$} & \bl{$r_1 + r_2$} \\
\\
& \bl{$\mid$} & \bl{$r^*$} \\
\end{tabular}
\end{column}
\begin{column}{3cm}
\begin{tabular}{@{\hspace{-7mm}}rrl@{}}
\bl{$v$} & \bl{$::=$} & \\
& & \bl{$Empty$} \\
& \bl{$\mid$} & \bl{$Char(c)$} \\
& \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
& \bl{$\mid$} & \bl{$Left(v)$} \\
& \bl{$\mid$} & \bl{$Right(v)$} \\
& \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\
\end{tabular}
\end{column}
\end{columns}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{textblock}{10}(3,5)
\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
\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{textblock}{6}(1,0.8)
\begin{bubble}[6cm]
\small
\begin{tabular}{ll}
\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
\end{tabular}
\end{bubble}
\end{textblock}
\begin{textblock}{6}(1,11.4)
\begin{bubble}[7.6cm]
\small
\begin{tabular}{ll}
\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
\end{tabular}
\end{bubble}
\end{textblock}
\begin{textblock}{6}(12,11.4)
\begin{bubble}[2cm]
\small
\begin{tabular}{ll}
\bl{$|v_1|$}: & \bl{$abc$}\\
\bl{$|v_2|$}: & \bl{$bc$}\\
\bl{$|v_3|$}: & \bl{$c$}\\
\bl{$|v_4|$}: & \bl{$[]$}
\end{tabular}
\end{bubble}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Simplification}
\begin{itemize}
\item If we simplify after the derivative, then we are builing the
value for the simplified regular expression, but \emph{not} for the original
regular expression.
\end{itemize}
\begin{center}
\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
\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{center}
\small
\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$}
$\mapsto$
\bl{$(b \cdot c) + \ONE$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[t]
% \begin{center}
% \bl{$\only<1>{(b \cdot c)}%
% \only<2-3>{(\underline{b \cdot c})}%
% \only<1-3>{+}%
% \only<1>{(\ZERO + \ONE)}%
% \only<2-3>{(\underline{\ZERO + \ONE})}$}%
% \only<4->{%
% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
% }
% $\mapsto$
% \bl{$(b \cdot c) + \ONE$}
% \end{center}\bigskip
% \onslide<3->{%
% \begin{center}
% \begin{tabular}{lcl}
% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
% \end{tabular}
% \end{center}}
% \only<4>{%
% \begin{center}
% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
% \quad \bl{$\lambda v.\,$}
% case \bl{$v = Left(v')$}:
% & return \bl{$Left(f_{s1}(v'))$}\\
% \quad \phantom{$\lambda v.\,$}
% case \bl{$v = Right(v')$}:
% & return \bl{$Right(f_{s2}(v'))$}\\
% \end{tabular}
% \end{center}}%
% \only<5->{%
% \begin{center}
% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
% \quad \bl{$\lambda v.\,$}
% case \bl{$v = Left(v')$}:
% & return \bl{$Left(v')$}\\
% \quad \phantom{$\lambda v.\,$}
% case \bl{$v = Right(v')$}:
% & return \bl{$Right(Right(v'))$}\\
% \end{tabular}
% \end{center}}%
% \only<6->{%
% \begin{center}
% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
% \bl{$\textit{mkeps}$} simplified case: &
% \bl{$\textit{Right}(\textit{Empty})$}\\
% rectified case: &
% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
% \end{tabular}
% \end{center}}%
% \end{frame}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Records}
\begin{itemize}
\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
\item \bl{$nullable(x:r) \dn nullable(r)$}
\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$}
\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
\item \bl{$inj\,(x:r)\,c\,Rec(x, v) \dn Rec(x, inj\,r\,c\,v)$}
\end{itemize}\bigskip\bigskip\pause
\small
for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Environments}
Obtaining the ``recorded'' parts of a value:
\begin{center}
\begin{tabular}{lcl}
\bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
\bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
\bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
\bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
\bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
\bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} &
\bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
\bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{While Tokens}
\begin{center}
\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
& & \phantom{(}\pcode{("i" : ID)} +\\
& & \phantom{(}\pcode{("o" : OP)} + \\
& & \phantom{(}\pcode{("n" : NUM)} + \\
& & \phantom{(}\pcode{("s" : SEMI)} +\\
& & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
& & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
& & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\consolas
\begin{center}
\code{"if true then then 42 else +"}
\end{center}
\only<1>{
\small\begin{tabular}{l}
KEYWORD(if),\\
WHITESPACE,\\
IDENT(true),\\
WHITESPACE,\\
KEYWORD(then),\\
WHITESPACE,\\
KEYWORD(then),\\
WHITESPACE,\\
NUM(42),\\
WHITESPACE,\\
KEYWORD(else),\\
WHITESPACE,\\
OP(+)
\end{tabular}}
\only<2>{
\small\begin{tabular}{l}
KEYWORD(if),\\
IDENT(true),\\
KEYWORD(then),\\
KEYWORD(then),\\
NUM(42),\\
KEYWORD(else),\\
OP(+)
\end{tabular}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Coursework 1: Submissions}
\begin{itemize}
\item Scala (29)
\item Haskell (1)
\item Kotlin (1)
\item Rust (1)
\end{itemize}\bigskip\bigskip
\small
Please get in contact if you intend to do CW Strand 2. No zips please.
Give definitions also on paper, if asked, and be truthful! BTW, simp
can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}!
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Coursework: PLs (16)}
%
%\begin{itemize}
%\item Java (16)
%\item C++, C, C\# (14)
%\item JavaScript (10)
%\item Scala (9)
%\item Python (9)
%\item PHP (6)
%\item Haskell (3)
%\item Ruby (4)
%\item Bash, Perl, Powershell (2)
%\item TypeScript (1)
%\item R (1)
%\item Coconut (1)
%\item Pascal (1)
%\end{itemize}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Coursework: Nullable}
%
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
% \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\
% \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\
%
%\end{tabular}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%%%\frametitle{Coursework: der}
%
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
% \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
% \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\
% \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\
% \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} &
% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
% \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} &
% \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
% & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
% \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} &
% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
%
% \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} &
% \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
% \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
% \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
% \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
% \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\
%\end{tabular}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Coursework: CFUN}
%
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
% \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\
% \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} &
% \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\
% \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\
% \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\
% \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\
%\end{tabular}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Lexer, Parser}
\mbox{}\\[-16mm]\mbox{}
\begin{center}
\begin{tikzpicture}[scale=1,
node/.style={
rectangle,rounded corners=3mm,
very thick,draw=black!50,
minimum height=18mm, minimum width=20mm,
top color=white,bottom color=black!20}]
\node (0) at (-2.3,0) {};
\node (A) at (0,0) [node] {};
\node [below right] at (A.north west) {lexer};
\node (B) at (3,0) [node] {};
\node [below right=1mm] at (B.north west)
{\mbox{}\hspace{-1mm}parser};
\node (C) at (6,0) [node] {};
\node [below right] at (C.north west)
{\mbox{}\hspace{-1mm}code gen};
\node (1) at (8.4,0) {};
\draw [->,line width=4mm] (0) -- (A);
\draw [->,line width=4mm] (A) -- (B);
\draw [->,line width=4mm] (B) -- (C);
\draw [->,line width=4mm] (C) -- (1);
\end{tikzpicture}
\end{center}
Today a parser.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{What Parsing is Not}
Usually parsing does not check semantic correctness, e.g.
\begin{itemize}
\item whether a function is not used before it
is defined
\item whether a function has the correct number of arguments
or are of correct type
\item whether a variable can be declared twice in a scope
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regular Languages}
While regular expressions are very useful for lexing, there is
no regular expression that can recognise the language
\bl{$a^nb^n$}.\bigskip
\begin{center}
\bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}
\end{center}\bigskip\bigskip
\small
\noindent So we cannot find out with regular expressions
whether parentheses are matched or unmatched. Also regular
expressions are not recursive, e.g.~\bl{$(1 + 2) + 3$}.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Hierarchy of Languages}
\begin{center}
\begin{tikzpicture}
[rect/.style={draw=black!50,
top color=white,
bottom color=black!20,
rectangle,
very thick,
rounded corners}, scale=1.2]
\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
\draw (0,-1.4) node [rect] {regular languages};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{CF Grammars}
A \alert{\bf context-free grammar} \bl{$G$} consists of
\begin{itemize}
\item a finite set of nonterminal symbols (e.g.~$\meta{A}$ upper case)
\item a finite set terminal symbols or tokens (lower case)
\item a start symbol (which must be a nonterminal)
\item a set of rules
\begin{center}
\bl{$\meta{A} ::= \textit{rhs}$}
\end{center}
where \bl{\textit{rhs}} are sequences involving terminals and nonterminals,
including the empty sequence \bl{$\epsilon$}.\medskip\pause
We also allow rules
\begin{center}
\bl{$\meta{A} ::= \textit{rhs}_1 | \textit{rhs}_2 | \ldots$}
\end{center}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Palindromes}
A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
\bl{\begin{plstx}[margin=3cm]
: \meta{S} ::= a\cdot\meta{S}\cdot a\\
: \meta{S} ::= b\cdot\meta{S}\cdot b\\
: \meta{S} ::= a\\
: \meta{S} ::= b\\
: \meta{S} ::= \epsilon\\
\end{plstx}}\pause
or
\bl{\begin{plstx}[margin=2cm]
: \meta{S} ::= a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\
\end{plstx}}\pause\bigskip
\small
Can you find the grammar rules for matched parentheses?
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Arithmetic Expressions}
\bl{\begin{plstx}[margin=3cm,one per line]
: \meta{E} ::= num\_token
| \meta{E} \cdot + \cdot \meta{E}
| \meta{E} \cdot - \cdot \meta{E}
| \meta{E} \cdot * \cdot \meta{E}
| ( \cdot \meta{E} \cdot ) \\
\end{plstx}}\pause
\bl{\texttt{1 + 2 * 3 + 4}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{A CFG Derivation}
\begin{enumerate}
\item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip
\item Replace any nonterminal \bl{\meta{X}} in the string by the
right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip
\item Repeat 2 until there are no nonterminals left
\end{enumerate}
\begin{center}
\bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Example Derivation}
\bl{\begin{plstx}[margin=2cm]
: \meta{S} ::= \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\
\end{plstx}}\bigskip
\begin{center}
\begin{tabular}{lcl}
\bl{\meta{S}} & \bl{$\rightarrow$} & \bl{$a\meta{S}a$}\\
& \bl{$\rightarrow$} & \bl{$ab\meta{S}ba$}\\
& \bl{$\rightarrow$} & \bl{$aba\meta{S}aba$}\\
& \bl{$\rightarrow$} & \bl{$abaaba$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Example Derivation}
\bl{\begin{plstx}[margin=3cm,one per line]
: \meta{E} ::= num\_token
| \meta{E} \cdot + \cdot \meta{E}
| \meta{E} \cdot - \cdot \meta{E}
| \meta{E} \cdot * \cdot \meta{E}
| ( \cdot \meta{E} \cdot ) \\
\end{plstx}}
\small
\begin{center}
\begin{tabular}{@{}c@{}c@{}}
\begin{tabular}{@{\hspace{-2mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{4mm}}}
\bl{\meta{E}} & \bl{$\rightarrow$} & \bl{$\meta{E}*\meta{E}$}\\
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}$}\\
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
& \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
\end{tabular} &\pause
\begin{tabular}{@{}l@{\hspace{0mm}}l@{\hspace{1mm}}l}
\bl{$\meta{E}$} & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}$}\\
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}+\meta{E}$}\\
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
& \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
\end{tabular}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Context Sensitive Grammars}
It is much harder to find out whether a string is parsed
by a context sensitive grammar:
\bl{\begin{plstx}[margin=2cm]
: \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\
: \meta{A} ::= a\\
: b\meta{A} ::= \meta{A}b\\
\end{plstx}}\pause
\begin{center}
\bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$}
\end{center}\pause
\begin{center}
\tt Time flies like an arrow;\\
fruit flies like bananas.
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Language of a CFG}
Let \bl{$G$} be a context-free grammar with start symbol \bl{\meta{S}}.
Then the language \bl{$L(G)$} is:
\begin{center}
\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge \meta{S} \rightarrow^* c_1\ldots c_n \}$}
\end{center}\pause
\begin{itemize}
\item Terminals, because there are no rules for replacing them.
\item Once generated, terminals are ``permanent''.
\item Terminals ought to be tokens of the language\\
(but can also be strings).
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Parse Trees}
\mbox{}\\[-12mm]
\bl{\begin{plstx}: \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} | \meta{T} \cdot - \cdot \meta{E}\\
: \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\
: \meta{F} ::= num\_token | ( \cdot \meta{E} \cdot )\\
\end{plstx}}
\begin{center}\small
\begin{tikzpicture}[level distance=8mm, blue]
\node {$\meta{E}$}
child {node {$\meta{T}$}
child {node {$\meta{T}$}
child {node {(\,$\meta{E}$\,)}
child {node{$\meta{F}$ *{} $\meta{F}$}
child {node {$\meta{T}$} child {node {2}}}
child {node {$\meta{T}$} child {node {3}}}
}
}
}
child {node {+}}
child {node {$\meta{T}$}
child {node {(\,$\meta{E}$\,)}
child {node {$\meta{F}$}
child {node {$\meta{T}$ +{} $\meta{T}$}
child {node {3}}
child {node {4}}
}
}}
}};
\end{tikzpicture}
\end{center}
\begin{textblock}{5}(1, 6.5)
\bl{\texttt{(2*3)+(3+4)}}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Arithmetic Expressions}
\bl{\begin{plstx}[margin=3cm,one per line]
: \meta{E} ::= num\_token
| \meta{E} \cdot + \cdot \meta{E}
| \meta{E} \cdot - \cdot \meta{E}
| \meta{E} \cdot * \cdot \meta{E}
| ( \cdot \meta{E} \cdot ) \\
\end{plstx}}\pause\bigskip
A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} such
that \bl{$\meta{E} \rightarrow^+ \meta{E}\cdot \ldots$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Ambiguous Grammars}
A grammar is \alert{\bf ambiguous} if there is a string that
has at least two different parse trees.
\bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::= num\_token
| \meta{E} \cdot + \cdot \meta{E}
| \meta{E} \cdot - \cdot \meta{E}
| \meta{E} \cdot * \cdot \meta{E}
| ( \cdot \meta{E} \cdot ) \\
\end{plstx}}
\bl{\texttt{1 + 2 * 3 + 4}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{`Dangling' Else}
Another ambiguous grammar:\bigskip
\begin{center}
\bl{\begin{tabular}{lcl}
$E$ & $\rightarrow$ & if $E$ then $E$\\
& $|$ & if $E$ then $E$ else $E$ \\
& $|$ & \ldots
\end{tabular}}
\end{center}\bigskip
\bl{\texttt{if a then if x then y else c}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Parser Combinators}
One of the simplest ways to implement a parser, see
{\small\url{https://vimeo.com/142341803}}\bigskip
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
\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 part
\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]
Function parser (code \bl{$p \Rightarrow 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]
\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{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{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{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{Abstract Parser Class}
\small
\lstinputlisting[language=Scala,xleftmargin=1mm]
{../progs/app7.scala}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\small
\fontsize{10}{12}\selectfont
\lstinputlisting[language=Scala,xleftmargin=1mm]
{../progs/app8.scala}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Two Grammars}
Which languages are recognised by the following two grammars?
\begin{center}
\bl{\begin{tabular}{lcl}
$\meta{S}$ & $\rightarrow$ & $1 \cdot \meta{S} \cdot \meta{S}$\\
& $|$ & $\epsilon$
\end{tabular}}
\end{center}\bigskip
\begin{center}
\bl{\begin{tabular}{lcl}
$\meta{U}$ & $\rightarrow$ & $1 \cdot \meta{U}$\\
& $|$ & $\epsilon$
\end{tabular}}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Ambiguous Grammars}
\begin{center}
\begin{tikzpicture}
\begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
enlargelimits=false,
xtick={0,100,...,1000},
xmax=1050,
ymax=33,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
width=11cm,
height=7cm,
legend entries={unambiguous,ambiguous},
legend pos=north east,
legend cell align=left,
x tick label style={font=\small,/pgf/number format/1000 sep={}}]
\addplot[blue,mark=*, mark options={fill=white}]
table {s-grammar1.data};
\only<2>{
\addplot[red,mark=triangle*, mark options={fill=white}]
table {s-grammar2.data};}
\end{axis}
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{While-Language}
\mbox{}\\[-23mm]\mbox{}
\bl{\begin{plstx}[rhs style=,one per line]: \meta{Stmt} ::= skip
| \meta{Id} := \meta{AExp}
| if \meta{BExp} then \meta{Block} else \meta{Block}
| while \meta{BExp} do \meta{Block}\\
: \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}
| \meta{Stmt}\\
: \meta{Block} ::= \{ \meta{Stmts} \}
| \meta{Stmt}\\
: \meta{AExp} ::= \ldots\\
: \meta{BExp} ::= \ldots\\\end{plstx}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{An Interpreter}
\begin{center}
\bl{\begin{tabular}{l}
$\{$\\
\;\;$x := 5 \text{;}$\\
\;\;$y := x * 3\text{;}$\\
\;\;$y := x * 4\text{;}$\\
\;\;$x := u * 3$\\
$\}$
\end{tabular}}
\end{center}
\begin{itemize}
\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
\item \bl{\texttt{eval(stmt, env)}}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Interpreter\end{tabular}}
\begin{center}
\bl{\begin{tabular}{@{}lcl@{}}
$\text{eval}(n, E)$ & $\dn$ & $n$\\
$\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\
$\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\
$\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\
$\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\
$\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\
$\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\
$\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\
\end{tabular}}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}
\begin{center}
\bl{\begin{tabular}{@{}lcl@{}}
$\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\
$\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\
\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;
\text{eval}(cs_1,E)$}\\
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\
\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;
\text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\
$\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\
\end{tabular}}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Test Program}
\mbox{}\\[-18mm]\mbox{}
{\lstset{language=While}%%\fontsize{10}{12}\selectfont
\texttt{\lstinputlisting{../progs/loops.while}}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}
\begin{center}
\begin{tikzpicture}
\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
\addplot+[smooth] file {interpreted.data};
\end{axis}
\end{tikzpicture}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}
\begin{itemize}
\item introduced in 1995
\item is a stack-based VM (like Postscript, CLR of .Net)
\item contains a JIT compiler
\item many languages take advantage of JVM's infrastructure (JRE)
\item is garbage collected $\Rightarrow$ no buffer overflows
\item some languages compile to the JVM: Scala, Clojure\ldots
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: