Given grammar :
E→num
E→E+E / E∗E
|
+ |
x |
num |
$ |
E |
I0 |
|
|
I2 |
|
I1 |
I1 |
I3 |
I4 |
|
ACCEPT |
|
I2 |
R3 |
R3 |
|
R3 |
|
I3 |
|
|
I2 |
|
I5 |
I4 |
|
|
I2 |
|
I6 |
I5 |
I3, R1 |
I4, R1 |
|
R1 |
|
I6 |
I3, R2 |
I4,R2 |
|
R2 |
|
Note: Shift-reduce conflict: Yacc’s default action in the case of a shift-reduce conflict is to choose the shift action. So when there is a situation to choose b/w shift and reduce (eg (I6,+)) we will choose shift.
# In the below table E(i) is used just for identification purpose.
STACK |
INPUT |
ACTION |
OUTPUT |
I0 |
3x2+1$ |
(I0,num) : Shift I2 |
|
I03I2 |
x2+1$ |
(I2,x) : Reduce by E->num |
E(1).val=num.val=3 |
I0E(1)I1 |
x2+1$ |
(I1,x) : Shift I4 |
|
I0E(1)I1xI4 |
2+1$ |
(I4,num): Shift I2 |
|
I0E(1)I1xI42I2 |
+1$ |
(I2,+) : Reduce by E->num |
E(2).val=num.val=2 |
I0E(1)I1xI4E(2)I6 |
+1$ |
(I6,+): Shift I3 |
|
I0E(1)I1xI4E(2)I6+I3 |
1$ |
(I3,num): Shift I2 |
|
I0E(1)I1xI4E(2)I6+I31I2 |
$ |
(I2,$): Reduce by E->num |
E(3).val=num.val=1 |
I0E(1)I1xI4E(2)I6+I3E(3)I5 |
$ |
(I5,$): Reduce by E->E+E |
E(4).val=E(2).val+E(3).val=2+1=3 |
I0E(1)I1xI4E(4)I6 |
$ |
(I6,$): Reduce by E->ExE |
E(5).val=E(1).valxE(4).val=3x3=9 |
I0E(5)I1 |
$ |
(I1,$): ACCEPT |
|