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 KAA23642; Sun, 15 Aug 2004 10:24:32 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA23768 for ; Sun, 15 Aug 2004 10:24:31 +0200 (MET DST) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7F8OSRM009232 for ; Sun, 15 Aug 2004 10:24:29 +0200 Received: from [192.168.1.200] (ppp197-3.lns1.syd2.internode.on.net [203.122.197.3]) by smtp1.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i7F8OO4Y080737; Sun, 15 Aug 2004 17:54:26 +0930 (CST) Subject: Re: [Caml-list] CFG's and OCaml From: skaller Reply-To: skaller@users.sourceforge.net To: Jon Harrop Cc: Ocaml Mailing List In-Reply-To: <200408150226.53550.jon@jdh30.plus.com> References: <200408150226.53550.jon@jdh30.plus.com> Content-Type: text/plain Message-Id: <1092558263.29139.865.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 15 Aug 2004 18:24:24 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 411F1DBC.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 sourceforge:01 2004:99 n-ary:01 sublanguage:01 operands:01 operands:01 parses:01 floats:01 9660:01 glebe:01 compiler:01 semantics:01 ints:01 ocaml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sun, 2004-08-15 at 11:26, Jon Harrop wrote: > I believe you are unnecessarily constraining the AST to be a binary tree. What > is wrong with an n-ary tree: > > type ast = ... | Less of ast list | ... > > Less [a; b; c] Indeed: for operator * in the type sublanguage of Ocaml that is mandatory. > I think Skaller referred to the implementation of a parser for this as a > "chain operator", which I understand to be a way non-associative operators > may be parsed to create a node in the AST with a list of operands, rather > than the usual pair of operands. Yes, but the phrase 'non-associative' has a different meaning than what I called 'chain operator'. Non-associative means a binary operator that *requires brackets* for example in TeX x ^ y ^ z is an *error* because ^ is neither left nor right associative but non-associative. On the other hand in 'mathematics' + is actually associative -- it isn't left or right associative, its associative: a + b + c means the same as BOTH (a + b) + c and a + (b + c) This means the compiler could choose three distint parses: (a) left assoc (b) right assoc (c) chain operator and the user would not be allowed to depend on the implementation chosen. Few languages do that, but it would be useful because it allows superior optimisation -- for example constant folding both 1 + 2 + three one + 2 + 3 is impossible with left or right assoc because you can't tell from the parse tree if the client used brackets to override the usual precedence -- you can ignore that if you happen to know the semantics of course: for ints, you might. But it would be risky for floats. -- 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 ------------------- 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