1 00:00:00,000 --> 00:00:04,702 Welcome back, In this video, we're going to continue our lecture on lexical 2 00:00:04,702 --> 00:00:09,658 analysis with some examples from past programming languages where interesting 3 00:00:09,658 --> 00:00:18,447 lexical problems arose. So we've already talked a little bit about Fortran and what 4 00:00:18,447 --> 00:00:22,633 are the interesting lexical rules in Fortran is the white space is 5 00:00:22,633 --> 00:00:27,630 insignificant so white space doesn't matter and something like VAR1 to which 6 00:00:27,630 --> 00:00:32,814 could be a variable name VAR1 is exactly the same as VA R1 so these two program 7 00:00:32,814 --> 00:00:37,999 fragments have to mean exactly the same thing sand the idea in Fortran is that you 8 00:00:37,999 --> 00:00:43,308 can take your program and you could delete all the blanks from it and that shouldn't 9 00:00:43,308 --> 00:00:48,680 change what the program means at all. Let's take a look at an example of how 10 00:00:48,680 --> 00:00:53,664 Fortran's white space rule affects lexical analysis. Here are a couple of Fortran 11 00:00:53,664 --> 00:00:58,833 code fragments and I should say that this example is taken from the dragon book and 12 00:00:58,833 --> 00:01:03,941 actually couple of the later examples were also taken from an older edition of the 13 00:01:03,941 --> 00:01:09,172 dragon book. But anyway what we have here, this is actually the header of a Fortran 14 00:01:09,172 --> 00:01:17,002 loop. And you know it's a loop because it has the key word do, which is like four in 15 00:01:17,002 --> 00:01:24,124 modern C or C++ so I'd say loop key word And then we have out iteration variable I 16 00:01:24,124 --> 00:01:28,984 and we have a range that I will vary between. So, in this case I will go from 17 00:01:28,984 --> 00:01:34,030 one up to 25. And then this number five here, this is a little bit odd, something 18 00:01:34,030 --> 00:01:39,383 you don't see in modern languages. In the old days in Fortran you would have your do 19 00:01:39,383 --> 00:01:44,613 statement at the top of the loop and then the size of the loop or all the statements 20 00:01:44,613 --> 00:01:49,252 included in the loop Were named by a label, they came right after the do 21 00:01:49,252 --> 00:01:54,151 statement. So, the loop will extend from the, the header, the do statement down to 22 00:01:54,151 --> 00:01:59,174 the label five. So whatever statement was able with five, all of the statements in 23 00:01:59,174 --> 00:02:04,569 between would be part of the loop. And so, the loop would execute those statements 24 00:02:04,569 --> 00:02:09,654 then we'll go back around to the header and then we keep executing those until it 25 00:02:09,654 --> 00:02:14,987 had done so for every one of the values of the iteration variable, in this case, one 26 00:02:14,987 --> 00:02:20,330 to 25. Now, here's a nother code fragment and as you can see this one is almost 27 00:02:20,330 --> 00:02:25,860 exactly the same as the one above. The only difference is, let me just switch 28 00:02:25,860 --> 00:02:31,530 colors, is here that this particular fragment has a comma in that position and 29 00:02:31,530 --> 00:02:37,933 this fragment has a period. And it turns out that this difference makes all the 30 00:02:37,933 --> 00:02:45,072 difference that these two fragment of code mean completely different things. So, this 31 00:02:45,072 --> 00:02:51,227 fragment, the first one, is in fact a do loop as I said before so it has the 32 00:02:51,227 --> 00:02:58,038 keyword do, the label five, the variable I and the range one to 25. Now this fragment 33 00:02:58,038 --> 00:03:04,350 down here, this is actually a variable name, do 5I, So far as writing without the 34 00:03:04,350 --> 00:03:10,383 blanks. Remember the blanks don't matter, This would be do 5I and this is an 35 00:03:10,383 --> 00:03:16,666 assignment equals the number 1.25. Okay, And so you can see here these symbols, the 36 00:03:16,666 --> 00:03:22,148 sequence, the first sequence of symbols is interpreted completely differently 37 00:03:22,148 --> 00:03:28,057 depending on whether there's a period or a comma further on. And so let's just be a 38 00:03:28,057 --> 00:03:33,752 little more precise about that. How do we know what do is? So let's just focus on 39 00:03:33,752 --> 00:03:39,732 the keyword here do and when we're at this point, when our focus is here right after 40 00:03:39,732 --> 00:03:44,930 the zero. And keep in mind that, that the way this is going to be implemented is by 41 00:03:44,930 --> 00:03:50,078 a left to right scan so we're going to be walking in this direction over the, over 42 00:03:50,078 --> 00:03:54,848 the input looking at each character successfully and when our focus reaches 43 00:03:54,848 --> 00:03:59,682 this point, we can make a decision. Is this a, is this a keyword 'cause we've 44 00:03:59,682 --> 00:04:04,448 seen the entire keyword too. And the problem is that we don't have information 45 00:04:04,448 --> 00:04:09,080 to make that decision. We don't know whether this is do or whether it's going 46 00:04:09,080 --> 00:04:14,134 to be eventually be part of a variable name like do 5I. And the only way to know 47 00:04:14,134 --> 00:04:18,946 is to look ahead in the input to this position to see whether there's a comma or 48 00:04:18,946 --> 00:04:24,890 a period there. So this is an example of lexical analysis that requires look ahead. 49 00:04:24,900 --> 00:04:31,073 In order to understand the role of due, as we're going left to right. We have to pick 50 00:04:31,073 --> 00:04:35,809 ahead of the input to see some symbols that come later on. And we can't possibly 51 00:04:35,809 --> 00:04:40,717 disambiguate role of do until that poin t because up to this point, the sequence and 52 00:04:40,717 --> 00:04:45,397 the symbols are exactly the same and so the only thing that distinguishes them is 53 00:04:45,397 --> 00:04:49,734 something that's much, much further on. And as you can imagine, having lots of 54 00:04:49,734 --> 00:04:54,414 look ahead complicates the implementation of lexical analysis and so one of the 55 00:04:54,414 --> 00:04:59,426 goals in the design of lexical systems is to minimize the amount of the look ahead 56 00:04:59,436 --> 00:05:04,199 or bound the amount of look ahead that is required. So you might wonder why Fortran 57 00:05:04,199 --> 00:05:09,094 has this funny rule about white space. It turns out that on punch card machines it 58 00:05:09,094 --> 00:05:13,988 was easy to add extra blanks by accidents and as a result they added this rule to 59 00:05:13,988 --> 00:05:18,823 the language so the punch card operator wouldn't have to redo their work all the 60 00:05:18,823 --> 00:05:25,301 time. Fortunately today we don't enter our programs anymore on punch cards. But this 61 00:05:25,301 --> 00:05:29,590 example does help us understand better what we're trying to do in lexical 62 00:05:29,590 --> 00:05:34,112 analysis so as I said the goal is to partition the string. We're trying to buy 63 00:05:34,112 --> 00:05:38,872 the string up into the logically units of the language. And this is implemented by 64 00:05:38,872 --> 00:05:43,125 reading left to right. So we're doing a left to right scan over the input, 65 00:05:43,125 --> 00:05:47,144 recognizing one token at a time. And because of that, look ahead may be 66 00:05:47,144 --> 00:05:51,688 required to decide where one token ends and the next token begins. And again, I 67 00:05:51,688 --> 00:05:56,407 want to stress that look ahead is always needed but we would like to minimize the 68 00:05:56,407 --> 00:06:00,892 amount of look ahead. And in fact, we like to bound it to some constant to this, 69 00:06:00,892 --> 00:06:05,086 because it will simplify the implementation of lexical analyzer quite a 70 00:06:05,086 --> 00:06:10,716 bit. Now just to illustrate to look ahead is something that we always have to worry 71 00:06:10,716 --> 00:06:15,613 about. Let's consider this example which we've looked at before and just notice 72 00:06:15,613 --> 00:06:20,572 that when we're reading left to right, let's look at this keyword else here, when 73 00:06:20,572 --> 00:06:26,709 we read the E. We have to decide is that a variable name or some symbol but itself or 74 00:06:26,709 --> 00:06:32,252 do we want to consider it together with the symbols that follow them. And so 75 00:06:32,252 --> 00:06:37,202 there's a look ahead issue here. After we scanned E, we have to decide does that sit 76 00:06:37,202 --> 00:06:41,548 by itself or is it part of a larger lexical unit? And, you know there a re 77 00:06:41,548 --> 00:06:46,316 single character variable names in this example like I, J, and Z and so it's not 78 00:06:46,316 --> 00:06:51,145 unreasonable that E could also be one and another example is this double-equals. 79 00:06:51,145 --> 00:06:56,035 When we read a single equal sign, how do we decide whether that's a single equals 80 00:06:56,035 --> 00:07:00,984 like these other assignments or that it's really a double-equals. Well, in order to 81 00:07:00,984 --> 00:07:05,668 do that, if our focus point is right here, we have to look ahead and see. There's 82 00:07:05,668 --> 00:07:10,318 another = coming up and that's how we know or how we will know. That we wanted to 83 00:07:10,318 --> 00:07:17,869 combine it into a single symbol instead of considering this equals by itself. Another 84 00:07:17,869 --> 00:07:26,523 example from a, a language from long ago PL [inaudible] is a interesting language. 85 00:07:26,523 --> 00:07:38,175 It was designed by IBM and it stands for Programming Language One. Alright, It was 86 00:07:38,175 --> 00:07:43,387 designed to be the programming language. At least with an IBM that would be used by 87 00:07:43,387 --> 00:07:48,384 everybody and is supposed to encompass all the features that every programmer would 88 00:07:48,384 --> 00:07:53,143 ever need. And as such, it was supposed to be very, very general and have very few 89 00:07:53,143 --> 00:07:58,098 restrictions. And so, one of the features of PL [inaudible] is that Keywords are not 90 00:07:58,098 --> 00:08:02,879 reserved. So, in PL [inaudible] you can use a keyword both as a keyword and also 91 00:08:02,879 --> 00:08:07,901 as a variable. So you can use keywords and other roles other than keywords and that 92 00:08:07,901 --> 00:08:12,258 means you can write interesting, interesting sentences or interesting 93 00:08:12,258 --> 00:08:16,615 programs like this. And let me just read this out loud because it sounds 94 00:08:16,615 --> 00:08:21,908 interesting, if else then, then = else, else = then. And the correct organization 95 00:08:21,908 --> 00:08:28,745 here of course is that this is a keyword, this is a keyword and this is a keyword. 96 00:08:28,745 --> 00:08:35,583 And the other things, switch colors here, are all variables. These are all variable 97 00:08:35,583 --> 00:08:40,105 names. And as you can imagine this mix a lexical analysis somewhat difficult 98 00:08:40,105 --> 00:08:44,867 because when we're just scanning left to right like when we're coming through here 99 00:08:44,867 --> 00:08:49,571 when we say we're at to this point, you know how do we decide whether these things 100 00:08:49,571 --> 00:08:54,505 are going to be variable names or keywords without seeing what's going on in the rest 101 00:08:54,505 --> 00:09:00,268 of the expression so lexical analysis in PL [inaudible] was quite challenging. So 102 00:09:00,268 --> 00:09:04,864 here's another example from PL [inaudible]. Here we have a program 103 00:09:04,864 --> 00:09:10,087 fragment, we have the word declare and then an open paren and a close paren 104 00:09:10,087 --> 00:09:16,006 encompassing a bunch of arguments so we'll point out the balance parens here and then 105 00:09:16,006 --> 00:09:22,330 just a list of n things inside the parens. And it turns out that the pending on the 106 00:09:22,330 --> 00:09:28,167 larger context in which this whole expressions sits, this could be either a 107 00:09:28,167 --> 00:09:32,940 keyword. Or it could be in array reference that mean when, yeah, that mean declare 108 00:09:32,940 --> 00:09:37,726 here could either be a keyword or it could be a name of an array and this could be 109 00:09:37,726 --> 00:09:42,222 the end [inaudible] to the array. And as it happens, there is no way looking at 110 00:09:42,222 --> 00:09:47,008 just this much that we can decide. This fragment is valid, is a valid declaration 111 00:09:47,008 --> 00:09:51,505 and it's also a valid array reference. So, it would depend on what came next. It 112 00:09:51,505 --> 00:09:56,117 might depend on for example whether there was an equal sign here in which cases 113 00:09:56,117 --> 00:10:00,960 would be interpreted as an assignment and, and declare would be the name of an array. 114 00:10:00,960 --> 00:10:06,628 And, the interesting thing about this example is that because the number of 115 00:10:06,628 --> 00:10:12,448 arguments in here is unbounded. There could be n of them for any n. This 116 00:10:12,448 --> 00:10:19,903 requires unbounded look ahead. Okay, So to implement this properly as you're scanning 117 00:10:19,903 --> 00:10:25,485 left to right to decide whether declare again is a keyword or re-reference, we 118 00:10:25,485 --> 00:10:30,780 would have to scan beyond this entire argument list to see what came next. 119 00:10:32,080 --> 00:10:37,103 Fortren and PL [inaudible] were designed in the 1950s and 1960s respectively and 120 00:10:37,103 --> 00:10:42,064 those experiences taught us a lot about what not to do in the lexical design of 121 00:10:42,064 --> 00:10:47,088 programming languages. So things are a lot better today but the problems have not 122 00:10:47,088 --> 00:10:51,987 gone away completely and I'll use an example from C++ that illustrate this. So 123 00:10:51,987 --> 00:10:56,949 here's an example of C++ template syntax which you may be familiar with or you may 124 00:10:56,949 --> 00:11:03,570 have seen the similar syntax in Java. And C++ has another operator called Stream 125 00:11:03,570 --> 00:11:10,940 Input. So this operator here reads from an input stream and stores the results in a 126 00:11:10,940 --> 00:11:17,483 variable. And the problem is, here that there's a conflict with nested templates, 127 00:11:17,483 --> 00:11:26,046 So for example, if I have a template o peration that looks like this. Okay. 128 00:11:26,046 --> 00:11:31,343 Notice what happens here. So my intention here is to have a nested application of 129 00:11:31,343 --> 00:11:36,510 templates but I wind up with two great than signs together at the end and this 130 00:11:36,510 --> 00:11:41,741 looks just like the stream operator and the question is what should the lexical 131 00:11:41,741 --> 00:11:47,103 analyzer do? Should it interpret this as two close brackets for template or should 132 00:11:47,103 --> 00:11:52,335 it interpret it as a two greater than signs stuck together as a stream operator. 133 00:11:52,335 --> 00:11:57,370 And it turns out that for a very long time, I think most C++ compilers have now 134 00:11:57,370 --> 00:12:01,998 fixed this. The C++ compiler in this situation would regard this as a stream 135 00:12:01,998 --> 00:12:07,210 operator and you would get a syntax there. And what do you think the solution was, it 136 00:12:07,210 --> 00:12:12,484 turns out that the only fix that you could really do to make this lexically analyzed 137 00:12:12,484 --> 00:12:17,696 the correct way was to insert a blank so you would have to write this and you would 138 00:12:17,696 --> 00:12:22,846 have to remember to put the blank in there so that the two greater than signs were 139 00:12:22,846 --> 00:12:28,058 not together. And you know that's kind of ugly that we have to put in white space to 140 00:12:28,058 --> 00:12:35,575 fix the lexical analysis of the program. So to summarize the goal of lexical 141 00:12:35,575 --> 00:12:40,074 analysis is to partition the input streams into lexemes, okay. So we have drop down 142 00:12:40,074 --> 00:12:44,245 dividing lines in the string to decide where the lexemes lie and we want to 143 00:12:44,245 --> 00:12:48,415 identify the token of each lexeme, And because, exactly because we're doing a 144 00:12:48,415 --> 00:12:52,860 left to right scan, sometimes we have to have look ahead. Sometimes we have to peek 145 00:12:52,860 --> 00:12:57,305 ahead in the input string to figure out what the current string we're looking at, 146 00:12:57,305 --> 00:13:01,640 what the current substring we're looking at, what role it plays in the language?