Merge remote-tracking branch 'origin/maint'

[bison.git] / src / lalr.c

diff --git a/src/lalr.c b/src/lalr.c
index 0101149833cad5f3380bd3044f24a609a6c52115..1ceda002b454fcddd9993da74c665c3d3f84040f 100644 (file)
--- a/src/lalr.c
+++ b/src/lalr.c
@@ -1,7 +1,7 @@
 /* Compute lookahead criteria for Bison.
 
 /* Compute lookahead criteria for Bison.
 

-   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
-   2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+   Copyright (C) 1984, 1986, 1989, 2000-2012 Free Software Foundation,
+   Inc.

 
    This file is part of Bison, the GNU Compiler Compiler.
 
 
    This file is part of Bison, the GNU Compiler Compiler.
 


@@ -19,8 +19,7 @@
    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 
    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 

-/* 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 <config.h>
    tokens they accept.  */
 
 #include <config.h>


@@ -28,7 +27,6 @@
 
 #include <bitset.h>
 #include <bitsetv.h>
 
 #include <bitset.h>
 #include <bitsetv.h>

-#include <quotearg.h>

 
 #include "LR0.h"
 #include "complain.h"
 
 #include "LR0.h"
 #include "complain.h"


@@ -36,7 +34,7 @@
 #include "getargs.h"
 #include "gram.h"
 #include "lalr.h"
 #include "getargs.h"
 #include "gram.h"
 #include "lalr.h"

-#include "muscle_tab.h"
+#include "muscle-tab.h"

 #include "nullable.h"
 #include "reader.h"
 #include "relation.h"
 #include "nullable.h"
 #include "reader.h"
 #include "relation.h"


@@ -86,14 +84,14 @@ set_goto_map (void)
       transitions *sp = states[s]->transitions;
       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
       transitions *sp = states[s]->transitions;
       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)

-       {
-         ngotos++;
+        {
+          ngotos++;

 
 

-         /* Abort if (ngotos + 1) would overflow.  */
-         aver (ngotos != GOTO_NUMBER_MAXIMUM);
+          /* Abort if (ngotos + 1) would overflow.  */
+          aver (ngotos != GOTO_NUMBER_MAXIMUM);

 
 

-         goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
-       }
+          goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
+        }

     }
 
   {
     }
 
   {


@@ -101,8 +99,8 @@ set_goto_map (void)
     int i;
     for (i = ntokens; i < nsyms; i++)
       {
     int i;
     for (i = ntokens; i < nsyms; i++)
       {

-       temp_map[i - ntokens] = k;
-       k += goto_map[i - ntokens];
+        temp_map[i - ntokens] = k;
+        k += goto_map[i - ntokens];

       }
 
     for (i = ntokens; i < nsyms; i++)
       }
 
     for (i = ntokens; i < nsyms; i++)


@@ -120,11 +118,11 @@ set_goto_map (void)
       transitions *sp = states[s]->transitions;
       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
       transitions *sp = states[s]->transitions;
       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)

-       {
-         goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
-         from_state[k] = s;
-         to_state[k] = sp->states[i]->number;
-       }
+        {
+          goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
+          from_state[k] = s;
+          to_state[k] = sp->states[i]->number;
+        }

     }
 
   free (temp_map);
     }
 
   free (temp_map);


@@ -148,11 +146,11 @@ map_goto (state_number s0, symbol_number sym)
       middle = (low + high) / 2;
       s = from_state[middle];
       if (s == s0)
       middle = (low + high) / 2;
       s = from_state[middle];
       if (s == s0)

-       return middle;
+        return middle;

       else if (s < s0)
       else if (s < s0)

-       low = middle + 1;
+        low = middle + 1;

       else
       else

-       high = middle - 1;
+        high = middle - 1;

     }
 }
 
     }
 }
 


@@ -175,24 +173,24 @@ initialize_F (void)
 
       int j;
       FOR_EACH_SHIFT (sp, j)
 
       int j;
       FOR_EACH_SHIFT (sp, j)

-       bitset_set (goto_follows[i], TRANSITION_SYMBOL (sp, j));
+        bitset_set (goto_follows[i], TRANSITION_SYMBOL (sp, j));

 
       for (; j < sp->num; j++)
 
       for (; j < sp->num; j++)

-       {
-         symbol_number sym = TRANSITION_SYMBOL (sp, j);
-         if (nullable[sym - ntokens])
-           edge[nedges++] = map_goto (stateno, sym);
-       }
+        {
+          symbol_number sym = TRANSITION_SYMBOL (sp, j);
+          if (nullable[sym - ntokens])
+            edge[nedges++] = map_goto (stateno, sym);
+        }

 
       if (nedges == 0)
 
       if (nedges == 0)

-       reads[i] = NULL;
+        reads[i] = NULL;

       else
       else

-       {
-         reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
-         memcpy (reads[i], edge, nedges * sizeof edge[0]);
-         reads[i][nedges] = END_NODE;
-         nedges = 0;
-       }
+        {
+          reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
+          memcpy (reads[i], edge, nedges * sizeof edge[0]);
+          reads[i][nedges] = END_NODE;
+          nedges = 0;
+        }

     }
 
   relation_digraph (reads, ngotos, &goto_follows);
     }
 
   relation_digraph (reads, ngotos, &goto_follows);


@@ -233,53 +231,53 @@ build_relations (void)
       rule **rulep;
 
       for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
       rule **rulep;
 
       for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)

-       {
-         bool done;
-         int length = 1;
-         item_number const *rp;
-         state *s = states[from_state[i]];
-         states1[0] = s->number;
-
-         for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); rp++)
-           {
-             s = transitions_to (s->transitions,
-                                 item_number_as_symbol_number (*rp));
-             states1[length++] = s->number;
-           }
-
-         if (!s->consistent)
-           add_lookback_edge (s, *rulep, i);
-
-         length--;
-         done = false;
-         while (!done)
-           {
-             done = true;
-             /* Each rhs ends in a rule number, and there is a
-                sentinel (ritem[-1]=0) before the first rhs, so it is safe to
-                decrement RP here.  */
-             rp--;
-             if (ISVAR (*rp))
-               {
-                 /* Downcasting from item_number to symbol_number.  */
-                 edge[nedges++] = map_goto (states1[--length],
-                                            item_number_as_symbol_number (*rp));
-                 if (nullable[*rp - ntokens])
-                   done = false;
-               }
-           }
-       }
+        {
+          bool done;
+          int length = 1;
+          item_number const *rp;
+          state *s = states[from_state[i]];
+          states1[0] = s->number;
+
+          for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); rp++)
+            {
+              s = transitions_to (s->transitions,
+                                  item_number_as_symbol_number (*rp));
+              states1[length++] = s->number;
+            }
+
+          if (!s->consistent)
+            add_lookback_edge (s, *rulep, i);
+
+          length--;
+          done = false;
+          while (!done)
+            {
+              done = true;
+              /* Each rhs ends in a rule number, and there is a
+                 sentinel (ritem[-1]=0) before the first rhs, so it is safe to
+                 decrement RP here.  */
+              rp--;
+              if (ISVAR (*rp))
+                {
+                  /* Downcasting from item_number to symbol_number.  */
+                  edge[nedges++] = map_goto (states1[--length],
+                                             item_number_as_symbol_number (*rp));
+                  if (nullable[*rp - ntokens])
+                    done = false;
+                }
+            }
+        }

 
       if (nedges == 0)
 
       if (nedges == 0)

-       includes[i] = NULL;
+        includes[i] = NULL;

       else
       else

-       {
-         int j;
-         includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
-         for (j = 0; j < nedges; j++)
-           includes[i][j] = edge[j];
-         includes[i][nedges] = END_NODE;
-       }
+        {
+          int j;
+          includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
+          for (j = 0; j < nedges; j++)
+            includes[i][j] = edge[j];
+          includes[i][nedges] = END_NODE;
+        }

     }
 
   free (edge);
     }
 
   free (edge);


@@ -328,7 +326,7 @@ compute_lookahead_tokens (void)
 `----------------------------------------------------*/
 
 static int
 `----------------------------------------------------*/
 
 static int

-state_lookahead_tokens_count (state *s, bool default_rule_only_for_accept)
+state_lookahead_tokens_count (state *s, bool default_reduction_only_for_accept)

 {
   int n_lookahead_tokens = 0;
   reductions *rp = s->reductions;
 {
   int n_lookahead_tokens = 0;
   reductions *rp = s->reductions;


@@ -344,14 +342,15 @@ state_lookahead_tokens_count (state *s, bool default_rule_only_for_accept)
   /* 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
   /* 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'.  However, for states that have any rules, treat only
-     the accepting state as consistent (since there is never a lookahead
-     token that makes sense there, and so no lookahead token should be
-     read) if the user has otherwise disabled default rules.  */
+     `consistent'.  However, do not treat a state with any reductions as
+     consistent unless it is the accepting state (because there is never
+     a lookahead token that makes sense there, and so no lookahead token
+     should be read) if the user has otherwise disabled default
+     reductions.  */

   if (rp->num > 1
       || (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0))
       || (rp->num == 1 && rp->rules[0]->number != 0
   if (rp->num > 1
       || (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0))
       || (rp->num == 1 && rp->rules[0]->number != 0

-          && default_rule_only_for_accept))
+          && default_reduction_only_for_accept))

     n_lookahead_tokens += rp->num;
   else
     s->consistent = 1;
     n_lookahead_tokens += rp->num;
   else
     s->consistent = 1;


@@ -369,18 +368,20 @@ initialize_LA (void)
 {
   state_number i;
   bitsetv pLA;
 {
   state_number i;
   bitsetv pLA;

-  bool default_rule_only_for_accept;
+  bool default_reduction_only_for_accept;

   {
   {

-    char *default_rules = muscle_percent_define_get ("lr.default_rules");
-    default_rule_only_for_accept = 0 == strcmp (default_rules, "accepting");
-    free (default_rules);
+    char *default_reductions =
+      muscle_percent_define_get ("lr.default-reductions");
+    default_reduction_only_for_accept = STREQ (default_reductions, "accepting");
+    free (default_reductions);

   }
 
   /* Compute the total number of reductions requiring a lookahead.  */
   nLA = 0;
   for (i = 0; i < nstates; i++)
     nLA +=
   }
 
   /* Compute the total number of reductions requiring a lookahead.  */
   nLA = 0;
   for (i = 0; i < nstates; i++)
     nLA +=

-      state_lookahead_tokens_count (states[i], default_rule_only_for_accept);
+      state_lookahead_tokens_count (states[i],
+                                    default_reduction_only_for_accept);

   /* Avoid having to special case 0.  */
   if (!nLA)
     nLA = 1;
   /* Avoid having to special case 0.  */
   if (!nLA)
     nLA = 1;


@@ -392,12 +393,13 @@ initialize_LA (void)
   for (i = 0; i < nstates; i++)
     {
       int count =
   for (i = 0; i < nstates; i++)
     {
       int count =

-        state_lookahead_tokens_count (states[i], default_rule_only_for_accept);
+        state_lookahead_tokens_count (states[i],
+                                      default_reduction_only_for_accept);

       if (count)
       if (count)

-       {
-         states[i]->reductions->lookahead_tokens = pLA;
-         pLA += count;
-       }
+        {
+          states[i]->reductions->lookahead_tokens = pLA;
+          pLA += count;
+        }

     }
 }
 
     }
 }
 


@@ -419,21 +421,21 @@ lookahead_tokens_print (FILE *out)
       int n_lookahead_tokens = 0;
 
       if (reds->lookahead_tokens)
       int n_lookahead_tokens = 0;
 
       if (reds->lookahead_tokens)

-       for (k = 0; k < reds->num; ++k)
-         if (reds->lookahead_tokens[k])
-           ++n_lookahead_tokens;
+        for (k = 0; k < reds->num; ++k)
+          if (reds->lookahead_tokens[k])
+            ++n_lookahead_tokens;

 
       fprintf (out, "State %d: %d lookahead tokens\n",
 
       fprintf (out, "State %d: %d lookahead tokens\n",

-              i, n_lookahead_tokens);
+               i, n_lookahead_tokens);

 
       if (reds->lookahead_tokens)
 
       if (reds->lookahead_tokens)

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

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