GATE CSE 2005 | Question: 83a

Question

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?

• A. It detects recursion and eliminates recursion

• B. It detects reduce-reduce conflict, and resolves

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

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

Comments

In general, we will never come across an RR conflict if we don't have 2 productions with same RHS but different LHS ...

example-  A-> .d

                  B-> .d

---

Link of next part--> https://gateoverflow.in/87037/gate2005-83b

---

Why is it tagged difficult? It's just a factual question.

---

Yes, its simple factual question of yaac tool. Both shift and reduce possible but yacc prefers shift. 

Hence Answer is (C).

Answer 1

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$

Comments

I have a doubt , it contains left recursion then why not A is the answer?

correct me plz anyone.

---

1, '+',2 is at the TOS . So it reduces first and generats 1 + 2 = 3.Now 3,'*',3 is at the TOS so after reducing it generates 9. so '1+2' is evaluated first in the expression '3*1+2', so it is RIGHT ASSOCIATIVE.

---

One simple doubt. Why interpreter in step 10 reduces E+E first not E*E? Because it is LALR(1)>>RMD in reverse. Am I correct?

Answer 2

Adding  Nandan Jha  answer....

A

Comments

What happened in case of RR conflict ....can anyone explain how to solve 3*3+1 in this cae

---

 3*3+1 

here no precedence for fixed for * and + so YACC will produce 12 as Ans as it favor Shift operation.

---

When you are standing at state 0, it’s clear that you’ve seen E+E(i.e E+E. ) and you are about to see either ‘+’ or ‘*’ (i.e E.+E or E.*E).

Here Yaac tool choses to shift the next operator rather than reducing already seen expression

(i.e E+E. )

Here we can confirm

• ‘+’ is right-associative
• ‘*’ is having higher priority than ‘+’

Coming to state 1, it’s clear that we’ve seen E*E(i.e E*E. ) and you are about to see either ‘+’ or ‘*’

(i.e E.+E or E.*E )

But yaac choses to shift the next operator without reducing E*E expression

Here we can confirm

• ‘*’ is right-associative
• ‘+’ is having higher priority than ‘*’

From the above confirmations, we can conclude

• ‘+’ is right-associative
• ‘*’ is right-associative
• There is no consistent relation between ‘+’ and ‘*’ (We can treat them as equal priority)

Therefore,3 * 2 + 1

                  \     \  /

                     \   3

                        \/

                         9

                 3 + 2 * 1

                  \     \  /

                     \   2

                        \/

                         5

Answer 3

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 4

Follow the link...I tried explaining both the questions...srry for the bad handwriting though...

https://gateoverflow.in/?qa=blob&qa_blobid=15270491569523623302
 

Comments

You can upload pictures with your answers.