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

[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-14 (20:22) From: Jon Harrop Subject: Re: [Caml-list] CFG's and OCaml
```On Saturday 14 August 2004 04:33, Brian Hurt wrote:
> > 3. If so, is the fact that most languages disallow "a<b<c" due to this?
>
> No.  "a<b<c" is parsed the same way as "a+b+c".

Sorry, I should have been more specific. With left- or right- or
non-associative, commuting, 'a->'a->'a operators (like + and *) you can get
away with parsing that way, e.g. "a+b+c" as:

either  (a+b)+c  or  a+(b+c)

But you can't do this with comparison 'a->'a->bool operators because it forces
you to deviate from conventional mathematical meaning, e.g. you get a type
error in OCaml on the "3" in "1<2<3" because it parses as "(1<2)<3" which
evaluates to "true<3" which just doesn't make any sense.

IMHO, being able to do "1<2<false", although valid in OCaml and many other
languages, is not terribly useful. Indeed, it can lead to overt
confusingnesses:

# false=false=false;;
- : bool = false
# false=false=false=false;;
- : bool = true

I thought that the ML family were designed to mimic mathematical notation
where possible but, AFAIK, most implementations don't do "a<b<c" this way.

I had always assumed that this was a limitation of LALR(1) but, according to
skaller and Eric, I was wrong.

On Saturday 14 August 2004 08:55, skaller wrote:
> ...
> It is possible to make < a chain operator instead,
> ...

I see. You don't just make (x + y) an expression in the grammar but a whole
new rule "sum" which contains (x + y) or (x + sum) and has the precendence of
"+"?

So I want to take all comparison operators "'a -> 'a -> bool" and make a rule
"inequality" for a (x op1 y) or (x op1 comparison) chain "operator" which,
say, builds a list of operand and operators? Then you could do "x0 <= x <
x1". Woohoo!

Would this have to be a conflict in the grammar with "a<b<c" parsed as
"(a<b)<c"?

> > 4. Could that be added to OCaml? ;-)
>
> Not without breaking existing code...

Right, because somebody somewhere is bound to have done the equivalent of
"2<5<false" in their OCaml code. But does "2<5<false" have defined behaviour?

> > 5. Is it productive to think in terms of coercing lex and yacc into doing
> > as much of the work as possible
>
> I personally think you should do the opposite -- let lex/yacc
> do the least possible work since they're fairly rigid.
> You may need to fiddle with your grammar to get the language
> you want -- and it is better if that has the minimum
> impact on your semantic logic. IMHO.

But making more use of lex and yacc is good because they detect conflicts or
ambiguities? Not great in the sense that reduce-reduce conflicts can be a
nightmare to get rid of though (especially if you don't own the grammar), but