From: Akim Demaille Date: Sun, 30 Jun 2002 17:31:51 +0000 (+0000) Subject: * src/lalr.c (traverse, digraph, matrix_print, transpose): Move X-Git-Tag: BISON-1_49b~107 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/0e4d575330619dff7baab4fff77789773c7903b9 * src/lalr.c (traverse, digraph, matrix_print, transpose): Move to... * src/relation.h, src/relation.c (traverse, relation_digraph) (relation_print, relation_transpose): New. --- diff --git a/ChangeLog b/ChangeLog index 32efdc1b..d45579e3 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2002-06-30 Akim Demaille + + * src/lalr.c (traverse, digraph, matrix_print, transpose): Move + to... + * src/relation.h, src/relation.c (traverse, relation_digraph) + (relation_print, relation_transpose): New. + + 2002-06-30 Akim Demaille * src/state.h, src/state.c (shifts_to): New. diff --git a/src/Makefile.am b/src/Makefile.am index fabfdf0a..7b67e8e3 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -55,6 +55,7 @@ bison_SOURCES = \ print_graph.c print_graph.h \ reader.c reader.h \ reduce.c reduce.h \ + relation.c relation.h \ scan-gram.l \ scan-skel.l \ state.c state.h \ diff --git a/src/lalr.c b/src/lalr.c index c3a55cc4..251878a0 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -27,6 +27,7 @@ #include "system.h" #include "bitset.h" #include "bitsetv.h" +#include "relation.h" #include "quotearg.h" #include "symtab.h" #include "gram.h" @@ -56,76 +57,6 @@ static short **includes; static shorts **lookback; -/*---------------------------------------------------------------. -| digraph & traverse. | -| | -| The following variables are used as common storage between the | -| two. | -`---------------------------------------------------------------*/ - -static short **R; -static short *INDEX; -static short *VERTICES; -static int top; -static int infinity; - -static void -traverse (int i) -{ - int j; - int height; - - VERTICES[++top] = i; - INDEX[i] = height = top; - - if (R[i]) - for (j = 0; R[i][j] >= 0; ++j) - { - if (INDEX[R[i][j]] == 0) - traverse (R[i][j]); - - if (INDEX[i] > INDEX[R[i][j]]) - INDEX[i] = INDEX[R[i][j]]; - - bitset_or (F[i], F[i], F[R[i][j]]); - } - - if (INDEX[i] == height) - for (;;) - { - j = VERTICES[top--]; - INDEX[j] = infinity; - - if (i == j) - break; - - bitset_copy (F[j], F[i]); - } -} - - -static void -digraph (short **relation) -{ - int i; - - infinity = ngotos + 2; - INDEX = XCALLOC (short, ngotos + 1); - VERTICES = XCALLOC (short, ngotos + 1); - top = 0; - - R = relation; - - for (i = 0; i < ngotos; i++) - INDEX[i] = 0; - - for (i = 0; i < ngotos; i++) - if (INDEX[i] == 0 && R[i]) - traverse (i); - - XFREE (INDEX); - XFREE (VERTICES); -} static void @@ -280,7 +211,7 @@ initialize_F (void) } } - digraph (reads); + relation_digraph (reads, ngotos, &F); for (i = 0; i < ngotos; i++) XFREE (reads[i]); @@ -309,91 +240,6 @@ add_lookback_edge (state_t *state, rule_number_t ruleno, int gotono) } -static void -matrix_print (FILE *out, short **matrix, int n) -{ - int i, j; - - for (i = 0; i < n; ++i) - { - fprintf (out, "%3d: ", i); - if (matrix[i]) - for (j = 0; matrix[i][j] != -1; ++j) - fprintf (out, "%3d ", matrix[i][j]); - fputc ('\n', out); - } - fputc ('\n', out); -} - -/*-------------------------------------------------------------------. -| Return the transpose of R_ARG, of size N. Destroy R_ARG, as it is | -| replaced with the result. | -| | -| R_ARG[I] is NULL or a -1 terminated list of numbers. | -| | -| RESULT[NUM] is NULL or the -1 terminated list of the I such as NUM | -| is in R_ARG[I]. | -`-------------------------------------------------------------------*/ - -static short ** -transpose (short **R_arg, int n) -{ - /* The result. */ - short **new_R = XCALLOC (short *, n); - /* END_R[I] -- next entry of NEW_R[I]. */ - short **end_R = XCALLOC (short *, n); - /* NEDGES[I] -- total size of NEW_R[I]. */ - short *nedges = XCALLOC (short, n); - int i, j; - - if (trace_flag) - { - fputs ("transpose: input\n", stderr); - matrix_print (stderr, R_arg, n); - } - - /* Count. */ - for (i = 0; i < n; i++) - if (R_arg[i]) - for (j = 0; R_arg[i][j] >= 0; ++j) - ++nedges[R_arg[i][j]]; - - /* Allocate. */ - for (i = 0; i < n; i++) - if (nedges[i] > 0) - { - short *sp = XCALLOC (short, nedges[i] + 1); - sp[nedges[i]] = -1; - new_R[i] = sp; - end_R[i] = sp; - } - - /* Store. */ - for (i = 0; i < n; i++) - if (R_arg[i]) - for (j = 0; R_arg[i][j] >= 0; ++j) - { - *end_R[R_arg[i][j]] = i; - ++end_R[R_arg[i][j]]; - } - - free (nedges); - free (end_R); - - /* Free the input: it is replaced with the result. */ - for (i = 0; i < n; i++) - XFREE (R_arg[i]); - free (R_arg); - - if (trace_flag) - { - fputs ("transpose: output\n", stderr); - matrix_print (stderr, new_R, n); - } - - return new_R; -} - static void build_relations (void) @@ -459,7 +305,7 @@ build_relations (void) XFREE (edge); XFREE (states1); - includes = transpose (includes, ngotos); + relation_transpose (&includes, ngotos); } @@ -469,7 +315,7 @@ compute_FOLLOWS (void) { int i; - digraph (includes); + relation_digraph (includes, ngotos, &F); for (i = 0; i < ngotos; i++) XFREE (includes[i]); diff --git a/src/relation.c b/src/relation.c new file mode 100644 index 00000000..fc48c28f --- /dev/null +++ b/src/relation.c @@ -0,0 +1,181 @@ +/* Binary relations. + Copyright (C) 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 "bitsetv.h" +#include "relation.h" +#include "getargs.h" + +void +relation_print (relation_t relation, size_t size, FILE *out) +{ + unsigned i, j; + + for (i = 0; i < size; ++i) + { + fprintf (out, "%3d: ", i); + if (relation[i]) + for (j = 0; relation[i][j] != -1; ++j) + fprintf (out, "%3d ", relation[i][j]); + fputc ('\n', out); + } + fputc ('\n', out); +} + + +/*---------------------------------------------------------------. +| digraph & traverse. | +| | +| The following variables are used as common storage between the | +| two. | +`---------------------------------------------------------------*/ + +static relation_t R; +static relation_nodes_t INDEX; +static relation_nodes_t VERTICES; +static int top; +static int infinity; +static bitsetv F; + +static void +traverse (int i) +{ + int j; + int height; + + VERTICES[++top] = i; + INDEX[i] = height = top; + + if (R[i]) + for (j = 0; R[i][j] >= 0; ++j) + { + if (INDEX[R[i][j]] == 0) + traverse (R[i][j]); + + if (INDEX[i] > INDEX[R[i][j]]) + INDEX[i] = INDEX[R[i][j]]; + + bitset_or (F[i], F[i], F[R[i][j]]); + } + + if (INDEX[i] == height) + for (;;) + { + j = VERTICES[top--]; + INDEX[j] = infinity; + + if (i == j) + break; + + bitset_copy (F[j], F[i]); + } +} + + +void +relation_digraph (relation_t relation, size_t size, + bitsetv *function) +{ + unsigned i; + + infinity = size + 2; + INDEX = XCALLOC (relation_node_t, size + 1); + VERTICES = XCALLOC (relation_node_t, size + 1); + top = 0; + + R = relation; + F = *function; + + for (i = 0; i < size; i++) + INDEX[i] = 0; + + for (i = 0; i < size; i++) + if (INDEX[i] == 0 && R[i]) + traverse (i); + + XFREE (INDEX); + XFREE (VERTICES); + + *function = F; +} + + +/*-------------------------------------------. +| Destructively transpose R_ARG, of size N. | +`-------------------------------------------*/ + +void +relation_transpose (relation_t *R_arg, int n) +{ + /* The result. */ + relation_t new_R = XCALLOC (relation_nodes_t, n); + /* END_R[I] -- next entry of NEW_R[I]. */ + relation_t end_R = XCALLOC (relation_nodes_t, n); + /* NEDGES[I] -- total size of NEW_R[I]. */ + int *nedges = XCALLOC (int, n); + int i, j; + + if (trace_flag) + { + fputs ("relation_transpose: input\n", stderr); + relation_print (*R_arg, n, stderr); + } + + /* Count. */ + for (i = 0; i < n; i++) + if ((*R_arg)[i]) + for (j = 0; (*R_arg)[i][j] >= 0; ++j) + ++nedges[(*R_arg)[i][j]]; + + /* Allocate. */ + for (i = 0; i < n; i++) + if (nedges[i] > 0) + { + relation_node_t *sp = XCALLOC (relation_node_t, nedges[i] + 1); + sp[nedges[i]] = -1; + new_R[i] = sp; + end_R[i] = sp; + } + + /* Store. */ + for (i = 0; i < n; i++) + if ((*R_arg)[i]) + for (j = 0; (*R_arg)[i][j] >= 0; ++j) + { + *end_R[(*R_arg)[i][j]] = i; + ++end_R[(*R_arg)[i][j]]; + } + + free (nedges); + free (end_R); + + /* Free the input: it is replaced with the result. */ + for (i = 0; i < n; i++) + XFREE ((*R_arg)[i]); + free (*R_arg); + + if (trace_flag) + { + fputs ("relation_transpose: output\n", stderr); + relation_print (new_R, n, stderr); + } + + *R_arg = new_R; +} diff --git a/src/relation.h b/src/relation.h new file mode 100644 index 00000000..8a82b854 --- /dev/null +++ b/src/relation.h @@ -0,0 +1,50 @@ +/* Binary relations. + Copyright (C) 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 RELATION_H_ +# define RELATION_H_ + +/* Performing operations on graphs coded as list of adjacency. + + If GRAPH is a relation_t, then GRAPH[Node] is a list of adjacent + nodes, ended with -1. */ + +typedef short relation_node_t; +typedef relation_node_t *relation_nodes_t; +typedef relation_nodes_t *relation_t; + + +/* Report a RELATION that has SIZE vertices. */ +void relation_print PARAMS ((relation_t relation, size_t size, + FILE *out)); + +/* Compute the transitive closure of the FUNCTION on the RELATION with + SIZE vertices. + + If RELATION (NODE-1, NODE-2) then on exit FUNCTION[NODE-1] was + extended (unioned) with FUNCTION[NODE-2]. */ +void relation_digraph PARAMS ((relation_t relation, size_t size, + bitsetv *function)); + +/* Destructively transpose *R_ARG, of size N. */ +void relation_transpose PARAMS ((relation_t *R_arg, int n)); + +#endif /* ! RELATION_H_ */