From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id A07BEBC8E for ; Wed, 16 Feb 2005 05:42:38 +0100 (CET) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j1G4gala023563 for ; Wed, 16 Feb 2005 05:42:37 +0100 Received: from [192.168.1.200] (ppp212-197.lns2.syd3.internode.on.net [203.122.212.197]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id j1G4gOGP093883; Wed, 16 Feb 2005 15:12:25 +1030 (CST) Subject: Re: [Caml-list] Right recursion with ocamlyacc From: skaller Reply-To: skaller@users.sourceforge.net To: Markus Mottl Cc: Jon Harrop , caml-list@yquem.inria.fr In-Reply-To: <20050216035811.GA17612@mobile> References: <200502160210.46048.jon@jdh30.plus.com> <20050216035811.GA17612@mobile> Content-Type: text/plain Organization: Message-Id: <1108528944.5095.125.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 16 Feb 2005 15:42:24 +1100 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 4212CF3C.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 recursion:01 ocamlyacc:01 sourceforge:01 markus:01 mottl:01 wrote:01 wrote:01 ocaml:01 recursion:01 ocamlyacc:01 recursive:01 grammar:01 stack:01 associative: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 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