From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 02094BC8E for ; Wed, 16 Feb 2005 05:33:50 +0100 (CET) Received: from ptb-relay01.plus.net (ptb-relay01.plus.net [212.159.14.212]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j1G4Xn0A021212 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 16 Feb 2005 05:33:49 +0100 Received: from [80.229.56.224] (helo=chetara) by ptb-relay01.plus.net with esmtp (Exim) id 1D1Gsn-0003De-3C for caml-list@yquem.inria.fr; Wed, 16 Feb 2005 04:33:49 +0000 From: Jon Harrop Organization: University of Cambridge To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Right recursion with ocamlyacc Date: Wed, 16 Feb 2005 04:35:23 +0000 User-Agent: KMail/1.7.1 References: <200502160210.46048.jon@jdh30.plus.com> <20050216035811.GA17612@mobile> In-Reply-To: <20050216035811.GA17612@mobile> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200502160435.23574.jon@jdh30.plus.com> X-Miltered: at concorde with ID 4212CD2D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 recursion:01 ocamlyacc:01 markus:01 mottl:01 wrote:01 wrote:01 ocaml:01 recursion:01 ocamlyacc:01 recursive:01 grammar:01 stack:01 ocaml:01 avoiding:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: 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.