Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree.
So, my question is: Why is it necessary to do both of them? What are we trying to really prove by doing them?
For one particular parse tree there are many possible derivations, depending on the order in which the expansions are done. In a sense, a parse tree represent all of the derivations you'd consider "the same" (as you state). It is easy to see that for a given derivation tree there is exactly one leftmost and one rightmost derivation, which in a sense also represent the set of the derivations you'd deem "the same".
For applications, you are interested in the parse tree as a representation of some underlying structure that has a specific meaning. For example, the parse tree of an expression describes the order in which operations are to be performed. If some string has several parse trees, there is no single meaning (the grammar is ambiguous), that is clearly useless.
Reconstructing a (hopefully the only) parse tree for a string is parsing, different parsing methods reconstruct leftmost or rightmost derivations.
The only practical reason derivations are important is that you want to invert them ("parsing"), and when doing so this affects the capabilities and efficiency of the resulting parsing algorithm.
Look up "non-canonical parsers" to get an idea of what this means.
