GATE CSE 2000 | Question: 2.21, ISRO2015-24

Question

Given the following expression grammar:

$$\begin{align}
E &\to E * F \mid F + E \mid F \\[1em]
F &\to F - F \mid id
\end{align}$$

Which of the following is true?

• A. $*$ has higher precedence than $+$
• B. $-$ has higher precedence than $*$
• C. $+$ and $-$ have same precedence
• D. $+$ has higher precedence than $*$

Comments

the operator which is more far away from the starting symbol will always have higher precedence.

Answer 1

Correct Option: B

Operator which is at lower level in the grammar is termed to have higher precedence.

Comments

First of all given grammer is unambiguous. Right?

Here the highlighted - and * are on same level but at different children. So for precedence these kind of cases should not be considered. Right??

Besides this, want to confirm :-

* left associative

+ right associative

* and + has same precedence.

But bcz of associativity * placed in stack should be performed first.

How far the following table is right? (dont consider id and $ cases)

	id	+	*	-
Id
+		<	<	<
*		>	>	<
-		>	>	>

- Will be left associative or not.

I think it should be left associative in this way only it can have highest precedence. 

---

@ gateasp17 we do not create table after determining associativity and precedence, we construct table just to determine associativity and precedence, You are doing opposite way.
Now you may say that we can determine associativity without using table. Using argument like
"Operator which is at lower level in the grammar is termed to have higher precedence." But is it formal procedure ?

We first compute leading and trailing of nonterminals then we construct table and then we determine associativity and precedence.

---

So everytime ..to answer such question we need operator relation table constructed using Lead and Trails..

Can't we answer it using this argument 

"Operator which is at lower level in the grammar is termed to have higher precedence."

---

any reference for the above topics, not understanding the solution

---

I think grammar is ambiguous as a-a-a can have 2 parse tree     (- has no associativity)

---

@Apoorva Jain you are right . The given grammar is ambigious...

Answer 2

F->F-E

Operator at lower  level in tree has higher precedence than operator at upper levels

- has higher precedence than  +and *

+  and * have equal precedence

Answer 3

option b is right

Answer 4

Precedence of '*' = Precedence of '+' < precedence of '-' < Precedence of 'id'