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 DAA12827; Sun, 15 Aug 2004 03:30:13 +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 DAA12534 for ; Sun, 15 Aug 2004 03:30:11 +0200 (MET DST) Received: from ptb-relay03.plus.net (ptb-relay03.plus.net [212.159.14.214]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7F1UBRM003203 for ; Sun, 15 Aug 2004 03:30:11 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay03.plus.net with esmtp (Exim) id 1Bw9qc-00007g-UF for caml-list@inria.fr; Sun, 15 Aug 2004 01:30:11 +0000 From: Jon Harrop To: Ocaml Mailing List Subject: Re: [Caml-list] CFG's and OCaml Date: Sun, 15 Aug 2004 02:26:53 +0100 User-Agent: KMail/1.6.2 References: In-Reply-To: MIME-Version: 1.0 Content-Disposition: inline Message-Id: <200408150226.53550.jon@jdh30.plus.com> Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 411EBCA3.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 2004:99 n-ary:01 operands:01 operands:01 n-ary:01 implemented:01 pierre:01 -ary:01 ocaml's:01 boils:01 semantically:01 semantics:01 ocaml:01 coerce:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Saturday 14 August 2004 21:55, Brian Hurt wrote: > The syntax of a language doesn't enforce a given meaning on the language > being parsed. "Colorless green ideas sleep furiously" is a syntactically > correct English sentence, even if it is utterly meaningless. I think I see what you mean. ;-) > The AST of a > < < > / \ / \ > a < or < c > / \ / \ > b c a b > > i.e. a < (b < c) or (a < b) < c. 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] 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. So the AST becomes an n-ary tree, in order to represent n-ary operators. I'd have assumed that pattern matches were implemented in this way but a previous post by Pierre suggested otherwise, because patterns have "no notion of evaluation semantics" so a pattern match is not really a (2n+1)-ary operator. > What the meaning of these two > expressions are is entirely up to the compiler- more spefically, up to the > parts which are not lex or yacc based. I'm not sure again. :-) If you coerce the parsing into using a single, binary AST then I believe you lose the ability to distinguish between Less[a; b; c] and Less[Less[a; b]; c] etc. You have to create different binary AST node types, e.g. InequalityLess(InequalityLess(a, b), c) to mean Less[a; b; c]. > Although this does bring up one interesting question- is a syntactically different than (afalse), which you probably wouldn't... > Generally, languages want to consider "extra" parenthesis to be harmless. Yes, so, as you say, this boils down to "should a