HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is rightmost sentential forms?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
sententialformsrightmostwhat

Problem

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:



  • $a \ast b + c$



  • $( a - b ) \ast c$



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

Solution

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

Context

StackExchange Computer Science Q#62342, answer score: 7

Revisions (0)

No revisions yet.