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

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

On Sat, 2004-08-14 at 10:25, Jon Harrop wrote:
> I have some (probably trivial) questions about parsers:
> 
> 1. Are most programming languages designed to be implementable using lex and 
> yacc?

No :) Felix is, and many academic languages are,
but most industrial kind of languages aren't.
Heck, can you really use the word 'designed' for them?

> 2. If so, are their designs restricted by this?

There are some constraints I wish didn't exist
in the Felix grammar. Its not too bad -- I tend to
accept if a simple parsing engine can parse it,
so can a human, so conforming to the constraints
is a good idea anyhow.

> 3. If so, is the fact that most languages disallow "a<b<c" due to this?

Felix is LALR(1) and supports the following Pythonesque syntax:

  a < b &< c &< d

which is NOT quite what you proposed: we don't want
to get confused with

 (a < b) < c

which is the interpretation you'd get if you make <
a left associative binary operator.

It is possible to make < a chain operator instead,
that is, associative multi-ary: I do that with
operator + and * since it is necessary for the
correct interpretation of the type:

	a * b * c

which is NOT the same as

	(a * b) * c


> 4. Could that be added to OCaml? ;-)

Not without breaking existing code -- but Camlp4 could
add the

	a < b &< c &< d 

syntax easily I expect.

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

> and then using postprocessing to do the rest 
> (e.g. this is the way I'd implement a<b<c)?

For chain operator like '+' and '*' in Felix,
yacc just returns a list.

If the context is a type, the result builds a tuple kind
with n arguments.

If the context is executable code, it is remapped into
a left associative binary operator using a fold_left over
the list.

I actually *could* do this inside the parser, but
I don't, i use a separate 'desugaring' phase
to rewrite the syntax tree. (Actually i recode it
rather than rewriting it).

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