Section 2.2 of the Happy user manual advises to you use left recursion rather than right recursion, because right recursion is "inefficient". Basically they're saying that if you try to parse a long sequence of items, right recursion will overflow the parse stack, whereas left recursion uses constant stack. The canonical example given is
items : item { $1 : [] }
| items "," item { $3 : $1 }
Unfortunately, this means that the list of items comes out backwards.
Now it's easy enough to apply reverse
at the end (although maddeningly annoying that you have to do this everywhere the parser is called, rather than once where it's defined). However, if the list of items is large, surely reverse
is also going to overflow the Haskell stack? No?
Basically, how do I make it so that I can parse arbitrarily-large files and still get the results out in the correct order?
If all you want is the entire items
to be reverse
d every time, you can define
items : items_ {reverse $1}
items_ : item { $1 : [] }
| items_ "," item { $3 : $1 }
reverse
won't overflow the stack. If you need to convince yourself of this, try evaluating length $ reverse [1..10000000]