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.
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
