English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Right recursion with ocamlyacc
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-02-16 (04:42)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Right recursion with ocamlyacc
On Wed, 2005-02-16 at 14: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?  Left recursion runs
> in constant stack space so this would be the way to go...

Kind of tricky to represent right associative binary
operator with left recursion .. right recursion is 
much more natural:

rterm: atom rterm { Rterm ($1, $2) }

The thing is, right assoc requires terms to
be stacked up one way or another. Left recursion
defers the problem to client code, and must introduce
intermediate term structure to do that.

Why would I believe my own data structures
would perform more efficiently than the parser stack?

John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net