A pathological example that blows up

[panyam]

Ive been using Jison as a validator for test cases (for another generator I have been building) and found that for some cases the LR1 table construction blows up.

Here is a very minimal example:

%%
S : S E ;
S : ;

E : A ;

A : A a ;
A : ;

Running this on the command line (jison -p lr1 -t ) causes the number of canonical closure items to balloon up (resulting in node's heap getting overflown).

My generator produces this parse table (each entry is a state number, set if lr1 items, next set (the goto set) and entries in the parse table) but Id love to be able to validate this using Jison too:

{
  '0': {
    items: [
      'Start ->  . S   /   <EOF>',
      'S ->  . S E   /   <EOF>',
      'S ->  .    /   <EOF>',
      'S ->  . S E   /   a',
      'S ->  .    /   a'
    ],
    actions: { '<EOF>': [ 'R <S -> >' ], S: [ '1' ], a: [ 'R <S -> >' ] },
    next: { S: 1 }
  },
  '1': {
    items: [
      'A ->  . A a   /   <EOF>',
      'A ->  .    /   <EOF>',
      'A ->  . A a   /   a',
      'A ->  .    /   a',
      'Start -> S .    /   <EOF>',
      'S -> S . E   /   <EOF>',
      'S -> S . E   /   a',
      'E ->  . A   /   <EOF>',
      'E ->  . A   /   a'
    ],
    actions: {
      '<EOF>': [ 'R <A -> >', 'Acc' ],
      E: [ '2' ],
      A: [ '3' ],
      a: [ 'R <A -> >' ]
    },
    next: { E: 2, A: 3 }
  },
  '2': {
    items: [ 'S -> S E .    /   <EOF>', 'S -> S E .    /   a' ],
    actions: { '<EOF>': [ 'R <S -> S E>' ], a: [ 'R <S -> S E>' ] },
    next: {}
  },
  '3': {
    items: [
      'A -> A . a   /   <EOF>',
      'A -> A . a   /   a',
      'E -> A .    /   <EOF>',
      'E -> A .    /   a'
    ],
    actions: { '<EOF>': [ 'R <E -> A>' ], a: [ 'S4', 'R <E -> A>' ] },
    next: { a: 4 }
  },
  '4': {
    items: [ 'A -> A a .    /   <EOF>', 'A -> A a .    /   a' ],
    actions: { '<EOF>': [ 'R <A -> A a>' ], a: [ 'R <A -> A a>' ] },
    next: {}
  }
}