[PATCH] Fix some comments concerning LR(0) versus LALR(1).

[Joel E. Denny]

I pushed this to branch-2.5 and master.

>From 1c4ad777cb220ea669dc934c9b600a25a824a658 Mon Sep 17 00:00:00 2001
From: Joel E. Denny <address@hidden>
Date: Mon, 4 Jan 2010 14:13:43 -0500
Subject: [PATCH] Fix some comments concerning LR(0) versus LALR(1).

Stop equating LR(0) with nondeterminism and LALR(1) with
determinism.  That is, if all states are consistent, then LR(0)
tables are deterministic.  On the other hand, LALR(1) tables
might be nondeterministic before conflict resolution, and GLR
permits LALR(1) tables to remain nondeterministic.
* src/LR0.c, src/LR0.h: Here.
* src/lalr.c, src/lalr.h: Here.
* src/main.c (main): Here.
* src/state.c, src/state.h: Here.

* src/ielr.h (ielr): In preconditions, expect LR(0) not LALR(1)
parser tables.
---
 ChangeLog   |   17 +++++++++++++++++
 src/LR0.c   |    6 +++---
 src/LR0.h   |    3 ++-
 src/ielr.h  |    4 ++--
 src/lalr.c  |    3 +--
 src/lalr.h  |    3 +--
 src/main.c  |    9 ++++-----
 src/state.c |    2 +-
 src/state.h |    2 +-
 9 files changed, 32 insertions(+), 17 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 1743e18..885a574 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,22 @@
 2010-01-04  Joel E. Denny  <address@hidden>
 
+       Fix some comments concerning LR(0) versus LALR(1).
+
+       Stop equating LR(0) with nondeterminism and LALR(1) with
+       determinism.  That is, if all states are consistent, then LR(0)
+       tables are deterministic.  On the other hand, LALR(1) tables
+       might be nondeterministic before conflict resolution, and GLR
+       permits LALR(1) tables to remain nondeterministic.
+       * src/LR0.c, src/LR0.h: Here.
+       * src/lalr.c, src/lalr.h: Here.
+       * src/main.c (main): Here.
+       * src/state.c, src/state.h: Here.
+
+       * src/ielr.h (ielr): In preconditions, expect LR(0) not LALR(1)
+       parser tables.
+
+2010-01-04  Joel E. Denny  <address@hidden>
+
        maint: run "make update-copyright"
 
 2009-12-30  Joel E. Denny  <address@hidden>
diff --git a/src/LR0.c b/src/LR0.c
index fa56324..2628027 100644
--- a/src/LR0.c
+++ b/src/LR0.c
@@ -1,4 +1,4 @@
-/* Generate the nondeterministic finite state machine for Bison.
+/* Generate the LR(0) parser states for Bison.
 
    Copyright (C) 1984, 1986, 1989, 2000-2002, 2004-2007, 2009-2010 Free
    Software Foundation, Inc.
@@ -329,8 +329,8 @@ set_states (void)
 
 
 /*-------------------------------------------------------------------.
-| Compute the nondeterministic finite state machine (see state.h for |
-| details) from the grammar.                                         |
+| Compute the LR(0) parser states (see state.h for details) from the |
+| grammar.                                                           |
 `-------------------------------------------------------------------*/
 
 void
diff --git a/src/LR0.h b/src/LR0.h
index 4418871..2f4aff1 100644
--- a/src/LR0.h
+++ b/src/LR0.h
@@ -1,4 +1,5 @@
-/* Generate the nondeterministic finite state machine for bison,
+/* Generate the LR(0) parser states for Bison.
+
    Copyright (C) 1984, 1986, 1989, 2000-2002, 2009-2010 Free Software
    Foundation, Inc.
 
diff --git a/src/ielr.h b/src/ielr.h
index 2dc5def..668b67e 100644
--- a/src/ielr.h
+++ b/src/ielr.h
@@ -26,8 +26,8 @@
 
 /**
  * \pre
- *   - \c ::states is of size \c ::nstates and defines an LALR(1) parser for
- *     the users's grammar.
+ *   - \c ::states is of size \c ::nstates and defines an LR(0) parser
+ *     for the users's grammar.
  *   - \c ::ntokens is the number of tokens in the grammar.
  * \post
  *   - \c ::states is of size \c ::nstates (which might be greater than
diff --git a/src/lalr.c b/src/lalr.c
index 5944a48..6f099a8 100644
--- a/src/lalr.c
+++ b/src/lalr.c
@@ -19,8 +19,7 @@
    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 
-/* Compute how to make the finite state machine deterministic; find
-   which rules need lookahead in each state, and which lookahead
+/* Find which rules need lookahead in each state, and which lookahead
    tokens they accept.  */
 
 #include <config.h>
diff --git a/src/lalr.h b/src/lalr.h
index 5cd7775..88ff7b4 100644
--- a/src/lalr.h
+++ b/src/lalr.h
@@ -33,8 +33,7 @@
 
 /** Build the LALR(1) automaton.
 
-   Compute how to make the finite state machine deterministic; find
-   which rules need lookahead in each state, and which lookahead
+   Find which rules need lookahead in each state, and which lookahead
    tokens they accept.
 
    Also builds:
diff --git a/src/main.c b/src/main.c
index 05470d7..5c852ac 100644
--- a/src/main.c
+++ b/src/main.c
@@ -97,15 +97,14 @@ main (int argc, char *argv[])
   nullable_compute ();
   timevar_pop (TV_SETS);
 
-  /* Convert to nondeterministic finite state machine.  In file LR0.
-     See state.h for more info.  */
+  /* Compute LR(0) parser states.  See state.h for more info.  */
   timevar_push (TV_LR0);
   generate_states ();
   timevar_pop (TV_LR0);
 
-  /* Make it deterministic by computing lookahead sets.  Except when LALR(1) is
-     requested, split states to eliminate LR(1)-relative inadequacies.  In file
-     lalr and ielr.  */
+  /* Add lookahead sets to parser states.  Except when LALR(1) is
+     requested, split states to eliminate LR(1)-relative
+     inadequacies.  */
   ielr ();
 
   /* Find and record any conflicts: places where one token of
diff --git a/src/state.c b/src/state.c
index aa80ebc..dd25379 100644
--- a/src/state.c
+++ b/src/state.c
@@ -1,4 +1,4 @@
-/* Type definitions for nondeterministic finite state machine for Bison.
+/* Type definitions for the finite state machine for Bison.
 
    Copyright (C) 2001-2007, 2009-2010 Free Software Foundation, Inc.
 
diff --git a/src/state.h b/src/state.h
index 99e09c4..a1ed993 100644
--- a/src/state.h
+++ b/src/state.h
@@ -1,4 +1,4 @@
-/* Type definitions for nondeterministic finite state machine for Bison.
+/* Type definitions for the finite state machine for Bison.
 
    Copyright (C) 1984, 1989, 2000-2004, 2007, 2009-2010 Free Software
    Foundation, Inc.
-- 
1.5.4.3