edited by
20,197 views
56 votes
56 votes

Statement for Linked Answer Questions 83a & 83b:

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

The above grammar and the semantic rules are fed to a yaac tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yaac for the given grammar?

  1. It detects recursion and eliminates recursion

  2. It detects reduce-reduce conflict, and resolves

  3. It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action

  4. It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action

edited by

7 Answers

Best answer
145 votes
145 votes

Given grammar:

$\begin{align*} &E \rightarrow \text{num} \\ &E \rightarrow E + E\mid E*E \\ \end{align*}$

First $LR(1) \text{ item}:E^{\prime} \rightarrow \bullet E \ \text{,} \$ $

$\textbf{YACC default action on SR: Choose SHIFT action}$

While parsing $3*2+1,$ at some point of time stack content $ :\begin{array}{|c|} \hline 1\\+\\ 2\\ *\\3\\ \hline\end{array}$

Then reduce handles one by one to generate output $=9.$


  • num does not create any conflict.
  • Additionally here no states differ by lookahead symbols only. 
  • $\Rightarrow$ $\text{LALR(1) and LR(1)}$ tables are same.
  • $LR(1)$ table only for state0 and state1:

        So total $2+2 = 4$ SR conflict originated in two states of the DFA.

  • Shift-reduce conflict: Yacc’s default action in the case of a shift-reduce conflict is to choose the shift action.
  • Reduce-reduce conflict : Yacc’s default action in the case of a reduce-reduce conflict is to reduce using the production that comes first, textually, in the input grammar specification.

and LEX-YACC-gcc output after implementing the given grammar :

As we can see from the output reduction on $E \rightarrow \text{num}$ is carried out as soon as top of stack contains a num.  So, no conflict related to $E \rightarrow num$.

one example : Because of YACC shift preference, even if $3*2$ ($E*E$) handle found on top of the stack at some point of time, it will shift on reading $+$ instead of reducing with $E\rightarrow E * E$. In this way, the complete input will be pushed into the stack. After that only reduce work starts as shown below. 

  • Equal precedence because of the given grammar $E\rightarrow E+E \ | \ E*E$ , (single level)
  • and Right associativity  :

How YACC handles conflicts

Here are the required files (calc.l and calc.y) to regenerate the above interpreter.

Correct Answer: $C$

edited by
55 votes
55 votes

Adding  Nandan Jha  answer....

A

11 votes
11 votes

Option C) is the answer ...

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

Answer:

Related questions

31 votes
31 votes
2 answers
1
go_editor asked Nov 27, 2016
11,379 views
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.$$\begin{array}{l|l} E\rightarrow numbe...
24 votes
24 votes
2 answers
2
37 votes
37 votes
4 answers
3
Kathleen asked Sep 22, 2014
23,302 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...