patternMinor
In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?
Viewed 0 times
thewhatfreederivationsimportanceanddoingcfgbothgrammar
Problem
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?
So, my question is: Why is it necessary to do both of them? What are we trying to really prove by doing them?
Solution
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.
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.
Context
StackExchange Computer Science Q#54365, answer score: 9
Revisions (0)
No revisions yet.