49 |
49 |
50 The purpose of a compiler is to transform a program a human can read and |
50 The purpose of a compiler is to transform a program a human can read and |
51 write into code the machine can run as fast as possible. Developing a |
51 write into code the machine can run as fast as possible. Developing a |
52 compiler is an old craft going back to 1952 with the first compiler |
52 compiler is an old craft going back to 1952 with the first compiler |
53 written by Grace Hopper.\footnote{Who many years ago was invited on a |
53 written by Grace Hopper.\footnote{Who many years ago was invited on a |
54 talk show hosted by David Letterman, see |
54 talk show hosted by David Letterman. |
55 \url{https://youtu.be/3N_ywhx6_K0?t=31}.} Why studying compilers |
55 \here{https://youtu.be/3N_ywhx6_K0?t=31}.} Why studying compilers |
56 nowadays? An interesting answer is given by John Regher in his compiler |
56 nowadays? An interesting answer is given by John Regher in his compiler |
57 blog:\footnote{\url{http://blog.regehr.org/archives/1419}} |
57 blog:\here{http://blog.regehr.org/archives/1419} |
58 |
58 |
59 \begin{quote}\it{}``We can start off with a couple of observations |
59 \begin{quote}\it{}``We can start off with a couple of observations |
60 about the role of compilers. First, hardware is getting weirder |
60 about the role of compilers. First, hardware is getting weirder |
61 rather than getting clocked faster: almost all processors are |
61 rather than getting clocked faster: almost all processors are |
62 multicores and it looks like there is increasing asymmetry in |
62 multicores and it looks like there is increasing asymmetry in |
105 pattern---is it an email address, for example. In this way we can |
105 pattern---is it an email address, for example. In this way we can |
106 exclude user input that would otherwise have nasty effects on our |
106 exclude user input that would otherwise have nasty effects on our |
107 program (crashing it or making it go into an infinite loop, if not |
107 program (crashing it or making it go into an infinite loop, if not |
108 worse). This kind of ``inspecting'' mechanism is also implemented in |
108 worse). This kind of ``inspecting'' mechanism is also implemented in |
109 popular network security tools such as Snort and |
109 popular network security tools such as Snort and |
110 Bro.\footnote{\url{www.snort.org}, \url{www.bro.org}} They scan incoming |
110 Bro.\here{www.snort.org}\here{www.bro.org} They scan incoming |
111 network traffic for computer viruses or malicious packets. Similarly |
111 network traffic for computer viruses or malicious packets. Similarly |
112 filtering out spam usually involves looking for some signature |
112 filtering out spam usually involves looking for some signature |
113 (essentially a string pattern). The point is that the fast |
113 (essentially a string pattern). The point is that the fast |
114 Knuth-Morris-Pratt algorithm for strings is not good enough for such |
114 Knuth-Morris-Pratt algorithm for strings is not good enough for such |
115 string \emph{patterns}.\smallskip |
115 string \emph{patterns}.\smallskip |