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.
(cherry picked from commit 1c4ad777cb220ea669dc934c9b600a25a824a658)

diff --git a/ChangeLog b/ChangeLog
index 7ad82da0f6a14766feeb8f4dfbec2f5269ffbf31..5120acaa24c5b47fefffb97e4f3e6a86c4e0cd01 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,20 @@
+2010-01-04  Joel E. Denny  <jdenny@clemson.edu>
+
+       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  <jdenny@clemson.edu>
 
        maint: run "make update-copyright"

diff --git a/src/LR0.c b/src/LR0.c
index fc582a6ecd0c2c23853b2f47093fc09004c21ba1..31eab0da1ccf142075b0301b8ab28e93557dfbb9 100644 (file)
--- 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-2010 Free Software
    Foundation, Inc.
@@ -328,8 +328,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 4418871347eefb7f92a05434340d21c12bc22612..2f4aff1225b386fe4f0de33a736fa07bc08280af 100644 (file)
--- 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 2dc5defbac02c088c79673e139994ac2936964c6..668b67e95670e378ff5901b0f1fcdae1059dc6b9 100644 (file)
--- 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 5944a483b93d55d31abed88c47fec37b2f1e3df7..6f099a8b0e5d619d7235a51e0fbc7989ec927042 100644 (file)
--- 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 5cd777504b1e8a90d569bf79b9f868f3da30281d..88ff7b4119baa3a15eb93a36a09f2edfc74c7c07 100644 (file)
--- 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 05470d7998e49f7c2469e91ea776453286cc92a6..5c852ac0fb1dd815da3858ef9a63a3ea61114c58 100644 (file)
--- 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 aa80ebcd578de6c861f7d31140888ac6eb491935..dd253798034266140934ceeaa933a73560bf5662 100644 (file)
--- 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 99e09c447d989060c426ac0ed88c626829cd24c2..a1ed9934db8c761c98cbf49821fea96cf1ef0002 100644 (file)
--- 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.