[kazinator]

If you are using a shift-reduce parser, you may have to fix right recursion instead.

If you have a right recursive construct, the parser stack usage will be proportional to the length of the instances of the construct. That can be a problem.

For instance:

   stuff : /* empty */
         | item stuff
         ;

If you have 10,000 items in a sequence of stuff, they all get pushed onto the stack which is then popped by a long cascade of rightmost reductions.

You have to refactor for left recursion.

I ran into this when parsing Lisp this way. Lisp lists are right recursive; they are naturally constructed from the right end, by consing onto the front. When you write the obvious parser rules, the list does not start being constructed until the closing parenthesis is seen, and the cascade of reductions pulls it out of the stack.

This is not a problem like runaway left recursion; it is an insidious bug that you won't even notice with small test cases.

Switching to left recursion means that you have to construct the list left-to-right somehow. Either the rules maintain a tail pointer somehow, or the list is consed up in reverse and then destructively reversed. A minor complication is support for the consing dot.