patternMinor
What is rightmost sentential forms?
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:
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.
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
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.