# What is rightmost sentential forms?

I'm solving some past job interview problems. I met an embarrassing question about compilers.

The question is :

Consider the following grammar, with start symbol $E$:

\begin{align*} E &\rightarrow E \ast E\\ &\quad \mid E ~/~ E\\ &\quad \mid E + E\\ &\quad \mid E - E\\ &\quad \mid (E)\\ &\quad \mid a \mid b \mid c \mid \ldots \mid x \mid y \mid z \end{align*}

The following strings are legal derivations from this grammar:

1. $a \ast b + c$
2. $( a - b ) \ast c$
3. $a ~/~ ( b – c)$

Which of the above are rightmost sentential forms?

When I was an undergraduate student, I learned that rightmost(leftmost) sentential form is result of rightmost(leftmost) derivation. so, I think if $1,2,3$ are legal derivations form above grammar then absolutely all of $1,2,3$ are rightmost sentential form. If I'm correct, above question is very worthless.

Is there any counter example that is not rightmost sentential form of the grammar $G$ although it is a legal derivation from $G$?

OR

Is there another definition about rightmost sentential form corresponding to above question? I have googled "rightmost sentential form" but there are few results and most of them is the definition that I already know.

• LR parsers find right-most derivations, LL parsers left-most derivations. I don't know what a "rightmost sentential form" is supposed to be. – Raphael Aug 9 '16 at 21:06

I found other answers here confusing, so let me explain it clearly here-

Definitions:

A sentential form is any string derivable from the start symbol. Note that this includes the forms with non-terminals at intermediate steps as well.

A right-sentential form is a sentential form that occurs in a step of rightmost derivation (RMD).

A sentence is a sentential form consisting only of terminals

The examples in your question are all sentences. And since any way of derivation (including RMD) ultimately leads to a sentence, technically all sentences are right-sentential as well as left-sentential forms. So there isn't any counter example which you asked for.

Clarifying Examples : Page 2 of this link

• "since any way of derivation (including RMD) ultimately leads to a sentence, technically all sentences are right-sentential as well as left-sentential forms" -- there is a logical error in this sentence. A proof that all sentences are right-sentential and left-sentential requires some work. (Note that any way of derivation leads to a sentential form, but not all sentential forms are right-sentential, etc.) – Alexey Oct 28 '18 at 11:14

The grammar can be parsed both left-most and right-most.

a∗b+c can be derived left-most:

E
E * E
E * E + E
a * E + E
a * b + E
a * b + e


and also right-most (correct precedence:)

        E
E + E
E * E + E
E * E + c
E * b + c
a * b + c


Only in the following form the grammar is both unambiguously left-recursive and arithmetically correct

S → E

E → T | E + T | E - T

T → F | T * F | T / F | (E)

F → a | b | c | ... | 1 | 2 | 3 | ...

• I don't know how this answer is helping answer the question, except to know that each line in your second example is a right-sentential form. – Udayraj Deshmukh Feb 25 '18 at 4:07

I agree, that all the above examples given are rightmost sentential forms. I am not quite sure, how much this is correct, but I thought of a slight modification to definition of right sentential form. Here it goes,

The right sentential form is the sentential form in which the input string when parsed from right-to-left and reduced whenever possible would give final output as the start symbol

Here reduction operation means to replace the symbol or set of symbols by the non-terminal symbol such that the symbol(s) satisfies some rule corresponding to that non-terminal symbol.

I thought of this definition because when I made the parse tree for the example strings given, I found that first example produced two parse trees, but both of them when parsed from right to left and reduced accordingly will ultimately lead to the start symbol.

• I think the above definition is incorrect. A sentential form is any string (including ones with non-terminals) derivable from the start symbol. A right-sentential form is any string that occurs during making a rightmost derivation. Examples : Page 2 of this link – Udayraj Deshmukh Feb 25 '18 at 3:49

Right derivation: when you select right most non terminal everytime to derive the string from G then it will result in the right sentetntial form If there is a legal derivation for G it must have atmost one right or left derivation, which results in right sentential form or left sentential form.

this can be proved for example consider a grammar G which derives the strings not by left or right derivations but by mixed , so now i can rearrange the productions to produce only the right and then the left, it is a simple arrangement as we do not have any conditions when to apply the the production rules.So i think there will be no grammar G for which there will be a derivation but not a right most derivation tree