grwalter@watmath.waterloo.edu (Fred Walter) (09/15/87)
This version of bison is an update to the version on FISH disk 51,
which was an update to the version on disk 4 that Johan Widen did.
The changes that Doug Leavitt supplied in the Diffs directory
were found to be necessary, so I merged them into the source,
along with making some other minor changes.
The problem that was fixed was that bison was causing the AMIGA to
guru when used on sufficiently large/complex source files.
Only the files that were changed are included in the following shar
file. (ie. you need a copy of the sources from FISH disk 51 to
compile this). If people desire, I can post the uuencoded binary (all
100k+ of it).
There probably are still more bugs left.
... sigh.
G. R. Walter
grwalter@watmath.waterloo.cdn
# This is a shell archive.
# Remove everything above and including the cut line.
# Then run the rest of the file through sh.
#----cut here-----cut here-----cut here-----cut here----#
#!/bin/sh
# Xshar: Extended Shell Archiver.
# This archive created: Tue Sep 15 14:06:14 1987
# By: Craig Norborg (Purdue University Computing Center)
# Run the following text with /bin/sh to create:
# BISON.LNK
# LR0.c
# MAKE.BISON
# Makefile
# README
# allocate.c
# calc.y
# closure.c
# new.h
# print.c
# string.h
# symtab.c
# warshall.c
cat << \SHAR_EOF > BISON.LNK
FROM LIB:c.o+allocate.o+warshall.o+closure.o+output.o
FROM reader.o+lr0.o+symtab.o+nullable.o+lex.o+print.o
FROM files.o+main.o+derives.o+lalr.o+conflicts.o
FROM gram.o+getargs.o
TO bison
LIB LIB:lc.lib+LIB:amiga.lib
NODEBUG
SHAR_EOF
cat << \SHAR_EOF > LR0.c
/* Generate the nondeterministic finite state machine for bison,
copyright (C) 1984 Bob Corbett and Richard Stallman
Permission is granted to anyone to make or distribute verbatim copies of this program
provided that the copyright notice and this permission notice are preserved;
and provided that the recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.
Permission is granted to distribute derived works or enhanced versions of
this program under the above conditions with the additional condition
that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.
Anything distributed as part of a package containing portions derived
from this program, which cannot in current practice perform its function usefully
in the absense of what was derived directly from this program,
is to be considered as forming, together with the latter,
a single work derived from this program,
which must be entirely covered by a permission notice identical to this one
in order for distribution of the package to be permitted.
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them. Help stamp out software-hoarding! */
/* See comments in state.h for the data structures that represent it.
The entry point is generate_states. */
#include <stdio.h>
#include "machine.h"
#include "new.h"
#include "gram.h"
#include "state.h"
extern short *itemset;
extern short *itemsetend;
int nstates;
int final_state;
core *first_state;
shifts *first_shift;
reductions *first_reduction;
int get_state();
core *new_state();
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;
/* hash table for states, to recognize equivalent ones. */
#define STATE_TABLE_SIZE 1009
static core **state_table;
allocate_itemsets()
{
register short *itemp;
register int symbol;
register int i;
register count;
register int maxcount;
register short *symbol_count;
count = 0;
symbol_count = NEW2(nsyms, short);
itemp = ritem;
symbol = *itemp++;
while (symbol)
{
if (symbol > 0)
{
count++;
symbol_count[symbol]++;
}
symbol = *itemp++;
}
/* see comments before new-itemset. All the vectors of items
live inside kernel_items. The number of active items after
some symbol cannot be more than the number of times that symbol
appears as an item, which is symbol_count[symbol].
We allocate that much space for each symbol. */
kernel_base = NEW2(nsyms, short *);
kernel_items = NEW2(count, short);
count = 0;
maxcount = 0;
for (i = 0; i < nsyms; i++)
{
kernel_base[i] = kernel_items + count;
count += symbol_count[i];
if (maxcount < symbol_count[i])
maxcount = symbol_count[i];
}
shift_symbol = symbol_count;
kernel_end = NEW2(nsyms, short *);
}
allocate_storage()
{
allocate_itemsets();
shiftset = NEW2(nsyms, short);
redset = NEW2(nrules + 1, short);
state_table = NEW2(STATE_TABLE_SIZE, core *);
}
free_storage()
{
FREE(shift_symbol);
FREE(redset);
FREE(shiftset);
FREE(kernel_base);
FREE(kernel_end);
FREE(kernel_items);
FREE(state_table);
}
/* compute the nondeterministic finite state machine (see state.h for details)
from the grammar. */
generate_states()
{
allocate_storage();
initialize_closure(nitems);
initialize_states();
while (this_state)
{
/* Set up ruleset and itemset for the transitions out of this state.
ruleset gets a 1 bit for each rule that could reduce now.
itemset gets a vector of all the items that could be accepted next. */
closure(this_state->items, this_state->nitems);
/* record the reductions allowed out of this state */
save_reductions();
/* find the itemsets of the states that shifts can reach */
new_itemsets();
/* find or create the core structures for those states */
append_states();
/* create the shifts structures for the shifts to those states,
now that the state numbers transitioning to are known */
if (nshifts > 0)
save_shifts();
/* states are queued when they are created; process them all */
this_state = this_state->next;
}
/* discard various storage */
finalize_closure();
free_storage();
/* set up initial and final states as parser wants them */
augment_automaton();
}
/* Find which symbols can be shifted in the current state,
and for each one record which items would be active after that shift.
Uses the contents of itemset.
shift_symbol is set to a vector of the symbols that can be shifted.
For each symbol in the grammer, kernel_base[symbol] points to
a vector of item numbers activated if that symbol is shifted,
and kernel_end[symbol] points after the end of that vector. */
new_itemsets()
{
register int i;
register int shiftcount;
register short *isp;
register short *ksp;
register int symbol;
#ifdef TRACE
fprintf(stderr, "Entering new_itemsets\n");
#endif
for (i = 0; i < nsyms; i++)
kernel_end[i] = NULL;
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;
}
/* Use the information computed by new_itemset to find the state numbers
reached by each shift transition from the current state.
shiftset is set up as a vector of state numbers of those states. */
append_states()
{
register int i;
register int j;
register int symbol;
#ifdef TRACE
fprintf(stderr, "Entering append_states\n");
#endif
/* first sort shift_symbol into increasing order */
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);
}
}
/* find the state number for the state we would get to
(from the current state) by shifting symbol.
Create a new state if no equivalent one exists already.
Used by append_states */
int
get_state(symbol)
int symbol;
{
register int key;
register short *isp1;
register short *isp2;
register short *iend;
register core *sp;
register int found;
int n;
#ifdef TRACE
fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
#endif
isp1 = kernel_base[symbol];
iend = kernel_end[symbol];
n = iend - isp1;
/* add up the target state's active item numbers to get a hash key */
key = 0;
while (isp1 < iend)
key += *isp1++;
key = key % STATE_TABLE_SIZE;
sp = state_table[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 /* bucket exhausted and no match */
{
sp = sp->link = new_state(symbol);
found = 1;
}
}
}
}
else /* bucket is empty */
{
state_table[key] = sp = new_state(symbol);
}
return ((int) sp->number);
}
/* subroutine of get_state. create a new state for those items, if necessary. */
core *
new_state(symbol)
int symbol;
{
register int n;
register core *p;
register short *isp1;
register short *isp2;
register short *iend;
#ifdef TRACE
fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
#endif
if (nstates >= MAXSHORT)
toomany("states");
isp1 = kernel_base[symbol];
iend = kernel_end[symbol];
n = iend - isp1;
p = (core *) allocate((unsigned) (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);
}
initialize_states()
{
register core *p;
p = (core *) allocate((unsigned) (sizeof(core) - sizeof(short)));
first_state = last_state = this_state = p;
nstates = 1;
}
save_shifts()
{
register shifts *p;
register short *sp1;
register short *sp2;
register short *send;
p = (shifts *) allocate((unsigned) (sizeof(shifts) +
(nshifts - 1) * sizeof(short)));
p->number = this_state->number;
p->nshifts = nshifts;
sp1 = shiftset;
sp2 = p->shifts;
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;
}
}
/* find which rules can be used for reduction transitions from the current state
and make a reductions structure for the state to record their rule numbers. */
save_reductions()
{
register short *isp;
register short *rp1;
register short *rp2;
register int item;
register int count;
register reductions *p;
short *rend;
/* find and count the active items that represent ends of rules */
count = 0;
for (isp = itemset; isp < itemsetend; isp++)
{
item = ritem[*isp];
if (item < 0)
{
redset[count++] = -item;
}
}
/* make a reductions structure and copy the data into it. */
if (count)
{
p = (reductions *) allocate((unsigned) (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;
}
}
}
/* Make sure that the initial state has a shift that accepts the
grammar's start symbol and goes to the next-to-final state,
which has a shift going to the final state, which has a shift
to the termination state.
Create such states and shifts if they don't happen to exist already. */
augment_automaton()
{
register int i;
register int k;
register core *statep;
register shifts *sp;
register shifts *sp2;
register shifts *sp1;
sp = first_shift;
if (sp)
{
if (sp->number == 0)
{
k = sp->nshifts;
statep = first_state->next;
while (statep->accessing_symbol < start_symbol
&& statep->number < k)
statep = statep->next;
if (statep->accessing_symbol == start_symbol)
{
k = statep->number;
while (sp->number < k)
{
sp1 = sp;
sp = sp->next;
}
if (sp->number == k)
{
sp2 = (shifts *) allocate((unsigned) (sizeof(shifts)
+ sp->nshifts * sizeof(short)));
sp2->next = sp->next;
sp2->number = k;
sp2->nshifts = sp->nshifts + 1;
sp2->shifts[0] = nstates;
for (i = sp->nshifts; i > 0; i--)
sp2->shifts[i] = sp->shifts[i - 1];
sp1->next = sp2;
FREE(sp);
}
else
{
sp2 = NEW(shifts);
sp2->next = sp;
sp2->number = k;
sp2->nshifts = 1;
sp2->shifts[0] = nstates;
sp1->next = sp2;
if (!sp)
last_shift = sp2;
}
}
else
{
k = statep->number;
sp = first_shift;
sp2 = (shifts *) allocate((unsigned) (sizeof(shifts)
+ sp->nshifts * sizeof(short)));
sp2->next = sp->next;
sp2->nshifts = sp->nshifts + 1;
for (i = 0; i < k; i++)
sp2->shifts[i] = sp->shifts[i];
sp2->shifts[k] = nstates;
for (i = k; i < sp->nshifts; i++)
sp2->shifts[i + 1] = sp->shifts[i];
first_shift = sp2;
if (last_shift == sp)
last_shift = sp2;
FREE(sp);
insert_start_shift();
}
}
else
{
sp = NEW(shifts);
sp->next = first_shift;
sp->nshifts = 1;
sp->shifts[0] = nstates;
first_shift = sp;
insert_start_shift();
}
}
else
{
sp = NEW(shifts);
sp->nshifts = 1;
sp->shifts[0] = nstates;
first_shift = sp;
last_shift = sp;
insert_start_shift();
}
statep = (core *) allocate((unsigned) (sizeof(core) - sizeof(short)));
statep->number = nstates;
last_state->next = statep;
last_state = statep;
sp = NEW(shifts);
sp->number = nstates++;
sp->nshifts = 1;
sp->shifts[0] = nstates;
last_shift->next = sp;
last_shift = sp;
final_state = nstates;
statep = (core *) allocate((unsigned) (sizeof(core) - sizeof(short)));
statep->number = nstates++;
last_state->next = statep;
last_state = statep;
}
/* subroutine of augment_automaton */
insert_start_shift()
{
register core *statep;
register shifts *sp;
statep = (core *) allocate((unsigned) (sizeof(core) - sizeof(short)));
statep->number = nstates;
statep->accessing_symbol = start_symbol;
last_state->next = statep;
last_state = statep;
sp = NEW(shifts);
sp->number = nstates++;
sp->nshifts = 1;
sp->shifts[0] = nstates;
last_shift->next = sp;
last_shift = sp;
}
SHAR_EOF
cat << \SHAR_EOF > MAKE.BISON
lc -damiga -cw #?.c
blink with BISON.LNK
SHAR_EOF
cat << \SHAR_EOF > Makefile
CC = cc
#CFLAGS = -g
LPRFLAGS =
OBJ1 = LR0.o allocate.o closure.o conflicts.o derives.o files.o
OBJ2 = getargs.o gram.o lalr.o lex.o main.o nullable.o output.o
OBJ3 = print.o reader.o symtab.o warshall.o
OBJECTS = $(OBJ1) $(OBJ2) $(OBJ3)
CFILES1 = LR0.c allocate.c closure.c conflicts.c derives.c files.c
CFILES2 = getargs.c gram.c lalr.c lex.c main.c nullable.c output.c
CFILES3 = print.c reader.c symtab.c warshall.c
CFILES = $(CFILES1) $(CFILES2) $(CFILES3)
FILES1 = Makefile files.h gram.h lex.h machine.h new.h state.h
FILES2 = symtab.h types.h
FILES = $(FILES1) $(FILES2) $(CFILES)
start : bison
listing :
pr $(FILES) | lpr $(LPRFLAGS)
lint :
lint $(CFILES)
clean :
rm -f *.o
bison : $(OBJECTS)
$(CC) -o bison $(OBJECTS)
LR0.o : LR0.c
$(CC) $(CFLAGS) -c LR0.c
allocate.o : allocate.c
$(CC) $(CFLAGS) -c allocate.c
closure.o : closure.c
$(CC) $(CFLAGS) -c closure.c
conflicts.o : conflicts.c
$(CC) $(CFLAGS) -c conflicts.c
derives.o : derives.c
$(CC) $(CFLAGS) -c derives.c
files.o : files.c files.h
$(CC) $(CFLAGS) -c files.c
getargs.o : getargs.c
$(CC) $(CFLAGS) -c getargs.c
gram.o : gram.c
$(CC) $(CFLAGS) -c gram.c
lalr.o : lalr.c
$(CC) $(CFLAGS) -c lalr.c
lex.o : lex.c lex.h
$(CC) $(CFLAGS) -c lex.c
main.o : main.c
$(CC) $(CFLAGS) -c main.c
nullable.o : nullable.c
$(CC) $(CFLAGS) -c nullable.c
output.o : output.c
$(CC) $(CFLAGS) -c output.c
print.o : print.c
$(CC) $(CFLAGS) -c print.c
reader.o : reader.c
$(CC) $(CFLAGS) -c reader.c
symtab.o : symtab.c symtab.h
$(CC) $(CFLAGS) -c symtab.c
warshall.o : warshall.c
$(CC) $(CFLAGS) -c warshall.c
SHAR_EOF
cat << \SHAR_EOF > README
This version of bison is an update to the version on FISH disk 51,
which was an update to the version on disk 4 that Johan Widen did.
The changes that Doug Leavitt supplied in the Diffs directory
were found to be necessary, so I merged them into the source,
along with making some other minor changes.
The problem that was fixed was that bison was causing the AMIGA to
guru when used on sufficiently large/complex source files.
To compile this using Lattice C 3.10 just
execute MAKE.BISON
There probably are still more bugs left.
... sigh.
G. R. Walter
grwalter@watmath.waterloo.cdn
SHAR_EOF
cat << \SHAR_EOF > allocate.c
/* Allocate and clear storage for bison,
copyright (C) 1984 Bob Corbett and Richard Stallman
Permission is granted to anyone to make or distribute verbatim copies of this program
provided that the copyright notice and this permission notice are preserved;
and provided that the recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.
Permission is granted to distribute derived works or enhanced versions of
this program under the above conditions with the additional condition
that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.
Anything distributed as part of a package containing portions derived
from this program, which cannot in current practice perform its function usefully
in the absense of what was derived directly from this program,
is to be considered as forming, together with the latter,
a single work derived from this program,
which must be entirely covered by a permission notice identical to this one
in order for distribution of the package to be permitted.
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them. Help stamp out software-hoarding! */
#include <stdio.h>
char *
allocate(n)
register unsigned n;
{
register char *block;
#ifdef amiga
extern char *calloc();
#else
register char *cp;
register char *cend;
extern char *malloc();
#endif
#ifdef amiga
block = calloc(n+4,1);
#else
block = malloc(n);
#endif
if (block == NULL)
{
fprintf(stderr, "storage limit exceeded");
done(1);
}
#ifdef amiga
block[0] = 'A';
block[1] = 'M';
block[2] = 'E';
block[3] = 'N';
return(block+4);
#else
for(cp = block, cend = block+n; cp < cend; *cp++ = 0);
return (block);
#endif
}
#ifdef amiga
void
bisonfree(loc)
char *loc;
{
register unsigned long l1, l2;
register char *p;
if (loc == (char *)0)
return;
l1 = (unsigned long)loc;
l2 = l1 - 4;
if (l2 > l1)
return; /* check for wrap */
p = (char *)l2;
if (p[0] != 'A' || p[1] != 'M' || p[2] != 'E' || p[3] != 'M')
return; /* Not allocated memory */
free(p); /* Free the real location */
}
#endif
SHAR_EOF
cat << \SHAR_EOF > calc.y
%{
#include <ctype.h>
int regs[26];
int base;
int val;
int printflag;
%}
%start stmt
%token DIGIT LETTER EXIT
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS
%%
stmt : expr
{ val = $1; printflag = 1; }
| LETTER '=' expr
{ regs[$1] = $3; }
| EXIT
{ exit(0); }
;
expr : '(' expr ')'
{ $$ = $2; }
| expr '+' expr
{ if ($1 == 69)
{
$$ = 2;
printf ("$1 became %d\n", $1);
$1 = 69;
}
$$ = $1 + $3; }
| expr '-' expr
{ $$ = $1 - $3; }
| expr '*' expr
{ $$ = $1 * $3; }
| expr '/' expr
{ $$ = $1 / $3; }
| expr '%' expr
{ $$ = $1 % $3; }
| expr '|' expr
{ $$ = $1 | $3; }
| expr '&' expr
{ $$ = $1 & $3; }
| '-' expr %prec UMINUS
{ $$ = - $2; }
| LETTER
{ $$ = regs[$1]; }
| number
/* | '?'
{ yydebug = !yydebug; }
*/ ;
number : DIGIT
{ $$ = $1; base = ($1 == 0) ? 8 : 10; }
| number DIGIT
{ $$ = base * $1 + $2; }
;
%%
static int eol;
int
yylex()
{
int c;
while ( (c=getchar()) == ' ') {}
if (c == '\n')
{ eol = 1;
return 0; }
if (c == 'Q')
return(EXIT);
if (islower(c))
{
yylval = c - 'a';
return (LETTER);
}
if (isdigit(c))
{
yylval = c - '0';
return (DIGIT);
}
return (c);
}
yyerror(s)
char *s;
{
printf("%s\n", s);
}
main()
{
for (;;)
{
eol = 0;
printflag = 0;
if (yyparse()) printflag = 0;
if (printflag) printf("%d\n", val);
while (!eol) yylex();
}
}
SHAR_EOF
cat << \SHAR_EOF > closure.c
/* Subroutines for bison, copyright (C) 1984 Bob Corbett and Richard Stallman
Permission is granted to anyone to make or distribute verbatim copies of this program
provided that the copyright notice and this permission notice are preserved;
and provided that the recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.
Permission is granted to distribute derived works or enhanced versions of
this program under the above conditions with the additional condition
that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.
Anything distributed as part of a package containing portions derived
from this program, which cannot in current practice perform its function usefully
in the absense of what was derived directly from this program,
is to be considered as forming, together with the latter,
a single work derived from this program,
which must be entirely covered by a permission notice identical to this one
in order for distribution of the package to be permitted.
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them. Help stamp out software-hoarding! */
/* subroutines of file LR0.c.
Entry points:
closure (items, n)
Given a vector of item numbers items, of length n,
set up ruleset and itemset to indicate what rules could be run
and which items could be accepted when those items are the active ones.
ruleset contains a bit for each rule. closure sets the bits
for all rules which could potentially describe the next input to be read.
itemset is a vector of item numbers; itemsetend points to just beyond the end
of the part of it that is significant.
closure places there the indices of all items which represent units of
input that could arrive next.
initialize_closure (n)
Allocates the itemset and ruleset vectors,
and precomputes useful data so that closure can be called.
n is the number of elements to allocate for itemset.
finalize_closure ()
Frees itemset, ruleset and internal data.
*/
#include <stdio.h>
#include "machine.h"
#include "new.h"
#include "gram.h"
extern short **derives;
short *itemset;
short *itemsetend;
static unsigned *ruleset;
/* internal data. See comments before set_fderives and set_firsts. */
static unsigned *fderives;
static unsigned *firsts;
/* number of words required to hold a bit for each rule */
static int rulesetsize;
/* number of words required to hold a bit for each variable */
static int varsetsize;
initialize_closure(n)
int n;
{
itemset = NEW2(n, short);
rulesetsize = WORDSIZE(nrules + 1);
ruleset = NEW2(rulesetsize, unsigned);
set_fderives();
}
/* set fderives to an nvars by nrules matrix of bits
indicating which rules can help derive the beginning of the data
for each nonterminal. For example, if symbol 5 can be derived as
the sequence of symbols 8 3 20, and one of the rules for deriving
symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set. */
set_fderives()
{
register unsigned *rrow;
register unsigned *vrow;
register int j;
register unsigned mask;
register unsigned cword;
register short *rp;
int ruleno;
int i;
fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
set_firsts();
rrow = fderives + ntokens * rulesetsize;
for (i = ntokens; i < nsyms; i++)
{
vrow = firsts + ((i - ntokens) * varsetsize);
cword = *vrow++;
mask = 1;
for (j = ntokens; j < nsyms; j++)
{
if (cword & mask)
{
rp = derives[j];
while ((ruleno = *rp++) > 0)
{
SETBIT(rrow, ruleno);
}
}
mask <<= 1;
if (mask == 0)
{
cword = *vrow++;
mask = 1;
}
}
vrow += varsetsize;
rrow += rulesetsize;
}
#ifdef DEBUG
print_fderives();
#endif
FREE(firsts);
}
/* set firsts to be an nvars by nvars bit matrix indicating which items
can represent the beginning of the input corresponding to which other items.
For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20,
the symbol 8 can be the beginning of the data for symbol 5,
so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */
set_firsts()
{
register unsigned *row;
register int symbol;
register short *sp;
register int rowsize;
int i;
varsetsize = rowsize = WORDSIZE(nvars);
firsts = NEW2(nvars * rowsize, unsigned);
row = firsts;
for (i = ntokens; i < nsyms; i++)
{
sp = derives[i];
while (*sp >= 0)
{
symbol = ritem[rrhs[*sp++]];
if (ISVAR(symbol))
{
symbol -= ntokens;
SETBIT(row, symbol);
}
}
row += rowsize;
}
RTC(firsts, nvars);
#ifdef DEBUG
print_firsts();
#endif
}
closure(core, n)
short *core;
int n;
{
register int ruleno;
register unsigned word;
register unsigned mask;
register short *csp;
register unsigned *dsp;
register unsigned *rsp;
short *csend;
unsigned *rsend;
int symbol;
int itemno;
rsp = ruleset;
rsend = ruleset + rulesetsize;
csend = core + n;
if (n == 0)
{
dsp = fderives + start_symbol * rulesetsize;
while (rsp < rsend)
*rsp++ = *dsp++;
}
else
{
while (rsp < rsend)
*rsp++ = 0;
csp = core;
while (csp < csend)
{
symbol = ritem[*csp++];
if (ISVAR(symbol))
{
dsp = fderives + symbol * rulesetsize;
rsp = ruleset;
while (rsp < rsend)
*rsp++ |= *dsp++;
}
}
}
ruleno = 0;
itemsetend = itemset;
csp = core;
rsp = ruleset;
while (rsp < rsend)
{
word = *rsp++;
if (word == 0)
{
ruleno += BITS_PER_WORD;
}
else
{
mask = 1;
while (mask)
{
if (word & mask)
{
itemno = rrhs[ruleno];
while (csp < csend && *csp < itemno)
*itemsetend++ = *csp++;
*itemsetend++ = itemno;
}
mask <<= 1;
ruleno++;
}
}
}
while (csp < csend)
*itemsetend++ = *csp++;
#ifdef DEBUG
print_closure(n);
#endif
}
finalize_closure()
{
FREE(itemset);
FREE(ruleset);
FREE(fderives + ntokens * rulesetsize);
}
#ifdef DEBUG
print_closure(n)
int n;
{
register short *isp;
printf("\n\nn = %d\n\n", n);
for (isp = itemset; isp < itemsetend; isp++)
printf(" %d\n", *isp);
}
print_firsts()
{
register int i;
register int j;
register unsigned *rowp;
register unsigned cword;
register unsigned mask;
extern char **tags;
printf("\n\n\nFIRSTS\n\n");
for (i = ntokens; i < nsyms; i++)
{
printf("\n\n%s firsts\n\n", tags[i]);
rowp = firsts + ((i - ntokens) * vrowsize);
cword = *rowp++;
mask = 1;
for (j = 0; j < nsyms; j++)
{
if (cword & mask)
printf(" %s\n", tags[j + ntokens]);
mask <<= 1;
if (mask == 0)
{
cword = *rowp++;
mask = 1;
}
}
}
}
print_fderives()
{
register int i;
register int j;
register unsigned *rp;
register unsigned cword;
register unsigned mask;
extern char **tags;
printf("\n\n\nFDERIVES\n");
for (i = ntokens; i < nsyms; i++)
{
printf("\n\n%s derives\n\n", tags[i]);
rp = fderives + i * rrowsize;
cword = *rp++;
mask = 1;
for (j = 0; j <= nrules; j++)
{
if (cword & mask)
printf(" %d\n", j);
mask <<= 1;
if (mask == 0)
{
cword = *rp++;
mask = 1;
}
}
}
fflush(stdout);
}
#endif
SHAR_EOF
cat << \SHAR_EOF > new.h
/* Storage allocation interface for bison,
copyright (C) 1984 Bob Corbett and Richard Stallman
Permission is granted to anyone to make or distribute verbatim copies of this program
provided that the copyright notice and this permission notice are preserved;
and provided that the recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.
Permission is granted to distribute derived works or enhanced versions of
this program under the above conditions with the additional condition
that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.
Anything distributed as part of a package containing portions derived
from this program, which cannot in current practice perform its function usefully
in the absense of what was derived directly from this program,
is to be considered as forming, together with the latter,
a single work derived from this program,
which must be entirely covered by a permission notice identical to this one
in order for distribution of the package to be permitted.
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them. Help stamp out software-hoarding! */
#define NEW(t) ((t *) allocate((unsigned) sizeof(t)))
#define NEW2(n, t) ((t *) allocate((unsigned) ((n) * sizeof(t))))
#ifdef amiga
#define FREE(x) bisonfree(x);
#else
#define FREE(x) {if(x) free((char *) (x));}
#endif
extern char *allocate();
SHAR_EOF
cat << \SHAR_EOF > print.c
/* Print information on generated parser, for bison,
copyright (C) 1984 Bob Corbett and Richard Stallman
Permission is granted to anyone to make or distribute verbatim copies of this program
provided that the copyright notice and this permission notice are preserved;
and provided that the recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.
Permission is granted to distribute derived works or enhanced versions of
this program under the above conditions with the additional condition
that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.
Anything distributed as part of a package containing portions derived
from this program, which cannot in current practice perform its function usefully
in the absense of what was derived directly from this program,
is to be considered as forming, together with the latter,
a single work derived from this program,
which must be entirely covered by a permission notice identical to this one
in order for distribution of the package to be permitted.
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them. Help stamp out software-hoarding! */
#include <stdio.h>
#include "machine.h"
#include "new.h"
#include "files.h"
#include "gram.h"
#include "state.h"
extern char **tags;
extern int nstates;
extern short *accessing_symbol;
extern core **state_table;
extern shifts **shift_table;
extern reductions **reduction_table;
extern char *consistent;
extern char any_conflicts;
terse()
{
if (any_conflicts)
{
conflict_log();
}
}
verbose()
{
register int i;
if (any_conflicts)
verbose_conflict_log();
for (i = 0; i < nstates; i++)
{
print_state(i);
}
}
print_state(state)
int state;
{
fprintf(foutput, "\n\nstate %d\n\n", state);
print_core(state);
print_actions(state);
}
print_core(state)
int state;
{
register int i;
register int k;
register int rule;
register core *statep;
register short *sp;
register short *sp1;
statep = state_table[state];
k = statep->nitems;
if (k == 0) return;
for (i = 0; i < k; i++)
{
sp1 = sp = ritem + statep->items[i];
while (*sp > 0)
sp++;
rule = -(*sp);
fprintf(foutput, " %s -> ", tags[rlhs[rule]]);
for (sp = ritem + rrhs[rule]; sp < sp1; sp++)
{
fprintf(foutput, "%s ", tags[*sp]);
}
putc('.', foutput);
while (*sp > 0)
{
fprintf(foutput, " %s", tags[*sp]);
sp++;
}
putc('\n', foutput);
}
putc('\n', foutput);
}
print_actions(state)
int state;
{
register int i;
register int k;
register int state1;
register int symbol;
register shifts *shiftp;
register reductions *redp;
register int rule;
shiftp = shift_table[state];
redp = reduction_table[state];
if (!shiftp && !redp)
{
fprintf(foutput, " NO ACTIONS\n");
return;
}
if (shiftp)
{
k = shiftp->nshifts;
for (i = 0; i < k; i++)
{
if (! shiftp->shifts[i]) continue;
state1 = shiftp->shifts[i];
symbol = accessing_symbol[state1];
if (ISVAR(symbol)) break;
fprintf(foutput, " %-4s\tshift %d\n", tags[symbol], state1);
}
if (i > 0)
putc('\n', foutput);
}
else
{
i = 0;
k = 0;
}
if (consistent[state] && redp)
{
rule = redp->rules[0];
symbol = rlhs[rule];
fprintf(foutput, " $default\treduce %d (%s)\n\n",
rule, tags[symbol]);
}
else if (redp)
{
print_reductions(state);
}
if (i < k)
{
for (; i < k; i++)
{
if (! shiftp->shifts[i]) continue;
state1 = shiftp->shifts[i];
symbol = accessing_symbol[state1];
fprintf(foutput, " %-4s\tgoto %d\n", tags[symbol], state1);
}
putc('\n', foutput);
}
}
SHAR_EOF
cat << \SHAR_EOF > string.h
extern char *strcat();
extern char *strncat();
extern char *strcpy();
extern char *strncpy();
extern char *stpcpy();
extern char *stpblk();
extern char *stpsym();
extern char *stptok();
extern char *stpchr();
extern char *strchr();
extern char *strrchr();
extern char *stpbrk();
extern char *strpbrk();
extern int strcmp();
extern int strncmp();
extern int strlen();
SHAR_EOF
cat << \SHAR_EOF > symtab.c
/* Symbol table manager for Bison,
copyright (C) 1984 Bob Corbett and Richard Stallman
Permission is granted to anyone to make or distribute verbatim copies of this program
provided that the copyright notice and this permission notice are preserved;
and provided that the recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.
Permission is granted to distribute derived works or enhanced versions of
this program under the above conditions with the additional condition
that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.
Anything distributed as part of a package containing portions derived
from this program, which cannot in current practice perform its function usefully
in the absense of what was derived directly from this program,
is to be considered as forming, together with the latter,
a single work derived from this program,
which must be entirely covered by a permission notice identical to this one
in order for distribution of the package to be permitted.
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them. Help stamp out software-hoarding! */
#include <stdio.h>
#ifdef BSD
#include <strings.h>
#else
#include <string.h>
#endif
#include "new.h"
#include "symtab.h"
#include "gram.h"
bucket **symtab;
bucket *firstsymbol;
bucket *lastsymbol;
int
hash(key)
char *key;
{
register char *cp;
register int k;
cp = key;
k = 0;
while (*cp)
k = ((k << 1) ^ (*cp++)) & 0x3fff;
return (k % TABSIZE);
}
char *
copys(s)
char *s;
{
register int i;
register char *cp;
register char *result;
i = 1;
for (cp = s; *cp; cp++)
i++;
result = allocate(i);
strcpy(result, s);
return (result);
}
tabinit()
{
symtab = NEW2(TABSIZE, bucket *);
firstsymbol = NULL;
lastsymbol = NULL;
}
bucket *getsym(key)
char *key;
{
register int hashval;
register bucket *bp;
register int found;
hashval = hash(key);
bp = symtab[hashval];
found = 0;
while (bp != NULL && found == 0)
{
if (strcmp(key, bp->tag) == 0)
found = 1;
else
bp = bp->link;
}
if (found == 0)
{
nsyms++;
bp = NEW(bucket);
bp->link = symtab[hashval];
bp->next = NULL;
bp->tag = copys(key);
bp->class = SUNKNOWN;
if (firstsymbol == NULL)
{
firstsymbol = bp;
lastsymbol = bp;
}
else
{
lastsymbol->next = bp;
lastsymbol = bp;
}
symtab[hashval] = bp;
}
return (bp);
}
free_symtab()
{
register int i;
register bucket *bp, *bptrail;
for (i = 0; i < TABSIZE; i++)
{
bp = symtab[i];
while (bp)
{
bptrail = bp;
bp = bp->link;
FREE(bptrail);
}
}
}
SHAR_EOF
cat << \SHAR_EOF > warshall.c
/* Generate transitive closure of a matrix,
copyright (C) 1984 Bob Corbett and Richard Stallman
Permission is granted to anyone to make or distribute verbatim copies of this program
provided that the copyright notice and this permission notice are preserved;
and provided that the recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.
Permission is granted to distribute derived works or enhanced versions of
this program under the above conditions with the additional condition
that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.
Anything distributed as part of a package containing portions derived
from this program, which cannot in current practice perform its function usefully
in the absense of what was derived directly from this program,
is to be considered as forming, together with the latter,
a single work derived from this program,
which must be entirely covered by a permission notice identical to this one
in order for distribution of the package to be permitted.
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them. Help stamp out software-hoarding! */
#include <stdio.h>
#include "machine.h"
/* given n by n matrix of bits R, modify its contents
to be the transive closure of what was given. */
void
TC(R, n)
unsigned *R;
int n;
{
register int rowsize;
register unsigned mask;
register unsigned *rowj;
register unsigned *rp;
register unsigned *rend;
register unsigned *ccol;
unsigned *relend;
unsigned *cword;
unsigned *rowi;
rowsize = WORDSIZE(n) * sizeof(unsigned);
relend = (unsigned *) ((unsigned) R + n*rowsize);
cword = R;
mask = 1;
rowi = R;
while (rowi < relend)
{
ccol = cword;
rowj = R;
while (rowj < relend)
{
if (*ccol & mask)
{
rp = rowi;
rend = (unsigned *) ((unsigned) rowj + rowsize);
while (rowj < rend)
*rowj++ |= *rp++;
}
else
{
rowj = (unsigned *) ((unsigned) rowj + rowsize);
}
ccol = (unsigned *) ((unsigned) ccol + rowsize);
}
mask <<= 1;
if (mask == 0)
{
mask = 1;
cword++;
}
rowi = (unsigned *) ((unsigned) rowi + rowsize);
}
}
/* Reflexive Transitive Closure. Same as TC
and then set all the bits on the diagonal of R. */
void
RTC(R, n)
unsigned *R;
int n;
{
register int rowsize;
register unsigned mask;
register unsigned *rp;
register unsigned *relend;
TC(R, n);
rowsize = WORDSIZE(n) * sizeof(unsigned);
relend = (unsigned *) ((unsigned) R + n*rowsize);
mask = 1;
rp = R;
while (rp < relend)
{
*rp |= mask;
mask <<= 1;
if (mask == 0)
{
mask = 1;
rp++;
}
rp = (unsigned *) ((unsigned) rp + rowsize);
}
}
SHAR_EOF