welcome back in this video we're going to continue our lecture on lexical
analysis
with some examples from past programming languages were interesting like the core
problems arose
so sorry cock a little bit about fortran
and what are the interesting lexical rules in Fortran is that white spaces
insignificant
so white bass doesn't matter and something like
var1 which could be a variable name by one
is exactly the same as be a space are one so these two
program fragments have to mean exactly the same thing and the idea in Fortran
if they could take your program and you could delete all the blank from it and
that shouldn't change
with the program means that all let's take a look at an example
love how for trans white space role effects lexical analysis
you're a couple of Fortran code fragments United say this example is
taken from the dragon book
and actually a couple other later examples are also taken from an older
edition
up the Dragon Boat up anyway what we have here this is actually
the header I V for training and Luke and
you know it's a loop because it has the key word
do which is like four in modern
CRC plus plus so it's a it's a loop keyword
and then we have our iteration variable I and we have a range
that I will vary between so in this case I will go from
wine up to 25 and then this number five here this is a little bit
on something you don't see in modern languages I
in the old days in Fortran you would have your to statement at the top of the
loop and then
the size the loop or they all the statements included in the loop
but so were named by a label they came right after the two statements so
this the loop will extend from the
the header the the two statement down to the label 52 whatever state was able
with five all the statements in between
would be part of the loop and so the loop would execute
I'm those statements then we go back around to the other and we keep
executing those until
it done so for every one the values of the iteration very well in this case
12 25 now here's another go for a win
and as you can see this one is almost exactly the same
as the one above the only difference is
when reached which colors is here the
this particular fragment has Akala in that position
and this fragment as period and it turns out that this difference
I makes all the difference that these two
fragrance above code mean completely different things
so this fragrance the first one
is in fact a do look a as I said before so it has the other key word do
the label 5 the variable by and the range
125 now this fragment down here
this is actually a very able name do 5i
so if I was right it without the blanks remember the place no matter
this would be do 5i and then this is an assignment
equals the number 1.25
okay and so you can see here
the these symbols this secret is for sequences symbols is interpreted it
completely differently
depending on whether there's a period
or a comma for their %ah and so it's just a mobile more precise about that
how do we know
what do is solicits focus on the key word here to do
and when we're at this point when our focus is here
right after the O ants to keep in mind
that the that the way this is going to be implemented by a left to right: scams
or going to be
walking in this direction over the over the inchoate
looking at his character successfully and when our focus reaches this point we
can make a decision is this
a a is a key work could be seen the entire keyword do
and the problem is there we don't have enough information to make that decision
we don't know whether this is due
our weather is going to eventually be part of a variable name
I like 25 I and the only way to know is to look
ahead in the input to this position to see whether there's a comma or period
there
so this is an example of what's called else is that requires
look ahead in order to understand the role of do
as we're going left to right we have to
peek ahead in the input to see some simple to come later on
we can't possibly disambiguate a the role of two
until that point because up to this point sequences the symbols are exactly
the same and so the only thing at this thing which is a myth something as much
much further on
and as you can imagine having lotsa look ahead I complicates the implementation
of lexical analysis and so what are the goals
I in the design of lexical systems I is to minimize the amount of work ahead
about the amount of work ahead
that is required so you might wonder why fortran has this funny rule
about white space it turns out that I'm punch card machine that was
easy to add extra blanks by accident and
as a result they added this rule to the language to so the point where operators
wouldn't have to redo their work all the time
fortunate today we don't enter our programs anymore and punch cards
but this example does help us understand it better what we're trying to do in
lexical analysis
so as I said the goal is to partition the spring we're trying to buy this ring
up
into the logical units are language
and this is implemented by reading left to right so we're doing a left-right
scan
over the input recognizing one token at a time
and because of that look ahead may be required to decide where one token and
and the next token begins again I want to stress that look ahead is always
needed
up but we would like to minimize the amount of work ahead in fact we'd like
to bounded
to some cuts been but that this because that will simplify
the implementation up like the klan allies are quite a bit
now just illustrate that look ahead is something that we always have to
worry about let's consider this example what we look at before
and just notice either way we're reading left to right
let's look at this keyword else here well we've read the e
we have to decide is that a variable name
or some simple by itself or do we want to
consider it together with the symbols apollo it
and so the look-ahead issue here when we after his candy we have decided that
set by itself or is it part of a larger lexical unit and
know there are single character variable names in this example like I Janz
and so it's not unreasonable that he could also be one
and another example a is this double he calls
when we read a single equal sign how do we decide
whether that's a single equals like these other assignments
or that it's really a double eagles well in order to do that if we're
have our focus point is right here we have to look ahead and see
that there's another equals coming up and that's how we know or how we will
now
that we want to combine the two into a single simple instead of
considering this equals by itself
that another example from a a language from long ago
peel wine I is a interesting language it was designed by IBM
and it stands for programming
language one
I it was designed to be the programming language
at least within IBM there be used by everybody
as opposed to encompass all the features the any programmer would ever need
and as such he was both be very very general and have very few restrictions
and so one of the features appeal one
I is that keywords are not preserved so
PNP 01 you can use the keyword both
as a keyword and also as a variable so you can use the keywords and other roles
rather than keywords and that means you can rate
interesting the interesting sentences are interesting programs like this
you know it is read this out loud because it sounds interesting if health
and then equal sell sell sell sequels that
and the correct organization here course
is thats the this is a keyword
this is the key word and this is the key word
and the other things which colors here are all variables these are all
variable names and as you can imagine
this makes a lexical analysis somewhat difficult because
when we're just scanning left to right like when we're coming through here went
there at this point
you know how do we decide whether these things are going to be very well names
or or keywords without seeing what's going on the rest of the expression so
let's call the house is in pa1 I was quite challenging
so here's another example from pa1 here we have
a program fragment we have the word declare
and then an open for an hour and a close friend encompassing a bunch of our guys
I point out the
bells friends here and then just allister N Things
inside the Kerens made it turns out
that depending on the larger context in which this
all a expression sets this could be either a keyword
war it could be an array reference now anyway yet I mean be clear here could
either be keyword
or it could be the name of an array in these could be the indices to the right
and as it happens that there is no way
looking at just this much that we can decide
I this fragment is valid Isabella declaration and it's also a valid array
reference so it would depend on what came next day might depend on for
example whether there was
equal sign here in which case it would be interpreted
as an assignment and and be clear would be the name with an array
and the interesting thing about this example is that because the number
arguments in here is unbounded there could be
and have them for any n a this requires
on pounded look ahead
okay so to implement this properly a
at risk anything left to right to decide whether declare again
is the key word or a reference we would have to scan beyond this entire argument
list to see
what came next
for training peel one were designed in the 1950s and 1960s
respectively and those experiences tell us a lot about what not to do
in the electrical design a programming languages so things are a lot better
today but the problems have not gone away completely and values
an example from people's plus illustrate this
I so here's an example C pas plus templates in tax which you may be
familiar with
or you may have seen the similar syntax in Java
and see what was another operator
called Ustream input so this operator here
are read from it InputStream in stores the result in a variable
and the problem is here there's a conflict with nested templates
so for example if I have a
template I operation that looks like this
okay know is what happens here so my intention here
is to have nested application of templates by I wind up with a greater
than signs together at the end
and this looks just like the stream operator and the question is what should
the lexical analyzer do
I should its I interpret this as
to close brackets for templates are sure that interpret it as a
to greater than sign stuck together as a stream operator
and it turns out that for a very long time I think most people as possible by
others have no fix this
this report was compiler in this situation would regard this as a spin
operator and you get a syntax error
and what do you think the solution was it turns out that the only fact that you
could really do to make this
so likely analyze the correct way was to insert a blank the we have to write
this and you have to remember to put the blank in there
so that the two greater than signs were not together and no that's kinda ugly
thats we have two put in white space to fix
the lexical analysis of the program
so to summarize the goal lexical analysis is to partition the InputStream
intellect themes
things or have dropped and dividing lines in the string to the side
where the like seems like and we will identify the token
each like seeing and because exactly because we're doing a left rates can
sometimes
we have to have a look at some point we have to peek ahead in the InputStream
to figure out what the current string we're looking at the current substring
we're looking at what role it plays
in the language