hey what's going on everyone my name is
Tyler and welcome to episode three of
our building a interpreter from scratch
Series so in the previous episode we
finished the AST types for our basic
interpreter and the parser that we're
going to be implementing today however I
wanted to quickly note that in the
description of all of these videos there
will be a link to a GitHub page
containing all of the source code for
every single lesson so
um previously I never made GitHub source
code links available here I'm deciding
to do so as there's going to be a lot to
this and if you get lost or just want to
go back and actually have a reference to
follow along then you can follow along
here plus I'll also go through and
actually add comments to the source and
stuff like that that'll make it a little
bit easier to read so currently there's
episode one and two right here and the
other thing I wanted to show you guys is
a really cool reference called AST
Explorer and it's that https htex
explore.net this will also be linked in
the description below but what this is
is it's a way for us to kind of check
our AST against a popular other popular
programming language parsers for example
here's the Parson parser for JavaScript
using Acorn and we can see what happens
when we type in code so let x equals 45
and we can see that it actually shows us
kind of what we should kind of be
striving for right a variable
declaration statements with a declarator
of an identifier and an initial value of
literal we can kind of see how do how
does JavaScript handle
these kind of complex statements right
so how do they handle a function
declaration or parameter lists and
things like that so if you ever get lost
or want to extend the language but you
also kind of want to base it off of a
language of your favorite choosing you
can actually do this and kind of play
around and just see what should be
happening right it's really useful for
things like order of operations
so we can see here that this is what
we'll have working by the end of this
video we'll have things like this
working
Etc where we'll be able to take in
binary expressions and we'll want it to
be right recursive as we can see here
it's not left recursive so let's
actually get started now and implement
the parser for our basic language types
that we have so far so we're going to
implement a parser that'll support our
program node numeric literal an
identifier and a binary expression but
the last thing we need to do before we
can actually get started with that is
change some code in the lexer currently
we have a few different token types we
have closed paren open paren equals
binary operators let identifiers and
numbers however we need to add an
additional type called an eof token and
this signifies
the end of file so you can think of an
eof as a token that's not really visible
it's not visible but it signifies the
last character in a file this is going
to be really useful and cause a lot less
issues when we're in our parser itself
so we're going to add this token and all
we're going to do is inside of our
tokenize function after our while loop
before we return the tokens let's just
do return or sorry we're going to do
tokens dot push
and we're just going to add a token
which is going to have the type
of token type Dot eof
and the value is just going to be eof or
ends
a file like so and that's all we're
going to do we're just going to make
sure that we actually add our end of
file token
um
just in case so that way we don't really
have to worry about that so now we can
actually get started with episode three
so what I'm going to do is I'm going to
open up the pan prompt type in copy
episode 2 and so we're going to make
sure this is recursive so I'm going to
make sure to add a dash r
and I'm going to create our episode
three
parser folder and then we're going to CD
into episode three
like that
and there we go so now we can actually
view this in vs code and get started
with our parser so let's open this
invisible Studio okay
okay so this is everyone's favorite part
typically the parser is the most fun to
implement and also the most complicated
but we're going to walk through this and
go step by step so let's create a
parser.ts file
and what we're going to want to do is
we're going to want to import our types
from our AST so we're going to want to
import a statements
a program
a expression a binary
expression
a numeric literal
as well as an identifier like so so
we're going to import all of the types
we need
from our from these files so we can
actually get started with that we're
also going to need to import a node type
we're going to need to open import
sorry not node type we're going to need
to import from The Elixir so we're going
to need the tokenize
function so we're going to import
there we go if I can type
from dot slash
and we're going to get this from the
alexa.ts so we're going to need our
tokenize as well as our token
and token type values like this so now
that we have all these let's create a
class and we're going to export this as
defaults we're going to call it
um parser
now the job of the parser is to take in
our tokens that we created from our
tokenizer so what we're going to do is
we're going to do const actually we'll
make this a private variable we'll call
it tokens it's of type token array and
let's give it a default value of an
empty array next we're going to want to
create a public method and we're going
to call this produce
is T like so
and it's going to take in a string which
is the source code and what we want to
do is we want to return a program so
we're going to return
a program like so
so I'm going to type return Pro
and now let's actually create this
program so we're going to do const
program is equal to and we're going to
define a program type so we're going to
say this is of type program and what we
want is for a program so we can recall a
program node consists of this right here
so let's just copy this over
and get rid of that
and there we go now we have our program
type that we can produce like so let's
also use the source code to produce our
tokens array so we can save this Dot
tokens is equal to and we'll call our
tokenize function
and we're going to pass in the source
code like so so there we go now we have
the ability to produce an AST of type
program where each element in this body
is going to be an array of statements so
what we're going to want to do is we're
going to want to Loop while we have
tokens left
in our program so what we're going to do
is we're going to do while
not
eof like that and we're going to call
this this dots not eof
so we're just going to Loop while we're
not at the end of the file so we're
going to create a function for this
privates nuts eof
which is going to return a Boolean and
all we're going to do is we're just
going to do return
this dots
tokens of 0 dots type is equal to or is
not equal to
and we're going to do token type Dot eof
so what this is saying is return this
dot tokens basically the first token DOT
type is not equal to end up file and
we're just going to return true if it
isn't if it is then we know we're at the
end of the file and we should not
continue parsing so that's basically it
for that we're going to parse
and there we go and while we're parsing
what we're going to want to do is we're
going to want to append to the body
every single statement we find so we're
going to call this dot or sorry we're
going to do program dot body dot push
and we're going to push on a new
statement so we're going to do this dots
um stmt like that now a statements I'm
going to call it parse statements this
function we haven't created but let's go
ahead and create it and this is going to
be basically the entry point for our
parser so in here I'm going to go down
here and go private
part statement which returns in
statements like so and there we go this
will actually be the end of our produce
AST function for a good bit of time
there's not going to need to be much
that we do in here until later we
actually get into some complex error
handling so I'm actually going to just
going to minimize this
okay
so to produce a statement we kind of
need to look at our AST and say well we
don't really have any statements that
we're trying to deal with we've already
dealt with the program which is the only
type of statement these are all
Expressions so for now we actually don't
have anything to parse in the future
we'll have different types of statements
like function expressions or sorry
function declaration statements try
catch blocks variable declarations while
Loops etc etc but for now we don't
really have anything so we skip to parse
expression and what we're going to do is
we're just going to do return this dots
parse
expression like so
and now we can actually kind of get
started doing stuff so we're going to
create our parse expression function
which is going to return an expression
now since expression inherits from
statements this works right so an
expression is a statement but a
statement is not an expression so now
what we can do is we can say okay what
type do we want to parse first let's for
now just parse the primary expressions
like numeric literals and identifiers so
we're going to create a function
called parse primary
expression it's going to return an
expression
and what we're going to do is we need to
parse and determine what our current
token is to determine whether we're an
identifier or a numeric literal so to
get access to the current token I'm just
going to say TK is equal to this dots
tokens at index 0. however this looks
really ugly and in the future we might
want to change the way this actually
works so what we're going to do is we're
going to change this to be its own
function so we're going to come up here
and add a function called X
then all it's going to do is return
this dots tokens at index 0 as a token
just in case typescript has any issues
with that and there we go so now we have
this at function which will simply
return the current token we're at so
this starts
there we go
and now we're just going to do token
dots
type just like that so now we can do a
big if case or we can actually do a
switch case as well so we're going to do
switch on TK
and we're going to handle the case where
it's of type token type Dot and we want
to build a handle an identifier right so
what we're going to do is we're just
going to return an identifier
like so so what we need to do is we need
to create an identifier type so we're
going to say this kind is identifier
in the symbol
is equal to
this dot x dot value however there's an
issue here if we think about how this
would work right let's just kind of take
a quick look at our code by actually
first calling this function from inside
our parse expression so we're going to
return this Dot
uh
cross primary
and there we go and then also just
quickly adding a defaults
return
um
as
we're just gonna lie real quick to our
compiler there we go right so let's
imagine what would actually happen if we
were to pass in a source that looks
something like this if we just passed in
the variable Foo bar into a program what
would happen is we would have two tokens
and our tokens array it would not be the
end of the file so what would happen is
it would call program.body.push it would
call parse statement which would return
a statement parse statement we'll call
parse expression parse expression we'll
call parse primary and parse primary is
going to get the type of the token we're
currently at which again is of type
identifier right because Fubar would be
an identifier
it's going to hit this switch and it's
going to return an identifier however
though returning back through the call
chain it's going to iteratively keep
doing this forever since we're not
actually getting rid of that token we
want to advance so we're at the eof
so what we're going to do is we're going
to instead of doing this dot at dot
value we're going to create a function
called Advance which simply Returns the
previous token and increments it or AKA
gets rid of it so what we're going to do
is we're going to create a function
called
next sorry there we go or we can also
call it eats is a common term you'll see
so what we're going to do is we're going
to do let's or a const prev is equal to
this dot at
as a token or what we can do is we can
just do this dot tokens dot shift and
say it's a token because we know it'll
be a token and now we have this previous
token we can just simply return
like so so now we have the ability to
get a token that we are just at as well
as advance to the next token and this is
just going to remove it from the
beginning of the array
okay so now instead of calling this dot
at dot value we'll call
this dot eats
dot value and there we go now we have
the ability to parse a identifier type
now let's also add supports
for parsing a token of type number and
what we're going to do is say this is of
type numeric
literal
this is no longer a number this or a new
identifier this is a numeric literal and
a numeric literal if we look at the type
a numeric literal is going to contain a
value field containing the actual number
entered in the code so we're going to do
value
and what we're going to do is we're
going to do parse floats of are this dot
eats
dots value like so now the reason we're
doing parse floats not parse ends is
because currently we only support
um integers but in the future we will
support floating Point values and right
now we want to make sure that we can
actually parse those and handle those so
there we go now we have the ability in
our parse primary expression to actually
parse a primary expression and in the
default case instead of returning like
this what we're going to end up doing
rights is this is going to trick the
compiler
for typescripts right what we're going
to do is we're going to do a console
.air and we're just going to say
unexpected
token found during
parsing
and what we're going to do is we're
going to actually give the token those
just phones so this dot ants like so and
then we're just going to do Deno dot
exits of one and now we don't need to
trick the compiler so what we're doing
here is we're saying if we get to a
private primary expression we're not
going to handle anything else at this
point in time the most high priority
types are primary Expressions they are
literal types it cannot get any more
priority than that so if we make it down
here and we have no clue what this token
is then we must have gotten to an
unexpected token right maybe they typed
in two parentheses instead of one or
something like that now that we have
this working let's actually go ahead and
quickly test this out before we
Implement binary Expressions because
they're a little bit more complex so
let's create a main.ts file
and in here let's also create a folder
that's going to contain all of our
not compiler we'll call it
front end code and I'm going to add the
AST The Elixir as well as the parser and
there we go and now we're just going to
import
parser from our front end dot slash
parser.ts
and in here we're just going to
implement our Ripple
function like so so this is going to be
async
function of Ripple let's just make sure
we actually don't forget to call it
and what we're going to do is we're just
going to do punch parser
is equal to a new parser so we have our
parser now
we're going to just do a while true Loop
so we're going to keep iterating
basically forever I'm just going to do a
const.log
um
Rebel V
0.1 right
so now we have this Ripple that we can
use and what we're going to do is we're
going to do a const
is equal to prompts which is going to
actually ask the user in the terminal
for some input we're just going to do a
greater than sunk that's what everyone
does and then we're just going to do if
no inputs
or if input dot contains or not contains
sorry dot includes
exits then we're just going to do a Deno
dot exit
so this is just going to check
for no user
or exit keyword there we go and now we
know if we make it to this point the
user wants to enter code so we're going
to do const AST is equal to our const
program
I'll call it is equal to and we're going
to do parser
dot produce AST and we're going to pass
in our source code which is of type
input so we're going to do inputs
and there we go I also don't need to
make this asynchronous I don't know I
thought I did and there we go now we can
actually console.log our program that
we're getting back and remember our
program is of type program so let's
actually quickly give this a quick run
and just see if this all works
so we can open up our terminal clear it
out and do a Deno
run
Dash a because we want to
allow terminal access and in the future
we'll also want other stuff so we're
just going to do Dash a main dot TS here
we can see our Ripple is starting up and
we can enter something like exit and
it'll exit let's enter something like
the value 10 and what do you know we get
a program type right it's of kind
program the body though is a single
value of numeric literal we can enter 10
x in Foo bar and what you'll see is we
get a program which has an array
containing three statements now these
three statements each are them
self-expressions but we can see that
this works now let's go ahead and try
typing something like let's and we can
see unexpected token found during
parsing value let type of two which is
if we recall type 2 is 0 1 2 oh a let
token so that makes sense
so there we go now let's actually go
ahead and implement the binary
expression and really see how the
recursive descent parser works so let's
actually get started now and Implement a
binary expression So currently we have
the ability to eat a token return the
token we're at in return if we're at an
end of file what we also want to be able
to do is parse from a statement we go to
a parser parse expression then we parse
a primary expression before we do that
though a primary expression has the
highest order of Precedence so what we
probably want to do is we want to handle
orders of
precedence currently the highest order
of Precedence is a primary
primary expression
however just above that would be an
additive
and just above that would be a multi
multiplicative expression above that
would be a unary or sorry below that
would be a unary
which we'll Implement in the next
episode hopefully
so these are kind of the Orders of
Precedence that we'll be dealing with a
primary expression is the highest order
of Precedence we want this value to be
evaluated first right a unit expression
is just above that then we have
multiplicative and additive expression
here we would have something like a
comparison
then we would have things like logical
Expressions so things like the and and
or keywords and then up here we'd have
things like function
function call and a member
as well as things like
expression now for now we're not going
to deal with any of these but I just
wanted to kind of show you that the
order of Precedence is important and
it's important to keep in mind that the
higher precedence of value is we
actually want to parse that last because
that'll actually give it more precedence
in the tree itself so let's get started
by implementing the multiplicative
Addison or um comparison Expressions we
already have primary out of the way so
let's Implement multiplicative and
additive so instead of from parsed
expression we call parse primary let's
call
call additive so we'll do this stop
parse
additive
expression
like so and we're just going to for now
just return these up to call stack so
let's create this method called parse
expression which returns a expr type
expression right
now what we want to do because in
additive expression has left hand
precedence right if you do something
like 10 plus 5 minus 5. what we want to
happen is this whole thing is an
additive expression where the operator
is minus
the right hand side is 5 and the left
hand side is its own additive expression
right that's the same thing as wrapping
this in parentheses so that's what we
want to do we want to implement left
hand precedence so to do that we
actually parse the left hand value first
so we do left is equal to and what we're
going to do is we're just going to do
this
dot parse primary expression because to
signify presidents what we want to do is
parse the left hand side first
which will then parse 10
then we'll actually handle the operators
and this will all bubble up so we're
going to parse a primary expression
which is then going to get these values
here
now after we parse the left hand side we
actually want to do a while loop two
parse the operator token itself so we're
going to do while
this dot at dot value is equal to a plus
or this dot X
thoughts
is equal to a minus so while there are
still operators in between an expression
and a right-hand side we're going to
parse this what we're going to want to
do is get the operator
by doing this dot eats
and what we're going to do is pass in
the value like so
then we're going to want to get access
to the right hand side
because after an operator after we eat
this value the current value is going to
be
either a 5 or for example
it could be another expression like
something like this so we want to build
a handle that so right is equal to this
dot parse
we're going to parse a primary
expression this time and now we have
everything we need to make a binary
expression we have a kind a left-hand
side a right hand side and an operator
now what we're going to do is we're just
going to do const by knock
of type binary
expression
has a kind of
[Applause]
binary expression like so
five minutes two equals there we go so
it has a kind of binary expression as a
left value
a rights value ends an operator value
like so and now we have this type of
binary expression now you may be tempted
to think oh so we just return this here
right we return
R by not like so and we're done and
that's not the case we actually want to
return
outside of here so we want you to return
left but now we're not capturing the Spy
knob and what we want to do to support
this left recursive rules is we actually
want to say instead of this
we just want to say left
is equal to a new
binary
expression
like so and the reason we can't is
because this is a constant
okay so let's kind of take a look at
what we just did we parse the left hand
side and that's because we want to be
able to support recursive precedence
then we can imagine if this is our code
right here
10 plus 5 minus 5. what will happen is
we'll parse this left hand side we'll
get a 10. then we'll get an operator
because we'll be found at a plus we'll
get a right hand side which is a 5 at
this case
then we're going to say that is equal to
the left so this whole thing becomes
this right here then we get a minus so
we're back in this loop again then we
get our right which will be a 5. and
this whole thing will now become left
again through this assignment and we
return it up and bubble it up the tree
and by the time we're done with this
we'll just have an eof token in our eof
and our body will contain these proper
types so that's a lot that's a lot to
take in but let's actually give this a
shot and see if this works so
um did not mean to open Discord there we
go
okay let's actually give this a quick
run so denor run Dash a main.ts let's
make sure we actually call parse
additive and we do here we go so now we
can do something like 10 minus 5. in
what do you know you can actually see
that we get a type of program our body
contains one element and that is a
binary expression where the left hand
side is a numeric literal
right 10 the right hand side is a
numeric literal and the operator is
minus this also works like this so now
we would expect to get 10 minus X
plus Y and what do you know this is
recursive like so we get a program a
body binary the left hand side contains
the 10 minus X the right hand side
contains the y in the operator
separating these this is a left a right
and this whole thing is a binary this is
also a binary so it's very recursive if
you have any questions and want to go
more into depth with this ask me on my
Discord and I'll be sure to step through
this one-on-one if you'd like okay so
now we actually want to implement R
right 10 times 2. ah times isn't
supported right this is only an additive
expression so all we're going to do is
we're just going to copy this block
and instead from parse additive we're
going to change the name to parse
to multiplicative I think I spelled that
right and what we're going to do is from
additive we're going to call parse
multiplicative expression why why are we
going to call a multiplicative because
it has more precedence so we want to
parse it further down the tree remember
more precedence equals further down the
tree and we're going to also do the same
call here so parse multiplicative
expression
and there we go now to just change this
we do a mine array um slash
and we do a star
however if we also wanted to support
modulus we'll put this in right here
this is exactly where we'll support the
modulus operator like so so I'm just
going to add it like so I'm going to add
the modulus operator while we're on it
and while we're at it I'm also going to
change the Elixir to support the modulus
operator so in here we're going to
change this line like so we're going to
add a new rule
two supports
the modulus operator which is on the
exact same precedence of multiplication
division like so so there we go now we
have support for these three operators
and these are all multiplicative so they
will parse primary because that's
further down the chain let's give this a
quick run and make sure this works so we
can do 10 plus 5 times 3 and what you'll
see that's really neat is this follows
the order of operations right if we
think of this statement 10 plus 5 times
3 we want to evaluate 5 times 3 first
and then we want to add 10 to it and
that's exactly what this says we have an
operator of plus the left hand side is
10 and the right hand side says evaluate
this block
before getting to this plus operation so
this is really cool we can see the right
hand side has precedence we could also
do 10
modulus 2 minus three and sure enough we
get the modulus operator and now it's
left hand because left side recursion is
full load over right hand side because
of the Precedence just like our order of
operations now the one thing we're
missing besides exponents is PEMDAS for
our parentheses we're not handling
parentheses so if we do 34 minus 5 times
2 we expect this to work but it doesn't
because we haven't handled a
parenthesized expression so let's go
ahead and add support for a
parenthesized expression and this is
actually really simple to implement what
we're going to do is inside of our
default right before the default we're
going to say okay we've made it this far
right we've handled the case of an
identifier we've handled a number and
the future we'll handle booleans as well
as null types but here we also want to
handle the case where we're at a token
type of open paren just like that and
now what we're going to do is really
important we want to eat so this thought
eats
we're going to eat
opening
eat the opening parenthesis then we want
to get the value
so const value is equal to this dot
parse expression so we want to get the
value inside of the parenthesis and we
also want to eat
the
paren and then we just do return
value like so and this wants us to be in
a block that's why it's killing at us
and there we go now there's one big
issue with this and that is we're not
going to get error messages if there's a
closing Trend missing and I really want
to have error messages if an unexpected
token is found for example imagine
inside of our binary expression if we
parse this we maybe want to have a value
a rise if it's something we don't Define
so for example if we parse
a closing if we parse this value and we
don't get a closing print let's create a
function that will actually eat but if a
value is not defined like we can say it
expects a token type of closing paren
and we give an error message like
unexpected token found
inside
um
inside front says expression
like that and then we can do this dot
adds like so so imagine we actually want
to pass in our eat function
um an optional parameter like this and
let's just call it eat let's call it
expect
so expect is going to do the exact same
thing as eat however it's going to also
log an error if it fails so let's go
ahead and Implement our expect function
and all we're going to do is we're just
going to do private
expect it takes in a type of token
type and it takes in an err if let's
just do any for now
and what we're going to do is we're just
going to do if actually we'll get our
previous values so pre is equal to
dot tokens dot shifts
as a token then we're going to say if uh
no previous
or
prev DOT type is equal to type
then what we're going to want to do is
throw an error so we're just going to do
console.error
so we're going to do parser error and
then we're going to pass in our err
and this uh we're gonna pass in the
previous value that we are expecting and
then we're going to do expecting
and we're going to pass in type like so
there we go so not the most beautiful
error message but it should help a lot
with debugging then what we're going to
want to do is we're going to want to do
Deno
dot exits
give an error code of 1 and then return
our priv if we were successful so now
this expect function is going to handle
exactly what we want I'm also going to
get rid of this any type because I don't
really care that it's any type for now
and there we go so now if we look at our
code we see that a produce AST function
is actually going to make a call
to our lexor it's going to get all of
our tokens it's going to create this
program type while we're not at the end
of the file we're going to push through
and parse every statement we locate then
we're going to return the program
inside a parse statement we don't really
have anything to parse no variable
declarations functions nothing like that
so I'm going to parse an expression
inside of parse expression we don't
really have anything to parse either and
the future we'll be checking the look
ahead we'll be looking ahead to see what
tokens there are but for now we don't
need to look ahead we can look at our
current token and determine it so we
return a value from a additive
expression an additive expression simply
gets the left hand side and you can
imagine right if this is our expression
45 times 3 minus 5 what will happen is
it'll parse the left hand side that will
go to the primary in here then so we'll
get back a 45 then we're in the primary
at this point so it'll actually see this
star it'll parse the star and the right
hand side so it'll actually give this 45
times 3 will come back here as a binary
expression then we'll parse the operator
which will be minus
the right hand side will be five and
we'll return this binary expression
which encloses this one and that is why
we do the left precedence as well as why
we do additive before multiplicative
because multiplicative Expressions have
more precedence so hope you guys
understood this and hopefully this was a
good
um concept to learn in the next episode
we'll actually get started by traversing
this tree that we're creating right so
here we can do 45 minus five times three
let's do five times three plus four
and we see unexpected token inside print
size oh it's because this was supposed
to be right
a another thing so we do 45 minus 5
times 34 divided by Foo bar
and
oh I messed up the um eat function
um in the expect function it's if the
type does not equal that type then we
want to throw an error right this is
valid code right there so we'll do 45
minus
Foo Bar times
X Plus Y and there we go right this all
works so there we go in the next episode
we'll actually get started implementing
our interpreter so that's going to be
really exciting for those of you who
want to see how to implement a tree walk
interpreter and yeah and I'll see you
guys in the next video bye