Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] CFG's and OCaml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-08-15 (08:24)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] CFG's and OCaml
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


	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

John Skaller,
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: