开发者

Dealing with infinite loops when constructing states for LR(1) parsing

开发者 https://www.devze.com 2022-12-28 05:58 出处:网络
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.

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.

Fro开发者_高级运维m 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?


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.

0

精彩评论

暂无评论...
验证码 换一张
取 消