# Re: States Creation

## mwdeeds@yahoo.com (Matt Deeds)31 Mar 2002 23:33:19 -0500

From comp.compilers

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)
| List of all articles for this month |

 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.

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

-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