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 (01:30)
From: Jon Harrop <jon@j...>
Subject: Re: [Caml-list] CFG's and OCaml
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<b<c has to be one of two ways:
>        <                <
>       / \              / \
>     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<b<c
> syntactically different than (a<b)<c?

In conventional mathematical notation, I would say yes. Although the latter is 
only meaningful if you've defined a comparison over booleans (e.g. OCaml's 
true>false), 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<b<c and (a<b)<c be 
semantically different?".


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