So now we have all the machinery we need
to tell if a string is valid.
However, it's going to turn out that's not enough.
Remember those upside down parse trees we talked about earlier?
We really wanted those, as well,
for our HTML and JavaScript programs
in order to interpret them--to get at their meaning correctly.
So here, I've written a pretty standard arithmetic expression grammar.
An expression can be a number
or an expression plus an expression
or an expression minus an expression or maybe
a negated expression, like negative 3.
And we'll want to build up parse trees for this.
Now this time, I've written the tokens as plus and minus and not
instead of the symbols, + or -.
That's our choice; we can do it either way we want.
And the particular format I'm going to pick
for our abstract syntax tree is
nested tuples--or nested lists, in Python.
So if we end up using this rule: expression goes to number,
we're just going to return the tuple:
("number", 5)--if the input was 5.
Similarly, if the input is something like: not 5,
We'll end up returning: ("not", of the "number", 5).
Note the nesting.
So let's say I call this number: number 1.
We really want to return this tuple:
"number"--in quotes, just as a string, so we know what it is--
followed by the value of the token.
If this was Thing Number 2 in our reduction rule--
not expression--I'd really want this to be filled with a 2.
If over here, this was a 3,
I would want to return "binop".
That stands for Binary Operator, binary just meaning "two things".
So things like: Plus, Minus, Times, and Divide--
those are arithmetic operations that take two arguments--
one on the left, and one on the right.
We call those Binary Operators, as a class, just to save space.
But whatever this third expression was,
that's what I'd want this subtree--
this subpart of my tuple--to be.
So just as we've seen before how we can
encode token rules in Python
and do some processing, like chopping off the quotes
after we've specified how the token works,
using regular expressions,
it's going to turn out that there's a similar way
for us to do that for grammar rules in Python.
Now let me explain a little bit about what's going on.
This format is totally arbitrary,
but it's going to be very easy for us to use
for assignments and to test your knowledge.
For tokens, we used a "t_" to mean
I'm defining a rule for a token.
For parsing rules,
we're going to use a "p_"
to define the name of a parsing rule.
And then here--just to help us out--
we're going to write down what the left-hand side of the rule is.
This is how you parse an expression
when that expression is a number.
And just as out token rules were, in some sense,
under-the-hood functions of this object, (t),
our parsing rules are under-the-hood functions of this object, (p).
And this is the parse tree--
or, more accurately, a number of parse trees.
Here's our rule, written out,
and this is very similar to:
(exp --> number)--except that there's no great way to write the arrow,
so instead, we'll just write a colon, by convention.
But you should view this as the arrow.
So this is: expression can be rewritten as NUMBER,
and we just put it in quotes, like a string, and then down here
we have to tell Python--or tell our parsing library--
how to build up the abstract syntax tree.
p[0] is our returned parse tree.
The numbering here is every one of these elements of our grammar rule--
except the colon gets a number.
So the expression on the left is zero,
This NUMBER over here is 1.
So the parse tree I want associated with this expression,
when we're all done,
is a tuple that I make, by combining the word "number"
with the value of this actual token.
Let me show you another one of these,
and then it'll be a little clearer.
So here, once again, I start with the (p_).
We're going to do that for all of our parsing rules.
Here's what I'm telling you how to parse; I'm telling you how to parse an expression.
There might be multiple different ways to parse an expression.
It could be a number, it could be a (not) expression.
So we use another underscore, in being a little more specific.
And then down here I've written out my grammar rule
in almost English--and again, this colon
is like the arrow that we would normally draw.
And then below that, I have written out
how to construct the final abstract syntax tree.
This expression is number zero, this (not) is number 1,
This expression is number 2, so we want our
parse tree for number zero
to be the tuple I make, by putting the word "not"--
so that I know what it is--in front of the parse tree for number 2.
If we were to see the input: NOT 5
executing these two rules, in the right order--
this one first, and then that one--
would give us this tree:
"not", ("number", 5).
Note the nesting.
I could alternatively draw it as--
This is just a Python was of encoding this visual representation.