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

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

On Sun, 2004-08-15 at 06:19, Jon Harrop wrote:
> On Saturday 14 August 2004 04:33, Brian Hurt wrote:

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

The actual grammar production is like:

sum: difference sum | difference

which looks right associative. But it isn't, because the real
thing is:

sum: difference sum { $1 :: $2 } | difference { [$1] }

which you can see constructs a list -- I can interpret that
as either left or right associative, or as an n-ary operator.
I have cheated the parser by NOT building the parse tree
you'd expect, but a list :)

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

Of course, you have to decide whether

	a < b < c

means

	(a < b) < c

or

	a < n && b < c

You can actually parse it and generate a list either way,
and make the decision later. However you can't easily
defer the decision to type analysis .. because the typing
usually would depend on already knowing the precedence.

you *could* do a trial typing, and if it failed, try
the other precedence -- it would work, but heck it would
surely confuse the programmer as well as the compiler :)

That's why i use

	a < b &< c &< d &< e

in Felix. This notation doesn't conflict with
the usual precedence for <.

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

Recall Ocaml has a polymorphic comparison operator .. it has to
work on basic types like bool too.

Exercise: it actually has a real meaning in terms of boolean
operators (assume false < true). Hint: do the truth table :)

> But making more use of lex and yacc is good because they detect conflicts or 
> ambiguities? 

Except that often they're unwanted, and an artefact of the
grammar you have chosen, rather than the language you want
to parse. As you said: there is a tradeoff.

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