Instead of attaching lookaheads and duplicating the rules being

reduced by a state, attach the lookaheads to the reductions.
* src/state.h (state_t): Remove the `lookaheads',
`lookaheads_rule' member.
(reductions_t): Add a `lookaheads' member.
Use a regular array for the `rules'.
* src/state.c (reductions_new): Initialize the lookaheads member
to 0.
(state_rule_lookaheads_print): Adjust.
* src/state.h, src/state.c (state_reductions_find): New.
* src/conflicts.c (resolve_sr_conflict, set_conflicts)
(count_rr_conflicts): Adjust.
* src/lalr.c (LArule): Remove.
(add_lookback_edge): Adjust.
(state_lookaheads_count): New.
(states_lookaheads_initialize): Merge into...
(initialize_LA): this.
(lalr_free): Adjust.
* src/main.c (main): Don't free nullable and derives too early: it
is used by --verbose.
* src/print.c, src/print_graph.c, src/tables.c: Adjust.

diff --git a/ChangeLog b/ChangeLog
index da461eea654bbbf5e08b971699b52dc549cd04b6..b50e350301802473727e822a714ce42f7b931137 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,28 @@
+2002-08-01  Akim Demaille  <akim@epita.fr>
+
+       Instead of attaching lookaheads and duplicating the rules being
+       reduced by a state, attach the lookaheads to the reductions.
+
+       * src/state.h (state_t): Remove the `lookaheads',
+       `lookaheads_rule' member.
+       (reductions_t): Add a `lookaheads' member.
+       Use a regular array for the `rules'.
+       * src/state.c (reductions_new): Initialize the lookaheads member
+       to 0.
+       (state_rule_lookaheads_print): Adjust.
+       * src/state.h, src/state.c (state_reductions_find): New.
+       * src/conflicts.c (resolve_sr_conflict, set_conflicts)
+       (count_rr_conflicts): Adjust.
+       * src/lalr.c (LArule): Remove.
+       (add_lookback_edge): Adjust.
+       (state_lookaheads_count): New.
+       (states_lookaheads_initialize): Merge into...
+       (initialize_LA): this.
+       (lalr_free): Adjust.
+       * src/main.c (main): Don't free nullable and derives too early: it
+       is used by --verbose.
+       * src/print.c, src/print_graph.c, src/tables.c: Adjust.
+

 2002-08-01  Akim Demaille  <akim@epita.fr>
 
        * src/derives.h, src/derives.c (derives): A `rule_t***' instead of
 2002-08-01  Akim Demaille  <akim@epita.fr>
 
        * src/derives.h, src/derives.c (derives): A `rule_t***' instead of

diff --git a/src/conflicts.c b/src/conflicts.c
index cbf385ac3049d18786c377baded8a93aa5fff83b..1c24d7e23ebee0234754487f4fa1f386d76c165f 100644 (file)
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -175,14 +175,15 @@ flush_reduce (bitset lookaheads, int token)
 `------------------------------------------------------------------*/
 
 static void
 `------------------------------------------------------------------*/
 
 static void

-resolve_sr_conflict (state_t *state, int lookahead,
+resolve_sr_conflict (state_t *state, int ruleno,

                     symbol_t **errs)
 {
   symbol_number_t i;
                     symbol_t **errs)
 {
   symbol_number_t i;

+  reductions_t *reds = state->reductions;

   /* Find the rule to reduce by to get precedence of reduction.  */
   /* Find the rule to reduce by to get precedence of reduction.  */

-  rule_t *redrule = state->lookaheads_rule[lookahead];
+  rule_t *redrule = reds->rules[ruleno];

   int redprec = redrule->prec->prec;
   int redprec = redrule->prec->prec;

-  bitset lookaheads = state->lookaheads[lookahead];
+  bitset lookaheads = reds->lookaheads[ruleno];

   int nerrs = 0;
 
   for (i = 0; i < ntokens; i++)
   int nerrs = 0;
 
   for (i = 0; i < ntokens; i++)


@@ -259,6 +260,7 @@ set_conflicts (state_t *state, symbol_t **errs)
 {
   int i;
   transitions_t *transitions = state->transitions;
 {
   int i;
   transitions_t *transitions = state->transitions;

+  reductions_t *reds = state->reductions;

 
   if (state->consistent)
     return;
 
   if (state->consistent)
     return;


@@ -271,10 +273,9 @@ set_conflicts (state_t *state, symbol_t **errs)
   /* Loop over all rules which require lookahead in this state.  First
      check for shift-reduce conflict, and try to resolve using
      precedence.  */
   /* Loop over all rules which require lookahead in this state.  First
      check for shift-reduce conflict, and try to resolve using
      precedence.  */

-  for (i = 0; i < state->nlookaheads; ++i)
-    if (state->lookaheads_rule[i]->prec
-       && state->lookaheads_rule[i]->prec->prec
-       && !bitset_disjoint_p (state->lookaheads[i], lookaheadset))
+  for (i = 0; i < reds->num; ++i)
+    if (reds->rules[i]->prec && reds->rules[i]->prec->prec
+       && !bitset_disjoint_p (reds->lookaheads[i], lookaheadset))

       {
        resolve_sr_conflict (state, i, errs);
        break;
       {
        resolve_sr_conflict (state, i, errs);
        break;


@@ -282,12 +283,12 @@ set_conflicts (state_t *state, symbol_t **errs)
 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */
 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */

-  for (i = 0; i < state->nlookaheads; ++i)
+  for (i = 0; i < reds->num; ++i)

     {
     {

-      if (!bitset_disjoint_p (state->lookaheads[i], lookaheadset))
+      if (!bitset_disjoint_p (reds->lookaheads[i], lookaheadset))

        conflicts[state->number] = 1;
 
        conflicts[state->number] = 1;
 

-      bitset_or (lookaheadset, lookaheadset, state->lookaheads[i]);
+      bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);

     }
 }
 
     }
 }
 


@@ -333,6 +334,7 @@ count_sr_conflicts (state_t *state)
   int i;
   int src_count = 0;
   transitions_t *transitions = state->transitions;
   int i;
   int src_count = 0;
   transitions_t *transitions = state->transitions;

+  reductions_t *reds = state->reductions;

 
   if (!transitions)
     return 0;
 
   if (!transitions)
     return 0;


@@ -343,8 +345,8 @@ count_sr_conflicts (state_t *state)
   FOR_EACH_SHIFT (transitions, i)
     bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
 
   FOR_EACH_SHIFT (transitions, i)
     bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
 

-  for (i = 0; i < state->nlookaheads; ++i)
-    bitset_or (lookaheadset, lookaheadset, state->lookaheads[i]);
+  for (i = 0; i < reds->num; ++i)
+    bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);

 
   bitset_and (lookaheadset, lookaheadset, shiftset);
 
 
   bitset_and (lookaheadset, lookaheadset, shiftset);
 


@@ -365,17 +367,15 @@ static int
 count_rr_conflicts (state_t *state, int one_per_token)
 {
   int i;
 count_rr_conflicts (state_t *state, int one_per_token)
 {
   int i;

+  reductions_t *reds = state->reductions;

   int rrc_count = 0;
 
   int rrc_count = 0;
 

-  if (state->nlookaheads < 2)
-    return 0;
-

   for (i = 0; i < ntokens; i++)
     {
       int count = 0;
       int j;
   for (i = 0; i < ntokens; i++)
     {
       int count = 0;
       int j;

-      for (j = 0; j < state->nlookaheads; ++j)
-       if (bitset_test (state->lookaheads[j], i))
+      for (j = 0; j < reds->num; ++j)
+       if (bitset_test (reds->lookaheads[j], i))

          count++;
 
       if (count >= 2)
          count++;
 
       if (count >= 2)


@@ -456,9 +456,10 @@ conflicts_output (FILE *out)
   for (i = 0; i < nstates; i++)
     {
       state_t *s = states[i];
   for (i = 0; i < nstates; i++)
     {
       state_t *s = states[i];

+      reductions_t *reds = s->reductions;

       int j;
       int j;

-      for (j = 0; j < s->reductions->num; ++j)
-       used_rules[s->reductions->rules[j]->number] = TRUE;
+      for (j = 0; j < reds->num; ++j)
+       used_rules[reds->rules[j]->number] = TRUE;

       if (conflicts[i])
        {
          fprintf (out, _("State %d contains "), i);
       if (conflicts[i])
        {
          fprintf (out, _("State %d contains "), i);

diff --git a/src/lalr.c b/src/lalr.c
index 832f1fcf75b073a980cdaf6e096b1a763aa0f26f..2c0c942aeb216ab26c958efa11b616a5c0753de3 100644 (file)
--- a/src/lalr.c
+++ b/src/lalr.c
@@ -52,16 +52,6 @@ typedef struct goto_list_s
 } goto_list_t;
 
 
 } goto_list_t;
 
 

-/* LARULE is a vector which records the rules that need lookahead in
-   various states.  The elements of LARULE that apply to state S are
-   those from LOOKAHEADS[S] through LOOKAHEADS[S+1]-1.
-
-   If LR is the length of LArule, then a number from 0 to LR-1 can
-   specify both a rule and a state where the rule might be applied.
-   */
-
-static rule_t **LArule = NULL;
-

 /* LA is a LR by NTOKENS matrix of bits.  LA[l, i] is 1 if the rule
    LArule[l] is applicable in the appropriate state when the next
    token is symbol i.  If LA[l, i] and LA[l, j] are both 1 for i != j,
 /* LA is a LR by NTOKENS matrix of bits.  LA[l, i] is 1 if the rule
    LArule[l] is applicable in the appropriate state when the next
    token is symbol i.  If LA[l, i] and LA[l, j] are both 1 for i != j,


@@ -81,29 +71,6 @@ static goto_list_t **lookback;
 
 
 
 
 
 

-static void
-initialize_LA (void)
-{
-  state_number_t i;
-  int j;
-  rule_t **np;
-
-  /* Avoid having to special case 0.  */
-  if (!nLA)
-    nLA = 1;
-
-  LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
-  LArule = XCALLOC (rule_t *, nLA);
-  lookback = XCALLOC (goto_list_t *, nLA);
-
-  np = LArule;
-  for (i = 0; i < nstates; i++)
-    if (!states[i]->consistent)
-      for (j = 0; j < states[i]->reductions->num; j++)
-       *np++ = states[i]->reductions->rules[j];
-}
-
-

 static void
 set_goto_map (void)
 {
 static void
 set_goto_map (void)
 {


@@ -246,19 +213,11 @@ initialize_F (void)
 static void
 add_lookback_edge (state_t *state, rule_t *rule, int gotono)
 {
 static void
 add_lookback_edge (state_t *state, rule_t *rule, int gotono)
 {

-  int i;
-  goto_list_t *sp;
-
-  for (i = 0; i < state->nlookaheads; ++i)
-    if (state->lookaheads_rule[i] == rule)
-      break;
-
-  assert (state->lookaheads_rule[i] == rule);
-
-  sp = XCALLOC (goto_list_t, 1);
-  sp->next = lookback[(state->lookaheads - LA) + i];
+  int r = state_reduction_find (state, rule);
+  goto_list_t *sp = XCALLOC (goto_list_t, 1);
+  sp->next = lookback[(state->reductions->lookaheads - LA) + r];

   sp->value = gotono;
   sp->value = gotono;

-  lookback[(state->lookaheads - LA) + i] = sp;
+  lookback[(state->reductions->lookaheads - LA) + r] = sp;

 }
 
 
 }
 
 


@@ -365,68 +324,72 @@ compute_lookaheads (void)
 }
 
 
 }
 
 

-/*-------------------------------------------------------------.
-| Count the number of lookaheads required for each state       |
-| (NLOOKAHEADS member).  Compute the total number of LA, NLA.  |
-`-------------------------------------------------------------*/
+/*---------------------------------------------------------------.
+| Count the number of lookaheads required for STATE (NLOOKAHEADS |
+| member).                                                       |
+`---------------------------------------------------------------*/

 
 

-static void
-states_lookaheads_count (void)
+static int
+state_lookaheads_count (state_t *state)

 {
 {

-  state_number_t i;
-  nLA = 0;
-
-  /* Count   */
-  for (i = 0; i < nstates; i++)
-    {
-      int k;
-      int nlookaheads = 0;
-      reductions_t *rp = states[i]->reductions;
-      transitions_t *sp = states[i]->transitions;
-
-      /* We need a lookahead either to distinguish different
-        reductions (i.e., there are two or more), or to distinguish a
-        reduction from a shift.  Otherwise, it is straightforward,
-        and the state is `consistent'.  */
-      if (rp->num > 1
-         || (rp->num == 1 && sp->num &&
-             !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
-       nlookaheads += rp->num;
-      else
-       states[i]->consistent = 1;
-
-      for (k = 0; k < sp->num; k++)
-       if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
-         {
-           states[i]->consistent = 0;
-           break;
-         }
+  int k;
+  int nlookaheads = 0;
+  reductions_t *rp = state->reductions;
+  transitions_t *sp = state->transitions;
+
+  /* We need a lookahead either to distinguish different
+     reductions (i.e., there are two or more), or to distinguish a
+     reduction from a shift.  Otherwise, it is straightforward,
+     and the state is `consistent'.  */
+  if (rp->num > 1
+      || (rp->num == 1 && sp->num &&
+         !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
+    nlookaheads += rp->num;
+  else
+    state->consistent = 1;
+
+  for (k = 0; k < sp->num; k++)
+    if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
+      {
+       state->consistent = 0;
+       break;
+      }

 
 

-      states[i]->nlookaheads = nlookaheads;
-      nLA += nlookaheads;
-    }
+  return nlookaheads;

 }
 
 
 }
 
 

-/*--------------------------------------.
-| Initializing the lookaheads members.  |
-`--------------------------------------*/
+/*----------------------------------------------.
+| Compute LA, NLA, and the lookaheads members.  |
+`----------------------------------------------*/

 
 static void
 
 static void

-states_lookaheads_initialize (void)
+initialize_LA (void)

 {
   state_number_t i;
 {
   state_number_t i;

-  bitsetv pLA = LA;
-  rule_t **pLArule = LArule;
+  bitsetv pLA;

 
 

-  /* Initialize the members LOOKAHEADS and LOOKAHEADS_RULE for each
-     state.  */
+  /* Compute the total number of reductions requiring a lookahead.  */
+  nLA = 0;
+  for (i = 0; i < nstates; i++)
+    nLA += state_lookaheads_count (states[i]);
+  /* Avoid having to special case 0.  */
+  if (!nLA)
+    nLA = 1;
+
+  pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
+  lookback = XCALLOC (goto_list_t *, nLA);
+
+  /* Initialize the members LOOKAHEADS for each state which reductions
+     require lookaheads.  */

   for (i = 0; i < nstates; i++)
     {
   for (i = 0; i < nstates; i++)
     {

-      states[i]->lookaheads = pLA;
-      states[i]->lookaheads_rule = pLArule;
-      pLA += states[i]->nlookaheads;
-      pLArule += states[i]->nlookaheads;
+      int count = state_lookaheads_count (states[i]);
+      if (count)
+       {
+         states[i]->reductions->lookaheads = pLA;
+         pLA += count;
+       }

     }
 }
 
     }
 }
 


@@ -443,18 +406,26 @@ lookaheads_print (FILE *out)
   fprintf (out, "Lookaheads: BEGIN\n");
   for (i = 0; i < nstates; ++i)
     {
   fprintf (out, "Lookaheads: BEGIN\n");
   for (i = 0; i < nstates; ++i)
     {

+      reductions_t *reds = states[i]->reductions;

       bitset_iterator iter;
       bitset_iterator iter;

+      int nlookaheads = 0;
+
+      if (reds->lookaheads)
+       for (k = 0; k < reds->num; ++k)
+         if (reds->lookaheads[k])
+           ++nlookaheads;

 
       fprintf (out, "State %d: %d lookaheads\n",
 
       fprintf (out, "State %d: %d lookaheads\n",

-              i, states[i]->nlookaheads);
+              i, nlookaheads);

 
 

-      for (j = 0; j < states[i]->nlookaheads; ++j)
-       BITSET_FOR_EACH (iter, states[i]->lookaheads[j], k, 0)
-       {
-         fprintf (out, "   on %d (%s) -> rule %d\n",
-                  k, symbols[k]->tag,
-                  states[i]->lookaheads_rule[j]->number);
-       };
+      if (reds->lookaheads)
+       for (j = 0; j < reds->num; ++j)
+         BITSET_FOR_EACH (iter, reds->lookaheads[j], k, 0)
+         {
+           fprintf (out, "   on %d (%s) -> rule %d\n",
+                    k, symbols[k]->tag,
+                    reds->rules[j]->number);
+         };

     }
   fprintf (out, "Lookaheads: END\n");
 }
     }
   fprintf (out, "Lookaheads: END\n");
 }


@@ -462,9 +433,7 @@ lookaheads_print (FILE *out)
 void
 lalr (void)
 {
 void
 lalr (void)
 {

-  states_lookaheads_count ();

   initialize_LA ();
   initialize_LA ();

-  states_lookaheads_initialize ();

   set_goto_map ();
   initialize_F ();
   build_relations ();
   set_goto_map ();
   initialize_F ();
   build_relations ();


@@ -481,10 +450,6 @@ lalr_free (void)
 {
   state_number_t s;
   for (s = 0; s < nstates; ++s)
 {
   state_number_t s;
   for (s = 0; s < nstates; ++s)

-    {
-      states[s]->lookaheads = NULL;
-      states[s]->lookaheads_rule = NULL;
-    }
+    states[s]->reductions->lookaheads = NULL;

   bitsetv_free (LA);
   bitsetv_free (LA);

-  free (LArule);

 }
 }

diff --git a/src/main.c b/src/main.c
index c695ae5fc68561ae35baac6824e2f7b1ab015a89..e634f310fd69b02ca93dd2f94c88c3ee38938621 100644 (file)
--- a/src/main.c
+++ b/src/main.c
@@ -99,11 +99,6 @@ main (int argc, char *argv[])
   lalr ();
   timevar_pop (TV_LALR);
 
   lalr ();
   timevar_pop (TV_LALR);
 

-  timevar_push (TV_FREE);
-  nullable_free ();
-  derives_free ();
-  timevar_pop (TV_FREE);
-

   /* Find and record any conflicts: places where one token of
      lookahead is not enough to disambiguate the parsing.  In file
      conflicts.  Also resolve s/r conflicts based on precedence
   /* Find and record any conflicts: places where one token of
      lookahead is not enough to disambiguate the parsing.  In file
      conflicts.  Also resolve s/r conflicts based on precedence


@@ -153,6 +148,8 @@ main (int argc, char *argv[])
   timevar_pop (TV_PARSER);
 
   timevar_push (TV_FREE);
   timevar_pop (TV_PARSER);
 
   timevar_push (TV_FREE);

+  nullable_free ();
+  derives_free ();

   tables_free ();
   states_free ();
   reduce_free ();
   tables_free ();
   states_free ();
   reduce_free ();

diff --git a/src/print.c b/src/print.c
index 2a07affacecb9029829eeaf4a78f34484e5d3d9a..12466c905e4c4de54f55aba2a7fb9c9ae9e35c19 100644 (file)
--- a/src/print.c
+++ b/src/print.c
@@ -244,25 +244,25 @@ state_default_rule (state_t *state)
        bitset_set (shiftset, errp->symbols[i]->number);
   }
 
        bitset_set (shiftset, errp->symbols[i]->number);
   }
 

-  for (i = 0; i < state->nlookaheads; ++i)
+  for (i = 0; i < redp->num; ++i)

     {
       int count = 0;
 
       /* How many non-masked lookaheads are there for this reduction?
         */
     {
       int count = 0;
 
       /* How many non-masked lookaheads are there for this reduction?
         */

-      bitset_andn (lookaheadset, state->lookaheads[i], shiftset);
+      bitset_andn (lookaheadset, redp->lookaheads[i], shiftset);

       count = bitset_count (lookaheadset);
 
       if (count > cmax)
        {
          cmax = count;
       count = bitset_count (lookaheadset);
 
       if (count > cmax)
        {
          cmax = count;

-         default_rule = state->lookaheads_rule[i];
+         default_rule = redp->rules[i];

        }
 
       /* 3. And finally, each reduction is possibly masked by previous
         reductions (in R/R conflicts, we keep the first reductions).
         */
        }
 
       /* 3. And finally, each reduction is possibly masked by previous
         reductions (in R/R conflicts, we keep the first reductions).
         */

-      bitset_or (shiftset, shiftset, state->lookaheads[i]);
+      bitset_or (shiftset, shiftset, redp->lookaheads[i]);

     }
 
   return default_rule;
     }
 
   return default_rule;


@@ -322,25 +322,27 @@ print_reductions (FILE *out, state_t *state)
   /* Compute the width of the lookaheads column.  */
   if (default_rule)
     width = strlen (_("$default"));
   /* Compute the width of the lookaheads column.  */
   if (default_rule)
     width = strlen (_("$default"));

-  for (i = 0; i < ntokens; i++)
-    {
-      int count = bitset_test (shiftset, i);

 
 

-      for (j = 0; j < state->nlookaheads; ++j)
-       if (bitset_test (state->lookaheads[j], i))
-         {
-           if (count == 0)
-             {
-               if (state->lookaheads_rule[j] != default_rule)
+  if (redp->lookaheads)
+    for (i = 0; i < ntokens; i++)
+      {
+       int count = bitset_test (shiftset, i);
+
+       for (j = 0; j < redp->num; ++j)
+         if (bitset_test (redp->lookaheads[j], i))
+           {
+             if (count == 0)
+               {
+                 if (redp->rules[j] != default_rule)
+                   max_length (&width, symbols[i]->tag);
+                 count++;
+               }
+             else
+               {

                  max_length (&width, symbols[i]->tag);
                  max_length (&width, symbols[i]->tag);

-               count++;
-             }
-           else
-             {
-               max_length (&width, symbols[i]->tag);
-             }
-         }
-    }
+               }
+           }
+      }

 
   /* Nothing to report. */
   if (!width)
 
   /* Nothing to report. */
   if (!width)


@@ -350,37 +352,38 @@ print_reductions (FILE *out, state_t *state)
   width += 2;
 
   /* Report lookaheads (or $default) and reductions.  */
   width += 2;
 
   /* Report lookaheads (or $default) and reductions.  */

-  for (i = 0; i < ntokens; i++)
-    {
-      int defaulted = 0;
-      int count = bitset_test (shiftset, i);
+  if (redp->lookaheads)
+    for (i = 0; i < ntokens; i++)
+      {
+       int defaulted = 0;
+       int count = bitset_test (shiftset, i);

 
 

-      for (j = 0; j < state->nlookaheads; ++j)
-       if (bitset_test (state->lookaheads[j], i))
-         {
-           if (count == 0)
-             {
-               if (state->lookaheads_rule[j] != default_rule)
-                 print_reduction (out, width,
-                                  symbols[i]->tag,
-                                  state->lookaheads_rule[j], TRUE);
-               else
-                 defaulted = 1;
-               count++;
-             }
-           else
-             {
-               if (defaulted)
+       for (j = 0; j < redp->num; ++j)
+         if (bitset_test (redp->lookaheads[j], i))
+           {
+             if (count == 0)
+               {
+                 if (redp->rules[j] != default_rule)
+                   print_reduction (out, width,
+                                    symbols[i]->tag,
+                                    redp->rules[j], TRUE);
+                 else
+                   defaulted = 1;
+                 count++;
+               }
+             else
+               {
+                 if (defaulted)
+                   print_reduction (out, width,
+                                    symbols[i]->tag,
+                                    default_rule, TRUE);
+                 defaulted = 0;

                  print_reduction (out, width,
                                   symbols[i]->tag,
                  print_reduction (out, width,
                                   symbols[i]->tag,

-                                  default_rule, TRUE);
-               defaulted = 0;
-               print_reduction (out, width,
-                                symbols[i]->tag,
-                                state->lookaheads_rule[j], FALSE);
-             }
-         }
-    }
+                                  redp->rules[j], FALSE);
+               }
+           }
+      }

 
   if (default_rule)
     print_reduction (out, width,
 
   if (default_rule)
     print_reduction (out, width,

diff --git a/src/print_graph.c b/src/print_graph.c
index 272ffc53ff007df4f0164830c1198c3b4969610c..fe0ee76d9d52b3faa98b54dad40e0c7c223d8ff0 100644 (file)
--- a/src/print_graph.c
+++ b/src/print_graph.c
@@ -86,28 +86,23 @@ print_core (struct obstack *oout, state_t *state)
        obstack_fgrow1 (oout, " %s", symbols[*sp]->tag);
 
       /* Experimental feature: display the lookaheads. */
        obstack_fgrow1 (oout, " %s", symbols[*sp]->tag);
 
       /* Experimental feature: display the lookaheads. */

-      if ((report_flag & report_lookaheads)
-         && state->nlookaheads)
+      if (report_flag & report_lookaheads)

        {
        {

-         int j, k;
-         bitset_iterator biter;
-         int nlookaheads = 0;
+         /* Find the reduction we are handling.  */
+         reductions_t *reds = state->reductions;
+         int redno = state_reduction_find (state, &rules[rule]);

 
 

-         /* Look for lookaheads corresponding to this rule. */
-         for (j = 0; j < state->nlookaheads; ++j)
-           BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0)
-             if (state->lookaheads_rule[j]->number == rule)
-               nlookaheads++;
-
-         if (nlookaheads)
+         /* Print them if there are.  */
+         if (reds->lookaheads && redno != -1)

            {
            {

-             obstack_sgrow (oout, "  [");
-             for (j = 0; j < state->nlookaheads; ++j)
-               BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0)
-                 if (state->lookaheads_rule[j]->number == rule)
-                   obstack_fgrow2 (oout, "%s%s",
-                                   symbols[k]->tag,
-                                   --nlookaheads ? ", " : "");
+             bitset_iterator biter;
+             int k;
+             int not_first = 0;
+             obstack_sgrow (oout, "[");
+             BITSET_FOR_EACH (biter, reds->lookaheads[redno], k, 0)
+               obstack_fgrow2 (oout, "%s%s",
+                               not_first++ ? ", " : "",
+                               symbols[k]->tag);

              obstack_sgrow (oout, "]");
            }
        }
              obstack_sgrow (oout, "]");
            }
        }

diff --git a/src/state.c b/src/state.c
index eb244e28f043e4b23acfe6657f5f15ae24282b6e..71914025c96ac2112921bad287f0d5cde056c2b8 100644 (file)
--- a/src/state.c
+++ b/src/state.c
@@ -100,8 +100,8 @@ errs_new (int num, symbol_t **tokens)
 | Create a new array of N reductions.  |
 `-------------------------------------*/
 
 | Create a new array of N reductions.  |
 `-------------------------------------*/
 

-#define REDUCTIONS_ALLOC(Nreductions)                          \
-  (reductions_t *) xcalloc ((sizeof (reductions_t)             \
+#define REDUCTIONS_ALLOC(Nreductions)                          \
+  (reductions_t *) xcalloc ((sizeof (reductions_t)             \

                             + (Nreductions - 1) * sizeof (rule_t *)), 1)
 
 static reductions_t *
                             + (Nreductions - 1) * sizeof (rule_t *)), 1)
 
 static reductions_t *


@@ -110,6 +110,7 @@ reductions_new (int num, rule_t **reductions)
   reductions_t *res = REDUCTIONS_ALLOC (num);
   res->num = num;
   memcpy (res->rules, reductions, num * sizeof (reductions[0]));
   reductions_t *res = REDUCTIONS_ALLOC (num);
   res->num = num;
   memcpy (res->rules, reductions, num * sizeof (reductions[0]));

+  res->lookaheads = NULL;

   return res;
 }
 
   return res;
 }
 


@@ -196,6 +197,18 @@ state_reductions_set (state_t *state, int num, rule_t **reductions)
 }
 
 
 }
 
 

+int
+state_reduction_find (state_t *state, rule_t *rule)
+{
+  int i;
+  reductions_t *reds = state->reductions;
+  for (i = 0; i < reds->num; ++i)
+    if (reds->rules[i] == rule)
+      return i;
+  return -1;
+}
+
+

 /*------------------------.
 | Set the errs of STATE.  |
 `------------------------*/
 /*------------------------.
 | Set the errs of STATE.  |
 `------------------------*/


@@ -217,25 +230,21 @@ state_errs_set (state_t *state, int num, symbol_t **tokens)
 void
 state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
 {
 void
 state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
 {

-  int j, k;
-  bitset_iterator biter;
-  int nlookaheads = 0;
-  /* Count the number of lookaheads corresponding to this rule.  */
-  for (j = 0; j < state->nlookaheads; ++j)
-    BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0)
-      if (state->lookaheads_rule[j] == rule)
-       nlookaheads++;
+  /* Find the reduction we are handling.  */
+  reductions_t *reds = state->reductions;
+  int red = state_reduction_find (state, rule);

 
   /* Print them if there are.  */
 
   /* Print them if there are.  */

-  if (nlookaheads)
+  if (reds->lookaheads && red != -1)

     {
     {

+      bitset_iterator biter;
+      int k;
+      int not_first = 0;

       fprintf (out, "  [");
       fprintf (out, "  [");

-      for (j = 0; j < state->nlookaheads; ++j)
-       BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0)
-         if (state->lookaheads_rule[j] == rule)
-           fprintf (out, "%s%s",
-                    symbols[k]->tag,
-                    --nlookaheads ? ", " : "");
+      BITSET_FOR_EACH (biter, reds->lookaheads[red], k, 0)
+       fprintf (out, "%s%s",
+                not_first++ ? ", " : "",
+                symbols[k]->tag);

       fprintf (out, "]");
     }
 }
       fprintf (out, "]");
     }
 }

diff --git a/src/state.h b/src/state.h
index 32559cef4ba2441ff19aff2965493e03731876a4..f63cc4f8f52d38616472f3ee6e9780fc5ba31790 100644 (file)
--- a/src/state.h
+++ b/src/state.h
@@ -82,7 +82,7 @@
 #ifndef STATE_H_
 # define STATE_H_
 
 #ifndef STATE_H_
 # define STATE_H_
 

-# include "bitsetv.h"
+# include "bitset.h"

 
 
 /*-------------------.
 
 
 /*-------------------.


@@ -178,6 +178,7 @@ errs_t *errs_new PARAMS ((int num, symbol_t **tokens));
 typedef struct reductions_s
 {
   short num;
 typedef struct reductions_s
 {
   short num;

+  bitset *lookaheads;

   rule_t *rules[1];
 } reductions_t;
 
   rule_t *rules[1];
 } reductions_t;
 


@@ -198,17 +199,6 @@ struct state_s
   /* Nonzero if no lookahead is needed to decide what to do in state S.  */
   char consistent;
 
   /* Nonzero if no lookahead is needed to decide what to do in state S.  */
   char consistent;
 

-  /* Used in LALR, not LR(0).
-
-     When a state is not consistent (there is an S/R or R/R conflict),
-     lookaheads are needed to enable the reductions.  NLOOKAHEADS is
-     the number of lookahead guarded reductions of the
-     LOOKAHEADS_RULE.  For each rule LOOKAHEADS_RULE[R], LOOKAHEADS[R]
-     is the bitset of the lookaheads enabling this reduction.  */
-  int nlookaheads;
-  bitsetv lookaheads;
-  rule_t **lookaheads_rule;
-

   /* If some conflicts were solved thanks to precedence/associativity,
      a human readable description of the resolution.  */
   const char *solved_conflicts;
   /* If some conflicts were solved thanks to precedence/associativity,
      a human readable description of the resolution.  */
   const char *solved_conflicts;


@@ -234,6 +224,8 @@ void state_transitions_set PARAMS ((state_t *state,
 void state_reductions_set PARAMS ((state_t *state,
                                   int num, rule_t **reductions));
 
 void state_reductions_set PARAMS ((state_t *state,
                                   int num, rule_t **reductions));
 

+int state_reduction_find PARAMS ((state_t *state, rule_t *rule));
+

 /* Set the errs of STATE.  */
 void state_errs_set PARAMS ((state_t *state,
                             int num, symbol_t **errs));
 /* Set the errs of STATE.  */
 void state_errs_set PARAMS ((state_t *state,
                             int num, symbol_t **errs));

diff --git a/src/tables.c b/src/tables.c
index 67e9abadeb4a64be7893ee1fd8ad901142822884..75502759162d3a412c25b31c2a70e208c756a05a 100644 (file)
--- a/src/tables.c
+++ b/src/tables.c
@@ -239,6 +239,7 @@ static void
 conflict_row (state_t *state)
 {
   int i, j;
 conflict_row (state_t *state)
 {
   int i, j;

+  reductions_t *reds = state->reductions;

 
   if (! glr_parser)
     return;
 
   if (! glr_parser)
     return;


@@ -250,14 +251,13 @@ conflict_row (state_t *state)
 
        /* Find all reductions for token J, and record all that do not
           match ACTROW[J].  */
 
        /* Find all reductions for token J, and record all that do not
           match ACTROW[J].  */

-       for (i = 0; i < state->nlookaheads; i += 1)
-         if (bitset_test (state->lookaheads[i], j)
+       for (i = 0; i < reds->num; i += 1)
+         if (bitset_test (reds->lookaheads[i], j)

              && (actrow[j]
              && (actrow[j]

-                 != rule_number_as_item_number (state->lookaheads_rule[i]->number)))
+                 != rule_number_as_item_number (reds->rules[i]->number)))

            {
              assert (conflict_list_free > 0);
            {
              assert (conflict_list_free > 0);

-             conflict_list[conflict_list_cnt]
-               = state->lookaheads_rule[i]->number + 1;
+             conflict_list[conflict_list_cnt] = reds->rules[i]->number + 1;

              conflict_list_cnt += 1;
              conflict_list_free -= 1;
            }
              conflict_list_cnt += 1;
              conflict_list_free -= 1;
            }


@@ -304,22 +304,23 @@ action_row (state_t *state)
   for (i = 0; i < ntokens; i++)
     actrow[i] = conflrow[i] = 0;
 
   for (i = 0; i < ntokens; i++)
     actrow[i] = conflrow[i] = 0;
 

-  if (redp->num >= 1)
+  if (redp->lookaheads)

     {
       int j;
       bitset_iterator biter;
       /* loop over all the rules available here which require
     {
       int j;
       bitset_iterator biter;
       /* loop over all the rules available here which require

-        lookahead */
-      for (i = state->nlookaheads - 1; i >= 0; --i)
+        lookahead (in reverse order to give precedence to the first
+        rule) */
+      for (i = redp->num - 1; i >= 0; --i)

        /* and find each token which the rule finds acceptable
           to come next */
        /* and find each token which the rule finds acceptable
           to come next */

-       BITSET_FOR_EACH (biter, state->lookaheads[i], j, 0)
+       BITSET_FOR_EACH (biter, redp->lookaheads[i], j, 0)

        {
          /* and record this rule as the rule to use if that
             token follows.  */
          if (actrow[j] != 0)
            conflicted = conflrow[j] = 1;
        {
          /* and record this rule as the rule to use if that
             token follows.  */
          if (actrow[j] != 0)
            conflicted = conflrow[j] = 1;

-         actrow[j] = rule_number_as_item_number (state->lookaheads_rule[i]->number);
+         actrow[j] = rule_number_as_item_number (redp->rules[i]->number);

        }
     }
 
        }
     }
 


@@ -359,10 +360,10 @@ action_row (state_t *state)
       else
        {
          int max = 0;
       else
        {
          int max = 0;

-         for (i = 0; i < state->nlookaheads; i++)
+         for (i = 0; i < redp->num; i++)

            {
              int count = 0;
            {
              int count = 0;

-             rule_t *rule = state->lookaheads_rule[i];
+             rule_t *rule = redp->rules[i];

              symbol_number_t j;
 
              for (j = 0; j < ntokens; j++)
              symbol_number_t j;
 
              for (j = 0; j < ntokens; j++)