31 Mar 2002 23:33:19 -0500

Related articles |
---|

States Creation kidlim@yahoo.com (Agnes Lim) (2002-03-24) |

Re: States Creation kaarthik@cisco.com (Kaarthik) (2002-03-31) |

Re: States Creation mwdeeds@yahoo.com (2002-03-31) |

From: | mwdeeds@yahoo.com (Matt Deeds) |

Newsgroups: | comp.compilers |

Date: | 31 Mar 2002 23:33:19 -0500 |

Organization: | http://groups.google.com/ |

References: | 02-03-157 |

Keywords: | parse, LALR |

Posted-Date: | 31 Mar 2002 23:33:19 EST |

Hi, Anges.

Each "Item" coresponds to a state which the parser can be in when

parsing an input. The first state, I0 shows all the possible inputs

that can be parsed to make our goal state, E'. The first line shows

the goal state about to be parsed, E' -> .E, and the following lines

show all the possible things that the "E" on the right hand side could

be.

From state I0, we can consume an E to get to state I1, a T to get to

state I2, or an F to get to state I3 etc. From your message, it looks

like you understand this much.

I6 and I7 are reached from I4 after consuming a * or + respectivly.

I8 comes from consuming an E from I4. There are two ways we can

consume an E from I4, so we need to list them both in I8. (i.e. The

parser

cannot tell which of the two rules we are working on yet.)

Simillaryly I9 comes from consuming a T from I6, and again there are

two ways to consume a T in that state.

I hope that answers your question. Thanks for asking. Thinking about

this helped me with a problem in a grammar I am working on.

Good luck with your parser.

-Matt

"Agnes Lim" <kidlim@yahoo.com> wrote

*> I am writing a LR(0) Parser and needs some advise on the creation of the*

*> states from a given grammar.*

*>*

*> Below is an example taken from the 'Dragon Book'. Can someone*

*> explain how the states are being derived. I have tried to follow thru*

*> the algorithm in the example but was unable to derived the second set of*

*> Items I8 and I9.*

*>*

*> Thanks.*

*> ---------------------------------------------------------------------*

*> Example 1 :*

*> Given Grammar :*

*> E -> E + T*

*> E -> T*

*> T -> T * F*

*> T -> F*

*> F -> (E)*

*> F -> id*

*>*

*> Items created are as follows :*

*> I0 :*

*> E' -> .E*

*> E -> .E+T*

*> E -> .T*

*> T -> .T*F*

*> T -> .F*

*> F -> .(E)*

*> F -> .id*

*>*

*> I1 :*

*> E' -> E.*

*> E -> E.+T*

*>*

*> I2 :*

*> E -> T.*

*> T -> T.*F*

*>*

*> I3 :*

*> T -> F.*

*>*

*> I4 :*

*> F -> (.E)*

*> E -> .E+T*

*> E -> .T*

*> T -> .T*F*

*> T -> .F*

*> F -> .(E)*

*> F -> .id*

*>*

*> I5 :*

*> F -> id.*

*>*

*> I6 :*

*> E -> E+.T*

*> T -> .T*F*

*> T -> .F*

*> F -> .(E)*

*> F -> .id*

*>*

*> I7 :*

*> T -> T*.F*

*> F -> .(E)*

*> F -> .id*

*>*

*> I8 :*

*> F -> (E.)*

*> E -> E.+T*

*>*

*> I9 :*

*> E -> E+T.*

*> T -> T.*F*

*>*

*> I10 :*

*> T -> T*F.*

*>*

*> I11 :*

*> F -> (E).*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.