% !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}

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

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]

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}