The parse tree is a graph that shows how a particular string was derived using some
context free grammar. These trees have a direct connection to left most and right
most derivations which we shall explain now. One important use of the tree
representation of derivations is it let's us express the important concept of
ambiguity in grammars. That is, unambiguity or the ability for a grammar
to provide a unique tree structure for every string in its language is vital. For
example if a programming line which has ambiguity, then there are programs with
two or more distinct meanings. The same is true of a grammar for an actual language,
it would be insufficient to provide an intended meaning for all valid sentences
of the language. Parse trees for a [inaudible] tree are trees whose nodes are
each associated with a symbol of G. I'm going to draw you a little tree here.
Okay. Leaves are always labeled by either a terminal or by epsilon, so we might draw
for example an A on that one a terminal B on that one, and perhaps epsilon on that.
Interior nodes are labeled by a variable. Here are some examples. The important
property that makes a tree a parse tree is that there is a production of the grammar
with the label of the node in question as its head and the labels of its children
read left to right as its body. Okay? For example, if you look at this parse tree we
would infer that A goes to BC is a production also B goes to little A, little
B is a production and C goes to epsilon is a production. The root must be labeled by
the start symbol. In our example tree here I'm going to have to guess that if this is
the root, then "A" is in fact the start symbol. Here's a parse tree using the
grammar for the balanced parentheses that we discussed earlier. Notice how each
interior node is labeled by a variable. Here, here, here and here. Must be asked
because that's the only variable we have. Each leaf is labeled by a terminal, either
a left or right parenthesis, these are here, here, here, here, here and here.
Okay, the production of the root is S goes to [sound]. You can sort of see that by
looking at the root and its two children here's another interior node and the
labels of its children are left paren as right paren and you know that left paren
as right paren is another production of the grammar that's right here. And here we
have an example of a interior node labeled S and its children labeled left paren and
right paren that corresponds to this production body right here. You have the
same exact use of that production, here. Okay. The yield of the par street is the
string of labels and the leaves from the left. This order of leaves is the order
you visit them in during a pre-order traversal, path which would look something
like this. That's sort of a, pre order transversal path goes around the tree,
counter-clockwise. The order in which you visit the leaves is the order in which
their labels appear in the yield. So here the yield is left paren, left paren, right
paren, right paren, left paren, right paren. That's what we said here. In what
follows, we're also going to talk about parse trees with a route A that may not be
the start symbol. These trees follow all the other requirements of the parse tree.
The leaves are labeled by terminals or epsilon and an interior node with its
children form a production of the grammar. We're going to show how to convert
[inaudible] to leftmost to rightmost derivations and vice versa. As is often
the case, a [inaudible] made easier by proving something more general than what
we really need. In this case we'll talk about generalized parts tree that can have
any root labels, say "A". And we'll talk about left most and right most irrevations
for many variable "A". We'll prove two statements... One is that there is a parse
tree with root A and the yield W. And there is a left most derivation of W from
A [inaudible]. The second statement is the converse, that for every left most
derivation of W from A there is a general bias parse tree with root A and yield W.
The matter of right most derivations is completely analogous. We will start with
point one by showing how to convert parse trees to left most derivations. The proof
is an induction on the height of the tree. The basis is height one. That is a tree
consisting of a root label by some variable, A, and one or more leaves. They
must be a production with head A and body being in the labels of the leaves from
left to right. That's A one though A N in this picture. Then, A derives the yield of
the tree by the one step left most [inaudible] in which this production is
used. For the induction we'll assume statement one for height less than H and
prove it for H That is, we assume for every parse tree with root A and height of
up to H minus one there is a leftmost derivation of its yield from its root. Now
let's look at a parse tree of height H. The case H=1 is the basis, so H is at
least two. Thus the production used at the root has at least one variable on its
right side. Say this tree has root A and the children of the root labeled X1
through Xn. If Xi is variable, then it is the root of some sub tree of height at
most h minus one and some yield, say Wi. If XI is a terminal or epsilon then we
imagine XI is a root of a trivial tree, not a parse tree, that consists only of a
node labeled XI. The yield of this tree is just Xi itself, but for consistency we
shall refer to Xi as the stream of terminals, Wi. The yield of the entire
tree is W, which is W1 through Wn. We can put together a left most derivation of W
from A as follows. Start by applying the production at the root, so the second step
is X1, X2 up to Xn. That's this. Okay, now we need the left most derivation of W one
from X one. X one is the terminal that equals W one so we're already there. And
this step is then really zero step on the other hand, if X1 is a variable and we
apply the inductive hypothesis, the sub tree with root X1 and yield W1 has height
at most H minus one, so there is a left most derivation at W1 from X1. In that
case, this X1 has been replaced now left most derivation by W1 and this, goes to
star represents all the steps that were necessary to replace X1 by W1. Either way
we can conclude that there is a left most derivation of W1 X2 through Xn, that's
this. We can continue arguing this way For each XI in turn, either it is a terminal,
in which case nothing needs to be done, or it's a variable in which case we can
perform a leftmost derivation from WI from XI. The needed sequence of leftmost
derivations is a leftmost derivation of the entire yield W. That's W1 through Wn.
From A. Now we need to prove the other direction. That leftmost derivations can
be turned into parse trees. The proof is an induction on the number of steps of the
derivation. The bases of one step derivation. In this derivation a variable
A is replaced by a string of terminals, perhaps the empty string, using some
production for A. If the string is not empty then there is a parse tree of height
one with A at the root and the sequence of terminals in the body as the labels of the
children. This and there are the children. If the body is epsilon then there's again
a porous tree it has A at the root and one leaf labeled epsilon so it just sort of
looks like this. Now let's do the inductive step. We assume that left most
derivations of fewer than K steps can be turned into parse trees with the proper
yield. We will consider a K step derivation from string W from variable A
The first step of this derivation uses a production with head A and body X1 through
Xn for some n. Thus the second [inaudible] form in this derivation of W is X1 through
Xn, that's that. Remember the important properties of derivations. That production
bodies replace production heads at the position where the head is. Thus we can
divide W into the concatenation of n strings, W1 through Wn, in that order.
Where for all I, WI either is XI, if XI is a terminal. Or XI derives WI by a leftmost
derivation of fewer than K steps. Since the whole derivation is leftmost, the
derivation WI from XI must happen first. Then the derivation of W2 through X2 and
so on. So we know that each XI either is WI or derives WI in fewer than K steps at
the leftmost derivation. So the second case, where XI is a variable and the
leftmost derivation takes one or more steps, the inductive hypothesis tells us
that there is a parse tree with root XI and yield WI. Plus we can build the parse
tree shown... That is this. The root uses the first production of the derivation as
A goes to X1 through Xn and the Ith child either is Wi if Xi is a terminal or it is
the root of a parse tree from Xi deriving Wi. The yield of this tree is W1 through
Wn which is W. Okay, that is, this string W is W1 through Wn. All these strings are
derived left to right in that order. This proves the inductive step and we conclude
there is a leftmost derivation of W from A. ... And there is a parts true with root
"A" and a yield "W". It is also true that if there is a right most irrevations of
"W" from "A", then there is a parts true of root "A" and yield "W" and conversely.
But we are not going to prove that part, the proofs are essentially the same as
what we have seen. And in fact, any derivation even the one that isn't left
most or right most of a terminal strain "W" from variable "A" implies that there
is a parts true with root "A" and yield "W". The first step of any derivation from
A must use a production and replace A from some string of terminals and variables.
Say, X1 through Xn. If W's the terminal string ultimately derived, then we can
still break W into W1 through Wn, where each WI either is XI or is derived from XI
by fewer steps than the whole derivation. The only tricky part is that now the steps
of the derivation from XI and XJ may be intermingled and we have to sort the
derivation steps according to which XI is descendant as being replaced at that step.
We'll leave you to think through the details of this construction of parse
trees. As we mentioned at the beginning, it is important in many applications,
including parsing of programming languages In a compiler and parsing of natural
language sentences that we use a context-free grammar that assigns a unique
parse tree to each string of the language. We say a grammar is ambiguous if there is
at least one string in its language that has two different parse trees. Otherwise
it is unambiguous. The grammar for balanced parentheses that we have been
using is ambiguous, alas. I'll show you two parse trees for this balance string,
that is left, right, left, right, left, right on the next slide. Notice that each
of these trees has the same yield, that is three pairs of left and right parentheses.
However they're evidently not the same tree. The first replaces the first child
of the root by [sound]. And the second does the same but with the second child.
Notice that the two constructions we just gave, leftmost derivations from trees and
trees from leftmost derivations have the property that two different parse trees
produce different leftmost derivations and conversely The same is true for the
analogous transformations between rightmost derivations in trees Thus we
could also define a grammar to be ambiguous if it has a string with two
different leftmost derivations or two different rightmost derivations.
Fortunately just because one grammar for a language is ambiguous does not mean that
we can't find another grammar for the same language that is unambiguous. But as an
aside, which we'll get to later, the opposite is not true either. That is,
there are some ambiguous to which no unambiguous equivalent exists. Anyway.
Here is a grammar for balanced parenthesis that is unambiguous. Variable D, which is
the star symbol, generates all balanced strain But R, another variable generates
all strings that are balanced except for having one more right parenthesis than
left. By balance in this context I mean that no prefix of the string has more
right parentheses than left. And examples would include, well, a single, right
paren. Left, right, right that would be generated by R and also something like
this: left, left, right, left, right, right, right. Here's the unambiguous
grammar for balanced parentheses again. Suppose we're given a string of
parentheses which we'll call the input. And we want to find this leftmost
derivation or derivations. We claim that for every input symbol and for either
variable B or R there is only one choice of production that could possibly lead to
a leftmost derivation of the input. That is, no string of parentheses has two
distinct leftmost derivations and therefore the grammar is unambiguous.
Imagine we are constructing the left sentential form as we scan the input. As
we go, the terminals to the left of the left most variable must match the input or
we'll never derive that input string of terminals. So we can check out input
symbols as we match them Notice that the only place B can ever appear in a left and
central form is at the right end. That is because the only production with D in the
body, has lead [inaudible] and it also has head B that is this B can only go to a
string that has a B in it, and the only way a B can come, can appear is if it was
either the start symbol. Or it was the result of replacing this B at the end by
the, paren RB in that production. It does an easy induction on the number of times
this production is applied so that the B is still at the right end Now suppose B is
the leftmost variable of a left sentential form. If there's a left parenthesis as the
next unmatched input, and we have to expand the B using this production the
paren RB. Because if we use epsilon then the left sentential form has no more
variables and we can never generate the unmatched left paren. The only time we can
use epsilon to replace B is this production. Is when we have matched the
entire input and we have found the unique left most derivation. If R is the left
most variable then the next input symbol forces us to use one of the two R
productions, that is if the next input symbol is right paren You must use R goes
to right paren. That's here. And if the next input is a left paren you must use R
goes to left paren followed by two rights. There's never an option on a left
sentential form you're deriving can never match the input string. Here is an
example. Suppose we want to find the unique left most derivation for this
string of parentheses. That's this string right here. We set the string up as an
input with a pointer to the next symbol that must be matched in the left most
derivation. Okay. We start off with the left sentential form that is the start
symbol B alone. The next input to match is the left [inaudible] and we must therefore
expand this B, to left [inaudible] RB, that is using that production. Here we've
made the expansion. The first left paren has been removed from the input, since it
has been matched. That is it appears to the left of the left most variable in the
current left [inaudible] form. In essence, this left paren is what used to be on the
input there. Our next input symbol is another left paren and we have to expand
an r, the left most variable. That's this guy. Our only choice is to use the body
"R" goes to left [inaudible] "R", "R" [sound]. So we're going to do that. Okay.
That's what happened here. The R was replaced by paren RR and the second left
paren has been matched. It appears to the left of the leftmost variable as here. Now
next input is a right paren and we must expand the leftmost R. The only, choice is
the first production. That will enable us to match. Now the third input has been
matched. We have R to expand. And right paren has the next input. So we again use
R goes to the right paren. That is we expand that R, replacing it by a right
paren. That's what's going to happen. On the next slide. You have the left paren as
the next input and we must expand B, the choice is the first production for B
[inaudible] now, "R" is the left most variable, we are up here now and the next
input is the right [inaudible], so we replace the "R" of our right [inaudible],
[inaudible] using the first production for R, that's that and lets see Know there is
no more input to match and B must be expanded, that's B, the left most
variable. The only choice is to use the second B production, which is that. And we
effectively make the B disappear. And we're done. We have a leftmost derivation
of the original input, which of course, appears as the final step of the
derivation. Had we deviated from the choices we made at any step the, the
result of the left most derivation would not have been this input strain of
terminals There is a name for grammar such as our example where it is always possible
to choose unique production to use in a leftmost derivation of any string in the
language, in the simple manner that we illustrated. At each step we looked only
at the first unmatched symbol of the input and we were able to make the unique choice
correctly. Such a grammar is called [laugh] of one. Standing for leftmost
derivation, that's the first L, left to right scan, that's the second L, and one
symbol of look ahead. It is normal for a programming language to have an
[inaudible] of one grammar. Probably as this theory became widely understood by
designers of programming language as they saw the advantages of keeping the language
parse-able in this simple way and made choices to preserve this ability. In the
same argument we gave for our example grammar tells us all [inaudible] one
grammars are unambiguous. And remember unambiguity is vital for a programming
language as we must assign a unique meaning to any legal program of the
language. For balanced parens we found the first, simplest grammar that we wrote down
was ambiguous but we were able to redesign the grammar to make unambiguous. One might
hope for an algorithm that would do that for any ambiguous grammar But, alas, there
can not be such an algorithm. There are certain contexts for languages for which
every grammar is ambiguous. Such languages are called inherently ambiguous. We're not
going to get into the proofs of what I just said, but I'll give you an example of
an inherently ambiguous language. The set of strings of the form some number of
zeroes followed by some number of ones, followed by some numbers of twos. Such
that either the numbers of zeroes and ones are the same. That would be this condition
I equals J. Or the numbers of ones or twos are the same. That would be J equals K. Or
both, of course. The problem is that any grammar for this language must generate at
least some of the strings with equal numbers of all three symbols in two
different ways. In the first derivation, or parse tree, the grammar forces the
numbers of zeros and ones to be the same using the same trick we used to generate a
set of strings with the form zero to the n, one to the n. The grammar can generate
any number of twos to go along but it may happen to generate the same number of twos
as zeros and ones. The second derivation of parse tree makes sure the numbers of
ones and twos are the same, but may accidentally generate the same number of
zeros as well. Here's an example grammar. It is ambiguous but that doesn't prove the
language is inherently ambiguous. As I said, we're not going give that proof,
it's very complicated. However you might wish to play around with grammars from the
same language and see how you are forced to do something like this grammar in order
to generate exactly the language you want. To be easy and be familiar to observe that
A will generate all strains with one or more zeros followed by exactly the same
number of ones. We've seen essential this pair of productions, yes, as a complete
grammar before and it should also be obvious that "B" generates any string of
one or more two's and nothing else Likewise C generates the strings of one or
more zeros. And D generates one or more ones followed by exactly the same number
of twos. Now, all derivations start with "S" and the first production replaces it
by either "AB" or CD. If we go with AB, then we get strings where the zeros and
ones match, while if we go with CD, then the ones and twos match. As a result,
strings like 012 with the same number of each symbol will have two left most
derivations. One starting with S goes to AB, that's this, and the other starting
with S goes to CD. Here are the two derivations for zero, one, two.