6
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Well, there are different types of parser that obtain a left-most or right-most derivation starting from the input and a grammar. For example see LL vs LR parsers (note that they don't really handle every CFG but a subset of them). $\endgroup$ – Bakuriu Mar 13 '16 at 12:23
  • 1
    $\begingroup$ @PeterMortensen, It seems that there is a lot of cross-voting is going on this question, so please don't waste time in trying to make sense of the answers and editing them, till the moderators give a clear. I have already raised a flag. $\endgroup$ – Shreesh Mar 13 '16 at 13:44
8
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

protected by Community♦ Mar 13 '16 at 21:27

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?

Not the answer you're looking for? Browse other questions tagged or ask your own question.