views:

21

answers:

1

I'm currently constructing LR(1) states from the following grammar.

S->AS
S->c
A->aA
A->b

where A,S are nonterminals and a,b,c are terminals.

This is the construction of I0

I0: S' -> .S, epsilon
    ---------------
    S -> .AS, epsilon
    S -> .c, epsilon
    ---------------
    S -> .AS, a
    S -> .c, c
    A -> .aA, a
    A -> .b, b

And I1.

From S, I1: S' -> S., epsilon  //DONE

And so on. But when I get to constructing I4...

From a, I4: A -> a.A, a
        -----------
        A -> .aA, a
        A -> .b, b

The problem is A -> .aA

When I attempt to construct the next state from a, I'm going to once again get the exact same content of I4, and this continues infinitely. A similar loop occurs with

S -> .AS

So, what am I doing wrong? There has to be some detail that I'm missing, but I've browsed my notes and my book and either can't find or just don't understand what's wrong here. Any help?

A: 

I'm pretty sure I figured out the answer. Obviously, states can point to each other, so that eliminates the need to create new ones if it's content already exists. I'd still like it if someone can confirm this, though.

Bruce