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

5 votes
5 votes

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

4 votes
4 votes

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/

0 votes
0 votes
yes i provided the link to the image..bt frm nw on i will directly provide the image
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...