The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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 $*$
asked in Compiler Design by Veteran (68.9k points)
edited by | 2.3k views

1 Answer

+25 votes
Best answer

I guess its B.

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

answered by Veteran (19.6k 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.

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

32,694 questions
39,293 answers
36,701 users