Re: unreachable states after conflict resolution (was: Re: LR(1) paser generator based on Pager's algorithm)

[Joel E. Denny]

On Sun, 6 May 2007, Joel E. Denny wrote:

> --- ChangeLog 7 May 2007 02:28:42 -0000       1.1696
> +++ ChangeLog 7 May 2007 02:51:10 -0000
> @@ -1,5 +1,27 @@
>  2007-05-06  Joel E. Denny  <address@hidden>
>  
> +     If conflict resolution makes states unreachable, remove those states,
> +     report rules that are then unused, and don't report conflicts in those
> +     states.

I think the above change is NEWS-worthy, so I committed the patch below.

It occurs to me now that the above change might be a 
backward-compatibility problem because it can change the number of 
conflicts that Bison reports for existing grammars, and that can affect 
%expect and %expect-rr.  However, I see the previous behavior as 
incorrect.

Unfortunately, /usr/ccs/bin/yacc on Solaris 10 also exhibits the previous 
behavior.  Then again, it doesn't support %expect and %expect-rr.

Anyone have any ideas about how we should handle this?

Index: ChangeLog
===================================================================
RCS file: /sources/bison/bison/ChangeLog,v
retrieving revision 1.1697
diff -p -u -r1.1697 ChangeLog
--- ChangeLog   7 May 2007 02:56:56 -0000       1.1697
+++ ChangeLog   8 May 2007 04:19:49 -0000
@@ -1,3 +1,12 @@
+2007-05-07  Joel E. Denny  <address@hidden>
+
+       * NEWS (2.3a+): Mention yesterday's state-removal change.
+       (2.3a): Remove the %language entry, which was added after 2.3a.
+       * src/LR0.c, src/closure.c, src/closure.h, src/conflicts.c,
+       src/conflicts.h, src/lalr.c, src/lalr.h, src/print.c,
+       src/print_graph.c, src/state.c, src/state.h, tests/conflicts.at,
+       tests/existing.at: Update copyright date.
+
 2007-05-06  Joel E. Denny  <address@hidden>
 
        If conflict resolution makes states unreachable, remove those states,
Index: NEWS
===================================================================
RCS file: /sources/bison/bison/NEWS,v
retrieving revision 1.173
diff -p -u -r1.173 NEWS
--- NEWS        29 Jan 2007 10:54:42 -0000      1.173
+++ NEWS        8 May 2007 04:19:49 -0000
@@ -3,6 +3,18 @@ Bison News
 
 Changes in version 2.3a+ (????-??-??):
 
+* Previously, Bison sometimes generated parser tables with states that were
+  unreachable due to conflicts in predecessor states.  Bison now:
+
+    1. Removes unreachable states.
+
+    2. Does not report any conflicts that appeared in unreachable states.
+       WARNING: As a result, you may need to update %expect and %expect-rr
+       directives in existing grammar files.
+
+    3. For any rule used only in such states, Bison now reports the rule as
+       "never reduced because of conflicts".
+
 * The -g and --graph options now output graphs in Graphviz DOT format,
   not VCG format.
 
@@ -92,9 +104,6 @@ Changes in version 2.3a+ (????-??-??):
 
 Changes in version 2.3a, 2006-09-13:
 
-* Bison now supports generating Java parsers.  Grammars written for
-  the Java language should include the `%language "Java"' directive.
-
 * Instead of %union, you can define and use your own union type
   YYSTYPE if your grammar contains at least one <type> tag.
   Your YYSTYPE need not be a macro; it can be a typedef.
Index: src/LR0.c
===================================================================
RCS file: /sources/bison/bison/src/LR0.c,v
retrieving revision 1.97
diff -p -u -r1.97 LR0.c
--- src/LR0.c   7 May 2007 02:28:42 -0000       1.97
+++ src/LR0.c   8 May 2007 04:19:49 -0000
@@ -1,6 +1,6 @@
 /* Generate the nondeterministic finite state machine for Bison.
 
-   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005, 2006
+   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005, 2006, 2007
    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
Index: src/closure.c
===================================================================
RCS file: /sources/bison/bison/src/closure.c,v
retrieving revision 1.75
diff -p -u -r1.75 closure.c
--- src/closure.c       7 May 2007 02:28:42 -0000       1.75
+++ src/closure.c       8 May 2007 04:19:49 -0000
@@ -1,6 +1,6 @@
 /* Closures for Bison
 
-   Copyright (C) 1984, 1989, 2000, 2001, 2002, 2004, 2005 Free
+   Copyright (C) 1984, 1989, 2000, 2001, 2002, 2004, 2005, 2007 Free
    Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
Index: src/closure.h
===================================================================
RCS file: /sources/bison/bison/src/closure.h,v
retrieving revision 1.15
diff -p -u -r1.15 closure.h
--- src/closure.h       7 May 2007 02:28:42 -0000       1.15
+++ src/closure.h       8 May 2007 04:19:49 -0000
@@ -1,6 +1,6 @@
 /* Subroutines for bison
 
-   Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software
+   Copyright (C) 1984, 1989, 2000, 2001, 2002, 2007 Free Software
    Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
Index: src/conflicts.c
===================================================================
RCS file: /sources/bison/bison/src/conflicts.c,v
retrieving revision 1.117
diff -p -u -r1.117 conflicts.c
--- src/conflicts.c     7 May 2007 02:56:56 -0000       1.117
+++ src/conflicts.c     8 May 2007 04:19:49 -0000
@@ -1,7 +1,7 @@
 /* Find and resolve or report lookahead conflicts for bison,
 
-   Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005, 2006
-   Free Software Foundation, Inc.
+   Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
+   2007 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
Index: src/conflicts.h
===================================================================
RCS file: /sources/bison/bison/src/conflicts.h,v
retrieving revision 1.17
diff -p -u -r1.17 conflicts.h
--- src/conflicts.h     7 May 2007 02:56:56 -0000       1.17
+++ src/conflicts.h     8 May 2007 04:19:49 -0000
@@ -1,5 +1,5 @@
 /* Find and resolve or report lookahead conflicts for bison,
-   Copyright (C) 2000, 2001, 2002, 2004 Free Software Foundation, Inc.
+   Copyright (C) 2000, 2001, 2002, 2004, 2007 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
Index: src/lalr.c
===================================================================
RCS file: /sources/bison/bison/src/lalr.c,v
retrieving revision 1.112
diff -p -u -r1.112 lalr.c
--- src/lalr.c  7 May 2007 02:56:56 -0000       1.112
+++ src/lalr.c  8 May 2007 04:19:49 -0000
@@ -1,7 +1,7 @@
 /* Compute lookahead criteria for Bison.
 
    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
-   2006 Free Software Foundation, Inc.
+   2006, 2007 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
Index: src/lalr.h
===================================================================
RCS file: /sources/bison/bison/src/lalr.h,v
retrieving revision 1.35
diff -p -u -r1.35 lalr.h
--- src/lalr.h  7 May 2007 02:56:56 -0000       1.35
+++ src/lalr.h  8 May 2007 04:19:49 -0000
@@ -1,6 +1,6 @@
 /* Compute lookahead criteria for bison,
 
-   Copyright (C) 1984, 1986, 1989, 2000, 2002, 2004, 2006 Free Software
+   Copyright (C) 1984, 1986, 1989, 2000, 2002, 2004, 2006, 2007 Free Software
    Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
Index: src/print.c
===================================================================
RCS file: /sources/bison/bison/src/print.c,v
retrieving revision 1.101
diff -p -u -r1.101 print.c
--- src/print.c 7 May 2007 02:28:42 -0000       1.101
+++ src/print.c 8 May 2007 04:19:50 -0000
@@ -1,6 +1,6 @@
 /* Print information on generated parser, for bison,
 
-   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005
+   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005, 2007
    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
Index: src/print_graph.c
===================================================================
RCS file: /sources/bison/bison/src/print_graph.c,v
retrieving revision 1.63
diff -p -u -r1.63 print_graph.c
--- src/print_graph.c   7 May 2007 02:28:42 -0000       1.63
+++ src/print_graph.c   8 May 2007 04:19:50 -0000
@@ -1,6 +1,6 @@
 /* Output a graph of the generated parser, for Bison.
 
-   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Free Software
+   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software
    Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
Index: src/state.c
===================================================================
RCS file: /sources/bison/bison/src/state.c,v
retrieving revision 1.43
diff -p -u -r1.43 state.c
--- src/state.c 7 May 2007 02:56:56 -0000       1.43
+++ src/state.c 8 May 2007 04:19:50 -0000
@@ -1,6 +1,6 @@
 /* Type definitions for nondeterministic finite state machine for Bison.
 
-   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Free Software
+   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software
    Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
Index: src/state.h
===================================================================
RCS file: /sources/bison/bison/src/state.h,v
retrieving revision 1.52
diff -p -u -r1.52 state.h
--- src/state.h 7 May 2007 02:56:56 -0000       1.52
+++ src/state.h 8 May 2007 04:19:50 -0000
@@ -1,6 +1,6 @@
 /* Type definitions for nondeterministic finite state machine for Bison.
 
-   Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004 Free
+   Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2007 Free
    Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
Index: tests/conflicts.at
===================================================================
RCS file: /sources/bison/bison/tests/conflicts.at,v
retrieving revision 1.33
diff -p -u -r1.33 conflicts.at
--- tests/conflicts.at  7 May 2007 02:56:56 -0000       1.33
+++ tests/conflicts.at  8 May 2007 04:19:50 -0000
@@ -1,6 +1,6 @@
 # Exercising Bison on conflicts.                         -*- Autotest -*-
 
-# Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+# Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
 
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
Index: tests/existing.at
===================================================================
RCS file: /sources/bison/bison/tests/existing.at,v
retrieving revision 1.11
diff -p -u -r1.11 existing.at
--- tests/existing.at   7 May 2007 02:56:56 -0000       1.11
+++ tests/existing.at   8 May 2007 04:19:50 -0000
@@ -1,7 +1,7 @@
 # Exercising Bison on actual grammars.                   -*- Autotest -*-
 
-# Copyright (C) 1989, 1990, 1991, 1992, 2000, 2001, 2002, 2003, 2004, 2005
-# Free Software Foundation, Inc.
+# Copyright (C) 1989, 1990, 1991, 1992, 2000, 2001, 2002, 2003, 2004, 2005,
+# 2007 Free Software Foundation, Inc.
 
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by