From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id HAA30340; Fri, 13 Aug 2004 07:59:47 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA29409 for ; Fri, 13 Aug 2004 07:59:46 +0200 (MET DST) Received: from mail.davidb.org (adsl-64-172-240-129.dsl.sndg02.pacbell.net [64.172.240.129]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7D5ximL003175 for ; Fri, 13 Aug 2004 07:59:45 +0200 Received: from davidb by mail.davidb.org with local (Exim 4.34 #1 (Debian)) id 1BvV6K-0006Ub-Eg; Thu, 12 Aug 2004 22:59:40 -0700 Date: Thu, 12 Aug 2004 22:59:40 -0700 From: David Brown To: skaller Cc: Paul Snively , David McClain , Joshua Smith , caml-list Subject: Re: [Caml-list] Context Free Grammars? Message-ID: <20040813055940.GA24879@old.davidb.org> References: <93BB4D7C-EC83-11D8-9939-000A95C19BAA@Avisere.com> <411BB09A.7010307@trdlnk.com> <7D827B04-EC8B-11D8-9939-000A95C19BAA@Avisere.com> <55D5BF02-EC95-11D8-915C-000A27DEEC20@mac.com> <1092374548.29139.86.camel@pelican.wigram> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1092374548.29139.86.camel@pelican.wigram> User-Agent: Mutt/1.5.6i X-Miltered: at nez-perce with ID 411C58D0.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 caml-list:01 2004:99 $1,:01 typecode:01 expr:01 $1,:01 recursion:01 recursion:01 ocaml:01 dave:03 wrote:03 recursive:03 recursive:03 tail:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, Aug 13, 2004 at 03:22:28PM +1000, skaller wrote: > tlelement: > | lelement COLON factor { $1,Some (typecode_of_expr $3) } > | lelement { $1,None } > > lexprs: > | tlelement COMMA lexprs { $1 :: $3 } > | tlelement { [$1] } > > This works -- its part of the Felix grammar: tlelement > is left recursive, lexprs is right recursive, > and the reason is clear -- its the most efficient > way to build a list. > > Perhaps someone can explain why this actually works ..?? It is similar to tail recursion and non-tail recursion in ocaml code. The right recursive one works (at least some forms work), but you end up shifting the entire expression off and not reducing the entire thing until the end. In other words, even if you can use right recursion, the left recursive version will be more efficient. I think there are situations where a right recursive version wouldn't be able to parse, but a left one would. But, it is too late, and I don't think I can think about it right now :-) Dave ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners