From 65ccf9fc1dbcef40e0cae7c58ec6aabd6f4b6918 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Mon, 4 Mar 2002 14:29:27 +0000 Subject: [PATCH 1/1] * src/warshall.h, src/warshall.c (bitmatrix_print): Move to... * src/closure.c: here. (set_firsts): Use bitsetv_reflexive_transitive_closure instead of RTC. * src/warshall.h, src/warshall.c: Remove. * tests/sets.at (Broken Closure): Adjust. --- ChangeLog | 9 ++++ src/Makefile.am | 4 +- src/closure.c | 55 ++++++++++++++++++++++- src/warshall.c | 114 ------------------------------------------------ src/warshall.h | 25 ----------- tests/sets.at | 24 +++++----- 6 files changed, 76 insertions(+), 155 deletions(-) delete mode 100644 src/warshall.c delete mode 100644 src/warshall.h diff --git a/ChangeLog b/ChangeLog index 256d1f8f..8b1988d4 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2002-03-04 Akim Demaille + + * src/warshall.h, src/warshall.c (bitmatrix_print): Move to... + * src/closure.c: here. + (set_firsts): Use bitsetv_reflexive_transitive_closure instead of + RTC. + * src/warshall.h, src/warshall.c: Remove. + * tests/sets.at (Broken Closure): Adjust. + 2002-03-04 Akim Demaille * src/output.c (output_skeleton): tempdir is const. diff --git a/src/Makefile.am b/src/Makefile.am index 03b3b53b..bc591744 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -43,7 +43,7 @@ bison_SOURCES = LR0.c closure.c complain.c conflicts.c \ print_graph.h print_graph.c \ muscle_tab.h muscle_tab.c \ options.h options.c \ - print.c reader.c reduce.c symtab.c warshall.c vcg.c \ + print.c reader.c reduce.c symtab.c vcg.c \ scan-skel.l BUILT_SOURCES = scan-skel.c @@ -53,7 +53,7 @@ EXTRA_bison_SOURCES = vmsgetargs.c noinst_HEADERS = LR0.h closure.h complain.h conflicts.h \ derives.h \ files.h getargs.h gram.h lalr.h lex.h nullable.h \ - print.h reader.h reduce.h symtab.h warshall.h system.h \ + print.h reader.h reduce.h symtab.h system.h \ types.h vcg.h vcg_defaults.h EXTRA_DIST = build.com bison.cld vmshlp.mar diff --git a/src/closure.c b/src/closure.c index d45210e6..06c50364 100644 --- a/src/closure.c +++ b/src/closure.c @@ -27,7 +27,6 @@ #include "reader.h" #include "closure.h" #include "derives.h" -#include "warshall.h" /* NITEMSET is the size of the array ITEMSET. */ short *itemset; @@ -104,6 +103,54 @@ print_fderives (void) } fprintf (stderr, "\n\n"); } + +/*--------------------------------------------------------. +| Display the MATRIX array of SIZE bitsets of size SIZE. | +`--------------------------------------------------------*/ + +static void +bitmatrix_print (const char *title, bitsetv matrix) +{ + size_t i, j; + size_t size = bitset_size (matrix[0]); + + /* Title. */ + fprintf (stderr, "%s BEGIN\n", title); + + /* Column numbers. */ + fputs (" ", stderr); + for (i = 0; i < size; ++i) + putc (i / 10 ? '0' + i / 10 : ' ', stderr); + putc ('\n', stderr); + fputs (" ", stderr); + for (i = 0; i < size; ++i) + fprintf (stderr, "%d", i % 10); + putc ('\n', stderr); + + /* Bar. */ + fputs (" .", stderr); + for (i = 0; i < size; ++i) + putc ('-', stderr); + fputs (".\n", stderr); + + /* Contents. */ + for (i = 0; i < size; ++i) + { + fprintf (stderr, "%2d|", i); + for (j = 0; j < size; ++j) + fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr); + fputs ("|\n", stderr); + } + + /* Bar. */ + fputs (" `", stderr); + for (i = 0; i < size; ++i) + putc ('-', stderr); + fputs ("'\n", stderr); + + /* End title. */ + fprintf (stderr, "%s END\n\n", title); +} /*------------------------------------------------------------------. | Set FIRSTS to be an NVARS array of NVARS bitsets indicating which | @@ -131,7 +178,11 @@ set_firsts (void) bitset_set (FIRSTS (i), symbol - ntokens); } - RTC (firsts); + if (trace_flag) + bitmatrix_print ("RTC: Input", firsts); + bitsetv_reflexive_transitive_closure (firsts); + if (trace_flag) + bitmatrix_print ("RTC: Output", firsts); if (trace_flag) print_firsts (); diff --git a/src/warshall.c b/src/warshall.c deleted file mode 100644 index a7ef4cb6..00000000 --- a/src/warshall.c +++ /dev/null @@ -1,114 +0,0 @@ -/* Generate transitive closure of a matrix, - Copyright 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc. - - This file is part of Bison, the GNU Compiler Compiler. - - Bison is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. - - Bison is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with Bison; see the file COPYING. If not, write to - the Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. */ - - -#include "system.h" -#include "getargs.h" -#include "bitsetv.h" -#include "warshall.h" - -/*--------------------------------------------------------. -| Display the MATRIX array of SIZE bitsets of size SIZE. | -`--------------------------------------------------------*/ - -static void -bitmatrix_print (const char *title, bitsetv matrix) -{ - size_t i, j; - size_t size = bitset_size (matrix[0]); - - /* Title. */ - fprintf (stderr, "%s BEGIN\n", title); - - /* Column numbers. */ - fputs (" ", stderr); - for (i = 0; i < size; ++i) - putc (i / 10 ? '0' + i / 10 : ' ', stderr); - putc ('\n', stderr); - fputs (" ", stderr); - for (i = 0; i < size; ++i) - fprintf (stderr, "%d", i % 10); - putc ('\n', stderr); - - /* Bar. */ - fputs (" .", stderr); - for (i = 0; i < size; ++i) - putc ('-', stderr); - fputs (".\n", stderr); - - /* Contents. */ - for (i = 0; i < size; ++i) - { - fprintf (stderr, "%2d|", i); - for (j = 0; j < size; ++j) - fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr); - fputs ("|\n", stderr); - } - - /* Bar. */ - fputs (" `", stderr); - for (i = 0; i < size; ++i) - putc ('-', stderr); - fputs ("'\n", stderr); - - /* End title. */ - fprintf (stderr, "%s END\n\n", title); -} - -/*-------------------------------------------------------------------. -| Given the MATRIX array of N bitsets of size N, modify its contents | -| to be the transive closure of what was given. | -`-------------------------------------------------------------------*/ - -static void -TC (bitsetv matrix) -{ - int i, j; - - if (trace_flag) - bitmatrix_print ("TC: Input", matrix); - - /* R (J, I) && R (I, K) => R (J, K). - I *must* be the outter loop. */ - - for (i = 0; matrix[i]; ++i) - for (j = 0; matrix[j]; ++j) - if (bitset_test (matrix[j], i)) - bitset_or (matrix[j], matrix[j], matrix[i]); - - if (trace_flag) - bitmatrix_print ("TC: Output", matrix); -} - - -/*---------------------------------------------------------------. -| Reflexive Transitive Closure. Same as TC and then set all the | -| bits on the diagonal of MATRIX. | -`---------------------------------------------------------------*/ - -void -RTC (bitsetv matrix) -{ - int i; - - TC (matrix); - for (i = 0; matrix[i]; ++i) - bitset_set (matrix[i], i); -} diff --git a/src/warshall.h b/src/warshall.h deleted file mode 100644 index d97fdd8e..00000000 --- a/src/warshall.h +++ /dev/null @@ -1,25 +0,0 @@ -/* Generate transitive closure of a matrix, - Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc. - - This file is part of Bison, the GNU Compiler Compiler. - - Bison is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. - - Bison is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with Bison; see the file COPYING. If not, write to - the Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. */ - -#ifndef WARSHALL_H_ -# define WARSHALL_H_ - -void RTC PARAMS ((bitsetv)); -#endif /* !WARSHALL_H_ */ diff --git a/tests/sets.at b/tests/sets.at index 2c447cd2..7203dca1 100644 --- a/tests/sets.at +++ b/tests/sets.at @@ -163,22 +163,22 @@ h: 'h'; AT_CHECK([[bison --trace input.y]], [], [], [stderr]) -AT_CHECK([[sed -n 's/[ ]*$//;/^TC: Output BEGIN/,/^TC: Output END/p' stderr]], [], -[[TC: Output BEGIN +AT_CHECK([[sed -n 's/[ ]*$//;/^RTC: Output BEGIN/,/^RTC: Output END/p' stderr]], [], +[[RTC: Output BEGIN 012345678 .---------. - 0| 11111111| - 1| 1111111| - 2| 111111| - 3| 11111| - 4| 1111| - 5| 111| - 6| 11| - 7| 1| - 8| | + 0|111111111| + 1| 11111111| + 2| 1111111| + 3| 111111| + 4| 11111| + 5| 1111| + 6| 111| + 7| 11| + 8| 1| `---------' -TC: Output END +RTC: Output END ]]) AT_CLEANUP -- 2.45.2