edited by
11,376 views
31 votes
31 votes

Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.$$\begin{array}{l|l} E\rightarrow number & E.val = {number.val} \\\qquad \mid \ E \ \ ‘+\text{'} \ E & E^{(1)}.val = E^{(2)}.val + E^{(3)}.val     \\\qquad \mid \ E \ \ ‘\times\text{'} \  E & E^{(1)}.val = E^{(2)}.val \times E^{(3)}.val  \end{array}$$

Assume the conflicts of this question are resolved using yacc tool and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression $3 \times 2 + 1$. What precedence and associativity properties does the generated parser realize?

  1. Equal precedence and left associativity; expression is evaluated to $7$

  2. Equal precedence and right associativity; expression is evaluated to $9$

  3. Precedence of ‘$\times$’ is higher than that of ‘$+$’, and both operators are left associative; expression is evaluated to $7$

  4. Precedence of ‘$+$’ is higher than that of ‘$\times$’, and both operators are left associative; expression is evaluated to $9$

edited by

2 Answers

Best answer
56 votes
56 votes

LALR Parser is type of Bottom up Parser which uses Right most Derivation

For $3×2+1$

$E \rightarrow E * E$ (Both shift and reduce possible but yacc prefers shift)

     $ \rightarrow E * E + E$ 

     $ \rightarrow E * E + 1$

     $ \rightarrow E * 2 + 1$

     $ \rightarrow E * 3$

     $ \rightarrow 3 * 3$

     $ \rightarrow 9$

All the productions are in same level therefore all have same precedence

Therefore Ans is B. Equal precedence and right associativity; expression is evaluated to 9.

edited by
1 votes
1 votes

None of the Options is correct here ... The answer has to be "precedence of + is higher than * " and "both * and + are right associative"

Here we will never come across an RR conflict because we dont have 2 productions with the same RHS but different LHS ... 

EX : In the grammar, 

S->A/a, 

A->a
 

we have 2 productions with the same RHS (which is a) but different LHS (S and A) ... Now while parsing a string I might come across a single state with productions as A->a. and S->a. Now this state will create a conflict on whether should I reduce string "a" to S or A ... So clearly there is an RR conflict here .... 

But in the given grammar it is not the case ... 

While parsing a string say "num+num*num" from the above grammar,I will come across an SR conflict ... When ?? after scanning num+num , I have a choice on whether should I shift on * (as good as giving higher precedence to * over +) or reduce "num+num" to E (as good as giving higher precedence to + over *) ... So here there is an SR conflict ... 

YACC tool always goes in-favour of SHIFT incase of SR conflict (and first reduce incase of RR conflict) ...

So,since we are using YACC to resolve conflicts, here + will be given higher precedence over * but incase if we come across a string like 2+3+5 , it will be right associative ... 

None of the Options is correct here ...

edited by
Answer:

Related questions

24 votes
24 votes
2 answers
1
56 votes
56 votes
7 answers
3
37 votes
37 votes
4 answers
4
Kathleen asked Sep 22, 2014
23,301 views
The grammar $A \rightarrow AA \mid (A) \mid \epsilon$ is not suitable for predictive-parsing because the grammar is:ambiguousleft-recursiveright-recursivean operator-gram...