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

 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

---

@Shaik Masthan sir can we say that if grammar is ambiguous then it has equal precedence and associativity? Please confirm.

Thanks

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.

Answer 5

My answer answers both this question, and https://gateoverflow.in/87037/gate2005-83b one.

---

It detects recursion and eliminates recursion

I don't think a grammar that derives an arbitrary length string can work without recursion in it. Removing recursion from a grammar is never the solution.

---

It detects reduce-reduce conflict, and resolves

No chance that $E + E.$ and $E * E.$ (notice the dot) can coexist in a state. The states would be split when one moves to a different state on + transition, and the other moves to a different state on * transition.

---

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

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

SR conflict is definitely a possibility.

A state can have $E+E.$ along with a terminal transition.

 

What's the action of YACC on detecting an SR conflict?

YACC isn't quick to reduce the string back to the Varibale, it lets the string shift so as to see more of the string.

Hence, Option C  is correct.

 

PS: What does YACC do on an RR conflict?

It reduces the production that comes first textually.

---

 

Now, answering https://gateoverflow.in/87037/gate2005-83b

 

$3*2+1$

The SR conflict can be observed after the digit 2.

The compiler would be conflicted on whether to reduce $3*2$ into $6$, or to shift ahead and see more of the string.

It favours shift.

 

So, 

$3*2+1$ is entirely seen first.

Now, if you observe the grammar $+$ and $*$ have equal priority, and associativity isn't defined by the grammar properly.

 

The compiler is at the dot currently $3*2+1.$

This is as good as having an RR conflict. Whether to reduce $3*2$ first or $2+1$ first. As stated above, on an RR conflict, the compiler would reduce the production the comes first textually.

2+1 is closer to the dot, so do that first.

$3*2+1.$

=> $3*3.$

 

Now, do $3*3$, which results in 9.

 

If you notice, with equal precedence we treat symbols the same.

ie, $3<symbol> 2 <symbol> 1$

Still, we acted on the right symbol first, which means we implicitly assigned right asociativity.

Hence, Option B

Comments

NICE

---

Well explained :)

Answer 6

yacc conflict resolution is done using following rules:
shift is preferred over reduce while shift/reduce conflict.
first reduce is preferred over others while reduce/reduce conflict.

You can answer to this question straightforward by constructing LALR(1) parse table, though its a time taking process. To answer it faster, one can see intuitively that this grammar will have a shift-reduce conflict for sure. In that case, given this is a single choice question, (C) option will be the right answer.

Fool-proof explanation would be to generate LALR(1) parse table, which is a lengthy process. Once we have the parse table with us, we can clearly see that
i. reduce/reduce conflict will not arise in the above given grammar
ii. shift/reduce conflict will be resolved by giving preference to shift, hence making the expression calculator right associative.

According to the above conclusions, only correct option seems to be (C).

Referance:

http://dinosaur.compilertools.net/yacc/