71 |
71 |
72 \end{frame} |
72 \end{frame} |
73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
74 |
74 |
75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
76 \begin{frame}<1-11>[c] |
|
77 \frametitle{The Goal of this Module\ldots} |
|
78 |
|
79 \begin{center} |
|
80 \begin{tikzpicture}[scale=1, |
|
81 node/.style={ |
|
82 rectangle,rounded corners=3mm, |
|
83 very thick,draw=black!50,minimum height=18mm, minimum width=20mm, |
|
84 top color=white,bottom color=black!20,drop shadow}] |
|
85 |
|
86 \node at (3.05, 1.8) {\Large\bf \ldots{} you write a compiler}; |
|
87 |
|
88 \node (0) at (-2.3,0) {}; |
|
89 \node [above=5mm of 0] |
|
90 {\makebox[0mm]{\footnotesize |
|
91 \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; |
|
92 |
|
93 \node (A) at (0,0) [node] {}; |
|
94 \node [below right] at (A.north west) {lexer}; |
|
95 |
|
96 \node (B) at (3,0) [node] {}; |
|
97 \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; |
|
98 |
|
99 \node (C) at (6,0) [node] {}; |
|
100 \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; |
|
101 |
|
102 \node (1) at (8.4,0) {}; |
|
103 \node [above=5mm of 1] |
|
104 {\makebox[0mm]{\footnotesize |
|
105 \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}}; |
|
106 |
|
107 \draw [->,line width=4mm] (0) -- (A); |
|
108 \draw [->,line width=4mm] (A) -- (B); |
|
109 \draw [->,line width=4mm] (B) -- (C); |
|
110 \draw [->,line width=4mm] (C) -- (1); |
|
111 \end{tikzpicture} |
|
112 \end{center} |
|
113 |
|
114 \only<2,3,4>{ |
|
115 \begin{textblock}{1}(1,2.1) |
|
116 \begin{bubble}[9.8cm] |
|
117 \normalsize |
|
118 lexer input: a string\smallskip\\ |
|
119 \hspace{5mm}\code{"read(n);"}\medskip\\ |
|
120 lexer output: a sequence of tokens\smallskip\\ |
|
121 \hspace{5mm}\code{key(read) lpar id(n) rpar semi} |
|
122 \end{bubble} |
|
123 \end{textblock}} |
|
124 |
|
125 \only<3,4>{ |
|
126 \begin{textblock}{1}(6,7.8) |
|
127 \begin{tabular}{c} |
|
128 \includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm] |
|
129 \footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta) |
|
130 \end{tabular} |
|
131 \end{textblock}} |
|
132 |
|
133 \only<4>{ |
|
134 \begin{textblock}{1}(0.5,12)\small |
|
135 \begin{tabular}{l@{}c@{}l} |
|
136 \pcode{if} & $\;\Rightarrow\;$ & keyword\\ |
|
137 \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\ |
|
138 \end{tabular} |
|
139 \end{textblock}} |
|
140 |
|
141 \only<6>{ |
|
142 \begin{textblock}{1}(1,1.5) |
|
143 \begin{bubble}[8.5cm] |
|
144 \normalsize |
|
145 parser input: a sequence of tokens\smallskip\\ |
|
146 |
|
147 {\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\ |
|
148 |
|
149 parser output: an abstract syntax tree\smallskip\\ |
|
150 \footnotesize |
|
151 \hspace{2cm}\begin{tikzpicture} |
|
152 \node {\code{read}} |
|
153 child {node {\code{lpar}}} |
|
154 child {node {\code{n}}} |
|
155 child {node {\code{rpar}}}; |
|
156 \end{tikzpicture} |
|
157 \end{bubble} |
|
158 \end{textblock}} |
|
159 |
|
160 \only<8,9>{ |
|
161 \begin{textblock}{1}(1,1.5) |
|
162 \begin{bubble}[4cm] |
|
163 \normalsize |
|
164 code generation:\smallskip\\ |
|
165 \hspace{5mm}\code{istore 2}\\ |
|
166 \hspace{5mm}\code{iload 2}\\ |
|
167 \hspace{5mm}\code{ldc 10}\\ |
|
168 \hspace{5mm}\code{isub}\\ |
|
169 \hspace{5mm}\code{ifeq Label2}\\ |
|
170 \hspace{5mm}\code{iload 2}\\ |
|
171 \hspace{5mm}\code{...}\\ |
|
172 \end{bubble} |
|
173 \end{textblock}} |
|
174 |
|
175 \only<9>{ |
|
176 \begin{textblock}{6}(8.4,7) |
|
177 \begin{bubble}[5cm] |
|
178 \mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm] |
|
179 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
|
180 xlabel=n, |
|
181 enlargelimits=0.05, |
|
182 ybar interval=0.7, legend style=small] |
|
183 \addplot file {interpreted2.data}; |
|
184 \addplot file {compiled2.data}; |
|
185 %\legend{interpreted, compiled} |
|
186 \end{axis} |
|
187 \end{tikzpicture}} |
|
188 \end{bubble} |
|
189 \end{textblock}} |
|
190 |
|
191 \only<10>{ |
|
192 \begin{textblock}{6}(1,3) |
|
193 \begin{bubble}[11cm] |
|
194 Compiler explorers, e.g.: \url{https://gcc.godbolt.org} |
|
195 \begin{tikzpicture}[] |
|
196 \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}}; |
|
197 \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; |
|
198 \draw [->,line width=4mm, red] (0) -- (1); |
|
199 \node (2) [below=20mm] at (0) {\LARGE\bf``source''}; |
|
200 \node (3) [right=40mm] at (2) {\LARGE\bf``binary''}; |
|
201 \draw [->,line width=1mm] (2) -- (3); |
|
202 \end{tikzpicture} |
|
203 \end{bubble} |
|
204 \end{textblock}} |
|
205 |
|
206 |
|
207 \end{frame} |
|
208 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
209 |
|
210 |
|
211 |
|
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
76 \begin{frame}[t] |
213 \begin{frame}[t] |
77 \frametitle{Why Study Compilers?} |
214 \frametitle{Why Study Compilers?} |
78 |
215 |
79 |
216 |
80 John Regehr {\small(Univ.~Utah, LLVM compiler hacker)} |
217 John Regehr {\small(Univ.~Utah, LLVM compiler hacker)} |
115 \end{itemize}}} |
252 \end{itemize}}} |
116 |
253 |
117 \end{frame} |
254 \end{frame} |
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
119 |
256 |
120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
257 |
121 \begin{frame}[t] |
258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
122 \frametitle{What are Compilers?} |
259 \begin{frame}[c] |
123 |
260 \frametitle{Why Bother with Compilers?} |
124 \begin{center} |
261 |
125 \begin{tikzpicture}[] |
262 \textbf{Boeings 777}: First flight in 1994. They want to achieve |
126 \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}}; |
263 triple redundancy in hardware faults.\bigskip |
127 \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; |
|
128 \draw [->,line width=4mm, red] (0) -- (1); |
|
129 \node (2) [below=25mm] at (0) {\LARGE\bf``source''}; |
|
130 \node (3) [right=40mm] at (2) {\LARGE\bf``binary''}; |
|
131 \draw [->,line width=1mm] (2) -- (3); |
|
132 \end{tikzpicture} |
|
133 \end{center} |
|
134 |
|
135 \begin{textblock}{12}(1,14.5) |
|
136 Compiler explorers, e.g.: \url{https://gcc.godbolt.org} |
|
137 \end{textblock} |
|
138 |
|
139 \end{frame} |
|
140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
141 |
|
142 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
143 \begin{frame}[c] |
|
144 \frametitle{\begin{tabular}{c}Why Bother?\\[-2mm] Compilers \& Boeings 777\end{tabular}} |
|
145 |
|
146 First flight in 1994. They want to achieve triple redundancy in hardware |
|
147 faults.\bigskip |
|
148 |
264 |
149 They compile 1 Ada program to\medskip |
265 They compile 1 Ada program to\medskip |
150 |
266 |
151 \begin{itemize} |
267 \begin{itemize} |
152 \item Intel 80486 |
268 \item Intel 80486 |
310 \end{frame} |
426 \end{frame} |
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
427 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
312 |
428 |
313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
429 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
314 \begin{frame}[c] |
430 \begin{frame}[c] |
315 \frametitle{The Goal of this Module} |
|
316 |
|
317 \begin{center} |
|
318 \begin{tikzpicture}[scale=1, |
|
319 node/.style={ |
|
320 rectangle,rounded corners=3mm, |
|
321 very thick,draw=black!50,minimum height=18mm, minimum width=20mm, |
|
322 top color=white,bottom color=black!20,drop shadow}] |
|
323 |
|
324 \node at (3.05, 1.8) {\Large\bf write a compiler}; |
|
325 |
|
326 \node (0) at (-2.3,0) {}; |
|
327 \node [above=5mm of 0] |
|
328 {\makebox[0mm]{\footnotesize |
|
329 \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; |
|
330 |
|
331 \node (A) at (0,0) [node] {}; |
|
332 \node [below right] at (A.north west) {lexer}; |
|
333 |
|
334 \node (B) at (3,0) [node] {}; |
|
335 \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; |
|
336 |
|
337 \node (C) at (6,0) [node] {}; |
|
338 \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; |
|
339 |
|
340 \node (1) at (8.4,0) {}; |
|
341 \node [above=5mm of 1] |
|
342 {\makebox[0mm]{\footnotesize |
|
343 \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}}; |
|
344 |
|
345 \draw [->,line width=4mm] (0) -- (A); |
|
346 \draw [->,line width=4mm] (A) -- (B); |
|
347 \draw [->,line width=4mm] (B) -- (C); |
|
348 \draw [->,line width=4mm] (C) -- (1); |
|
349 \end{tikzpicture} |
|
350 \end{center} |
|
351 |
|
352 \only<2,3,4>{ |
|
353 \begin{textblock}{1}(1,2.1) |
|
354 \begin{bubble}[9.8cm] |
|
355 \normalsize |
|
356 lexer input: a string\smallskip\\ |
|
357 \hspace{5mm}\code{"read(n);"}\medskip\\ |
|
358 lexer output: a sequence of tokens\smallskip\\ |
|
359 \hspace{5mm}\code{key(read) lpar id(n) rpar semi} |
|
360 \end{bubble} |
|
361 \end{textblock}} |
|
362 |
|
363 \only<3,4>{ |
|
364 \begin{textblock}{1}(6,7.8) |
|
365 \begin{tabular}{c} |
|
366 \includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm] |
|
367 \footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta) |
|
368 \end{tabular} |
|
369 \end{textblock}} |
|
370 |
|
371 \only<4>{ |
|
372 \begin{textblock}{1}(0.5,12)\small |
|
373 \begin{tabular}{l@{}c@{}l} |
|
374 \pcode{if} & $\;\Rightarrow\;$ & keyword\\ |
|
375 \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\ |
|
376 \end{tabular} |
|
377 \end{textblock}} |
|
378 |
|
379 \only<5>{ |
|
380 \begin{textblock}{1}(1,1.5) |
|
381 \begin{bubble}[8.5cm] |
|
382 \normalsize |
|
383 parser input: a sequence of tokens\smallskip\\ |
|
384 |
|
385 {\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\ |
|
386 |
|
387 parser output: an abstract syntax tree\smallskip\\ |
|
388 \footnotesize |
|
389 \hspace{2cm}\begin{tikzpicture} |
|
390 \node {\code{read}} |
|
391 child {node {\code{lpar}}} |
|
392 child {node {\code{n}}} |
|
393 child {node {\code{rpar}}}; |
|
394 \end{tikzpicture} |
|
395 \end{bubble} |
|
396 \end{textblock}} |
|
397 |
|
398 \only<6,7>{ |
|
399 \begin{textblock}{1}(1,1.5) |
|
400 \begin{bubble}[4cm] |
|
401 \normalsize |
|
402 code generator:\smallskip\\ |
|
403 \hspace{5mm}\code{istore 2}\\ |
|
404 \hspace{5mm}\code{iload 2}\\ |
|
405 \hspace{5mm}\code{ldc 10}\\ |
|
406 \hspace{5mm}\code{isub}\\ |
|
407 \hspace{5mm}\code{ifeq Label2}\\ |
|
408 \hspace{5mm}\code{iload 2}\\ |
|
409 \hspace{5mm}\code{...}\\ |
|
410 \end{bubble} |
|
411 \end{textblock}} |
|
412 |
|
413 \only<7>{ |
|
414 \begin{textblock}{6}(8.4,7) |
|
415 \begin{bubble}[5cm] |
|
416 \mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm] |
|
417 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
|
418 xlabel=n, |
|
419 enlargelimits=0.05, |
|
420 ybar interval=0.7, legend style=small] |
|
421 \addplot file {interpreted2.data}; |
|
422 \addplot file {compiled2.data}; |
|
423 %\legend{interpreted, compiled} |
|
424 \end{axis} |
|
425 \end{tikzpicture}} |
|
426 \end{bubble} |
|
427 \end{textblock}} |
|
428 |
|
429 \end{frame} |
|
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
431 |
|
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
433 \begin{frame}[c] |
|
434 \frametitle{The Acad.~Subject is Mature} |
431 \frametitle{The Acad.~Subject is Mature} |
435 |
432 |
436 \bigskip |
433 \bigskip |
437 \begin{itemize} |
434 \begin{itemize} |
438 \item Turing Machines, 1936 (a tape as memory) |
435 \item Turing Machines, 1936 (a tape as memory) |