10-fyi-state-t.patch

[Akim Demaille]

A careful at this patch shows that the structure is overkill: one can
access to the symbol's accessing_symbol easily.  But I realized too
late, and will simplify later.

My opinion is that there is a lot of redundant information, and it
must be for speed.  But we are more concerned with readability than
with opaque optimizations.


Index: ChangeLog
from  Akim Demaille  <address@hidden>

        * src/lalr.h (state_t): New.
        (state_table): Be a state_t * instead of a core **.
        (accessing_symbol): Remove, part of state_t.
        * src/lalr.c: Adjust.
        (set_accessing_symbol): Merge into...
        (set_state_table): this.
        * src/print_graph.c, src/conflicts.c: Adjust.

Index: src/print_graph.c
--- src/print_graph.c Fri, 28 Sep 2001 09:33:42 +0200 akim
+++ src/print_graph.c Thu, 15 Nov 2001 22:36:26 +0100 akim
@@ -57,7 +57,7 @@
   short *sp;
   short *sp1;

-  statep = state_table[state];
+  statep = state_table[state].state;
   k = statep->nitems;

   if (k == 0)
@@ -88,7 +88,7 @@
     }
 }

-/* Output in graph_obstack edges specifications in incidence with current
+/* Output in graph_obstack edges specifications in incidence with current
    node.  */
 static void
 print_actions (int state, const char *node_name, struct obstack *node_obstack)
@@ -126,7 +126,7 @@
          if (!shiftp->shifts[i])
            continue;
          state1 = shiftp->shifts[i];
-         symbol = accessing_symbol[state1];
+         symbol = state_table[state1].accessing_symbol;

          if (ISVAR (symbol))
            break;
@@ -195,7 +195,7 @@
          if (!shiftp->shifts[i])
            continue;
          state1 = shiftp->shifts[i];
-         symbol = accessing_symbol[state1];
+         symbol = state_table[state1].accessing_symbol;

          new_edge (&edge);
          open_edge (&edge, fgraph);
@@ -210,7 +210,7 @@
     }
 }

-/* Output in GRAPH_OBSTACK the current node specifications and edges
+/* Output in GRAPH_OBSTACK the current node specifications and edges
    which go out from that node.  */
 static void
 print_state (int state)
@@ -223,28 +223,28 @@
   new_node (&node);    /* Set node attributs default value.  */
   sprintf (name, "%d", state);
   node.title = name;   /* Give a name to the node.  */
-
-  {
-    /* Here we begin to compute the node label. */
+
+  {
+    /* Here we begin to compute the node label. */
     obstack_sgrow (&node_obstack, "\t\tlabel:\t\"");   /* Open Label  */
-
-    /* Keep the size of NODE_OBSTACK before computing the label. It is
+
+    /* Keep the size of NODE_OBSTACK before computing the label. It is
        useful to format the label.  */
     node_output_size = obstack_object_size (&node_obstack);
-
+
     /* Compute the labels of nodes on the fly.  */
     print_core (state, &node_obstack);
     /* Compute edges and additionnal parts of node label.  */
     print_actions (state, node.title, &node_obstack);
-
+
     obstack_sgrow (&node_obstack, "\"\n");             /* Close Label.  */
-  }
+  }

   open_node (fgraph);
   /* Output a VCG formatted attributs list.  */
   output_node (&node, fgraph);
   /* Save the node label.  */
-  fwrite (obstack_base (&node_obstack),
+  fwrite (obstack_base (&node_obstack),
          obstack_object_size (&node_obstack), 1, fgraph);
   close_node (fgraph);

@@ -256,7 +256,7 @@
 print_graph (void)
 {
   int i;
-
+
   if (!graph_flag)
     return;

@@ -267,7 +267,7 @@

 #if 0
   graph.smanhattan_edges = yes;
-  graph.manhattan_edges = yes;
+  graph.manhattan_edges = yes;
 #endif

   graph.display_edge_labels = yes;
Index: src/conflicts.c
--- src/conflicts.c Thu, 15 Nov 2001 08:56:59 +0100 akim
+++ src/conflicts.c Thu, 15 Nov 2001 22:34:52 +0100 akim
@@ -68,7 +68,7 @@
       for (i = 0; i < k; i++)
        {
          if (shiftp->shifts[i]
-             && token == accessing_symbol[shiftp->shifts[i]])
+             && token == state_table[shiftp->shifts[i]].accessing_symbol)
            (shiftp->shifts[i]) = 0;
        }
     }
@@ -203,7 +203,7 @@
       k = shiftp->nshifts;
       for (i = 0; i < k; i++)
        {
-         symbol = accessing_symbol[shiftp->shifts[i]];
+         symbol = state_table[shiftp->shifts[i]].accessing_symbol;
          if (ISVAR (symbol))
            break;
          SETBIT (lookaheadset, symbol);
@@ -303,7 +303,7 @@
     {
       if (!shiftp->shifts[i])
        continue;
-      symbol = accessing_symbol[shiftp->shifts[i]];
+      symbol = state_table[shiftp->shifts[i]].accessing_symbol;
       if (ISVAR (symbol))
        break;
       SETBIT (shiftset, symbol);
@@ -541,7 +541,7 @@
        {
          if (!shiftp->shifts[i])
            continue;
-         symbol = accessing_symbol[shiftp->shifts[i]];
+         symbol = state_table[shiftp->shifts[i]].accessing_symbol;
          if (ISVAR (symbol))
            break;
          /* if this state has a shift for the error token,
@@ -656,7 +656,7 @@
            {
              if (!shiftp->shifts[i])
                continue;
-             symbol = accessing_symbol[shiftp->shifts[i]];
+             symbol = state_table[shiftp->shifts[i]].accessing_symbol;
              if (ISVAR (symbol))
                break;
              SETBIT (shiftset, symbol);
Index: src/lalr.c
--- src/lalr.c Fri, 28 Sep 2001 09:33:42 +0200 akim
+++ src/lalr.c Thu, 15 Nov 2001 22:30:17 +0100 akim
@@ -32,13 +32,17 @@
 #include "nullable.h"
 #include "derives.h"

+/* All the decorated states, indexed by the state number.  Warning:
+   there is a state_TABLE in LR0.c, but it is different and static.
+   */
+state_t *state_table = NULL;
+
 int tokensetsize;
 short *lookaheads;
 short *LAruleno;
 unsigned *LA;
-short *accessing_symbol;
+
 char *consistent;
-core **state_table;
 shifts **shift_table;
 reductions **reduction_table;
 short *goto_map;
@@ -146,22 +150,13 @@
 {
   core *sp;

-  state_table = XCALLOC (core *, nstates);
-
-  for (sp = first_state; sp; sp = sp->next)
-    state_table[sp->number] = sp;
-}
-
-
-static void
-set_accessing_symbol (void)
-{
-  core *sp;
-
-  accessing_symbol = XCALLOC (short, nstates);
+  state_table = XCALLOC (state_t, nstates);

   for (sp = first_state; sp; sp = sp->next)
-    accessing_symbol[sp->number] = sp->accessing_symbol;
+    {
+      state_table[sp->number].state = sp;
+      state_table[sp->number].accessing_symbol = sp->accessing_symbol;
+    }
 }


@@ -238,21 +233,21 @@

       rp = reduction_table[i];
       sp = shift_table[i];
-      if (rp && (rp->nreds > 1
-                || (sp && !ISVAR (accessing_symbol[sp->shifts[0]]))))
+      if (rp
+         && (rp->nreds > 1
+             || (sp && !ISVAR (state_table[sp->shifts[0]].accessing_symbol))))
        count += rp->nreds;
       else
        consistent[i] = 1;

       if (sp)
        for (k = 0; k < sp->nshifts; k++)
-         {
-           if (accessing_symbol[sp->shifts[k]] == error_token_number)
-             {
-               consistent[i] = 0;
-               break;
-             }
-         }
+         if (state_table[sp->shifts[k]].accessing_symbol
+             == error_token_number)
+           {
+             consistent[i] = 0;
+             break;
+           }
     }

   lookaheads[nstates] = count;
@@ -302,7 +297,7 @@
     {
       for (i = sp->nshifts - 1; i >= 0; i--)
        {
-         symbol = accessing_symbol[sp->shifts[i]];
+         symbol = state_table[sp->shifts[i]].accessing_symbol;

          if (ISTOKEN (symbol))
            break;
@@ -337,7 +332,7 @@
       for (i = sp->nshifts - 1; i >= 0; i--)
        {
          state2 = sp->shifts[i];
-         symbol = accessing_symbol[state2];
+         symbol = state_table[state2].accessing_symbol;

          if (ISTOKEN (symbol))
            break;
@@ -421,7 +416,7 @@

          for (j = 0; j < k; j++)
            {
-             symbol = accessing_symbol[sp->shifts[j]];
+             symbol = state_table[sp->shifts[j]].accessing_symbol;
              if (ISVAR (symbol))
                break;
              SETBIT (rowp, symbol);
@@ -429,7 +424,7 @@

          for (; j < k; j++)
            {
-             symbol = accessing_symbol[sp->shifts[j]];
+             symbol = state_table[sp->shifts[j]].accessing_symbol;
              if (nullable[symbol])
                edge[nedges++] = map_goto (stateno, symbol);
            }
@@ -574,7 +569,7 @@
     {
       nedges = 0;
       state1 = from_state[i];
-      symbol1 = accessing_symbol[to_state[i]];
+      symbol1 = state_table[to_state[i]].accessing_symbol;

       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
        {
@@ -591,7 +586,7 @@
              for (j = 0; j < k; j++)
                {
                  stateno = sp->shifts[j];
-                 if (accessing_symbol[stateno] == symbol2)
+                 if (state_table[stateno].accessing_symbol == symbol2)
                    break;
                }

@@ -709,7 +704,6 @@
   tokensetsize = WORDSIZE (ntokens);

   set_state_table ();
-  set_accessing_symbol ();
   set_shift_table ();
   set_reduction_table ();
   set_maxrhs ();
Index: src/lalr.h
--- src/lalr.h Sat, 11 Nov 2000 16:04:34 +0100 akim
+++ src/lalr.h Thu, 15 Nov 2001 22:28:19 +0100 akim
@@ -74,10 +74,23 @@
 extern unsigned *LA;


+/* A structure decorating a state, with additional information. */
+typedef struct state_s
+{
+  /* A state.  */
+  core *state;
+
+  /* Its accessing symbol. */
+  short accessing_symbol;
+} state_t;
+
+/* All the decorated states, indexed by the state number.  Warning:
+   there is a state_TABLE in LR0.c, but it is different and static.
+   */
+extern state_t *state_table;
+
 extern int tokensetsize;
 extern short *lookaheads;
-extern short *accessing_symbol;
-extern core **state_table;
 extern shifts **shift_table;
 extern reductions **reduction_table;

Index: src/output.c
--- src/output.c Thu, 11 Oct 2001 19:02:23 +0200 akim
+++ src/output.c Thu, 15 Nov 2001 22:42:48 +0100 akim
@@ -347,7 +347,13 @@
 static void
 output_stos (void)
 {
-  output_short_table (&table_obstack, NULL, "yystos", accessing_symbol,
+  int i;
+  short *values = (short *) alloca (sizeof (short) * nstates);
+  for (i = 0; i < nstates; ++i)
+    values[i] = state_table[i].accessing_symbol;
+  output_short_table (&table_obstack,
+                     "YYSTOS[STATE] -- Accessing symbol to the STATE",
+                     "yystos", values,
                      0, 1, nstates);
 }

@@ -579,7 +585,7 @@
          if (!shift_state)
            continue;

-         symbol = accessing_symbol[shift_state];
+         symbol = state_table[shift_state].accessing_symbol;

          if (ISVAR (symbol))
            break;
@@ -1121,7 +1127,6 @@
   XFREE (lookaheads);
   XFREE (LA);
   XFREE (LAruleno);
-  XFREE (accessing_symbol);

   goto_actions ();
   XFREE (goto_map + ntokens);
@@ -1292,9 +1297,6 @@
 free_itemsets (void)
 {
   core *cp, *cptmp;
-
-  XFREE (state_table);
-
   for (cp = first_state; cp; cp = cptmp)
     {
       cptmp = cp->next;
@@ -1345,6 +1347,8 @@
     output_stos ();
   output_rule_data ();
   output_actions ();
+  XFREE (state_table);
+
   if (!no_parser_flag)
     output_parser ();
   output_program ();
Index: src/print.c
--- src/print.c Thu, 15 Nov 2001 08:56:59 +0100 akim
+++ src/print.c Thu, 15 Nov 2001 22:36:06 +0100 akim
@@ -54,7 +54,7 @@
   short *sp;
   short *sp1;

-  statep = state_table[state];
+  statep = state_table[state].state;
   k = statep->nitems;

   if (k == 0)
@@ -124,7 +124,7 @@
          if (!shiftp->shifts[i])
            continue;
          state1 = shiftp->shifts[i];
-         symbol = accessing_symbol[state1];
+         symbol = state_table[state1].accessing_symbol;
          /* The following line used to be turned off.  */
          if (ISVAR (symbol))
            break;
@@ -184,7 +184,7 @@
          if (!shiftp->shifts[i])
            continue;
          state1 = shiftp->shifts[i];
-         symbol = accessing_symbol[state1];
+         symbol = state_table[state1].accessing_symbol;
          fprintf (out, _("    %-4s\tgo to state %d\n"),
                   tags[symbol], state1);
        }