The Gateway to Computer Science Excellence
+20 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 by Veteran (52.2k points)
edited by | 4.2k views

3 Answers

+32 votes
Best answer

I guess its B.

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

by Boss (19.9k points)
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)
+1 vote

option b is right

by Boss (36.5k points)
0 votes

Both B and D are true.  

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

by (269 points)
+ 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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
104,977 users