3 Oct 2005 00:21:17 -0400

Related articles |
---|

LR(0) generation Question mail@andrebetz.de (=?ISO-8859-1?Q?Andr=E9_Betz?=) (2005-10-02) |

Re: LR(0) generation Question cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-10-03) |

Re: LR(0) generation Question cdodd@acm.org (Chris Dodd) (2005-10-03) |

From: | Cleo Saulnier <cleos@nb.sympatico-dot-ca.remove> |

Newsgroups: | comp.compilers |

Date: | 3 Oct 2005 00:21:17 -0400 |

Organization: | Aliant Internet |

References: | 05-10-015 |

Keywords: | parse |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.