The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
4.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{align*}E \rightarrow & number \\ &| E \text{ '+' } E \\&| E \text{ '}\times\text{' } E \end{align*}$ $\begin {align*} &E.val = \text {number.val} \\ &E^{(1)}.val = E^{(2)}.val + E^{(3)}.val \\ &E^{(1)}.val = E^{(2)}.val \times E^{(3)}.val \end{align*}$

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

asked in Compiler Design by Veteran (69k points)
edited by | 4.2k views

6 Answers

+62 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.

answered by Veteran (59.9k points)
edited by
option B says equal precedence and right associativity, can you explain how is the precedence equal when + is evaluated first?
updated
Awesome explanation! :)

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

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

as lookaheads in the first canonical item on closure operation? the lookahead should just be $$$
U have to again reconsider the dot in the beginning of E . . Feb + and * will also come .
How??  The first LR(1) item must only have $ as the look-ahead.
@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 '*'?
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?
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? ;'(
+27 votes

Adding  Nandan Jha  answer....

A

answered by Veteran (69k points)

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 ??

 

does amibigious grammar has equal prescdence as well associativity all the time ?
@Arjun sir @Anirudh @ManojK Please explain $83-b$?
........................
+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
 

answered by (107 points)
You can upload pictures with your answers.
+2 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/

answered by Boss (8.4k points)
+2 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) ...

answered by Boss (7.7k points)
0 votes
yes i provided the link to the image..bt frm nw on i will directly provide the image
answered by (107 points)
can u show lookahead also...

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



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,230 answers
114,269 comments
38,799 users