% !TEX program = xelatex

\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{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}

\usepackage{tcolorbox}

\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}

\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}

\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{%

  \begin{tabular}{@ {}c@ {}}

  \\[-3mm]

  \LARGE Compilers and \\[-2mm] 

  \LARGE Formal Languages\\[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}

  \begin{center}

    \begin{tikzpicture}

      \node[drop shadow,fill=white,inner sep=0pt] 

      {\footnotesize\rowcolors{1}{capri!10}{white}

        \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline

          1 Introduction, Languages          & 6 While-Language \\

          2 Regular Expressions, Derivatives & 7 Compilation, JVM \\

          3 Automata, Regular Languages      & 8 Compiling Functional Languages \\

          4 Lexing, Tokenising               & 9 Optimisations \\

          \cellcolor{blue!50}

          5 Grammars, Parsing                & 10 LLVM \\ \hline

        \end{tabular}%

      };

    \end{tikzpicture}

  \end{center}

\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. BTW, simp 

%  can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}!

%  \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{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,drop shadow}]

  \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}

\only<2>{

\begin{textblock}{1}(3,6)

\begin{bubble}[8.5cm]

\normalsize

parser input: a sequence of tokens\smallskip\\

{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\

parser output: an abstract syntax tree\smallskip\\

\footnotesize

\hspace{2cm}\begin{tikzpicture}

  \node {\code{read}}

    child {node {\code{lpar}}}

    child {node {\code{n}}}

    child {node {\code{rpar}}};

\end{tikzpicture}

\end{bubble}

\end{textblock}}

\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]

  \LARGE

  \begin{center}

  Time flies like an arrow.\\ 

  Fruit flies like bananas.

  \end{center}  

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{CFGs}

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\}$}:

\only<1>{%

\bl{\begin{plstx}[margin=1cm]

: \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}}}

%

\only<2>{%

\bl{\begin{plstx}[margin=1cm]

: \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\

\end{plstx}}}

%\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} ::=  0 \mid 1 \mid 2 \mid ... \mid 9

   | \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} ::=  0 \mid 1 \mid 2 \mid ... \mid 9

   | \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{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} ::= 0 ... 9 | ( \cdot \meta{E} \cdot )\\

\end{plstx}}

\begin{textblock}{5}(6, 5)

\small

\begin{tikzpicture}[level distance=10mm, blue]

  \node {$\meta{E}$}

  child {node {$\meta{T}$}

    child {node {$\meta{F}$} child {node {1}}}

  }

  child {node {+}}

  child {node {$\meta{E}$}

    child[sibling distance=10mm] {node {$\meta{T}$}

      child {node {$\meta{F}$} child {node {2}}}

      child {node {*}}

      child {node {$\meta{T}$} child {node {$\meta{F}$} child {node {3}}}}

    }

    child {node {+}}

    child {node {$\meta{E}$} child {node {$\meta{T}$}

        child {node {$\meta{F}$} child {node {4}}}}}

  } 

  ;

\end{tikzpicture}

\end{textblock}

\begin{textblock}{5}(1, 10)

\bl{\texttt{1 + 2 * 3 + 4}}

\end{textblock}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Arithmetic Expressions}

\bl{\begin{plstx}[margin=3cm,one per line]

: \meta{E} ::=  0..9 

   | \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} ::=  0 ... 9 

   | \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{CYK Algorithm}

Suppose the grammar:

\begin{center}

\bl{\begin{tabular}{@ {}lcl@ {}}

$\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\

$\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\

$\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\

$\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\

$\meta{V}$ & $::=$ &  $\texttt{trains}$ 

\end{tabular}}