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.

marked as duplicate by David Richerby, Rick Decker, Ran G., Luke Mathieson, Gilles Apr 4 '16 at 22:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • Which grammar and word are you looking at? Hint: look at a non-linear grammar. – Raphael Mar 23 '16 at 9:09
  • 2
    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. – D.W. Mar 23 '16 at 10:37

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

  • I have never seen it explained this way around, but I now get your point. Thanks for clarifying! – Raphael Mar 23 '16 at 12:52
  • 1
    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! – Raphael Mar 23 '16 at 12:53

Please be specific with your question. I have a little explanation for you.

Now consider the grammar $$G = (\{S, A, B, C\}, \{a, b, c\}, S, P)$$ where $P = \{S \rightarrow ABC, A \rightarrow aA \mid \epsilon, B \rightarrow bB \mid \epsilon, C \rightarrow cC \mid \epsilon\}$.

With this grammar, there is a choice of variables to expand. Here is a sample derivation: $$S \Rightarrow ABC \Rightarrow aABC \Rightarrow aABcC \Rightarrow aBcC \Rightarrow abBcC \Rightarrow abBc \Rightarrow abbBc \Rightarrow abbc.$$

If we always expanded the leftmost variable first, we would have a leftmost derivation: $$S \Rightarrow ABC \Rightarrow aABC \Rightarrow aBC \Rightarrow abBC \Rightarrow abbBC \Rightarrow abbC \Rightarrow abbcC \Rightarrow abbc.$$

Conversely, if we always expanded the rightmost variable first, we would have a rightmost derivation: $$S ABC \Rightarrow ABcC \Rightarrow ABc \Rightarrow AbBc \Rightarrow AbbBc \Rightarrow Abbc \Rightarrow aAbbc \Rightarrow abbc.$$

There are two things to notice here:

  1. Different derivations result in quite different sentential forms.
  2. But for a context-free grammar, it really doesn't make much difference in what order we expand the variables.
  • While I understand the conventions you're using, it might be clearer if you made explicit the productions by writing, for example, $S\rightarrow ABC$. It might also help to do the same thing with the derivations, like this: $S\Rightarrow ABC\Rightarrow aABC$ and so on. – Rick Decker Mar 23 '16 at 17:39

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