Re: LR(0) generation Question

André Betz wrote:


> Hi I have a question about generating the LR(0) closure for an SLR(1)
> Parser Table. Following is a typical example:
>
> 0) E->E,'+',T. Epsfree=t First={(,id} Follow={+,)}
> 1) E->T. Epsfree=t First={(,id} Follow={+,)}
> 2) T->T,'*',F. Epsfree=t First={(,id} Follow={+,),*}
> 3) T->F. Epsfree=t First={(,id} Follow={+,),*}
> 4) F->'(',E,')'. Epsfree=t First={(} Follow={+,),*}
> 5) F->'id'. Epsfree=t First={id} Follow={+,),*}
> 6) E_->E. Epsfree=t First={(,id} Follow={}
>
> 0:
> (6,1) E_->.E;
> (0,1) E->.E,'+',T;
> (1,1) E->.T;
> (2,1) T->.T,'*',F;
> (3,1) T->.F;
> (4,1) F->.'(',E,')';
> (5,1) F->.'id';
>
>
> 1:
> (6,2) E_->E.;
> (0,2) E->E,.'+',T;
>
>
> 2:
> (1,2) E->T.;
> (2,2) T->T,.'*',F;
>
>
> 3:
> (3,2) T->F.;
>
>
> 4:
> (4,2) F->'(',.E,')';
> (0,1) E->.E,'+',T;
> (1,1) E->.T;
> (2,1) T->.T,'*',F;
> (3,1) T->.F;
> (4,1) F->.'(',E,')';
> (5,1) F->.'id';
>
>
> 5:
> (5,2) F->'id'.;
>
>
> 6:
> (0,3) E->E,'+',.T;
> (2,1) T->.T,'*',F;
> (3,1) T->.F;
> (4,1) F->.'(',E,')';
> (5,1) F->.'id';
>
>
> 7:
> (2,3) T->T,'*',.F;
> (4,1) F->.'(',E,')';
> (5,1) F->.'id';
>
>
> 8:
> (4,3) F->'(',E,.')';
> ? E->E,.'+',T;
>
>
> 9:
> (0,4) E->E,'+',T.;
> ? T->T,.'*',F;
>
> 10:
> (2,4) T->T,'*',F.;
>
>
> 11:
> (4,4) F->'(',E,')'.;
>
>
>
> goto[E,0]=1
> goto[T,0]=2
> goto[F,0]=3
> goto[(,0]=4
> goto[id,0]=5
> goto[+,1]=6
> goto[*,2]=7
> goto[E,4]=8
> goto[T,4]=2
> goto[F,4]=3
> goto[(,4]=4
> goto[id,4]=5
> goto[T,6]=9
> goto[F,6]=3
> goto[(,6]=4
> goto[id,6]=5
> goto[F,7]=10
> goto[(,7]=4
> goto[id,7]=5
> goto[),8]=11
>
>
> So my question is:
> Wy is in Closure(8) this rule E->E,.'+',T; added. This rule appears in
> Closure(1) also in Closure(9) is this rule T->T,.'*',F; added. So
> perhaps i didn't understand the goto calculation. I thought that a goto
> rule is added if the new goto doesn't exist in the goto list and the
> rule in he closure list also doen't exist, or is this wrong?
>
> Many Thanks
> André Betz
> mail@andrebetz.de




Read up on kernel items and non-kernel items. All kernel items must
match to use the same state/closure, otherwise a new state must be
created even if one of the kernel item (rule) exists in another state.


closure 8 is produced from advancing the dot over E from closure 4.
  > 4:
  > (4,2) F->'(',.E,')';
  > (0,1) E->.E,'+',T;


Advance the dots and you get...
  > 8:
  > (4,3) F->'(',E,.')';
  > ? E->E,.'+',T;


There are 2 rules that have a dot before E, so they must both be
included as kernel items in the new closure (8 in this case).


Closure 9 is the same thing as above, but taken from closure 6.


BTW, I have no idea what you meant by your last statement. All I know
is that a goto rule ALWAYS comes after reduction (when actually
parsing). Your goto table is strange to me. The goto's with tokens
{+,id,(,) etc} should be in the action table (and are called shift
actions), not the goto table although it may be considered a moot point
to differenciate them as they both lead to a new state. However,
reductions can only appear with tokens. Perhaps it's been too long
since I've done SLR... dunno.


Cle

Return to the comp.compilers page.
Search the comp.compilers archives again.