1 00:00:02,800 --> 00:00:07,153 Welcome back, in this second half of the lecture we'll continue with our overview 2 00:00:07,153 --> 00:00:16,123 of the structure of a compiler. Recall that a compiler has five major phases, 3 00:00:16,123 --> 00:00:20,728 lexical analysis, parsing, semantic analysis, optimization, and code 4 00:00:20,728 --> 00:00:26,133 generation. And now we're going to briefly talk about each one, and we're going to 5 00:00:26,133 --> 00:00:31,606 explain how a compiler understands these with an analogy to how humans understand 6 00:00:31,606 --> 00:00:39,333 English. The first step at understanding a program, both for a compiler and for a 7 00:00:39,333 --> 00:00:44,895 human, is to understand the words. Now, humans can look at this example sentence 8 00:00:44,895 --> 00:00:50,599 and immediately recognize that there are four words 'this is a' and 'sentence. And 9 00:00:50,599 --> 00:00:56,588 this is so automatic that you don't even think about it but there is [inaudible] 10 00:00:56,588 --> 00:01:02,220 real computation going on here. You have to recognize the separators, namely the 11 00:01:02,220 --> 00:01:07,698 blanks. And the punctuation, things like the periods, and also clues like capital 12 00:01:07,698 --> 00:01:13,298 letters. And these help you to divide up this group of letters into, a bunch of 13 00:01:13,298 --> 00:01:18,829 words that you can understand. And just to emphasize that this is not completely 14 00:01:18,829 --> 00:01:23,940 trivial, let's take a look at this sentence. And you can read this, but it 15 00:01:23,940 --> 00:01:29,201 takes a little bit of time Because I've put the separators in, in odd places. So 16 00:01:29,201 --> 00:01:34,195 you can see the word is, the word this, the word a, and the word sentence. But 17 00:01:34,195 --> 00:01:39,588 again this isn't something that comes to you immediately. You actually have to do 18 00:01:39,588 --> 00:01:45,181 some work to see where the divisions lie Because they're not given to you in the 19 00:01:45,181 --> 00:01:50,619 way that you're used to. The goal of lexical analysis, then, is to divide the 20 00:01:50,619 --> 00:01:55,953 program text into its words, or what we call in compiler speak, the tokens. So, 21 00:01:55,953 --> 00:02:01,357 here's an, an example piece of program text now, instead of a piece of English 22 00:02:01,357 --> 00:02:06,481 text, and let's walk through this and identify the tokens. So, there's some 23 00:02:06,481 --> 00:02:11,982 obvious ones that are keywords, like if, and then. >> And else that we want to 24 00:02:11,982 --> 00:02:17,238 identify. And then there are variable names, things like X, and Y, and Z. 25 00:02:17,466 --> 00:02:23,560 There's also constants, things like number one, and the number two. And then there 26 00:02:23,560 --> 00:02:29,805 are some operators, double equals is one, and the assignment operator is another. 27 00:02:29,805 --> 00:02:35,137 And here's already an interesting question. How do we know that double 28 00:02:35,137 --> 00:02:41,328 equals is not two individual equals signs? How do we know that we want this? To be a 29 00:02:41,328 --> 00:02:45,815 double equal so we want, and not two single equals. Well, we don't know right 30 00:02:45,815 --> 00:02:50,286 now but we'll talk about that. >> In the lecture on how we implement Lexico 31 00:02:50,286 --> 00:02:54,802 analysis. But we're not done with all the tokens in this example either, there's a 32 00:02:54,802 --> 00:02:59,652 few more. The semi colons, the punctuation are also tokens, and then the separators 33 00:02:59,652 --> 00:03:03,945 are also tokens, so here's a blank, that's a token, here's another blank, that's 34 00:03:03,945 --> 00:03:08,572 another token, and then there are lots of blanks here that serve to separate things 35 00:03:08,572 --> 00:03:12,977 like the keywords and the variable names and other symbols from each other. And 36 00:03:12,977 --> 00:03:19,254 those are the tokens of this example. So for humans, once the words are understood, 37 00:03:19,254 --> 00:03:23,193 the next step is to understand the structure of the sentence, and this is 38 00:03:23,193 --> 00:03:27,564 called parsing. And as we all learned in elementary school, this means diagramming 39 00:03:27,564 --> 00:03:31,887 sentences, and these diagrams are trees, and it's a very simple procedure. Let's 40 00:03:31,887 --> 00:03:37,581 look at this example. This line is a longer sentence. The first step in parsing 41 00:03:37,581 --> 00:03:43,785 is to identify the role of each word in the sentence. So we have things like nouns 42 00:03:43,785 --> 00:03:48,920 and verbs and adjectives. But then, the actual work of parsing is to group these 43 00:03:48,920 --> 00:03:52,845 words together into higher level constructs. So for example, this 44 00:03:52,845 --> 00:03:57,566 particular sentence consists of a subject, a verb, and an object, okay? And that 45 00:03:57,566 --> 00:04:02,287 actually forms an entire sentence. So, right here we have the root of the tree 46 00:04:02,287 --> 00:04:07,131 called a sentence, and that's broken down into constituent parts. The high level 47 00:04:07,131 --> 00:04:11,790 structure, as we said, is subject verb to object. And then the subject is more 48 00:04:11,790 --> 00:04:16,880 complicated, as is the object. And this is an example of parsing an English sentence. 49 00:04:17,280 --> 00:04:22,805 The analogy between parsing English text and parsing program text is very strong. 50 00:04:22,805 --> 00:04:28,399 In fact, they're exactly the same thing. So here's our little example piece of code 51 00:04:28,399 --> 00:04:33,430 again, so let's work through parsing it. So, clearly, this is an if then else 52 00:04:33,430 --> 00:04:38,442 statement, and so, the root of our diagram, of our parse tree, is gonna be if 53 00:04:38,442 --> 00:04:42,985 then else. [inaudible] Nothing else consists of three parts. There's a 54 00:04:42,985 --> 00:04:47,637 predicate, a then statement, and an L statement. And now let?s look at the 55 00:04:47,637 --> 00:04:53,010 predicate which consists of three pieces. There's a variable, a comparison operator 56 00:04:53,010 --> 00:04:58,383 and another variable and together those form a relation. So the comparison between 57 00:04:58,383 --> 00:05:03,625 two things is one of the things you can have as a valid predicate. Similarly, the 58 00:05:03,625 --> 00:05:09,063 then statement consists of an assignment where Z gets one, and the else statement also 59 00:05:09,063 --> 00:05:14,866 has the form of an assignment, Z gets two. And to, all together this is a parse tree, 60 00:05:14,866 --> 00:05:19,894 of the if-then-else, showing its structure, breaking it up into its 61 00:05:19,894 --> 00:05:27,310 constituent pieces. Now, once we've understood the sentence structure, the 62 00:05:27,310 --> 00:05:31,852 next step is to try to understand the meaning, of what has been written. And, 63 00:05:31,852 --> 00:05:36,969 this is hard. So, actually we don't know how this works for humans still. We don't 64 00:05:36,969 --> 00:05:42,009 understand, what happens after lexical analysis and parsing. We do know that 65 00:05:42,009 --> 00:05:47,049 people do lexical analysis and parsing in much the same way, that compilers 66 00:05:47,243 --> 00:05:52,025 lexically analyze and parse programs. But frankly, understanding meaning is 67 00:05:52,025 --> 00:05:57,001 something that is simply too hard for compilers. So, the first important thing 68 00:05:57,001 --> 00:06:02,235 to understand about, semantic analysis is that compilers can only do very limited 69 00:06:02,235 --> 00:06:06,747 kinds of semantic analysis. And in particular the kinds of things that 70 00:06:06,747 --> 00:06:11,097 compilers generally do are try to catch inconsistencies. So, if the program is 71 00:06:11,097 --> 00:06:15,842 somehow self inconsistent, [inaudible] compilers can often notice that and report 72 00:06:15,842 --> 00:06:21,876 errors. But they don't really know what the program is supposed to do. As an 73 00:06:21,876 --> 00:06:27,628 example of the kind of thing that we do in semantic analysis, again, using an analogy 74 00:06:27,628 --> 00:06:32,918 in English, let's consider the following sentence. So, Jack said Jerry left his 75 00:06:32,918 --> 00:06:38,207 assignment at home. And the question is, what, who does his, refer to here? It 76 00:06:38,207 --> 00:06:43,365 could be that his refers to Jerry, in which case we would read, Jack said Jerry 77 00:06:43,365 --> 00:06:48,432 left Jerry's assignment at home. Or it could refer to Jack. In which case, we 78 00:06:48,432 --> 00:06:53,240 could read the sentence as, Jack said Jerry left Jack's assignment at home. And 79 00:06:53,240 --> 00:06:58,476 without more information, we actually don't know which one. His is referring to, 80 00:06:58,476 --> 00:07:03,740 whether it's Jack, or it's Jerry. And even worse, let's take a look at this sentence 81 00:07:03,740 --> 00:07:08,426 down here. Jack said, Jack left his assignment at home. And the question is 82 00:07:08,426 --> 00:07:13,625 how many people are actually involved in this sentence? It could be as many as 83 00:07:13,625 --> 00:07:18,568 three, there could be two separate Jacks and his, could even refer to somebody 84 00:07:18,568 --> 00:07:23,719 completely different. We don't know without seeing the rest of the story. That 85 00:07:23,719 --> 00:07:28,718 surrounds this sentence, all the possibilities for his. But it could also 86 00:07:28,718 --> 00:07:33,860 be as few as, only a single person. It could be that Jack and Jack and his are 87 00:07:33,860 --> 00:07:39,003 all the same person in this sentence. And so this kind of ambiguity is a real 88 00:07:39,003 --> 00:07:44,376 problem, in semantic analysis. And the analogy in programming languages is 89 00:07:44,376 --> 00:07:49,739 variable bindings. So we would have variables, in this case, a variable called 90 00:07:49,739 --> 00:07:55,314 Jack or maybe more than one variable called Jack. And a programming language is 91 00:07:55,314 --> 00:08:01,241 going to have very strict rules to prevent the kind of ambiguities we had in the 92 00:08:01,241 --> 00:08:06,908 English sentences on the previous slide. So you know, in this example. Question is 93 00:08:06,908 --> 00:08:13,063 what value is printed by this output statement, and the answer is it's going to 94 00:08:13,063 --> 00:08:18,637 print four because this use of the variable Jack binds to this definition 95 00:08:18,637 --> 00:08:23,785 here. And the outer definition is hidden. So the outer definition is not active in 96 00:08:23,785 --> 00:08:28,507 this scope because it is hidden by the inner definition and that is just a 97 00:08:28,507 --> 00:08:34,415 standard rule of a lot of lexically scoped programming languages. Now the pilots 98 00:08:34,415 --> 00:08:39,195 perform many semantic texts besides analyzing the variable bindings. And so 99 00:08:39,195 --> 00:08:44,484 here's another example in English. So Jack looked her homework at home. And, under 100 00:08:44,484 --> 00:08:49,709 the usual naming conventions, assuming that Jack is male, we know there's a type 101 00:08:49,709 --> 00:08:54,679 mismatch between Jack and her. So we know that, whatever her is, it is not Jack. 102 00:08:54,679 --> 00:08:59,586 And, and therefore we known that this sentence is talking about two different 103 00:08:59,586 --> 00:09:06,336 people. And so this is, analogous to type checking. The fourth compiler phase, 104 00:09:06,336 --> 00:09:11,180 optimization, doesn't have a very strong counterpart in everyday English usage but 105 00:09:11,180 --> 00:09:15,729 it's a little bit like editing. And, in fact, it's a lot like what professional 106 00:09:15,729 --> 00:09:20,574 editors do when they have to reduce the length of an article to get it down to 107 00:09:20,574 --> 00:09:25,241 some word budget. So, for example, I have this phrase right here, but a little bit 108 00:09:25,241 --> 00:09:30,026 like ending; and if I didn't like it, if I thought it was too long, I could replace 109 00:09:30,204 --> 00:09:36,096 the middle four words, with two words. Akin to. So now it says, but akin to 110 00:09:36,096 --> 00:09:41,312 editing, and that means exactly the same thing as the original phrase, but uses 111 00:09:41,312 --> 00:09:46,545 fewer words. And the goal in program optimization Is to modify the program so 112 00:09:46,545 --> 00:09:51,467 that it uses less of some resource. Maybe we want to use less time, we want the 113 00:09:51,467 --> 00:09:56,956 program to run faster maybe we want it to use less space so that we can fit more 114 00:09:57,145 --> 00:10:02,571 data in memory. For a handheld device we might be interested in reducing the amount 115 00:10:02,571 --> 00:10:07,997 of power that it uses. If we have external communication we might be interested in 116 00:10:07,997 --> 00:10:13,060 reducing the number of network messages or the number of database accesses. And 117 00:10:13,060 --> 00:10:18,507 there's any number of resources that we might want to improve other program's use 118 00:10:18,507 --> 00:10:27,907 of. So here's a simple example of the kinds of optimizations a program might do. 119 00:10:27,907 --> 00:10:32,943 We can have a rule in our compiler that says X equals Y times zero, is the same as 120 00:10:32,943 --> 00:10:37,979 X equals zero. And this seems like a real improvement, because instead of doing the 121 00:10:37,979 --> 00:10:43,077 multiply, we can just do an assignment. So we save some computation by doing that. 122 00:10:43,077 --> 00:10:48,051 Now unfortunately this is not a correct rule. And this is one of the important 123 00:10:48,051 --> 00:10:52,228 things to know about compiling optimization, is that it's not always 124 00:10:52,228 --> 00:10:57,080 obvious when it's legal to do certain optimizations or not. Now it turns out 125 00:10:57,080 --> 00:11:04,490 That this particular rule is valid for integers. Okay, so if X and Y are 126 00:11:04,490 --> 00:11:11,570 integers, then multiplying by zero is always the same thing as just signing 127 00:11:11,570 --> 00:11:19,156 zero. But, it's invalid for floating point. And why is that, well because you 128 00:11:19,156 --> 00:11:25,326 have to know some details of the IEEE floating point standard, but there is a 129 00:11:25,326 --> 00:11:31,570 special number in the IEEE standard called not a number and it turns out that 130 00:11:31,570 --> 00:11:37,457 not a number called a NaN times zero is equal to not a number. Any particular 131 00:11:37,457 --> 00:11:42,882 non-number times zero is not equal to zero If X and Y are plotting point numbers, you 132 00:11:42,882 --> 00:11:47,924 can't do this optimization. In fact, if you did this optimization, it would break 133 00:11:47,924 --> 00:11:52,583 certain very important algorithms that rely on the proper propagation of 134 00:11:52,583 --> 00:12:00,942 not a number. Finally, the last compiler phase is code generation, often 135 00:12:00,942 --> 00:12:06,871 referred to as Code Gen, and Code Gen, can produce assembly code. That's the most 136 00:12:06,871 --> 00:12:11,286 common thing that a compiler would produce. But in general, it's a 137 00:12:11,286 --> 00:12:16,415 translation into some other language. And this is, entirely analogous to human 138 00:12:16,415 --> 00:12:21,804 translation. So just as a human translator might translate, English into French, a 139 00:12:21,804 --> 00:12:27,604 compiler will translate a high level program into assembly code. To wrap up, 140 00:12:27,604 --> 00:12:33,822 almost every compiler has the five phases that we outlined. However, the proportions 141 00:12:33,822 --> 00:12:39,817 have changed a lot over the years, and if we were to go back to FORTRAN I and 142 00:12:39,817 --> 00:12:45,661 look inside of that compiler, we would probably see a size and complexity that 143 00:12:45,661 --> 00:12:51,430 looks something like this. We have a fairly complex lexical analysis phase, an 144 00:12:51,430 --> 00:12:57,564 equally complicated parsing phase, a very small semantic analysis phase, a. A fairly 145 00:12:57,564 --> 00:13:03,574 involved optimization phase and another fairly involved code generation phase. And 146 00:13:03,574 --> 00:13:09,102 so we see a compiler where the complexity was sp, spread fairly evenly throughout 147 00:13:09,293 --> 00:13:14,821 except for its semantic analysis which is very weak in the early days. And today 148 00:13:14,821 --> 00:13:20,223 if we look at a modern compiler you'll see almost nothing in lengthening, very little 149 00:13:20,223 --> 00:13:25,434 in parsing, because we have extremely good tools to help us write those two phases. 150 00:13:25,624 --> 00:13:31,222 We would see a fairly involved thematic analysis phase. We would see a very large 151 00:13:31,222 --> 00:13:37,450 optimization phase, and this is in fact the dominant component off all modern 152 00:13:37,450 --> 00:13:43,839 compilers, and the a small code-generation phase because again we understand that 153 00:13:44,081 --> 00:13:49,505 phase very, very well. That's it for this lecture. Future lectures, we'll look at 154 00:13:49,505 --> 00:13:51,380 each of these phases in detail.