41 \begin{document} |
41 \begin{document} |
42 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019} |
42 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019} |
43 |
43 |
44 \section*{Handout 1} |
44 \section*{Handout 1} |
45 |
45 |
|
46 The purpose of a compiler is to transform a program a human can read |
|
47 and write into code the machine can run as fast as |
|
48 possible. Developping a compiler is an old craft going back to 1952 |
|
49 with the first compiler written by Grace Hopper. Why studiying |
|
50 compilers nowadays? An interesting answer is given by John Regher in |
|
51 his compiler |
|
52 blog:\footnote{\url{http://blog.regehr.org/archives/1419}} |
|
53 |
|
54 \begin{quote}\it{}``We can start off with a couple of observations |
|
55 about the role of compilers. First, hardware is getting weirder |
|
56 rather than getting clocked faster: almost all processors are |
|
57 multicores and it looks like there is increasing asymmetry in |
|
58 resources across cores. Processors come with vector units, crypto |
|
59 accelerators, bit twiddling instructions, and lots of features to |
|
60 make virtualization and concurrency work. We have DSPs, GPUs, |
|
61 big.little, and Xeon Phi. This is only scratching the |
|
62 surface. Second, we’re getting tired of low-level languages and |
|
63 their associated security disasters, we want to write new code, to |
|
64 whatever extent possible, in safer, higher-level |
|
65 languages. Compilers are caught right in the middle of these |
|
66 opposing trends: one of their main jobs is to help bridge the large |
|
67 and growing gap between increasingly high-level languages and |
|
68 increasingly wacky platforms. It’s effectively a perpetual |
|
69 employment act for solid compiler hackers.'' |
|
70 \end{quote} |
|
71 |
|
72 |
46 The first part of this module is about text processing, be it for |
73 The first part of this module is about text processing, be it for |
47 web-crawlers, compilers, dictionaries, DNA-data, spam-filters and so on. |
74 compilers, dictionaries, DNA-data, spam-filters and so on. |
48 When looking for a particular string, say \pcode{"foobar"}, in a large |
75 When looking for a particular string, say \pcode{"foobar"}, in a large |
49 text we can use the Knuth-Morris-Pratt algorithm, which is currently the |
76 text we can use the Knuth-Morris-Pratt algorithm, which is currently the |
50 most efficient general string search algorithm. But often we do |
77 most efficient general string search algorithm. But often we do |
51 \emph{not} just look for a particular string, but for string patterns. |
78 \emph{not} just look for a particular string, but for string patterns. |
52 For example, in program code we need to identify what are the keywords |
79 For example, in program code we need to identify what are the keywords |