9
$\begingroup$

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.

$\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
  • 3
    $\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

1 Answer 1

18
$\begingroup$

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: enter image description here

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 $$

$\endgroup$
2
  • $\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

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