I am a beginner started learning theoretical computer science. I just came through context-free grammars.
So my question is: what is the different between left-most and right-most derivation?
Because both of them gave me the same parse tree.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Which grammar and word are you looking at? Hint: look at a non-linear grammar. $\endgroup$– Raphael ♦Mar 23, 2016 at 9:09
-
4$\begingroup$ Your question is answered in the Wikipedia article on context-free grammars. en.wikipedia.org/wiki/… For future reference, we want you to do a significant amount of research/self-study before asking here -- there's little point in asking questions that are already covered in standard textbooks or online resources like Wikipedia. $\endgroup$– D.W. ♦Mar 23, 2016 at 10:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Given a derivation tree for a word, you can "implement" it as a sequence of productions in many different ways. The leftmost derivation is the one in which you always expand the leftmost non-terminal. The rightmost derivation is the one in which you always expand the rightmost non-terminal.
For example, here are two parse trees borrowed from Wikipedia:
The leftmost derivation corresponding to the left parse tree is $$ A \to A + A \to a + A \to a + A - A \to a + a - A \to a + a - a $$ The rightmost derivation corresponding to the left parse tree is $$ A \to A + A \to A + A - A \to A + A - a \to A + a - a \to a + a - a $$ The leftmost derivation corresponding to the right parse tree is $$ A \to A - A \to A + A - A \to a + A - A \to a + a - A \to a + a - a $$ The rightmost derivation corresponding to the right parse tree is $$ A \to A - A \to A - a \to A + A - a \to A + a - a \to a + a - a $$
answered Mar 23, 2016 at 7:45
-
$\begingroup$ I have never seen it explained this way around, but I now get your point. Thanks for clarifying! $\endgroup$– Raphael ♦Mar 23, 2016 at 12:52
-
3$\begingroup$ Novice readers may want to note that the underlying grammar $A \to A + A \mid A - A \mid a$ is ambiguous. Real-life grammars or such you create yourself for toy examples tend to be unambiguous, and in such there's only one parse tree (and, equivalently, only one left- and one right-derivation) per word. Left- and right-derivation will still differ if the grammar is non-linear, though! $\endgroup$– Raphael ♦Mar 23, 2016 at 12:53