3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ "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.) $\endgroup$ – Alexey Oct 28 '18 at 11:14
2
$\begingroup$

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 | ...
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Udayraj Deshmukh Feb 25 '18 at 4:07
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Udayraj Deshmukh Feb 25 '18 at 3:49
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

The answer is (iii).

Considering precedence rules, * operator has more precedence than + operator, but bracket () has more precedence than *.

So in (i), you start from the left where you have *, as there is no bracket in the string.

In (ii), you still start from the left due to the use of bracket for the + operator which make it to have higher precedence than *.

But in (iii), you must start from the right because of the use of bracket on the operator with the lesser precedence (+).

$\endgroup$
  • $\begingroup$ So the other answers are wrong? $\endgroup$ – Yuval Filmus Aug 16 '17 at 19:21
  • $\begingroup$ Also, perhaps you could be a little less playful in your answer, say not starting it with a greeting. $\endgroup$ – Yuval Filmus Aug 16 '17 at 19:22
  • $\begingroup$ The precedence rules you mention may be standard, but they are in no way implied by the grammar given. $\endgroup$ – Rick Decker Aug 24 '17 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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