472 views

Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.

 \begin{align*}E \rightarrow & number \\ &| E \text{ '+' } E \\&| E \text{ '}\times\text{' } E \end{align*} \begin {align*} &E.val = \text {number.val} \\ &E^{(1)}.val = E^{(2)}.val + E^{(3)}.val \\ &E^{(1)}.val = E^{(2)}.val \times E^{(3)}.val \end{align*}

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

reopened | 472 views

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

For 3×2+1

E->E * E (Both shift and reduce possible but yacc prefers shift)

->E * E + E

->E * E + 1

->E * 2 + 1

->E * 3

->3 * 3

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

selected by
@Arjun sir

So the question says conflicts will be resolved by "yacc" does that mean ambiguity will be resolved?
yes.
Ok. @Arjun Sir.

@Prajwal Shift-Reduce Conflict (NOT AMBIGUITY)will solve by yacc by preferring Shift operation over reduce operation.

So, here though it will find 3∗2 (E∗E) handle on top of the stack initially, it will shift on reading + instead of reducing with E→E∗E.

so it work like right associativity(and we know priority is same due to ambiguous grammar.)

so 3*(2+1) =9
What makes it right associative?
(Both shift and reduce possible but yacc prefers shift)  why do we say this