Welcome back, guys! Okay so in the previous lecture we have started building our parser
and implemented numeric literals, that is the only AST node our parser recognized is the
NumericLiteral node. And we also have said that each AST node should have a
type. Currently our program just returns the numeric literal, but let's actually introduce
a separate type for the program. So from now on the Program will be of its own type - the
"Program" - which will contain the "body", which for now will be just still NumericLiteral.
Let's check whether it works, and yes - our AST is now of type Program and which
body is the NumericLiteral. And we've been treating the whole string as just the number.
In today's lecture we're going to introduce the tokenizer, and recall from the previous lecture,
the purpose of the tokenizer is exactly to extract stream of tokens of different types.
We will introduce the NUMBER token which is specifically in our grammar rule for the
NumericLiteral and we'll also introduced today the STRING token, right we will introduce the strings.
So let's start from defining the Tokenizer class. Okay and the main API method here
is the string initializing. Alright let's have the method which is called "init" and it should
initialize the string. And since the tokenizer works with individual characters, right it has to
group individual characters into tokens, it has to track the position of each character. And we'll
be tracking it in the "_cursor" property. And the tokenizer should return the next token on demand,
and this is exactly the main API method which is called "getNextToken"
and which will be called from the parser. Now the first thing we check is, if there are no more
tokens, right if we don't have any more tokens, we just return null. So let's introduce this new
helper method which is also in the tokenizer API, it's "hasMoreTokens", and the condition here is:
our cursor is still hasn't reached the end of the string, right that is the string length. Otherwise
we have to recognize the tokens which are in our grammar. So for now we just support numbers,
and we also should be recognizing always from the cursor position, right so initially for
example the cursor stands at the beginning, let's say we have the string "123abc",
then we have to move forward until we reach some known token, for example NUMBER,
and the next token here would be some identifier "abc". And as you can see it starts from the
current position of the cursor, so to make it more convenient let's put it into a variable
"string" which will be exactly from the cursor position, right we slice the original string
from the cursor position. And then the tokenizer actually works at the state machine.
That's why as we will see in the next lecture it's directly related to the Regular Expressions
which are exactly based on the Finite automata, that is on the State machines.
So for now let's make it just completely manually, right if we recognized that the current character
is a number, that is the "isNaN" function returns false, we're going to consume each
character from the string, right increasing the cursor position until we still have the digit,
right until we still have a number, and we collect all the digits into the "number" token.
And then when we collected the number we have to return the token for this number, and as we said
in the previous lecture, tokens have the type and the value associated with this type. In this case
the type is the NUMBER and the value is actually extracted number, right from multiple digits. Okay
that should be it for the numbers. Let's get back to parser and require now our Tokenizer module.
In this case we're going to introduce the constructor function for the parser where
we initialize the tokenizer, that is the same tokenizer will be reused for multiple strings,
and we may also set the string in the constructor to the empty string. And then
in the "parse" method we're going to initialize the tokenizer, right we're going to pass the
string to the tokenizer module and which will reset the cursor to the beginning of the string.
And now we should talk about concept of the Lookahead. Now the Recursive-descent parser
which we implement in this class is known as to be "predictive parsing". What is predictive? - it
means it can predict specific production based on looking ahead at the current token. So what we're
going to do is to prime the tokenizer by obtaining the first token which is exactly our "lookahead",
which means we extracted the first token and based on the type of this token we will be able
to route parsing process accordingly. Now since we need only one token to look ahead, such parser
corresponds to the LL(1) parser in the automated parsing theory, that is we need only one lookahead
to correctly predict which production to parse. And now let's get back to NumericLiteral. Instead
of using the full string we're going to take the token from the tokenizer. Now the NumericLiteral
should expect by its grammar rule the NUMBER token, right this is exactly what is written
in its grammar rule: the NumericLiteral is the NUMBER. So let's introduce this function called
"_eat" which will consume the current token and will advance the tokenizer to the next token.
And this "_eat" function should exactly expect the current lookahead to be of this exact type. And
now when we obtain the token we can use it in the actual value for the numeric literal production,
and we take it from the "token.value" which should contain the number. And now let's implement the
helper function "_eat". And once again, this function would check that the current token,
that is the lookahead, has exactly this type which is passed as the parameter. And since tokenizer
may return null for the token, and if we got into the state, this means we reached the end of the
string but we expected something - and we exactly throw the syntax error "unexpected end of input".
Otherwise if we do have a token but it's different type, we also throw the error "unexpected token"
and we expected something else. Once we have done all these checks we can return the actual token.
But before that, as we said we have to advance the tokenizer to the next token, that is update
our lookahead. So once again what is happening here: the Program calls the NumericLiteral,
NumericLiteral calls the "_eat" function, that is check that the current token is exactly the number
and advance the cursor. Once we get the token, we can return it as the "token.value". Okay that
should be it, let's go ahead and check that we still have correctly working NumericLiteral.
Let's go ahead and execute, and yes - we still have 42 which means our tokenizer works. So
let's go ahead and introduce today the second type of literals known as the string literals.
And with this our Program is becoming just Literal, right we're going to have
two types of literals: the Literal is either the NumericLiteral or the StringLiteral. Okay
and now let's go back to the tokenizer and add the STRING tokens. So let's start from the strings
and support the strings in the double quotes. So if we determine that the current symbol is
the double quote, which means we're entering the STRING state, in this case we're going to collect
all the characters of the string - let's use the variable "s" - and we basically go into the loop
by collecting just the characters, again advancing the cursor. And the stopping condition is:
we either reach the closing double quote or we are at the end of the file, that is in the end of the
string. So let's introduce this function "isEOF" which checks that we have reached the end of the
string, that is the cursor equals to the length. And once we are done we also have to consume
the closing double quote and also append it to the string. And the token type in this case
is the STRING, and the value is "s". And now going back to the parser, to the Literal node,
how do we determine whether we're looking at the numeric literal or the string literal?
Well, this comes exactly from the lookahead. So we check if the type of the lookahead is NUMBER,
this means we have to parse the NumericalLiteral. Otherwise if the lookahead token is of type
STRING, this means it's a StringLiteral - pretty much simple. And we don't support
yet any other types of literals so we throw syntax error "unexpected literal production".
And we already have the NumericalLiteral, let's add the StringLiteral. Now the handler
for the strings is pretty much similar to the numbers: we have to eat the current STRING token,
and instead of converting the value to the number, we just need to return the value between of
string quotation, right we have to strip the quotes and return the actual value of the string,
so we use the "slice" method from 1 to -1 that is stripping the quotes. And the type should be
of course "StringLiteral." Okay sounds good, that should be it, so let's get back to our test runner
and try parsing the string "hello". Right we put it into quotes, okay let's execute - and
there we go - we have the strings now. Okay let's check again the number - it still works.
Let's put number into the quotes - and we got the string "42",
right not the number 42 but the string. And the string in JavaScript for example also may be used
in single quotes which we don't support yet, and this is your first assignment - please go ahead
and add support for the single quotes which should be pretty much the same.
So once again today we introduced the tokenizer. Let's again take a look at our
numbers and strings in the tokenizer. As you can see, the handling is pretty much manual right now,
and this manual handling looks pretty verbose. In fact we implement here the manual state machine,
right we're entering some state: either the NUMBER state and then spin in the loop for the numbers,
or we enter the STRING state and spin in the loop for the strings. So in the next lecture
we will refactor this manual handling and will introduce Regular Expressions, that is
exactly what the tokenizers are about. That's it for today, thanks and see you in the class.