File: [local] / src / usr.bin / yacc / lr0.c (download)
Revision 1.18, Thu Mar 13 01:18:22 2014 UTC (10 years, 3 months ago) by tedu
Branch: MAIN
CVS Tags: OPENBSD_7_5_BASE, OPENBSD_7_5, OPENBSD_7_4_BASE, OPENBSD_7_4, OPENBSD_7_3_BASE, OPENBSD_7_3, OPENBSD_7_2_BASE, OPENBSD_7_2, OPENBSD_7_1_BASE, OPENBSD_7_1, OPENBSD_7_0_BASE, OPENBSD_7_0, OPENBSD_6_9_BASE, OPENBSD_6_9, OPENBSD_6_8_BASE, OPENBSD_6_8, OPENBSD_6_7_BASE, OPENBSD_6_7, OPENBSD_6_6_BASE, OPENBSD_6_6, OPENBSD_6_5_BASE, OPENBSD_6_5, OPENBSD_6_4_BASE, OPENBSD_6_4, OPENBSD_6_3_BASE, OPENBSD_6_3, OPENBSD_6_2_BASE, OPENBSD_6_2, OPENBSD_6_1_BASE, OPENBSD_6_1, OPENBSD_6_0_BASE, OPENBSD_6_0, OPENBSD_5_9_BASE, OPENBSD_5_9, OPENBSD_5_8_BASE, OPENBSD_5_8, OPENBSD_5_7_BASE, OPENBSD_5_7, OPENBSD_5_6_BASE, OPENBSD_5_6, HEAD Changes since 1.17: +13 -33 lines
collapse variable declarations
|
/* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $ */
/* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 jtc Exp $ */
/*
* Copyright (c) 1989 The Regents of the University of California.
* All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* Robert Paul Corbett.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include "defs.h"
extern short *itemset;
extern short *itemsetend;
extern unsigned *ruleset;
int nstates;
core *first_state;
shifts *first_shift;
reductions *first_reduction;
short get_state(int);
core *new_state(int);
void allocate_itemsets(void);
void allocate_storage(void);
void append_states(void);
void free_storage(void);
void generate_states(void);
void initialize_states(void);
void new_itemsets(void);
void save_shifts(void);
void save_reductions(void);
void set_derives(void);
void print_derives(void);
void set_nullable(void);
static core **state_set;
static core *this_state;
static core *last_state;
static shifts *last_shift;
static reductions *last_reduction;
static int nshifts;
static short *shift_symbol;
static short *redset;
static short *shiftset;
static short **kernel_base;
static short **kernel_end;
static short *kernel_items;
void
allocate_itemsets(void)
{
short *itemp, *item_end;
int i, count, max, symbol;
short *symbol_count;
count = 0;
symbol_count = NEW2(nsyms, short);
item_end = ritem + nitems;
for (itemp = ritem; itemp < item_end; itemp++) {
symbol = *itemp;
if (symbol >= 0) {
count++;
symbol_count[symbol]++;
}
}
kernel_base = NEW2(nsyms, short *);
kernel_items = NEW2(count, short);
count = 0;
max = 0;
for (i = 0; i < nsyms; i++) {
kernel_base[i] = kernel_items + count;
count += symbol_count[i];
if (max < symbol_count[i])
max = symbol_count[i];
}
shift_symbol = symbol_count;
kernel_end = NEW2(nsyms, short *);
}
void
allocate_storage(void)
{
allocate_itemsets();
shiftset = NEW2(nsyms, short);
redset = NEW2(nrules + 1, short);
state_set = NEW2(nitems, core *);
}
void
append_states(void)
{
int i, j, symbol;
#ifdef TRACE
fprintf(stderr, "Entering append_states()\n");
#endif
for (i = 1; i < nshifts; i++) {
symbol = shift_symbol[i];
j = i;
while (j > 0 && shift_symbol[j - 1] > symbol) {
shift_symbol[j] = shift_symbol[j - 1];
j--;
}
shift_symbol[j] = symbol;
}
for (i = 0; i < nshifts; i++) {
symbol = shift_symbol[i];
shiftset[i] = get_state(symbol);
}
}
void
free_storage(void)
{
free(shift_symbol);
free(redset);
free(shiftset);
free(kernel_base);
free(kernel_end);
free(kernel_items);
free(state_set);
}
void
generate_states(void)
{
allocate_storage();
itemset = NEW2(nitems, short);
ruleset = NEW2(WORDSIZE(nrules), unsigned);
set_first_derives();
initialize_states();
while (this_state) {
closure(this_state->items, this_state->nitems);
save_reductions();
new_itemsets();
append_states();
if (nshifts > 0)
save_shifts();
this_state = this_state->next;
}
finalize_closure();
free_storage();
}
short
get_state(int symbol)
{
int n, found, key;
short *isp1, *isp2, *iend;
core *sp;
#ifdef TRACE
fprintf(stderr, "Entering get_state(%d)\n", symbol);
#endif
isp1 = kernel_base[symbol];
iend = kernel_end[symbol];
n = iend - isp1;
key = *isp1;
assert(0 <= key && key < nitems);
sp = state_set[key];
if (sp) {
found = 0;
while (!found) {
if (sp->nitems == n) {
found = 1;
isp1 = kernel_base[symbol];
isp2 = sp->items;
while (found && isp1 < iend) {
if (*isp1++ != *isp2++)
found = 0;
}
}
if (!found) {
if (sp->link) {
sp = sp->link;
} else {
sp = sp->link = new_state(symbol);
found = 1;
}
}
}
} else {
state_set[key] = sp = new_state(symbol);
}
return (sp->number);
}
void
initialize_states(void)
{
int i;
short *start_derives;
core *p;
start_derives = derives[start_symbol];
for (i = 0; start_derives[i] >= 0; ++i)
continue;
p = malloc(sizeof(core) + i * sizeof(short));
if (p == NULL)
no_space();
p->next = 0;
p->link = 0;
p->number = 0;
p->accessing_symbol = 0;
p->nitems = i;
for (i = 0; start_derives[i] >= 0; ++i)
p->items[i] = rrhs[start_derives[i]];
first_state = last_state = this_state = p;
nstates = 1;
}
void
new_itemsets(void)
{
int i, shiftcount;
short *isp, *ksp;
int symbol;
memset(kernel_end, 0, nsyms * sizeof(short *));
shiftcount = 0;
isp = itemset;
while (isp < itemsetend) {
i = *isp++;
symbol = ritem[i];
if (symbol > 0) {
ksp = kernel_end[symbol];
if (!ksp) {
shift_symbol[shiftcount++] = symbol;
ksp = kernel_base[symbol];
}
*ksp++ = i + 1;
kernel_end[symbol] = ksp;
}
}
nshifts = shiftcount;
}
core *
new_state(int symbol)
{
int n;
core *p;
short *isp1, *isp2, *iend;
#ifdef TRACE
fprintf(stderr, "Entering new_state(%d)\n", symbol);
#endif
if (nstates >= MAXSHORT)
fatal("too many states");
isp1 = kernel_base[symbol];
iend = kernel_end[symbol];
n = iend - isp1;
p = allocate(sizeof(core) + (n - 1) * sizeof(short));
p->accessing_symbol = symbol;
p->number = nstates;
p->nitems = n;
isp2 = p->items;
while (isp1 < iend)
*isp2++ = *isp1++;
last_state->next = p;
last_state = p;
nstates++;
return (p);
}
void
save_shifts(void)
{
shifts *p;
short *sp1, *sp2, *send;
p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
p->number = this_state->number;
p->nshifts = nshifts;
sp1 = shiftset;
sp2 = p->shift;
send = shiftset + nshifts;
while (sp1 < send)
*sp2++ = *sp1++;
if (last_shift) {
last_shift->next = p;
last_shift = p;
} else {
first_shift = p;
last_shift = p;
}
}
void
save_reductions(void)
{
short *isp, *rp1, *rp2;
int item, count;
reductions *p;
short *rend;
count = 0;
for (isp = itemset; isp < itemsetend; isp++) {
item = ritem[*isp];
if (item < 0) {
redset[count++] = -item;
}
}
if (count) {
p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
p->number = this_state->number;
p->nreds = count;
rp1 = redset;
rp2 = p->rules;
rend = rp1 + count;
while (rp1 < rend)
*rp2++ = *rp1++;
if (last_reduction) {
last_reduction->next = p;
last_reduction = p;
} else {
first_reduction = p;
last_reduction = p;
}
}
}
void
set_derives(void)
{
int i, k, lhs;
short *rules;
derives = NEW2(nsyms, short *);
rules = NEW2(nvars + nrules, short);
k = 0;
for (lhs = start_symbol; lhs < nsyms; lhs++) {
derives[lhs] = rules + k;
for (i = 0; i < nrules; i++) {
if (rlhs[i] == lhs) {
rules[k] = i;
k++;
}
}
rules[k] = -1;
k++;
}
#ifdef DEBUG
print_derives();
#endif
}
void
free_derives(void)
{
free(derives[start_symbol]);
free(derives);
}
#ifdef DEBUG
void
print_derives(void)
{
int i;
short *sp;
printf("\nDERIVES\n\n");
for (i = start_symbol; i < nsyms; i++) {
printf("%s derives ", symbol_name[i]);
for (sp = derives[i]; *sp >= 0; sp++) {
printf(" %d", *sp);
}
putchar('\n');
}
putchar('\n');
}
#endif
void
set_nullable(void)
{
int i, j;
int empty;
int done;
nullable = calloc(1, nsyms);
if (nullable == NULL)
no_space();
done = 0;
while (!done) {
done = 1;
for (i = 1; i < nitems; i++) {
empty = 1;
while ((j = ritem[i]) >= 0) {
if (!nullable[j])
empty = 0;
++i;
}
if (empty) {
j = rlhs[-j];
if (!nullable[j]) {
nullable[j] = 1;
done = 0;
}
}
}
}
#ifdef DEBUG
for (i = 0; i < nsyms; i++) {
if (nullable[i])
printf("%s is nullable\n", symbol_name[i]);
else
printf("%s is not nullable\n", symbol_name[i]);
}
#endif
}
void
free_nullable(void)
{
free(nullable);
}
void
lr0(void)
{
set_derives();
set_nullable();
generate_states();
}