[Aide] Aide Stack Overflow with large configuration files

[Bob Proulx]

Virolainen Pablo wrote:
> btw: this should fix the problem. (Yes, the fix is described in bison FAQ:)
> -lines : | line lines;
> +lines : lines line | ;

Yes.  That will convert the grammer from being a right recursive
grammer to being a left recursive grammer.  (The movement of the empty
statement in the OR from the left side to right side is not
signifcant.)  Left recursive grammers won't grow in memory usage while
right recursive grammers are dependent upon the input.

The difference can be seen with this example.

  thing : thing manythings

The right recursive grammer builds like this.

  thing thing thing
    \     \    /
     \     \  /
      \     \/
       \    /
        \  /
         \/

As you can see the stack in the parser grows.  It cannot reduce the
stack until it has seen all of the expressions.  The stack grows with
the input.  The memory use is unbounded.

The left recursive grammer is the mirror image of the above.

  thing : manythings thing

Given the same input.

  thing thing thing
    \    /     /
     \  /     /
      \/     /
       \    /
        \  /
         \/

Here you can see that the first two expressions can be reduced as soon
as the second expression is seen.  And then again with the next.  And
so on.  So the parser stack never grows very large.  The memory use is
bounded.

Bob

P.S.  I highly recommend the text "Introduction to Compiler
Construction with UNIX" by Axel T. Schreiner and H. George Friedman,
Jr., Prentice Hall, 1985.  It is a little dated now.  But the concepts
have not changed and I found it quite a readable text.  Of course it
is text I learned yacc parsing from and so I am biased.