In this video, we're going to take a rest
a little bit and talk about how compilers
handle errors and in particular, what kind
of error handling functionality is
available in parsers. Compiler has two
relatively distinct jobs. The first is to
translate valid programs. That is if it
gets a program from a programmer that is
correct, is a valid program, it needs to
produce correct code for that program.
Now, distinct from that task is the job of
giving good feedback. For erroneous
program and even just detecting the
invalid programs we don't want to compile
any program that isn't a valid program in
the programming language. And programming
languages have many different kinds of
errors. Here's just a few. So for example,
we might have lexical errors, that's for
using characters that don't even appear in
any balanced symbol in the language and
these would be detected by lexical
analysis phase. We could have syntax
errors and this would be the parsing
errors when all the individual lexical
units are correct but they're assembled in
some way that doesn't make sense and we
don't know how to compile it. There could
be semantic errors for example when types
mismatch. Here I've declared excess in
integer and use it as a function and that
would be the job of type checker to catch
those. And then Actually, there may be
many errors in your program that are not
errors of the programming language. The
program you wrote is actually a valid
program but it doesn't do what you
intended. You're likely bugging your
program and so while the compiler can
detect many kinds of errors, it doesn't
detect all of them and, you know once we
get past what the compiler can do, then
it's up to testers and users to find the
rest of the problems in the program. So,
what are the requirements for a good error
handling? Well, we want the [inaudible]
report errors accurately and clearly so
that we can identify what the problem is
quickly and fix it. The compiler itself
should recover from the error, error
quickly. So when it hits an error, it
shouldn' t take a long time to make a
[inaudible] on what to do before
proceeding. And finally, we don't want
error handling to slow down the
compilation of valid code. That is, we
shouldn't pay a price for the error
handling if we're not really using it. I'm
going to talk about three different kinds
of error handling. Panic mode and error
productions are the two that are used in
current compiler. So these are actually
things that people use today. Automatic
local or global correction is an idea that
was pursued excessively in the past. And I
think it's historically quite interesting
particularly as a contrast what people do
today and also why people try to do it a
long ago. [inaudible] is the simplest and
most popular method of error recovery
that's widely used and the basic ideas
that when an error is detected, the parser
is going to begin discarding tokens until
one that has a clear role in the language
is found and that's going to try to
restart itself and continue from that
point on. And these tokens, the ones that
it's looking for are called the
Synchronizing Tokens. And these are just
tokens that have a well-known role in the
language and so that we can reliably
identify where we are. So, a typical
strategy might be to try to skip to the
end of a statement or to the end of a
function if an error is found in a
statement or function and then begin
parsing either the next statement or the
next function. So let's look at a simple
hypothetical example of panic mode error
recovery. So here's an expression. Clearly
it has a problem. We shouldn't have two
plus signs in a row so something has gone
wrong here at the second plus and what's
going to happen is the parser is going to
come along. The parser is going to be
proceeding from left to right. It's gonna
see the open-paren, it's gonna see the
number one, it's gonna see the plus
everything is good and then it's gonna see
the second plus and it's not gonna know
what to do. It's going to realize. That
it's stuck and that there's no expression
in the language that has two p lus signs
in a row and it needs to do something to
recover. It's encountered a parsing error
and it has to take some error action at
this point. So in panic mode recovery,
what it's going to do is it's going to hit
the panic button. So right at this point,
it's going to say I give up, I'm not
parsing normally anymore. It goes into a
different mode. Where is simply throwing
away input until it finds something that
it recognizes and for example, we could
say that the policy in this particular,
for this particular kind of error, is to
skip ahead to the next integer and then
try to continue. So, we'll just throw away
the plus in this case and then it would
restart here at the two, expecting to see
another integer. Try to finish off this
expression and it would treat that as one
+ two and then the parenthesis would match
and the rest of the expression would parse
just fine. Now in tools such Bison, which
is widely used parser generator and one
that you may use for the project, there is
a special terminal symbol called error to
describe how much input to skip and the
productions that are given in Bison look
like this. So you would say at the
possibilities for e are that e could be an
integer, e could be an. The sum of the two
e's, two expressions, it could be a
parenthesized expression or if none of
this work, okay. So these are the normal
productions. Alright, If none of those
work, then we could try some of these
productions that have error in them. And
error is a special symbol for Bison and it
says, well, these are the alternatives to
try if these things over here didn't work.
So, if you find an error. Let's focus on
this one right here so if this says that
if you find an error while you're trying
to parse an e. Okay, we haven't actually
said how that works yet. We'll see that in
the future videos but conceptually, the
parser is trying to recognize one of these
kinds of expressions here. It's in a state
where it thinks it wanted to see an
integer or a + or a parenthesized
expression and if that isn't working out i
f it get stuck well then hit the panic
button and you can declare that it's in
error state and it can throw away all the
input. This error will match all the input
up to the next integer. And then this
whole thing could be counted as an e. As
one of these things and then we will try
to continue the parsing. Similarly, if we
encounter an error somewhere inside a pair
of match parenthesis, well, we could just
throw away the whole thing and just reset
at the parenthesis boundaries and they
continue parsing. So these are two
possible error recovery strategies if we
find an error for this particular kind of
symbol in the grammar. And you can have
these error, These productions that
involved the error token for, for as many
different kinds of symbols in the language
as you like. Another common strategy is to
use what are known as error productions
and this specify known common mistakes
that programmers make adjust as
alternative productions in the grammar. So
here's a simple example, let's say we were
working on a programming language or
compiler for a programming language that
was used by a lot of mathematicians and
instead of writing Five  x like computer
scientists do, these guys always wanted to
write five  x to just juxtapose the five
and the x to look more like normal
mathematical notation. And they complain
that this is always giving them parser
errors. If the parser is just complaining
over and over again then this is not a
well formed expression. Well, we could
just go in to our grammar and add a
production that made of, of well form. We
could just say well now it's legal, if I
have that one kind of expression is just
to have two expressions that [inaudible]
opposed next to each other with no
intervening operator. And this, has a
disadvantage obviously of complicating the
grammar. If we do this a lot our grammar
is gonna get a lot harder to understand.
It's gonna be a lot harder to maintain and
essentially all this is doing is promoting
common mistakes to alternative syntax but
this is used in practice. Peo ple do this
sort of thing and you will see for example
when you use TCC and other production C
compilers they will often warn you about
things you're not supposed to do but
they'll accept them anyway and this is
essentially the mechanism by which they do
that. Last strategy I want to talk about a
little bit is error correction. So, so far
we've just talked about strategies for
detecting errors but we could also try to
fix errors that is if the program has
mistakes in it, the compiler could try to
help the program out and say oh, you
obviously didn't mean to write that. Let
me try to find a program for you that,
that works. And, these kind of corrections
in some sense we wanted to find programs
that are nearby, programs that aren't too
different from the programs at the, that
the programmer supplied but we couldn't
compile correctly. And there's a few
different things that you can do to the
things that people have tried are things
like token insertions and deletions. So
here you'd like to minimize the edit
distance. That would be the metric that
you would use to determine whether a
program was close to the original program,
that the programmer supplied. You could
also do exhaustive search within some
bounce to try all possible programs that
are close to the program that was
supplied. And, a couple of disadvantages
to this actually, number of disadvantages.
You can imagine that this is hard to
implement. It, it's actually quite
complex. This will slow down the parsing
of correct programs because we need to
keep enough state around that we can
manage the search or, or the editing in
the case of that way actually doing
counter and error and of course nearby is
not really, is not really that clear what
that means and various notions of nearby
may or may not actually take us to a
program of the, the programmer would
actually be happy with. The best one
example of error correction is the
compiler PL [crosstalk]. This is PL
[inaudible] compiler, that's the PL part
and the C stands for either correction or
Cornell which is where the compiler was
built and PL [crosstalk] is well-known for
being willing to compile absolutely
anything. You could, you could give it the
phone book. You can and people did give it
things like speech from Hamlet soliloquy
and it would print out a lot of error
messages. Sometimes, these error messages
would be very funny to read. And it would,
in the end, do correction and produce
always a valid running PL [inaudible]
program. And you might ask why do people
bother with that? It doesn't seem but that
may not seem very compelling To us today.
And have to realize that when this work
was done back in the 1970s people live in
a very different world. There was a very
slow recompilation cycle. It could take a
whole day To get your program To compile
and run, you would essentially submit your
program in the morning and you might not
get results back until the afternoon. And,
with that kind of turnaround cycle, Even
one syntax error in your program was
devastating. You can lose a whole day
because you mistype the keyword and having
the compiler try to take a stab at finding
a working program for you if the
correction was small and you save an
entire day, you know to think it can fix
that one small mistake you made and give
you a valid run, that was actually a
useful thing to do. And so the goal then
was to find as many errors in one cycle as
possible. They would try, they would try
to find as many errors to try to recover.
Find as many errors as possible. Give you
as good feedback as possible so you could
fix as many errors, avoid as many retry
cycles as possible. And, and even possibly
automatically correct the program. So that
you could see if the correction were right
and, and then possibly the, the results
you got back were useful on the
[inaudible] to do even more debugging
before the next round. Now today, we're in
a completely different situation. We were
very fast, almost interactive
recompilation cycle for many projects and
as a result, users generally aren't
interested in finding many errors. They
ten d to correct only one error per cycle.
Compilers still report many errors, I'll
give you lots and lots of errors but my
observation certainly might have it.
Personally, what I see many other people
do is they only fix the first one because
it's the most reliable and the one that
definitely needs to be fixed before,
before you can try to compile again. If
the compilation is fast enough, that's
probably the most proactive thing to do.
And as result, complex error recovery
today is just less compelling than it was
a few decades ago.