Now that we have an understanding of formal grammars,
we're going to need to use them to understand or describe HTML and JavaScript.
We're going to design together formal grammars that exactly capture HTML and JavaScript
or at least interesting subsets of them.
If we were trying to understand English sentences,
there is a special kind of diagram we could make.
Here I have a very high level partial grammar for English.
A sentence has a noun phrase, a verb phrase, and an object.
A noun phrase is just a decorated noun, like maybe a noun with an adjective in front of it.
A verb phrase is a decorated verb, maybe a verb with an adverb in front of it.
Then the object could be a noun phrase or a noun or something more complicated.
For example, here is a sentence: "Wes reads Romance of the Three Kingdoms."
Now, there are various different ways to diagram English sentences.
We'll do something relatively simple.
We just want to indicate which part matches which grammatical form.
Our noun phrase is going to be "Wes." Our verb phrase is "reads."
The object is "Romance of the Three Kingdoms."
We could divide it up so that the object falls under the phrase
or that we draw these slightly differently, but mostly we want to know which part goes where.
Who is doing the reading? Is it Wes or the book.
This sort or diagram will help us figure that out.
In fact, in formal languages or with a grammar like this,
there is a more common way, a more pictoral way of representing these sentences.
We can draw something that looks a bit like an inverted tree.
I'm going to take each one of these productive rules
and puts its left hand-side at the top,
and then give it children, or branches, based on which rule is chosen
and what's available on the right.
Here we have a sort of a pyramid-like shape, or what's officially called a parse tree.
Remember that syntactic analysis is sometimes called parsing.
This might not look like a tree, but what you want to do
is imagine the tree growing upside down.
Here is our tree, and at various places--although it's starting with the trunk or the root--
it branches out, and all of these intermediate parts in the tree
represent none terminals in the grammar.
All of the leaves right at the end represent terminals
or tokens in the final sentence or utterance.
This is called a parse tree by longstanding tradition.
We draw them upside down, starting at the root with the start nonterminal.
While we're here, you too should consider reading Romance of the Three Kingdoms.
Written in the 14th century, it's a Chinese historical novel
about the end of the Han Dynasty. Good stuff.
Here's one of our favorite grammars from before--a simple arithmetic expression grammar.
Let's say that our input is 1 plus 2 plus 3.
Here is a possible parse tree.
We start at the top, at the root, with our nonterminal expression.
Each time we have a number of children equal to the number of symbols
to the right of the arrow.
If I'm using expression goes to expression plus expression,
I have one node with three children.
I need to get 1 plus 2 plus 3, so I'm going to need to use this first rule
at least twice--once to get this plus sign and once to get that one.
Here I'm using it once--one instance of rule one.
Here I'm using it twice--another instance of rule one.
You'll note that they overlap.
The first time we use this rule we started drawing this part of the tree.
This expression node was the result.
The second time, it was the thing we were choosing to expand.
This is normal. This represents the recursive structure of a grammar.
In a parse tree like this, these parts at the that have no children
are called "leaves."
The parts in the middle are called "nodes."
Sometimes the leaves are called "leaf nodes," which is a bit ambiguous.
These are always going to be terminals.
The intermediate nodes are always going to be nonterminals.