1 00:00:02,380 --> 00:00:07,066 In this video, we're going to take a rest a little bit and talk about how compilers 2 00:00:07,066 --> 00:00:11,414 handle errors and in particular, what kind of error handling functionality is 3 00:00:11,414 --> 00:00:19,726 available in parsers. Compiler has two relatively distinct jobs. The first is to 4 00:00:19,726 --> 00:00:25,417 translate valid programs. That is if it gets a program from a programmer that is 5 00:00:25,417 --> 00:00:30,894 correct, is a valid program, it needs to produce correct code for that program. 6 00:00:30,894 --> 00:00:36,432 Now, distinct from that task is the job of giving good feedback. For erroneous 7 00:00:36,432 --> 00:00:41,125 program and even just detecting the invalid programs we don't want to compile 8 00:00:41,125 --> 00:00:46,119 any program that isn't a valid program in the programming language. And programming 9 00:00:46,119 --> 00:00:50,887 languages have many different kinds of errors. Here's just a few. So for example, 10 00:00:50,887 --> 00:00:56,150 we might have lexical errors, that's for using characters that don't even appear in 11 00:00:56,150 --> 00:01:00,739 any balanced symbol in the language and these would be detected by lexical 12 00:01:00,739 --> 00:01:05,389 analysis phase. We could have syntax errors and this would be the parsing 13 00:01:05,389 --> 00:01:10,590 errors when all the individual lexical units are correct but they're assembled in 14 00:01:10,590 --> 00:01:15,801 some way that doesn't make sense and we don't know how to compile it. There could 15 00:01:15,801 --> 00:01:19,946 be semantic errors for example when types mismatch. Here I've declared excess in 16 00:01:19,946 --> 00:01:24,299 integer and use it as a function and that would be the job of type checker to catch 17 00:01:24,299 --> 00:01:29,942 those. And then Actually, there may be many errors in your program that are not 18 00:01:29,942 --> 00:01:34,752 errors of the programming language. The program you wrote is actually a valid 19 00:01:34,752 --> 00:01:39,186 program but it doesn't do what you intended. You're likely bugging your 20 00:01:39,186 --> 00:01:43,996 program and so while the compiler can detect many kinds of errors, it doesn't 21 00:01:43,996 --> 00:01:48,930 detect all of them and, you know once we get past what the compiler can do, then 22 00:01:48,930 --> 00:01:55,793 it's up to testers and users to find the rest of the problems in the program. So, 23 00:01:55,793 --> 00:02:00,479 what are the requirements for a good error handling? Well, we want the [inaudible] 24 00:02:00,479 --> 00:02:05,165 report errors accurately and clearly so that we can identify what the problem is 25 00:02:05,165 --> 00:02:09,504 quickly and fix it. The compiler itself should recover from the error, error 26 00:02:09,504 --> 00:02:13,727 quickly. So when it hits an error, it shouldn' t take a long time to make a 27 00:02:13,727 --> 00:02:17,777 [inaudible] on what to do before proceeding. And finally, we don't want 28 00:02:17,777 --> 00:02:21,768 error handling to slow down the compilation of valid code. That is, we 29 00:02:21,768 --> 00:02:26,309 shouldn't pay a price for the error handling if we're not really using it. I'm 30 00:02:26,309 --> 00:02:31,573 going to talk about three different kinds of error handling. Panic mode and error 31 00:02:31,573 --> 00:02:36,773 productions are the two that are used in current compiler. So these are actually 32 00:02:36,773 --> 00:02:42,102 things that people use today. Automatic local or global correction is an idea that 33 00:02:42,102 --> 00:02:47,561 was pursued excessively in the past. And I think it's historically quite interesting 34 00:02:47,561 --> 00:02:52,955 particularly as a contrast what people do today and also why people try to do it a 35 00:02:52,955 --> 00:02:59,054 long ago. [inaudible] is the simplest and most popular method of error recovery 36 00:02:59,054 --> 00:03:03,559 that's widely used and the basic ideas that when an error is detected, the parser 37 00:03:03,559 --> 00:03:08,232 is going to begin discarding tokens until one that has a clear role in the language 38 00:03:08,232 --> 00:03:12,349 is found and that's going to try to restart itself and continue from that 39 00:03:12,349 --> 00:03:16,851 point on. And these tokens, the ones that it's looking for are called the 40 00:03:16,851 --> 00:03:21,824 Synchronizing Tokens. And these are just tokens that have a well-known role in the 41 00:03:21,824 --> 00:03:26,189 language and so that we can reliably identify where we are. So, a typical 42 00:03:26,189 --> 00:03:30,919 strategy might be to try to skip to the end of a statement or to the end of a 43 00:03:30,919 --> 00:03:35,285 function if an error is found in a statement or function and then begin 44 00:03:35,285 --> 00:03:40,392 parsing either the next statement or the next function. So let's look at a simple 45 00:03:40,392 --> 00:03:44,784 hypothetical example of panic mode error recovery. So here's an expression. Clearly 46 00:03:44,784 --> 00:03:48,907 it has a problem. We shouldn't have two plus signs in a row so something has gone 47 00:03:48,907 --> 00:03:53,138 wrong here at the second plus and what's going to happen is the parser is going to 48 00:03:53,138 --> 00:03:57,316 come along. The parser is going to be proceeding from left to right. It's gonna 49 00:03:57,316 --> 00:04:01,008 see the open-paren, it's gonna see the number one, it's gonna see the plus 50 00:04:01,011 --> 00:04:05,242 everything is good and then it's gonna see the second plus and it's not gonna know 51 00:04:05,242 --> 00:04:09,848 what to do. It's going to realize. That it's stuck and that there's no expression 52 00:04:09,848 --> 00:04:15,102 in the language that has two p lus signs in a row and it needs to do something to 53 00:04:15,102 --> 00:04:20,175 recover. It's encountered a parsing error and it has to take some error action at 54 00:04:20,175 --> 00:04:24,848 this point. So in panic mode recovery, what it's going to do is it's going to hit 55 00:04:24,848 --> 00:04:29,264 the panic button. So right at this point, it's going to say I give up, I'm not 56 00:04:29,264 --> 00:04:33,948 parsing normally anymore. It goes into a different mode. Where is simply throwing 57 00:04:33,948 --> 00:04:38,711 away input until it finds something that it recognizes and for example, we could 58 00:04:38,711 --> 00:04:43,415 say that the policy in this particular, for this particular kind of error, is to 59 00:04:43,415 --> 00:04:48,238 skip ahead to the next integer and then try to continue. So, we'll just throw away 60 00:04:48,238 --> 00:04:53,060 the plus in this case and then it would restart here at the two, expecting to see 61 00:04:53,060 --> 00:04:57,883 another integer. Try to finish off this expression and it would treat that as one 62 00:04:57,883 --> 00:05:02,944 + two and then the parenthesis would match and the rest of the expression would parse 63 00:05:02,944 --> 00:05:09,130 just fine. Now in tools such Bison, which is widely used parser generator and one 64 00:05:09,130 --> 00:05:15,503 that you may use for the project, there is a special terminal symbol called error to 65 00:05:15,503 --> 00:05:21,649 describe how much input to skip and the productions that are given in Bison look 66 00:05:21,649 --> 00:05:27,490 like this. So you would say at the possibilities for e are that e could be an 67 00:05:27,490 --> 00:05:33,718 integer, e could be an. The sum of the two e's, two expressions, it could be a 68 00:05:33,718 --> 00:05:40,427 parenthesized expression or if none of this work, okay. So these are the normal 69 00:05:40,427 --> 00:05:46,210 productions. Alright, If none of those work, then we could try some of these 70 00:05:46,210 --> 00:05:51,418 productions that have error in them. And error is a special symbol for Bison and it 71 00:05:51,418 --> 00:05:56,564 says, well, these are the alternatives to try if these things over here didn't work. 72 00:05:56,564 --> 00:06:02,378 So, if you find an error. Let's focus on this one right here so if this says that 73 00:06:02,378 --> 00:06:08,050 if you find an error while you're trying to parse an e. Okay, we haven't actually 74 00:06:08,050 --> 00:06:12,715 said how that works yet. We'll see that in the future videos but conceptually, the 75 00:06:12,715 --> 00:06:17,614 parser is trying to recognize one of these kinds of expressions here. It's in a state 76 00:06:17,614 --> 00:06:21,475 where it thinks it wanted to see an integer or a + or a parenthesized 77 00:06:21,484 --> 00:06:26,163 expression and if that isn't working out i f it get stuck well then hit the panic 78 00:06:26,163 --> 00:06:30,899 button and you can declare that it's in error state and it can throw away all the 79 00:06:30,899 --> 00:06:35,462 input. This error will match all the input up to the next integer. And then this 80 00:06:35,462 --> 00:06:40,508 whole thing could be counted as an e. As one of these things and then we will try 81 00:06:40,508 --> 00:06:45,995 to continue the parsing. Similarly, if we encounter an error somewhere inside a pair 82 00:06:45,995 --> 00:06:51,416 of match parenthesis, well, we could just throw away the whole thing and just reset 83 00:06:51,416 --> 00:06:56,241 at the parenthesis boundaries and they continue parsing. So these are two 84 00:06:56,241 --> 00:07:01,728 possible error recovery strategies if we find an error for this particular kind of 85 00:07:01,728 --> 00:07:06,867 symbol in the grammar. And you can have these error, These productions that 86 00:07:06,867 --> 00:07:12,984 involved the error token for, for as many different kinds of symbols in the language 87 00:07:12,984 --> 00:07:18,595 as you like. Another common strategy is to use what are known as error productions 88 00:07:18,595 --> 00:07:22,749 and this specify known common mistakes that programmers make adjust as 89 00:07:22,749 --> 00:07:27,664 alternative productions in the grammar. So here's a simple example, let's say we were 90 00:07:27,664 --> 00:07:32,228 working on a programming language or compiler for a programming language that 91 00:07:32,228 --> 00:07:36,966 was used by a lot of mathematicians and instead of writing Five x like computer 92 00:07:36,966 --> 00:07:41,761 scientists do, these guys always wanted to write five x to just juxtapose the five 93 00:07:41,761 --> 00:07:46,146 and the x to look more like normal mathematical notation. And they complain 94 00:07:46,146 --> 00:07:50,824 that this is always giving them parser errors. If the parser is just complaining 95 00:07:50,824 --> 00:07:55,256 over and over again then this is not a well formed expression. Well, we could 96 00:07:55,256 --> 00:07:59,636 just go in to our grammar and add a production that made of, of well form. We 97 00:07:59,636 --> 00:08:04,477 could just say well now it's legal, if I have that one kind of expression is just 98 00:08:04,477 --> 00:08:09,029 to have two expressions that [inaudible] opposed next to each other with no 99 00:08:09,029 --> 00:08:13,711 intervening operator. And this, has a disadvantage obviously of complicating the 100 00:08:13,711 --> 00:08:18,583 grammar. If we do this a lot our grammar is gonna get a lot harder to understand. 101 00:08:18,583 --> 00:08:23,821 It's gonna be a lot harder to maintain and essentially all this is doing is promoting 102 00:08:23,821 --> 00:08:28,815 common mistakes to alternative syntax but this is used in practice. Peo ple do this 103 00:08:28,815 --> 00:08:33,870 sort of thing and you will see for example when you use TCC and other production C 104 00:08:33,870 --> 00:08:38,621 compilers they will often warn you about things you're not supposed to do but 105 00:08:38,621 --> 00:08:43,615 they'll accept them anyway and this is essentially the mechanism by which they do 106 00:08:43,615 --> 00:08:51,049 that. Last strategy I want to talk about a little bit is error correction. So, so far 107 00:08:51,049 --> 00:08:55,821 we've just talked about strategies for detecting errors but we could also try to 108 00:08:55,821 --> 00:09:00,475 fix errors that is if the program has mistakes in it, the compiler could try to 109 00:09:00,475 --> 00:09:04,953 help the program out and say oh, you obviously didn't mean to write that. Let 110 00:09:04,953 --> 00:09:09,608 me try to find a program for you that, that works. And, these kind of corrections 111 00:09:09,608 --> 00:09:14,439 in some sense we wanted to find programs that are nearby, programs that aren't too 112 00:09:14,439 --> 00:09:19,329 different from the programs at the, that the programmer supplied but we couldn't 113 00:09:19,329 --> 00:09:24,064 compile correctly. And there's a few different things that you can do to the 114 00:09:24,064 --> 00:09:29,132 things that people have tried are things like token insertions and deletions. So 115 00:09:29,132 --> 00:09:33,946 here you'd like to minimize the edit distance. That would be the metric that 116 00:09:33,946 --> 00:09:38,950 you would use to determine whether a program was close to the original program, 117 00:09:38,950 --> 00:09:43,828 that the programmer supplied. You could also do exhaustive search within some 118 00:09:43,828 --> 00:09:48,579 bounce to try all possible programs that are close to the program that was 119 00:09:48,579 --> 00:09:53,316 supplied. And, a couple of disadvantages to this actually, number of disadvantages. 120 00:09:53,492 --> 00:09:57,600 You can imagine that this is hard to implement. It, it's actually quite 121 00:09:57,600 --> 00:10:02,412 complex. This will slow down the parsing of correct programs because we need to 122 00:10:02,412 --> 00:10:07,224 keep enough state around that we can manage the search or, or the editing in 123 00:10:07,224 --> 00:10:11,802 the case of that way actually doing counter and error and of course nearby is 124 00:10:11,802 --> 00:10:16,790 not really, is not really that clear what that means and various notions of nearby 125 00:10:16,790 --> 00:10:21,250 may or may not actually take us to a program of the, the programmer would 126 00:10:21,250 --> 00:10:25,671 actually be happy with. The best one example of error correction is the 127 00:10:25,671 --> 00:10:30,470 compiler PL [crosstalk]. This is PL [inaudible] compiler, that's the PL part 128 00:10:30,470 --> 00:10:35,717 and the C stands for either correction or Cornell which is where the compiler was 129 00:10:35,717 --> 00:10:40,772 built and PL [crosstalk] is well-known for being willing to compile absolutely 130 00:10:40,772 --> 00:10:45,949 anything. You could, you could give it the phone book. You can and people did give it 131 00:10:45,949 --> 00:10:50,986 things like speech from Hamlet soliloquy and it would print out a lot of error 132 00:10:50,986 --> 00:10:56,087 messages. Sometimes, these error messages would be very funny to read. And it would, 133 00:10:56,087 --> 00:11:00,869 in the end, do correction and produce always a valid running PL [inaudible] 134 00:11:00,869 --> 00:11:06,434 program. And you might ask why do people bother with that? It doesn't seem but that 135 00:11:06,434 --> 00:11:12,106 may not seem very compelling To us today. And have to realize that when this work 136 00:11:12,106 --> 00:11:17,327 was done back in the 1970s people live in a very different world. There was a very 137 00:11:17,327 --> 00:11:22,891 slow recompilation cycle. It could take a whole day To get your program To compile 138 00:11:22,891 --> 00:11:27,353 and run, you would essentially submit your program in the morning and you might not 139 00:11:27,353 --> 00:11:31,707 get results back until the afternoon. And, with that kind of turnaround cycle, Even 140 00:11:31,707 --> 00:11:35,672 one syntax error in your program was devastating. You can lose a whole day 141 00:11:35,672 --> 00:11:40,280 because you mistype the keyword and having the compiler try to take a stab at finding 142 00:11:40,280 --> 00:11:44,031 a working program for you if the correction was small and you save an 143 00:11:44,031 --> 00:11:48,371 entire day, you know to think it can fix that one small mistake you made and give 144 00:11:48,371 --> 00:11:52,443 you a valid run, that was actually a useful thing to do. And so the goal then 145 00:11:52,443 --> 00:11:56,836 was to find as many errors in one cycle as possible. They would try, they would try 146 00:11:56,836 --> 00:12:01,544 to find as many errors to try to recover. Find as many errors as possible. Give you 147 00:12:01,544 --> 00:12:06,264 as good feedback as possible so you could fix as many errors, avoid as many retry 148 00:12:06,264 --> 00:12:11,243 cycles as possible. And, and even possibly automatically correct the program. So that 149 00:12:11,243 --> 00:12:15,798 you could see if the correction were right and, and then possibly the, the results 150 00:12:15,798 --> 00:12:19,593 you got back were useful on the [inaudible] to do even more debugging 151 00:12:19,593 --> 00:12:24,039 before the next round. Now today, we're in a completely different situation. We were 152 00:12:24,039 --> 00:12:27,889 very fast, almost interactive recompilation cycle for many projects and 153 00:12:27,889 --> 00:12:31,901 as a result, users generally aren't interested in finding many errors. They 154 00:12:31,901 --> 00:12:36,239 ten d to correct only one error per cycle. Compilers still report many errors, I'll 155 00:12:36,239 --> 00:12:40,360 give you lots and lots of errors but my observation certainly might have it. 156 00:12:40,360 --> 00:12:44,997 Personally, what I see many other people do is they only fix the first one because 157 00:12:44,997 --> 00:12:49,296 it's the most reliable and the one that definitely needs to be fixed before, 158 00:12:49,296 --> 00:12:53,651 before you can try to compile again. If the compilation is fast enough, that's 159 00:12:53,651 --> 00:12:58,006 probably the most proactive thing to do. And as result, complex error recovery 160 00:12:58,006 --> 00:13:01,400 today is just less compelling than it was a few decades ago.