% !TEX program = xelatex

\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

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

\hfuzz=220pt 

\lstset{language=Scala,

        style=mystyle,

        numbersep=0pt,

        numbers=none,

        xleftmargin=0mm}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}     

% beamer stuff 

\renewcommand{\slidecaption}{CFL 01, King's College London}

%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect1/main.pdf

%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect2/main.pdf

%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect3/main.pdf

\begin{document}

%\begin{frame}[t]

%\begin{mybox}

%A physical explanation the \emph{dynamic matrix}\\

%lots of text

%\end{mybox}

%\begin{mybox2}{Test}

%A physical explanation the \emph{dynamic matrix}\\

%lots of text

%\end{mybox2}

%\begin{mybox3}{Test}

%A physical explanation the \emph{dynamic matrix}\\

%lots of text

%\end{mybox3}

%\end{frame}

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

\begin{frame}[t]

\frametitle{%  

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

  \\[-3mm]

  \LARGE Compilers and \\[-1mm] 

  \LARGE Formal Languages\\[-3mm] 

  \end{tabular}}

  \begin{center}

  %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}

  %\includegraphics[scale=0.31]{pics/ante2.jpg}\\

  %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}

  \end{center}

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

  \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

          \cellcolor{blue!50}

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

          5 Grammars, Parsing                & 10 LLVM \\ \hline

        \end{tabular}%

      };

    \end{tikzpicture}

  \end{center}

\end{frame}

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

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

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

\frametitle{The Goal of this Module\ldots}

\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 at (3.05, 1.8) {\Large\bf \ldots{} you write a compiler};

  \node (0) at (-2.3,0) {};  

  \node [above=5mm of 0]

  {\makebox[0mm]{\footnotesize

      \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; 

  \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) {};

  \node [above=5mm of 1]

  {\makebox[0mm]{\footnotesize

      \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};

  \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,3,4>{

\begin{textblock}{1}(1,2.1)

\begin{bubble}[9.8cm]

\normalsize

lexer input: a string\smallskip\\

\hspace{5mm}\code{"read(n);"}\medskip\\

lexer output: a sequence of tokens\smallskip\\

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

\end{bubble}

\end{textblock}} 

\only<3,4>{

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

\begin{tabular}{c}

\includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm]

\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)

\end{tabular}

\end{textblock}}

\only<4>{

\begin{textblock}{1}(0.5,12)\small

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

  \pcode{if}    & $\;\Rightarrow\;$ & keyword\\

  \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\

\end{tabular}  

\end{textblock}}

\only<6>{

\begin{textblock}{1}(1,1.5)

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

\only<8,9>{

\begin{textblock}{1}(1,1.5)

\begin{bubble}[4cm]

\normalsize

code generation:\smallskip\\

\hspace{5mm}\code{istore 2}\\ 

\hspace{5mm}\code{iload 2}\\ 

\hspace{5mm}\code{ldc 10}\\

\hspace{5mm}\code{isub}\\

\hspace{5mm}\code{ifeq Label2}\\ 

\hspace{5mm}\code{iload 2}\\

\hspace{5mm}\code{...}\\

\end{bubble}

\end{textblock}}

\only<9>{

\begin{textblock}{6}(8.4,7)

\begin{bubble}[5cm]

\mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm]

\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,

    xlabel=n,

    enlargelimits=0.05,

    ybar interval=0.7, legend style=small]

\addplot file {interpreted2.data};

\addplot file {compiled2.data};

%\legend{interpreted, compiled}

\end{axis}

\end{tikzpicture}}

\end{bubble}

\end{textblock}}

\only<10>{

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

  \begin{bubble}[11cm]

    Compiler explorers, e.g.: \url{https://gcc.godbolt.org} \;\video{https://youtu.be/ysaBmhMEyUg}

  \begin{tikzpicture}[]

  \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}};

  \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; 

  \draw [->,line width=4mm, red] (0) -- (1);   

  \node (2) [below=20mm] at (0) {\LARGE\bf source};

  \node (3) [right=40mm] at (2) {\LARGE\bf binary};

  \draw [->,line width=1mm] (2) -- (3);   

\end{tikzpicture}

\end{bubble}

\end{textblock}}

\only<11>{

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

  \begin{bubble}[11cm]

    Compiler explorer for Java: \url{https://javap.yawk.at} 

  \begin{tikzpicture}[]

  \node (0) at (-2.3,0) {\includegraphics[scale=0.4]{pics/jsource.png}};

  \node (1) [right=35mm] at (0) {\includegraphics[scale=0.4]{pics/jassmbl.png}}; 

  \draw [->,line width=4mm, red] (0) -- (1);   

  \node (2) [below=20mm] at (0) {\LARGE\bf source};

  \node (3) [right=40mm] at (2) {\LARGE\bf byte code};

  \draw [->,line width=1mm] (2) -- (3);   

\end{tikzpicture}

\end{bubble}

\end{textblock}}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Why Study Compilers?}

John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}

\here{https://blog.regehr.org/archives/1419}

\smallskip\\

\begin{bubble}[10.5cm]

  \bf ``\ldots{}It’s effectively a perpetual

  employment act for solid compiler hackers.''

\end{bubble}

\onslide<1->{

\only<2>{

\begin{itemize}

\item {\bf Hardware is getting weirder

  rather than getting clocked faster.}

\begin{itemize}

\item[]  ``Almost all processors are multicores nowadays and it looks

  like there is increasing asymmetry in resources across cores.

  Processors come with vector units, crypto accelerators etc. We have

  DSPs, GPUs, ARM big.little, and Xeon Phi. This is only scratching the

  surface.''

\end{itemize}  

\end{itemize}}

\only<3>{

\begin{itemize}

\item {\bf We’re getting tired of low-level languages and

    their associated security disasters.}

\begin{itemize}

\item [] ``We want to write new code, to whatever extent possible, in

  safer, higher-level languages. Compilers are caught right in the

  middle of these opposing trends: one of their main jobs is to help

  bridge the large and growing gap between increasingly high-level

  languages and increasingly wacky platforms.''

\end{itemize}  

\end{itemize}}}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Why Bother with Compilers?}

\textbf{Boeing 777's}: First flight in 1994. They want to achieve

triple redundancy for potential hardware faults.

\here{http://www.citemaster.net/get/db3a81c6-548e-11e5-9d2e-00163e009cc7/R8.pdf}\bigskip

They compile 1 Ada program to\medskip

\begin{itemize}

  \item Intel 80486

  \item Motorola 68040 (old Macintosh's)

  \item AMD 29050 (RISC chips used often in laser printers)

\end{itemize}\medskip\medskip

using 3 independent compilers.\bigskip\pause

\small Airbus uses C and static analysers. Recently started using CompCert.

\only<1->{%

\begin{textblock}{6}(8,4.5)

\includegraphics[scale=0.28]{../pics/777.png}

\end{textblock}}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{What Do Compilers Do?}

Remember BF*** from PEP?

\begin{center}

\begin{tabular}{rcl}

\bl{\texttt{>}} & $\Rightarrow$ & move one cell right\\

\bl{\texttt{<}} & $\Rightarrow$ & move one cell left\\

\bl{\texttt{+}} & $\Rightarrow$ & increase cell by one\\

\bl{\texttt{-}} & $\Rightarrow$ & decrease cell by one\\

\bl{\texttt{.}} & $\Rightarrow$ & print current cell\\

\bl{\texttt{,}} & $\Rightarrow$ & input current cell\\

\bl{\texttt{[}} & $\Rightarrow$ & loop begin\\

\bl{\texttt{]}} & $\Rightarrow$ & loop end\medskip\\

                & $\Rightarrow$ & everything else is a comment\\

\end{tabular}  

\end{center}  

\end{frame}

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

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

\begin{frame}[c]

  \frametitle{A ``Compiler'' for BF*** to C}

  \begin{center}

  \begin{tabular}{rcl}

  \bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\

  \bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\

  \bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\

  \bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\

  \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\

  \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\

  \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\

  \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\

                  & $\Rightarrow$ & ignore everything else\\

  \end{tabular}  

  \end{center}\bigskip  

  \texttt{char field[30000]\\ char *ptr = \&field[15000]}

\end{frame}

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

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

\begin{frame}[c]

  \frametitle{Another~``Compiler''~for~BF~to~C}

  \begin{center}

  \begin{tabular}{rcl}

  \bl{\texttt{>\ldots>}} & $\Rightarrow$ & \texttt{ptr += n}\\

  \bl{\texttt{<\ldots<}} & $\Rightarrow$ & \texttt{ptr -= n}\\

  \bl{\texttt{+\ldots+}} & $\Rightarrow$ & \texttt{(*ptr) += n}\\

  \bl{\texttt{-\ldots-}} & $\Rightarrow$ & \texttt{(*ptr) -= n}\\

  \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\

  \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\

  \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\

  \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\

                  & $\Rightarrow$ & ignore everything else\\

  \end{tabular}  

  \end{center}\bigskip  

  \texttt{char field[30000]\\ char *ptr = \&field[15000]}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{A Brief Compiler History}

\bigskip

\begin{itemize}

\item Turing Machines, 1936 (a tape as memory)

\item Regular Expressions, 1956\\

\item The first compiler for COBOL, 1957\\ (Grace Hopper)\medskip

\item But surprisingly research papers are still published nowadays\\

\item ``Parsing: The Solved Problem That Isn't''

  \here{https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html}

\end{itemize}

\begin{textblock}{8.5}(5,7.6)

\begin{flushright}

\includegraphics[scale=0.3]{pics/hopper.jpg}\\

\footnotesize\textcolor{gray}{Grace Hopper}\smallskip\\

{\small\textcolor{gray}{(she made it to David Letterman's Tonight Show

 \here{https://youtu.be/3N_ywhx6_K0?t=31})}}

\end{flushright}

\end{textblock}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Some Housekeeping}

\textbf{Exams will be online:}\bigskip

\begin{itemize}

\item final exam in January (30\%)

\item mid-term shortly after Reading Week (10\%)\bigskip

\item weekly engagement (10\%)  

\end{itemize}\bigskip\bigskip\pause

\textbf{Weekly Homework (optional):}

\begin{itemize}

\item uploaded on KEATS, send answers via email, responded individually

\item \alert{\bf all} questions in the exam and mid-term will be from the HW!!

\end{itemize}  

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Some Housekeeping}

\textbf{Coursework (5 accounting for 45\%):}\bigskip

\begin{itemize}

\item matcher (5\%)

\item lexer (8\%)

\item parser / interpreter (10\%)

\item JVM compiler (10\%)

\item LLVM compiler (12\%) 

\end{itemize}\bigskip\pause

you can use any programming language you like (Haskell, Rust)\\\pause

you can use any code I showed you and uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!}\pause

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Lectures 1 - 5}

transforming strings into structured data\\[10mm]

{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\

\hspace{5mm}(recognising ``words'')\\[6mm]

{\LARGE\bf Parsing}\medskip\\

\hspace{5mm}(recognising ``sentences'')

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

\begin{tabular}{c}

\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]

\footnotesize Stone of Rosetta

\end{tabular}

\end{textblock}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Lectures 1 - 5}

transforming strings into structured data\\[10mm]