GATE CSE 2000 | Question: 2.21, ISRO2015-24
in Compiler Design edited by
22 votes

Given the following expression grammar:

E &\to E * F \mid F + E \mid F \\[1em]
F &\to F - F \mid id

Which of the following is true?

  1. $*$ has higher precedence than $+$
  2. $-$ has higher precedence than $*$
  3. $+$ and $-$ have same precedence
  4. $+$ has higher precedence than $*$
in Compiler Design edited by

Subscribe to GO Classes for GATE CSE 2022

3 Answers

34 votes
Best answer

Correct Option: B

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

edited by


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 + * -
+   < < <
*   > > <
-   > > >

- 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 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)
2 votes

option b is right

0 votes

Both B and D are true.  

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


+ is at same level as *

am not able to construct syntax tree for 9*2+3

when i am making it, order of evaluation becomes = (9+2)*3

how to chk precedence b/w + & * now?





Related questions