projects
/
bison.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
(AC_INIT): Bump version number to 1.875c.
[bison.git]
/
src
/
lalr.c
diff --git
a/src/lalr.c
b/src/lalr.c
index 2c0c942aeb216ab26c958efa11b616a5c0753de3..7273805ac09107ba0e1f192591efcce346e770ce 100644
(file)
--- a/
src/lalr.c
+++ b/
src/lalr.c
@@
-1,5
+1,6
@@
-/* Compute look-ahead criteria for bison,
- Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002
+/* Compute look-ahead criteria for Bison.
+
+ Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003
Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@
-25,31
+26,33
@@
tokens they accept. */
#include "system.h"
tokens they accept. */
#include "system.h"
-#include "bitset.h"
-#include "bitsetv.h"
-#include "relation.h"
-#include "quotearg.h"
-#include "symtab.h"
-#include "gram.h"
-#include "reader.h"
+
+#include <bitset.h>
+#include <bitsetv.h>
+#include <quotearg.h>
+
#include "LR0.h"
#include "complain.h"
#include "LR0.h"
#include "complain.h"
-#include "lalr.h"
-#include "nullable.h"
#include "derives.h"
#include "getargs.h"
#include "derives.h"
#include "getargs.h"
+#include "gram.h"
+#include "lalr.h"
+#include "nullable.h"
+#include "reader.h"
+#include "relation.h"
+#include "symtab.h"
-goto_number
_t
*goto_map = NULL;
-static goto_number
_t
ngotos = 0;
-state_number
_t
*from_state = NULL;
-state_number
_t
*to_state = NULL;
+goto_number *goto_map = NULL;
+static goto_number ngotos = 0;
+state_number *from_state = NULL;
+state_number *to_state = NULL;
/* Linked list of goto numbers. */
/* Linked list of goto numbers. */
-typedef struct goto_list
_s
+typedef struct goto_list
{
{
- struct goto_list
_s
*next;
- goto_number
_t
value;
-} goto_list
_t
;
+ struct goto_list *next;
+ goto_number value;
+} goto_list;
/* LA is a LR by NTOKENS matrix of bits. LA[l, i] is 1 if the rule
/* LA is a LR by NTOKENS matrix of bits. LA[l, i] is 1 if the rule
@@
-65,8
+68,8
@@
size_t nLA;
comment is hardly needed. <grin>. */
static bitsetv F = NULL;
comment is hardly needed. <grin>. */
static bitsetv F = NULL;
-static goto_number
_t
**includes;
-static goto_list
_t
**lookback;
+static goto_number **includes;
+static goto_list **lookback;
@@
-74,24
+77,23
@@
static goto_list_t **lookback;
static void
set_goto_map (void)
{
static void
set_goto_map (void)
{
- state_number
_t state
;
- goto_number
_t
*temp_map;
+ state_number
s
;
+ goto_number *temp_map;
-
goto_map = XCALLOC (goto_number_t, nvars + 1) - ntokens
;
-
temp_map = XCALLOC (goto_number_t, nvars + 1) - ntokens
;
+
CALLOC (goto_map, nvars + 1)
;
+
CALLOC (temp_map, nvars + 1)
;
ngotos = 0;
ngotos = 0;
- for (s
tate = 0; state < nstates; ++state
)
+ for (s
= 0; s < nstates; ++s
)
{
{
- transitions
_t *sp = states[state
]->transitions;
+ transitions
*sp = states[s
]->transitions;
int i;
for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
{
int i;
for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
{
- if (ngotos == GOTO_NUMBER_MAX)
- fatal (_("too many gotos (max %d)"), GOTO_NUMBER_MAX);
-
+ if (ngotos >= GOTO_NUMBER_MAXIMUM)
+ abort ();
ngotos++;
ngotos++;
- goto_map[TRANSITION_SYMBOL (sp, i)]++;
+ goto_map[TRANSITION_SYMBOL (sp, i)
- ntokens
]++;
}
}
}
}
@@
-100,33
+102,33
@@
set_goto_map (void)
int i;
for (i = ntokens; i < nsyms; i++)
{
int i;
for (i = ntokens; i < nsyms; i++)
{
- temp_map[i] = k;
- k += goto_map[i];
+ temp_map[i
- ntokens
] = k;
+ k += goto_map[i
- ntokens
];
}
for (i = ntokens; i < nsyms; i++)
}
for (i = ntokens; i < nsyms; i++)
- goto_map[i
] = temp_map[i
];
+ goto_map[i
- ntokens] = temp_map[i - ntokens
];
- goto_map[nsyms] = ngotos;
- temp_map[nsyms] = ngotos;
+ goto_map[nsyms
- ntokens
] = ngotos;
+ temp_map[nsyms
- ntokens
] = ngotos;
}
}
-
from_state = XCALLOC (state_number_t
, ngotos);
-
to_state = XCALLOC (state_number_t
, ngotos);
+
CALLOC (from_state
, ngotos);
+
CALLOC (to_state
, ngotos);
- for (s
tate = 0; state < nstates; ++state
)
+ for (s
= 0; s < nstates; ++s
)
{
{
- transitions
_t *sp = states[state
]->transitions;
+ transitions
*sp = states[s
]->transitions;
int i;
for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
{
int i;
for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
{
- int k = temp_map[TRANSITION_SYMBOL (sp, i)]++;
- from_state[k] = s
tate
;
+ int k = temp_map[TRANSITION_SYMBOL (sp, i)
- ntokens
]++;
+ from_state[k] = s;
to_state[k] = sp->states[i]->number;
}
}
to_state[k] = sp->states[i]->number;
}
}
- XFREE (temp_map
+ ntokens
);
+ XFREE (temp_map);
}
}
@@
-136,39
+138,37
@@
set_goto_map (void)
`----------------------------------------------------------*/
static int
`----------------------------------------------------------*/
static int
-map_goto (state_number
_t state, symbol_number_t symbol
)
+map_goto (state_number
s0, symbol_number sym
)
{
int high;
int low;
int middle;
{
int high;
int low;
int middle;
- state_number
_t
s;
+ state_number s;
- low = goto_map[sym
bol
];
- high = goto_map[sym
bol
+ 1] - 1;
+ low = goto_map[sym
- ntokens
];
+ high = goto_map[sym
- ntokens
+ 1] - 1;
-
while (low <= high
)
+
for (;;
)
{
{
+ if (high < low)
+ abort ();
middle = (low + high) / 2;
s = from_state[middle];
middle = (low + high) / 2;
s = from_state[middle];
- if (s == s
tate
)
+ if (s == s
0
)
return middle;
return middle;
- else if (s < s
tate
)
+ else if (s < s
0
)
low = middle + 1;
else
high = middle - 1;
}
low = middle + 1;
else
high = middle - 1;
}
-
- assert (0);
- /* NOTREACHED */
- return 0;
}
static void
initialize_F (void)
{
}
static void
initialize_F (void)
{
- goto_number
_t **reads = XCALLOC (goto_number_t *
, ngotos);
- goto_number
_t *edge = XCALLOC (goto_number_t
, ngotos + 1);
+ goto_number
**reads = CALLOC (reads
, ngotos);
+ goto_number
*edge = CALLOC (edge
, ngotos + 1);
int nedges = 0;
int i;
int nedges = 0;
int i;
@@
-177,8
+177,8
@@
initialize_F (void)
for (i = 0; i < ngotos; i++)
{
for (i = 0; i < ngotos; i++)
{
- state_number
_t
stateno = to_state[i];
- transitions
_t
*sp = states[stateno]->transitions;
+ state_number stateno = to_state[i];
+ transitions *sp = states[stateno]->transitions;
int j;
FOR_EACH_SHIFT (sp, j)
int j;
FOR_EACH_SHIFT (sp, j)
@@
-186,14
+186,14
@@
initialize_F (void)
for (; j < sp->num; j++)
{
for (; j < sp->num; j++)
{
- symbol_number
_t symbol
= TRANSITION_SYMBOL (sp, j);
- if (nullable[sym
bol
])
- edge[nedges++] = map_goto (stateno, sym
bol
);
+ symbol_number
sym
= TRANSITION_SYMBOL (sp, j);
+ if (nullable[sym
- ntokens
])
+ edge[nedges++] = map_goto (stateno, sym);
}
if (nedges)
{
}
if (nedges)
{
-
reads[i] = XCALLOC (goto_number_t
, nedges + 1);
+
CALLOC (reads[i]
, nedges + 1);
memcpy (reads[i], edge, nedges * sizeof (edge[0]));
reads[i][nedges] = -1;
nedges = 0;
memcpy (reads[i], edge, nedges * sizeof (edge[0]));
reads[i][nedges] = -1;
nedges = 0;
@@
-211,13
+211,13
@@
initialize_F (void)
static void
static void
-add_lookback_edge (state
_t *state, rule_t *rule
, int gotono)
+add_lookback_edge (state
*s, rule *r
, int gotono)
{
{
- int r
= state_reduction_find (state, rule
);
- goto_list
_t *sp = XCALLOC (goto_list_t
, 1);
- sp->next = lookback[(s
tate->reductions->lookaheads - LA) + r
];
+ int r
i = state_reduction_find (s, r
);
+ goto_list
*sp = MALLOC (sp
, 1);
+ sp->next = lookback[(s
->reductions->lookaheads - LA) + ri
];
sp->value = gotono;
sp->value = gotono;
- lookback[(s
tate->reductions->lookaheads - LA) + r
] = sp;
+ lookback[(s
->reductions->lookaheads - LA) + ri
] = sp;
}
}
@@
-225,50
+225,50
@@
add_lookback_edge (state_t *state, rule_t *rule, int gotono)
static void
build_relations (void)
{
static void
build_relations (void)
{
- goto_number
_t *edge = XCALLOC (goto_number_t
, ngotos + 1);
- state_number
_t *states1 = XCALLOC (state_number_t
, ritem_longest_rhs () + 1);
+ goto_number
*edge = CALLOC (edge
, ngotos + 1);
+ state_number
*states1 = CALLOC (states1
, ritem_longest_rhs () + 1);
int i;
int i;
-
includes = XCALLOC (goto_number_t *
, ngotos);
+
CALLOC (includes
, ngotos);
for (i = 0; i < ngotos; i++)
{
int nedges = 0;
for (i = 0; i < ngotos; i++)
{
int nedges = 0;
- symbol_number
_t
symbol1 = states[to_state[i]]->accessing_symbol;
- rule
_t
**rulep;
+ symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
+ rule **rulep;
- for (rulep = derives[symbol1]; *rulep; rulep++)
+ for (rulep = derives[symbol1
- ntokens
]; *rulep; rulep++)
{
{
-
int
done;
+
bool
done;
int length = 1;
int length = 1;
- item_number
_t
*rp;
- state
_t *state
= states[from_state[i]];
- states1[0] = s
tate
->number;
+ item_number *rp;
+ state
*s
= states[from_state[i]];
+ states1[0] = s->number;
for (rp = (*rulep)->rhs; *rp >= 0; rp++)
{
for (rp = (*rulep)->rhs; *rp >= 0; rp++)
{
- s
tate = transitions_to (state
->transitions,
-
item_number_as_symbol_number (*rp));
- states1[length++] = s
tate
->number;
+ s
= transitions_to (s
->transitions,
+ item_number_as_symbol_number (*rp));
+ states1[length++] = s->number;
}
}
- if (!s
tate
->consistent)
- add_lookback_edge (s
tate
, *rulep, i);
+ if (!s->consistent)
+ add_lookback_edge (s, *rulep, i);
length--;
length--;
- done =
0
;
+ done =
false
;
while (!done)
{
while (!done)
{
- done =
1
;
+ done =
true
;
rp--;
/* JF added rp>=ritem && I hope to god its right! */
if (rp >= ritem && ISVAR (*rp))
{
rp--;
/* JF added rp>=ritem && I hope to god its right! */
if (rp >= ritem && ISVAR (*rp))
{
- /* Downcasting from item_number
_t to symbol_number_t.
*/
+ /* Downcasting from item_number
to symbol_number.
*/
edge[nedges++] = map_goto (states1[--length],
item_number_as_symbol_number (*rp));
edge[nedges++] = map_goto (states1[--length],
item_number_as_symbol_number (*rp));
- if (nullable[*rp])
- done =
0
;
+ if (nullable[*rp
- ntokens
])
+ done =
false
;
}
}
}
}
}
}
@@
-276,7
+276,7
@@
build_relations (void)
if (nedges)
{
int j;
if (nedges)
{
int j;
-
includes[i] = XCALLOC (goto_number_t
, nedges + 1);
+
CALLOC (includes[i]
, nedges + 1);
for (j = 0; j < nedges; j++)
includes[i][j] = edge[j];
includes[i][nedges] = -1;
for (j = 0; j < nedges; j++)
includes[i][j] = edge[j];
includes[i][nedges] = -1;
@@
-309,7
+309,7
@@
static void
compute_lookaheads (void)
{
size_t i;
compute_lookaheads (void)
{
size_t i;
- goto_list
_t
*sp;
+ goto_list *sp;
for (i = 0; i < nLA; i++)
for (sp = lookback[i]; sp; sp = sp->next)
for (i = 0; i < nLA; i++)
for (sp = lookback[i]; sp; sp = sp->next)
@@
-317,25
+317,25
@@
compute_lookaheads (void)
/* Free LOOKBACK. */
for (i = 0; i < nLA; i++)
/* Free LOOKBACK. */
for (i = 0; i < nLA; i++)
- LIST_FREE (goto_list
_t
, lookback[i]);
+ LIST_FREE (goto_list, lookback[i]);
XFREE (lookback);
bitsetv_free (F);
}
XFREE (lookback);
bitsetv_free (F);
}
-/*-----------------------------------------------------------
----
.
-| Count the number of lookaheads required for S
TATE
(NLOOKAHEADS |
-| member).
|
-`-----------------------------------------------------------
----
*/
+/*-----------------------------------------------------------.
+| Count the number of lookaheads required for S (NLOOKAHEADS |
+| member). |
+`-----------------------------------------------------------*/
static int
static int
-state_lookaheads_count (state
_t *state
)
+state_lookaheads_count (state
*s
)
{
int k;
int nlookaheads = 0;
{
int k;
int nlookaheads = 0;
- reductions
_t *rp = state
->reductions;
- transitions
_t *sp = state
->transitions;
+ reductions
*rp = s
->reductions;
+ transitions
*sp = s
->transitions;
/* We need a lookahead either to distinguish different
reductions (i.e., there are two or more), or to distinguish a
/* We need a lookahead either to distinguish different
reductions (i.e., there are two or more), or to distinguish a
@@
-346,12
+346,12
@@
state_lookaheads_count (state_t *state)
!TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
nlookaheads += rp->num;
else
!TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
nlookaheads += rp->num;
else
- s
tate
->consistent = 1;
+ s->consistent = 1;
for (k = 0; k < sp->num; k++)
if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
{
for (k = 0; k < sp->num; k++)
if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
{
- s
tate
->consistent = 0;
+ s->consistent = 0;
break;
}
break;
}
@@
-366,7
+366,7
@@
state_lookaheads_count (state_t *state)
static void
initialize_LA (void)
{
static void
initialize_LA (void)
{
- state_number
_t
i;
+ state_number i;
bitsetv pLA;
/* Compute the total number of reductions requiring a lookahead. */
bitsetv pLA;
/* Compute the total number of reductions requiring a lookahead. */
@@
-378,7
+378,7
@@
initialize_LA (void)
nLA = 1;
pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
nLA = 1;
pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
-
lookback = XCALLOC (goto_list_t *
, nLA);
+
CALLOC (lookback
, nLA);
/* Initialize the members LOOKAHEADS for each state which reductions
require lookaheads. */
/* Initialize the members LOOKAHEADS for each state which reductions
require lookaheads. */
@@
-401,12
+401,12
@@
initialize_LA (void)
static void
lookaheads_print (FILE *out)
{
static void
lookaheads_print (FILE *out)
{
- state_number
_t
i;
+ state_number i;
int j, k;
fprintf (out, "Lookaheads: BEGIN\n");
for (i = 0; i < nstates; ++i)
{
int j, k;
fprintf (out, "Lookaheads: BEGIN\n");
for (i = 0; i < nstates; ++i)
{
- reductions
_t
*reds = states[i]->reductions;
+ reductions *reds = states[i]->reductions;
bitset_iterator iter;
int nlookaheads = 0;
bitset_iterator iter;
int nlookaheads = 0;
@@
-448,7
+448,7
@@
lalr (void)
void
lalr_free (void)
{
void
lalr_free (void)
{
- state_number
_t
s;
+ state_number s;
for (s = 0; s < nstates; ++s)
states[s]->reductions->lookaheads = NULL;
bitsetv_free (LA);
for (s = 0; s < nstates; ++s)
states[s]->reductions->lookaheads = NULL;
bitsetv_free (LA);