From fca9c5eff1505d944e1ad142df057b11d51dad9a Mon Sep 17 00:00:00 2001 From: "Joel E. Denny" 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. (cherry picked from commit 1c4ad777cb220ea669dc934c9b600a25a824a658) --- 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 7ad82da0..5120acaa 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,20 @@ +2010-01-04 Joel E. Denny + + 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 maint: run "make update-copyright" diff --git a/src/LR0.c b/src/LR0.c index fc582a6e..31eab0da 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-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 44188713..2f4aff12 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 2dc5defb..668b67e9 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 5944a483..6f099a8b 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -19,8 +19,7 @@ along with this program. If not, see . */ -/* 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 diff --git a/src/lalr.h b/src/lalr.h index 5cd77750..88ff7b41 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 05470d79..5c852ac0 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 aa80ebcd..dd253798 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 99e09c44..a1ed9934 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. -- 2.45.2