Re: [Caml-list] Right recursion with ocamlyacc

[Jon Harrop <jon@jdh30.plus.com>]

On Wednesday 16 February 2005 03:58, Markus Mottl wrote:
> On Wed, 16 Feb 2005, Jon Harrop wrote:
> > I've just been converting a new Computer Language Shootout submission
> > from OCaml to C++ and found that bison falls over very easily with right
> > recursion (failing to load a 10^4-element list) but ocamlyacc had no
> > problems (even on a 10^5-element list).
>
> Why use right recursive productions in the grammar?

There was no justification for it, right recursion just happened to be most 
natural in this case. I've never worried about it before since it never came 
up.

> Left recursion runs in constant stack space so this would be the way to
> go... 

Yes, left recursion is definitely the way to go in general. But has anyone 
ever had a problem with right-recursion when using ocamlyacc? Is there a 
theoretical reason why this is not a problem with ocamlyacc?

When this came up, it occurred to me that (since switching to OCaml) I've 
neglected the stock advice of avoiding right recursion. And I'm not in the 
habit of parsing small files. :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.