CFG to parse tree - rightmost derivation

Question

So we have activity where we must generate a parse from a given grammar.

we are also asked which of the following given strings will the the grammar produced.

I was able to generate abcd

but in question 2 it says to regenerate the string from question 1 but using a rightmost derivation. but there are only 2 expansions, and in my knowledge, a rightmost/leftmost derivation is which side the parse tree is expanded more.

So I tried to lengthen my parse tree but the problem now is I can't generate any of the given strings to produce.

Am I missing something, or is there a mistake on my part?

Answer 1

A derivation starts with the start symbol (in this case <S>) and ends with the derived sentence (abcd). Each step in the derivation consists of substituting some non-terminal with one of its possible productions. The result of a derivation is called a "sentential form" if it still contains at least one non-terminal; otherwise, it's the derived sentence and the derivation has terminated.

After the first step in your derivation (as shown in your parse tree), you have the sentential form

a <S> c <B>

The next derivation step would either need to replace the <S> using one of its productions or to replace <B> with one of its productions. (Both possibilities lead to the same parse tree precisely because this is a context-free grammar, so the order of derivations doesn't matter.) If we chose to expand <S> using the production <S>→b, the result of the derivation step would be the sentential form

a b c <B>

In a rightmost derivation, the non-terminal chosen for each derivation step is the rightmost non-terminal in the sentential form. In a leftmost derivation, it's the leftmost non-terminal. If there is only one non-terminal in a sentential form, then it will be selected regardless since it is both leftmost and rightmost.

This has nothing to do with which way the parse tree leans. The same parse tree is produced regardless. (Or the same parse trees, if the grammar is ambiguous.)

You don't have to do a derivation in leftmost or rightmost order, unless your exam paper requires it. You'd still get the same parse if you always used the middle non-terminal, for some unambiguous definition of "middle". Or if you just chose a random non-terminal and expanded that. But no-one has ever found the need to talk about middlemost derivations, as far as I know.

Answer 2

As @rici said, for CGF, but in other words 1 (p.179)"any derivation has an equivalent leftmost and an equivalent rightmost derivation."

Furthermore, @rici wrote

This has nothing to do with which way the parse tree leans. The same parse tree is produced regardless. (Or the same parse trees, if the grammar is ambiguous.)

Interesting, your grammar is ambiguous, as can be seen for string acccc, using leftmost derivation:

1: Hopcroft et al. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 3rd ed.