[antlr-interest] [C runtime] Rewrite rules consuming *tons* of memory

[Kurt Otte]

Jim,

Sorry to add another thing to the list, but I think I may have found
another bug or perhaps there is a better way to construct the rewrite
rule to avoid making lots of AST copies.  Do you know of a way to
avoid rewrite rules doing lots of copies?

I have boiled my grammar down to show the problem using toy input.
When the parser is fed a nested block such as the one below it
consumes over 2GB of memory and crashes when it runs out of memory.


conditional
  : 'if' '(' constant ')' ifblock=block
     // This rewrite rule kills conditionals
      -> ^(CONDITIONAL constant ^(IF $ifblock))
  ;


if (0)
{
  if (0)
  {
    if (0)
    {
      if (0)
      {
        if (0)
        {
          if (0)
          {
            if (0)
            {
              boo;
            }
          }
        }
      }
    }
  }
}

When digging into it a bit with a profiler, it appears that the
problem is in the rewrite rule.  The rewrite rule for 'conditional' is
calling ADAPTOR->addChild()  and dupTree() recursively millions of
times which in effect continuously allocates memory until it runs out.
 Is there some way from a syntax point of view that I can construct a
rewrite rule such that it minimizes the tree dups?

Attached is a zip file, with this toy example to reproduce the problem.

Thanks in advance for any thoughts or advice,

Kurt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: memory_hog.zip
Type: application/zip
Size: 2472 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20080828/bf0156f7/attachment.zip