Subject: Re: ipnat_y.y
To: Chapman Flack <email@example.com>
From: Steven M. Bellovin <firstname.lastname@example.org>
Date: 10/13/2004 12:08:17
In message <200410131550.i9DFoWje014616@basm.cerias.purdue.edu>, Chapman Flack
>> A grammer that has shift/reduce conflicts is poorly written.
>Well, now ...
>Since yacc specifies exactly what it does with a shift-reduce conflict
>(always choose the shift), it is possible to have a grammar with
>conflicts where the author has reviewed all the conflicts reported
>and confirmed that the parser will unambiguously do exactly what's intended.
>Usually then there will be some comments in the documentation or makefile
>saying "expect 3 reduce-reduce and 5 shift-reduce conflicts from this grammar"
>and if yacc reports exactly that many, it's doing the right thing.
>Why don't all grammar writers go further and continue refactoring their
>grammars until the LALR parser generator doesn't report any conflicts?
>Because the kind of refactoring needed to get rid of those last conflicts
>can be quite elaborate and actually make the grammar longer, harder to read,
>harder to understand, and harder to modify. There are diminishing returns
>when you cross the line from refactoring driven by the clarity of your
>grammar to refactoring driven by the quirks of a parser-generator algorithm.
>That's why generators like yacc offer reasonable defaults for common
>ambiguities, and why some grammar writers don't mind taking advantage of them.
Right. There's a lot of discussion of precisely this point in the
original YACC paper. (Speaking of which -- what will it take to get
those papers into the tree? I thought that the legal obstacles had
been cleared up.)
--Steve Bellovin, http://www.research.att.com/~smb