21 %% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect1/main.pdf |
23 %% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect1/main.pdf |
22 %% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect2/main.pdf |
24 %% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect2/main.pdf |
23 %% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect3/main.pdf |
25 %% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect3/main.pdf |
24 |
26 |
25 \begin{document} |
27 \begin{document} |
|
28 |
|
29 |
26 |
30 |
27 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
31 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
28 \begin{frame}[t] |
32 \begin{frame}[t] |
29 \frametitle{% |
33 \frametitle{% |
30 \begin{tabular}{@ {}c@ {}} |
34 \begin{tabular}{@ {}c@ {}} |
31 \\[-3mm] |
35 \\[-3mm] |
32 \LARGE Compilers and \\[-1mm] |
36 \LARGE Compilers and \\[-1mm] |
33 \LARGE Formal Languages (1)\\[-3mm] |
37 \LARGE Formal Languages\\[-3mm] |
34 \end{tabular}} |
38 \end{tabular}} |
35 |
39 |
36 \begin{center} |
40 \begin{center} |
37 %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} |
41 %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} |
38 %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ |
42 %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ |
41 |
45 |
42 \normalsize |
46 \normalsize |
43 \begin{center} |
47 \begin{center} |
44 \begin{tabular}{ll} |
48 \begin{tabular}{ll} |
45 Email: & christian.urban at kcl.ac.uk\\ |
49 Email: & christian.urban at kcl.ac.uk\\ |
46 Office Hours: & Thursdays 12 -- 14\\ |
50 %Office Hours: & Thursdays 12 -- 14\\ |
47 Location: & N7.07 (North Wing, Bush House)\\ |
51 %Location: & N7.07 (North Wing, Bush House)\\ |
48 Slides \& Progs: & KEATS\\ |
52 Slides \& Progs: & KEATS\\ |
49 \end{tabular} |
53 \end{tabular} |
50 \end{center} |
54 \end{center} |
51 |
55 |
|
56 \begin{center} |
|
57 \begin{tikzpicture} |
|
58 \node[drop shadow,fill=white,inner sep=0pt] |
|
59 {\footnotesize\rowcolors{1}{capri!10}{white} |
|
60 \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline |
|
61 \cellcolor{blue!50} |
|
62 1 Introduction, Languages & 6 While-Language \\ |
|
63 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ |
|
64 3 Automata, Regular Languages & 8 Compiling Functional Languages \\ |
|
65 4 Lexing, Tokenising & 9 Optimisations \\ |
|
66 5 Grammars, Parsing & 10 LLVM \\ \hline |
|
67 \end{tabular}% |
|
68 }; |
|
69 \end{tikzpicture} |
|
70 \end{center} |
|
71 |
52 \end{frame} |
72 \end{frame} |
53 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
54 |
74 |
55 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
56 \begin{frame}[t] |
76 \begin{frame}[t] |
57 \frametitle{Why Study Compilers?} |
77 \frametitle{Why Study Compilers?} |
58 |
78 |
59 John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}\smallskip\\ |
79 |
|
80 John Regehr {\small(Univ.~Utah, LLVM compiler hacker)} |
|
81 \here{https://blog.regehr.org/archives/1419} |
|
82 \smallskip\\ |
60 |
83 |
61 \begin{bubble}[10.5cm] |
84 \begin{bubble}[10.5cm] |
62 \bf ``\ldots{}It’s effectively a perpetual |
85 \bf ``\ldots{}It’s effectively a perpetual |
63 employment act for solid compiler hackers.'' |
86 employment act for solid compiler hackers.'' |
64 \end{bubble} |
87 \end{bubble} |
102 \begin{tikzpicture}[] |
125 \begin{tikzpicture}[] |
103 \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}}; |
126 \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}}; |
104 \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; |
127 \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; |
105 \draw [->,line width=4mm, red] (0) -- (1); |
128 \draw [->,line width=4mm, red] (0) -- (1); |
106 \node (2) [below=25mm] at (0) {\LARGE\bf``source''}; |
129 \node (2) [below=25mm] at (0) {\LARGE\bf``source''}; |
107 \node (3) [right=35mm] at (2) {\LARGE\bf``binary''}; |
130 \node (3) [right=40mm] at (2) {\LARGE\bf``binary''}; |
108 \draw [->,line width=1mm] (2) -- (3); |
131 \draw [->,line width=1mm] (2) -- (3); |
109 \end{tikzpicture} |
132 \end{tikzpicture} |
110 \end{center} |
133 \end{center} |
111 |
134 |
112 \begin{textblock}{10}(1,13.5) |
135 \begin{textblock}{12}(1,14.5) |
113 Compiler explorers, e.g.: \url{https://gcc.godbolt.org} |
136 Compiler explorers, e.g.: \url{https://gcc.godbolt.org} |
114 \end{textblock} |
137 \end{textblock} |
115 |
138 |
116 \end{frame} |
139 \end{frame} |
117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
294 \begin{center} |
317 \begin{center} |
295 \begin{tikzpicture}[scale=1, |
318 \begin{tikzpicture}[scale=1, |
296 node/.style={ |
319 node/.style={ |
297 rectangle,rounded corners=3mm, |
320 rectangle,rounded corners=3mm, |
298 very thick,draw=black!50,minimum height=18mm, minimum width=20mm, |
321 very thick,draw=black!50,minimum height=18mm, minimum width=20mm, |
299 top color=white,bottom color=black!20}] |
322 top color=white,bottom color=black!20,drop shadow}] |
300 |
323 |
301 \node at (3.05, 1.8) {\Large\bf write a compiler}; |
324 \node at (3.05, 1.8) {\Large\bf write a compiler}; |
302 |
325 |
303 \node (0) at (-2.3,0) {}; |
326 \node (0) at (-2.3,0) {}; |
304 \node [above=5mm of 0] |
327 \node [above=5mm of 0] |
954 \end{frame} |
977 \end{frame} |
955 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
978 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
956 |
979 |
957 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
980 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
958 \begin{frame}[c] |
981 \begin{frame}[c] |
|
982 \frametitle{Languages (Sets of Strings)} |
|
983 |
|
984 \begin{itemize} |
|
985 |
|
986 \item A \alert{\bf Language} is a set of strings, for example\medskip |
|
987 \begin{center} |
|
988 \bl{$\{[], hello, foobar, a, abc\}$} |
|
989 \end{center}\bigskip |
|
990 |
|
991 \item \alert{\bf Concatenation} for strings and languages |
|
992 |
|
993 \begin{center} |
|
994 \begin{tabular}{rcl} |
|
995 \bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\ |
|
996 \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} |
|
997 \end{tabular} |
|
998 \end{center} |
|
999 \bigskip |
|
1000 |
|
1001 \small |
|
1002 \item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$} |
|
1003 |
|
1004 \[ |
|
1005 \bl{A \,@\, B = \{fooa, foob, bara, barb\}} |
|
1006 \] |
|
1007 |
|
1008 \end{itemize} |
|
1009 \end{frame} |
|
1010 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1011 |
|
1012 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1013 \begin{frame}[c] |
|
1014 \frametitle{Two Corner Cases} |
|
1015 |
|
1016 \Large |
|
1017 \begin{center} |
|
1018 \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ |
|
1019 \bl{$A \,@\, \{\} = \;?$} |
|
1020 \end{center} |
|
1021 |
|
1022 \end{frame} |
|
1023 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1024 |
|
1025 |
|
1026 |
|
1027 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1028 \begin{frame}[c] |
|
1029 \frametitle{ |
|
1030 The Meaning of a\\[-2mm] |
|
1031 Regular Expression} |
|
1032 |
|
1033 ...all the strings a regular expression can match. |
|
1034 |
|
1035 \begin{center} |
|
1036 \begin{tabular}{rcl} |
|
1037 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
|
1038 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
1039 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
|
1040 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
|
1041 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
|
1042 \bl{$L(r^*)$} & \bl{$\dn$} & \\ |
|
1043 \end{tabular} |
|
1044 \end{center} |
|
1045 |
|
1046 \begin{textblock}{14}(1.5,13.5)\small |
|
1047 \bl{$L$} is a function from regular expressions to |
|
1048 sets of strings (languages):\smallskip\\ |
|
1049 \bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
|
1050 \end{textblock} |
|
1051 |
|
1052 \end{frame} |
|
1053 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1054 |
|
1055 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1056 \begin{frame}[c] |
|
1057 \frametitle{The Power Operation} |
|
1058 |
|
1059 \begin{itemize} |
|
1060 \item The \alert{\textbf{\boldmath$n$th Power}} of a language: |
|
1061 |
|
1062 \begin{center} |
|
1063 \begin{tabular}{lcl} |
|
1064 \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
1065 \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} |
|
1066 \end{tabular} |
|
1067 \end{center}\bigskip |
|
1068 |
|
1069 \item[] For example |
|
1070 |
|
1071 \begin{center} |
|
1072 \begin{tabular}{lcl@{\hspace{10mm}}l} |
|
1073 \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ |
|
1074 \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ |
|
1075 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ |
|
1076 \end{tabular} |
|
1077 \end{center} |
|
1078 |
|
1079 \end{itemize} |
|
1080 |
|
1081 \end{frame} |
|
1082 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1083 |
|
1084 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1085 \begin{frame}[c] |
959 \frametitle{The Star Operation} |
1086 \frametitle{The Star Operation} |
960 |
1087 |
961 \begin{itemize} |
1088 \begin{itemize} |
962 \item The \alert{\bf Kleene Star} of a \underline{language}: |
1089 \item The \alert{\bf Kleene Star} of a \underline{language}: |
963 \bigskip |
1090 \bigskip |