Re: [Caml-list] CFG's and OCaml

[skaller <skaller@users.sourceforge.net>]

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