search
Log In
38 votes
9.2k views

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

in Compiler Design
edited by
9.2k views
0
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
2
0
Why is it tagged difficult? It's just a factual question.
0

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

Hence Answer is (C).

7 Answers

116 votes
 
Best answer

Given grammar :

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

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

  •  
  • 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
3
option B says equal precedence and right associativity, can you explain how is the precedence equal when + is evaluated first?
3
updated
5
Awesome explanation! :)
2

Thanx @Debashish now question 83b clear earlier there  was not proper explanation why we were taking right associatively

0
ANSWER IS C RIGHT?? WHY MARKED AS B HERE?
0
Wonderful
0
How did you get $$$ /+/*

as lookaheads in the first canonical item on closure operation? the lookahead should just be $$$
0
U have to again reconsider the dot in the beginning of E . . Feb + and * will also come .
1
How??  The first LR(1) item must only have $ as the look-ahead.
0
@Debashish Why can't precedence change? As SR conflict resolved in favour of shift,  '+' is done before '*'. Why can't we say that '+' has higher precedence over '*'?
0
Shouldn't the answer be (C)? as there is no R/R conflict for this grammar exists. there exists only 4 S/R conflicts, right?
0
can anyone please tell if I should  learn yacc too? This was asked in 2005 and I guess is now out of syllabus... can anyone confirm? ;'(
1
Debashish sir you always come with great explanation thanks sir
1
@Debashish Deka @sresta @arjun sir Please help.
 How??  The first LR(1) item must only have $ as the look-ahead I think.
1

How??  The first LR(1) item must only have $ as the look-ahead.

Once you write productions because of S =>.E,$, again you have to take closure because of E => .E+E and E=>.E*E. Find the closure recursively.

Reason : It will have different lookaheads. You can combine all like E=> .E+E , $,+,*

8

For those who don't understand why there are $,+,* lookaheads added.

0

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.

can you explain this via example.

@Nitesh Singh 2

@dd

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

correct me plz anyone.
1
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.
48 votes

Adding  Nandan Jha  answer....

A

0

Need proper analysis in 83b by left associative expression is evaluated to 7 and by right associative expression is evaluated to 9 ,why we are going for right only any particular reason ??

0
does amibigious grammar has equal prescdence as well associativity all the time ?
2
@Arjun sir @Anirudh @ManojK Please explain $83-b$?
1
........................
0
nice @kathlen
0
What happened in case of RR conflict ....can anyone explain how to solve 3*3+1 in this cae
0

 3*3+1 

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

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

8 votes

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

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

0
You can upload pictures with your answers.
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/

1 vote

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

0 votes
yes i provided the link to the image..bt frm nw on i will directly provide the image
0
can u show lookahead also...
1

@sapna318 look-ahead part will contain $,*,+ for all three productions!

Answer:

Related questions

23 votes
2 answers
1
4.3k views
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production. ... to $7$ Precedence of $+$' is higher than that of $\times$', and both operators are left associative; expression is evaluated to $9$
asked Nov 27, 2016 in Compiler Design jothee 4.3k views
19 votes
1 answer
2
5.1k views
Consider the grammar: $S \rightarrow (S) \mid a$ Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be $n_1, n_2$ and $n_3$ respectively. The following relationship holds good: $n_1 < n_2 < n_3$ $n_1 = n_3 < n_2$ $n_1 = n_2 = n_3$ $n_1 \geq n_3 \geq n_2$
asked Sep 22, 2014 in Compiler Design Kathleen 5.1k views
23 votes
3 answers
3
5.8k views
The grammar $A \rightarrow AA \mid (A) \mid \epsilon$ is not suitable for predictive-parsing because the grammar is: ambiguous left-recursive right-recursive an operator-grammar
asked Sep 22, 2014 in Compiler Design Kathleen 5.8k views
26 votes
2 answers
4
1.9k views
Consider the context-free grammar $E \rightarrow E + E$ $E \rightarrow (E * E)$ $E \rightarrow id$ where $E$ is the starting symbol, the set of terminals is $\{id, (,+,),*\}$, and the set of nonterminals is $\{E\}$. Which of the following terminal strings has more than one parse tree when parsed according to ... $id + (id* (id * id))$ $(id* (id * id)) + id$ $((id * id + id) * id)$
asked Nov 4, 2014 in Compiler Design Ishrat Jahan 1.9k views
...