From start symbol, produce more derivations until we get all terminals in our production.
Start symbol is our root of parse tree, and every derivationa will add some more nodes to parse tree.
Now I want to
point out that the rightmost and leftmost derivations I showed you have exactly the
same Parse Tree. And, this was not an accident. Every Parse Tree has a rightmost
and a leftmost derivation. It's just about the order in which the branches are added.
So for example, if I have the first production e goes to e + e, now I have a
choice on how to build my tree. I can either work on. This sub-tree or I can
work on that sub-tree. And if I build this one first, that will be a rightmost derivation. If I continue to always work on the rightmost non-terminal of course,
And if I work on this one first, I can use that to do a leftmost derivation. Now it's
important also to realize that there are many derivations besides rightmost and
leftmost. I could, I could choose non-terminals in some random order to do
my replacements. But the rightmost and leftmost ones are the ones that we're most
concerned with.
In parser implementation, we focus on the rightmost and leftmost derivations.
From start symbol, produce more derivations until we get all terminals in our production. Start symbol is our root of parse tree, and every derivationa will add some more nodes to parse tree.
Now I want to point out that the rightmost and leftmost derivations I showed you have exactly the same Parse Tree. And, this was not an accident. Every Parse Tree has a rightmost and a leftmost derivation. It's just about the order in which the branches are added. So for example, if I have the first production e goes to e + e, now I have a choice on how to build my tree. I can either work on. This sub-tree or I can work on that sub-tree. And if I build this one first, that will be a rightmost derivation. If I continue to always work on the rightmost non-terminal of course, And if I work on this one first, I can use that to do a leftmost derivation. Now it's important also to realize that there are many derivations besides rightmost and leftmost. I could, I could choose non-terminals in some random order to do my replacements. But the rightmost and leftmost ones are the ones that we're most concerned with.
In parser implementation, we focus on the rightmost and leftmost derivations.