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

[Brian Hurt <bhurt@spnz.org>]

On Fri, 13 Aug 2004, David McClain wrote:

> Uhuhh... Yes, I did that same "evil" thing as well, even before 
> discussing all these reduce/reduce conflicts/

Did you get all the symbols you needed to?  It looks like you need the 
entire first set for the "right" reduction rule.  If you missed a 
symbol, this could still be a problem.  This is why this trick is "evil".

> 
> What I find is that these screwball little tricks might help, and the 
> might not. YACC is just too darned sensitive to minor and non-obvious 
> perturbations in the input grammar specification. Realizing its legacy, 
> indeed it does arise from the old IBM-360, or more properly PDP-10, 
> days. That was the style of programming back then.. I remember it well.

The problem is that Yacc grammar is very dense.  Changing the yacc 
description in even minor ways can have very big effects on the grammar 
you are actually describing.

Take my example earlier of left vr.s right recursion.  Consider the 
expression 4 * 5 / 3.  With left recursion, this is parsed as
(4 * 5) / 3, or 20 / 3, or 6.  With right recursion, this is parsed as 4 * 
(5 / 3), or 4 * 1, or 4.  Opps.

One of the things I like about LALR(1) parsers is that my experience has 
been that if they get confused about something, sooner or later the user 
of the language will get confused about the exact same thing.  Even 
something as "harmless" as a shift/reduce conflict.  The classic example 
of this is the dangling else problem in C.  My number one complaint with 
Ocaml is the number of shift/reduce (and hidden reduce/reduce) conflicts 
in it's grammar.  These bite me on a regular basis.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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