diff -r 37b69593994c -r f7c7a75e0583 slides/slides01.tex --- a/slides/slides01.tex Mon Sep 07 12:27:08 2020 +0100 +++ b/slides/slides01.tex Tue Sep 15 23:13:45 2020 +0100 @@ -94,7 +94,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}<1-11>[c] +\begin{frame}<1-12>[c] \frametitle{The Goal of this Module\ldots} \begin{center} @@ -212,13 +212,28 @@ \only<10>{ \begin{textblock}{6}(1,3) \begin{bubble}[11cm] - Compiler explorers, e.g.: \url{https://gcc.godbolt.org} + 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''}; + \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} @@ -302,7 +317,202 @@ \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{A ``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}[c] + \frametitle{Recap} + + \begin{itemize} + \item interpreter \bl{\texttt{bfi.sc}} \\$\Rightarrow$ 11 mins\pause + \item simple compiler \bl{\texttt{bfi0.sc}}, no optimisations \\$\Rightarrow$ 20 secs\pause + \item ``advanced'' compiler \bl{\texttt{bfi1.sc}}, no optimisations \\$\Rightarrow$ 5 secs\bigskip\pause + + \item simple compiler \bl{\texttt{bfi0.sc}}, + \alert{\textbf{full optimisations}} \\$\Rightarrow$ 7 secs + \end{itemize}\bigskip\pause + + \hspace{4cm}all programs on KEATS + +\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{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 5 - 10} + + code generation for a small imperative and a small functional language\\[10mm] + + {\LARGE\bf Interpreters}\medskip\\ + \hspace{5mm}(directly runs a program)\\[6mm] + + {\LARGE\bf Compilers}\medskip\\ + \hspace{5mm}(generate JVM code and LLVM-IR code) + + \begin{textblock}{1}(8.8,8.1) + \begin{tabular}{c@{}c} + \includegraphics[scale=0.4]{../pics/javaduke.png} & + \includegraphics[scale=0.23]{../pics/llvmlogo.png} + \end{tabular} + \end{textblock} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Familiar Regular Expr.} +\small +\begin{center} +\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}} +\end{center}\smallskip + +\begin{center} +\begin{tabular}{@{}lp{8.5cm}@{}} +\pcode{re*} & matches 0 or more times\\ +\pcode{re+} & matches 1 or more times\\ +\pcode{re?} & matches 0 or 1 times\\ +\pcode{re\{n\}} & matches exactly \pcode{n} number of times\\ +\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\ +\pcode{[...]} & matches any single character inside the brackets\\ +\pcode{[^...]} & matches any single character not inside the +brackets\\ +\pcode{a-z A-Z} & character ranges\\ +\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\ +\pcode{.} & matches every character except newline\\ +\pcode{(re)} & groups regular expressions and remembers +the matched text +\end{tabular} +\end{center} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -470,156 +680,6 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{The Acad.~Subject is Mature} - -\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{What Do Compilers Do?} - -Remember BF*** from PEP? - -\begin{center} -\begin{tabular}{lcl} -\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}{lcl} - \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{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 5 - 10} - - code generation for a small imperative and a small functional language\\[10mm] - - {\LARGE\bf Interpreters}\medskip\\ - \hspace{5mm}(directly runs a program)\\[6mm] - - {\LARGE\bf Compilers}\medskip\\ - \hspace{5mm}(generate JVM code and LLVM-IR code) - - \begin{textblock}{1}(8.8,8.1) - \begin{tabular}{c@{}c} - \includegraphics[scale=0.4]{../pics/javaduke.png} & - \includegraphics[scale=0.23]{../pics/llvmlogo.png} - \end{tabular} - \end{textblock} - - \end{frame} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Familiar Regular Expr.} -\small -\begin{center} -\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}} -\end{center}\smallskip - -\begin{center} -\begin{tabular}{@{}lp{8.5cm}@{}} -\pcode{re*} & matches 0 or more times\\ -\pcode{re+} & matches 1 or more times\\ -\pcode{re?} & matches 0 or 1 times\\ -\pcode{re\{n\}} & matches exactly \pcode{n} number of times\\ -\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\ -\pcode{[...]} & matches any single character inside the brackets\\ -\pcode{[^...]} & matches any single character not inside the -brackets\\ -\pcode{a-z A-Z} & character ranges\\ -\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\ -\pcode{.} & matches every character except newline\\ -\pcode{(re)} & groups regular expressions and remembers -the matched text -\end{tabular} -\end{center} - - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\begin{frame}[c]