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

[Jon Harrop <jon@jdh30.plus.com>]

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?".

Cheers,
Jon.

-------------------
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