Happy analysis: left recursion and right recursion

Question

Section 2.2 of the Happy User Guide advises you to use left recursion rather than right recursion, because proper recursion is "inefficient." Basically they say that if you try to parse a long sequence of elements, proper recursion will overflow the parsing stacks, while the left recursion uses a constant stack. The given canonical example

items : item            { $1 : [] }
      | items "," item  { $3 : $1 }

Unfortunately, this means that the list of items goes back.

Now it’s easy enough to apply reverseat the end (although, unfortunately, it’s annoying that you should do this wherever the parser is called, and not once where it is defined). However, if the list of items is large, sure reverseto overflow the Haskell stack as well? No?

Basically, how can I do this so that I can parse arbitrarily large files and still get the results in the correct order?

Answer 1

If you want the whole to itemsbe reversed every time, you can define

items  : items_           {reverse $1}

items_ : item             { $1 : [] }
       | items_ "," item  { $3 : $1 }

reversewill not overflow the stack. If you need to make sure of this, try evaluatinglength $ reverse [1..10000000]