Re: bison lalr

[Paul Eggert]

twlevo <address@hidden> writes:

> line 271 lalr.c should it not be `if (*rp >= *ritem && ISVAR(*rp))'

No, that wouldn't be right, since the idea is that we should not
go backwards before the start of the rule.

However, you have pointed out an obscure addressing bug.  The current
code in some cases reads just before the start of an array, which has
undefined behavior in C and in theory could lead to a core dump.  I
installed the following patch.  Thanks for mentioning it.

2006-01-18  Paul Eggert  <address@hidden>

        Avoid undefined behavior that accessed just before the start of an
        array.  Problem reported by twlevo.
        * src/reader.c (packgram): Prepend a new sentinel before ritem.
        * src/lalr.c (build_relations): Rely on new sentinel.
        * src/gram.c (gram_free): Adjust to new sentinel.

Index: src/gram.c
===================================================================
RCS file: /cvsroot/bison/bison/src/gram.c,v
retrieving revision 1.59
diff -p -u -r1.59 gram.c
--- src/gram.c  22 Dec 2005 11:40:05 -0000      1.59
+++ src/gram.c  18 Jan 2006 23:43:15 -0000
@@ -1,6 +1,6 @@
 /* Allocate input grammar variables for Bison.
 
-   Copyright (C) 1984, 1986, 1989, 2001, 2002, 2003, 2005 Free
+   Copyright (C) 1984, 1986, 1989, 2001, 2002, 2003, 2005, 2006 Free
    Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
@@ -325,7 +325,8 @@ grammar_rules_never_reduced_report (cons
 void
 grammar_free (void)
 {
-  free (ritem);
+  if (ritem)
+    free (ritem - 1);
   free (rules);
   free (token_translations);
   /* Free the symbol table data structure.  */
Index: src/lalr.c
===================================================================
RCS file: /cvsroot/bison/bison/src/lalr.c,v
retrieving revision 1.106
diff -p -u -r1.106 lalr.c
--- src/lalr.c  9 Dec 2005 23:51:26 -0000       1.106
+++ src/lalr.c  18 Jan 2006 23:43:15 -0000
@@ -1,7 +1,7 @@
 /* Compute look-ahead criteria for Bison.
 
-   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005
-   Free Software Foundation, Inc.
+   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
+   2006 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -247,11 +247,11 @@ build_relations (void)
        {
          bool done;
          int length = 1;
-         item_number *rp;
+         item_number const *rp;
          state *s = states[from_state[i]];
          states1[0] = s->number;
 
-         for (rp = (*rulep)->rhs; *rp >= 0; rp++)
+         for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); rp++)
            {
              s = transitions_to (s->transitions,
                                  item_number_as_symbol_number (*rp));
@@ -266,9 +266,11 @@ build_relations (void)
          while (!done)
            {
              done = true;
+             /* Each rhs ends in an item number, and there is a
+                sentinel before the first rhs, so it is safe to
+                decrement RP here.  */
              rp--;
-             /* JF added rp>=ritem &&   I hope to god its right! */
-             if (rp >= ritem && ISVAR (*rp))
+             if (ISVAR (*rp))
                {
                  /* Downcasting from item_number to symbol_number.  */
                  edge[nedges++] = map_goto (states1[--length],
Index: src/reader.c
===================================================================
RCS file: /cvsroot/bison/bison/src/reader.c,v
retrieving revision 1.247
diff -p -u -r1.247 reader.c
--- src/reader.c        5 Jan 2006 13:38:58 -0000       1.247
+++ src/reader.c        18 Jan 2006 23:43:15 -0000
@@ -418,7 +418,11 @@ packgram (void)
   rule_number ruleno = 0;
   symbol_list *p = grammar;
 
-  ritem = xnmalloc (nritems, sizeof *ritem);
+  ritem = xnmalloc (nritems + 1, sizeof *ritem);
+
+  /* This sentinel is used by build_relations in gram.c.  */
+  *ritem++ = 0;
+
   rules = xnmalloc (nrules, sizeof *rules);
 
   while (p)