Re: States Creation

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).

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