welcome back to part number three
about bars am we
had they find some very simple parsers
then we developed in the second part
a few bars urge to go to a bar several
and you several bars in a row and
even doe the bars that we have defined are very primitive
they are already powerful enough to parse
a.m. arithmetic expressions that have like no deep structure
and and that's what we're going to do indicia lost
part of this lecture on barging here's the expressions that we're going to bars
and be want to have simple expressions that
are built from simple digits with addition and multiplication
I'm expression Gandhi me brent is sized
and moreover we want times to bind stronger
and blush and we won't bode have them to
associates to the right so what does that mean if we have a-plus B-plus she
we want to parse that a plush open brandy plushie
and every at 8 blush be dime si
we want to impart that as a plus be dime si
alright so this is fairly and conventional
just arithmetic expressions so how are we going to
emblem and this using those very very simple parser
that we defined in the previous two sections
well the first thing ever going to do as you're going to write down
a grammar for and these expressions
and an if you have taken
course in going by Lahr sore formal languages are
you know you lookin and a programming language
definition in the back where the grammar of the languages defined
you will find a grammar that looks very similar to this show
there's an expression there's a term there's a factor
and East three productions are used to encode
and the binding up the expressions and they can
defected these are defined like this in this regard to form
and an and coach
the ad shows a diff shell an expression is a term plus an expression
our Term a term is a factor dimes a derm
are a factor factors a digit or apprentice eyes expression
and a digit as well digit alright show that your day
recursion and bottoms but as I said
this is real standard encoding
of expressions in a grammar I'm
now what we're going to do is we're going to much Josh
this a grammar little bit and again
the it's also a very common every book an
on compiler she'll do this and often
and grammars are defined addition their way we'll do it they saying
an expression is a term followed by
plus an expression or the empty string
are absent on this in the AM departure and it doesn't recognize anything
an and then term as a factor
and followed by start term or
an again the bars are dead only recognizes the
an the empty input a game
so if we take this weekend
now immediately translated
this definition here which is recursive here
in expression is defined in their human expression
but there's first-term and and its recognizes the blusher
is here expression recognizes a derm
an a-plus and an expression
and then its returns an the expression
blush the term plus the expression and then this rom
is the and the anti-gay
alright so an you will image in the
return getter
and in his aim for term and the same
for factor so in some sense that going up to grammar
an has a one to one correspondence
and when this recursive and
an expression here and that's that then I think so
and some sense and decision the spartan
Combinator says they're called are like an internal DSL so incentive riding a
grammar
in some x31 the fine language like ya cadillacs
compiling that into another language
we can't do this all that has gone and use all the facilities
haskell to define helper functions and shown
and parsers are 10 I think
the the most elegant
you know internal DS house and that you can imagine
and and as I said you can do very sophisticated parsers
and you can push this I dear pretty far
now
next thing is we're going to define and evaluator
that takes a strain barges the and
tries to parse the string as an expression
and then return the resulting value
and if you we go back here
initiated for already
evaluating the an expression
as for parsing it biggest for parsing the plush
operator and then we're taking the term amor
adding the result of parsing the expression show
the result of this is already a parser offend
so instead of we're not even creating a parse tree
for immediately after parsing we're evaluating
the expression so that's what you see here we parse the expression
if in the end to it since this return
returns and either a
empty list or a single to left if it returns a single to left leading the
hatchery take that value
we take the first element which was the number and then there's the rest
the strain if this fails to parse the heads will throw an error
and this whole thing will fail so let's see here
if you're barging two dimes three-plus for
that should return two dimes 36 pledge for
as dan and guess what
that's the value we get and if we're evaluating
two dimes to replace for well we should get
is 3 bids for Saban times two ish 14
guess what is message as expected
okay in the exercises you will do
an sever all things red parsers
and in particular an one other thing said you will do
issue you will have to implement the sequencing operator
that we used but didn't define so
we have defiant various operators on partition one of the essential launch
these sequential composition we didn't define
and thats the main exercises this week
so and happy hacking
make sure you do your homework and see you next week
i buy