Subject: Re: ipnat_y.y
To: Chapman Flack <>
From: Steven M. Bellovin <>
List: current-users
Date: 10/13/2004 12:08:17
In message <>, 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,