% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphicss}
\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 \\[-1mm] 
  \LARGE Formal Languages\\[-5mm] 
  \end{tabular}}

  \normalsize
  \begin{center}
  \begin{tabular}{ll}
  Email:  & christian.urban at kcl.ac.uk\\
  Office Hour: & Fridays 11 -- 12\\
  Location: & N7.07 (North Wing, Bush House)\\
  Slides \& Progs: & KEATS\\
  Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\  
  \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}}
\end{center}

\bl{\texttt{Jeff trains geometry students}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{CYK Algorithm}

\begin{center}
  \begin{tikzpicture}[scale=1,line width=0.8mm]
  \draw (-2,0) -- (2,0);
  \draw (-2,1) -- (2,1);
  \draw (-2,2) -- (1,2);
  \draw (-2,3) -- (0,3);
  \draw (-2,4) -- (-1,4);
  
  \draw (0,0) -- (0, 3);
  \draw (1,0) -- (1, 2);
  \draw (2,0) -- (2, 1);
  \draw (-1,0) -- (-1, 4);
  \draw (-2,0) -- (-2, 4);
  
  \draw (-1.5,-0.5) node {\footnotesize{}\texttt{Jeff}}; 
  \draw (-0.5,-1.0) node {\footnotesize{}\texttt{trains}}; 
  \draw ( 0.5,-0.5) node {\footnotesize{}\texttt{geometry}}; 
  \draw ( 1.5,-1.0) node {\footnotesize{}\texttt{students}}; 
  
  \draw (-1.5,0.5) node {$N$}; 
  \draw (-0.5,0.5) node {$N,V$}; 
  \draw ( 0.5,0.5) node {$N$}; 
  \draw ( 1.5,0.5) node {$N$}; 

  \draw (-2.4, 3.5) node {$1$}; 
  \draw (-2.4, 2.5) node {$2$}; 
  \draw (-2.4, 1.5) node {$3$}; 
  \draw (-2.4, 0.5) node {$4$}; 
  \end{tikzpicture}
  \end{center}

\begin{textblock}{5}(10,10)
\small\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}}  
\end{textblock}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Chomsky Normal Form}

A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:

\bl{\begin{plstx}[margin=0cm]
: \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a\cdot a | b\cdot b | a | b \\
\end{plstx}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{CYK Algorithm}


\begin{itemize}
\item fastest possible algorithm for recognition problem
\item runtime is \bl{$O(n^3)$}\bigskip
\item grammars need to be transformed into CNF
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
  \begin{mybox3}{}\it 
    "The C++ grammar is ambiguous, context-dependent and potentially
    requires infinite lookahead to resolve some ambiguities."
  \end{mybox3}\bigskip


  \hfill from the \href{http://www.computing.surrey.ac.uk/research/dsrg/fog/FogThesis.pdf}{PhD thesis} by Willink (2001)
  
  \small
  \begin{center}
  \begin{lstlisting}[language={},numbers=none]
    int(x), y, *const z;
    int(x), y, new int;
  \end{lstlisting}
  \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}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\begin{frame}[t,fragile]
\begin{mybox3}{}
  For CW2, please include '$\backslash$' as a symbol in strings, because
  the collatz program contains
  \begin{lstlisting}[language=Scala, numbers=none]
  write "\n";\end{lstlisting}  
\end{mybox3}
\end{frame}

\begin{frame}[t]
\begin{mybox3}{}
  val (r1s, f1s) = simp(r1)\\
  val (r2s, f2s) = simp(r2)\\
  how are the
  first rectification functions f1s and f2s made? could you maybe
  show an example?
\end{mybox3}
\end{frame}

\begin{frame}<1-24>[c]
\end{frame}


\end{document}

%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: