4.8k views

Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.

 \begin{align*}E \rightarrow & number \\ &\mid E \text{ '+' } E \\&\mid 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

edited | 4.8k views

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.
• $\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  :

Here are the required files (calc.l and calc.y) to regenerate the above interpreter.

edited
+2
option B says equal precedence and right associativity, can you explain how is the precedence equal when + is evaluated first?
+3
updated
+4
Awesome explanation! :)
+1

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? ;'(
0
Debashish sir you always come with great explanation thanks sir

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

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

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/

yes i provided the link to the image..bt frm nw on i will directly provide the image
0
+1

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