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

Posted by Bruce on Stack Overflow See other posts from Stack Overflow or by Bruce
Published on 2010-04-28T12:57:32Z Indexed on 2010/04/28 13:03 UTC
Read the original article Hit count: 237

Filed under:

parsing

|

lr1

|

infinite-loop

|

states

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?

© Stack Overflow or respective owner

Related posts about parsing

Hot to fix nautilus desktop on linux mint

as seen on Ask Ubuntu - Search for 'Ask Ubuntu'
so I'm using Linux Mint 13 with Cinnamon and suddenly there are no icons on the desktop and the right click doesn't work, it's like the desktop doesn't start up at all, but the Cinnamon interface and everything else are working just fine. This happens only when I open the session with Cinnamon, if… >>> More
Is parsing JSON faster than parsing XML

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm creating a sophisticated JavaScript library for working with my company's server side framework. The server side framework encodes its data to a simple XML format. There's no fancy namespacing or anything like that. Ideally I'd like to parse all of the data in the browser as JSON. However, if… >>> More
Looking for a tutorial on Recursive Descent Parsing.

as seen on Stack Overflow - Search for 'Stack Overflow'
I am trying to parse some data to no success. Can anyone recommend a good introduction with a lot of examples to Recursive Descent Parsing? I haven't been able to find any. >>> More
Parsing XML with Hpricot, a Gem of a Ruby Gem

as seen on Internet.com - Search for 'Internet.com'
Need to parse complex XML documents but don't know where to begin? Leave the task to Ruby's powerful Hpricot library. >>> More
Parsing scripts that use curly braces

as seen on Programmers - Search for 'Programmers'
To get an idea of what I'm doing, I am writing a python parser that will parse directx .x text files. The problem I have deals with how the files are formatted. Although I'm writing it in python, I'm looking for general algorithms for dealing with this sort of parsing. .x files define data using… >>> More

Related posts about lr1

lr parsing table

as seen on Stack Overflow - Search for 'Stack Overflow'
Could any1 explain how can i transform ll(1) parsing table to lr(1) parsing table? Or are there any tables already for lr1 mathematical parsing(+,-,/,*,^)? >>> More
Dealing with infinite loops when constructing states for LR(1) parsing

as seen on Stack Overflow - Search for 'Stack Overflow'
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 --------------- … >>> More