jimomura@lsuc.UUCP (09/13/87)
# 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
# shar: Shell Archiver
# Run the following text with /bin/sh to create:
# derives.c
# files.c
# files.h
# getargs.c
# gram.c
# gram.h
# lalr.c
# lex.c
# lex.h
# By: Jim Omura ()
cat << \SHAR_EOF > derives.c
/* Match rules with nonterminals for bison,
Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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! */
/* set_derives finds, for each variable (nonterminal), which rules can derive it.
It sets up the value of derives so that
derives[i - ntokens] points to a vector of rule numbers, terminated with a zero. */
#include <stdio.h>
#include "new.h"
#include "types.h"
#include "gram.h"
short **derives;
set_derives()
{
register int i;
register int lhs;
register shorts *p;
register short *q;
register shorts **dset;
register shorts *delts;
dset = NEW2(nvars, shorts *) - ntokens;
delts = NEW2(nrules + 1, shorts);
p = delts;
for (i = nrules; i > 0; i--)
{
lhs = rlhs[i];
p->next = dset[lhs];
p->value = i;
dset[lhs] = p;
p++;
}
derives = NEW2(nvars, short *) - ntokens;
q = NEW2(nvars + nrules, short);
for (i = ntokens; i < nsyms; i++)
{
derives[i] = q;
p = dset[i];
while (p)
{
*q++ = p->value;
p = p->next;
}
*q++ = -1;
}
#ifdef DEBUG
print_derives();
#endif
FREE(dset + ntokens);
FREE(delts);
}
free_derives()
{
FREE(derives[ntokens]);
FREE(derives + ntokens);
}
#ifdef DEBUG
print_derives()
{
register int i;
register short *sp;
extern char **tags;
printf("\n\n\nDERIVES\n\n");
for (i = ntokens; i < nsyms; i++)
{
printf("%s derives", tags[i]);
for (sp = derives[i]; *sp > 0; sp++)
{
printf(" %d", *sp);
}
putchar('\n');
}
putchar('\n');
}
#endif
SHAR_EOF
cat << \SHAR_EOF > files.c
/* Open and close files for bison,
Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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! */
#ifdef OSK
#include <strings.h>
#endif
#include <stdio.h>
#include "files.h"
#include "new.h"
#include "gram.h"
FILE *finput = NULL;
FILE *foutput = NULL;
FILE *fdefines = NULL;
FILE *ftable = NULL;
FILE *fattrs = NULL;
FILE *fguard = NULL;
FILE *faction = NULL;
FILE *fparser = NULL;
/* FILE *fparser1 = NULL; JF we don't need this anymore */
char *infile;
char *outfile;
char *defsfile;
char *tabfile;
char *attrsfile;
char *guardfile;
char *actfile;
char *tmpattrsfile;
char *tmptabfile;
/* JF nobody really uses these */
/* char *pfile;
char *pfile1; */
char *mktemp(); /* So the compiler won't complain */
FILE *tryopen(); /* This might be a good idea */
extern int verboseflag;
extern int definesflag;
int fixed_outfiles = 0;
char*
stringappend(string1, end1, string2)
char *string1;
int end1;
char *string2;
{
register char *ostring;
register char *cp, *cp1;
register int i;
cp = string2; i = 0;
while (*cp++) i++;
ostring = NEW2(i+end1+1, char);
cp = ostring;
cp1 = string1;
for (i = 0; i < end1; i++)
*cp++ = *cp1++;
cp1 = string2;
while (*cp++ = *cp1++) ;
return ostring;
}
/* JF this has been hacked to death. Nowaday it sets up the file names for
the output files, and opens the tmp files and the parser */
openfiles()
{
char *name_base;
#ifdef OSK
extern char *getenv();
char *temp_dir = getenv("TEMP");
#define TEMPD_L strlen(temp_dir)
#else
char *temp_dir = "";
#define TEMPD_L 0
#endif
register int i;
register char *cp;
name_base = fixed_outfiles ? "y.y" : infile;
cp = name_base;
i = 0;
while (*cp++) i++;
cp -= 2;
if (*cp-- == 'y' && *cp == '.')
i -= 2;
finput = tryopen(infile, "r");
fparser = tryopen(PFILE, "r");
if (verboseflag)
{
outfile = stringappend(name_base, i, ".output");
foutput = tryopen(outfile, "w");
}
if (definesflag)
{
defsfile = stringappend(name_base, i, ".tab.h");
fdefines = tryopen(defsfile, "w");
}
if (TEMPD_L == 0) temp_dir = ".";
actfile = mktemp(stringappend(temp_dir, TEMPD_L, TMP_ACT));
faction = tryopen(actfile, "w+");
#ifndef OSK
unlink(actfile);
#endif
tmpattrsfile = mktemp(stringappend(temp_dir, TEMPD_L, TMP_ATTRS));
fattrs = tryopen(tmpattrsfile,"w+");
#ifndef OSK
unlink(tmpattrsfile);
#endif
tmptabfile = mktemp(stringappend(temp_dir, TEMPD_L, TMP_TAB));
tabfile = stringappend(name_base, i, ".tab.c");
ftable = tryopen(tmptabfile, "w+");
#ifndef OSK
unlink(tmptabfile);
#endif
/* These are opened by open_extra_files, if at all */
attrsfile = stringappend(name_base, i, ".stype.h");
guardfile = stringappend(name_base, i, ".guard.c");
}
/* open the output files needed only for the semantic parser.
This is done when %semantic_parser is seen in the declarations section. */
open_extra_files()
{
FILE *ftmp;
int c;
/* JF change open parser file */
fclose(fparser);
fparser= tryopen(PFILE1, "r");
/* JF change from inline attrs file to separate one */
ftmp = tryopen(attrsfile, "w");
rewind(fattrs);
while((c=getc(fattrs))!=EOF) /* Thank god for buffering */
putc(c,ftmp);
fclose(fattrs);
fattrs=ftmp;
fguard = tryopen(guardfile, "w");
}
/* JF to make file opening easier. This func tries to open file
NAME with mode MODE, and prints an error message if it fails. */
FILE *
tryopen(name, mode)
char *name;
char *mode;
{
FILE *ptr;
ptr = fopen(name, mode);
if (ptr == NULL)
{
fprintf(stderr, "\nbison: ");
#ifdef OSK
fprintf(stderr, "error opening '%s'\n", name);
prerr(0, errno);
#else
perror(name);
#endif
done(2);
}
return ptr;
}
done(k)
int k;
{
if (faction)
fclose(faction);
#ifdef OSK
unlink(actfile);
#endif
if (fattrs)
fclose(fattrs);
#ifdef OSK
unlink(tmpattrsfile);
#endif
if (fguard)
fclose(fguard);
if (finput)
fclose(finput);
if (fparser)
fclose(fparser);
/* JF we don't need this anymore
if (fparser1)
fclose(fparser1); */
if (foutput)
fclose(foutput);
/* JF write out the output file */
if (k == 0 && ftable)
{
FILE *ftmp;
register int c;
ftmp=tryopen(tabfile, "w");
rewind(ftable);
while((c=getc(ftable)) != EOF)
putc(c,ftmp);
fclose(ftmp);
fclose(ftable);
#ifdef OSK
unlink (tmptabfile);
#endif
}
#ifdef OSK
if (k == 0) exit(k);
else exit(1);
#else
exit(k);
#endif
}
/* E O F */
SHAR_EOF
cat << \SHAR_EOF > files.h
/* File names and variables for bison,
Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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! */
/* These two should be pathnames for opening the sample parser files.
When bison is installed, they should be absolute pathnames.
XPFILE1 and XPFILE2 normally come from the Makefile. */
#define PFILE XPFILE /* Simple parser */
#define PFILE1 XPFILE1 /* Semantic parser */
extern FILE *finput; /* read grammar specifications */
extern FILE *foutput; /* optionally output messages describing the actions taken */
extern FILE *fdefines; /* optionally output #define's for token numbers. */
extern FILE *ftable; /* output the tables and the parser */
extern FILE *fattrs; /* if semantic parser, output a .h file that defines YYSTYPE */
/* and also contains all the %{ ... %} definitions. */
extern FILE *fguard; /* if semantic parser, output yyguard, containing all the guard code */
extern FILE *faction; /* output all the action code; precise form depends on which parser */
/* JF nowaday fparser is used for whatever parser is in use, instead of
opening both of them. */
extern FILE *fparser; /* read the semantic parser to copy into ftable */
/* JF extern FILE *fparser1; /* read the simple parser to copy into ftable */
extern char *infile;
extern char *outfile;
extern char *defsfile;
extern char *tabfile;
extern char *attrsfile;
extern char *guardfile;
extern char *actfile;
/* JF nobody seems to care about these
extern char *pfile;
extern char *pfile1; */
/*
* names for the temp files. under OSK the directory for the
* temp files is read from environment variable "TEMP"
*
* see file : FILE.C
*/
#ifdef OSK
#define TMP_ACT "/b.act.XXXXXX"
#define TMP_ATTRS "/b.attrs.XXXXXX"
#define TMP_TAB "/b.tab.XXXXXX"
#else
#define TMP_ACT "/tmp/b.act.XXXXXX"
#define TMP_ATTRS "/tmp/b.attrs.XXXXXX"
#define TMP_TAB "/tmp/b.tab.XXXXXX"
#endif
/* E O F */
SHAR_EOF
cat << \SHAR_EOF > getargs.c
/* Parse command line arguments for bison,
Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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 "files.h"
int verboseflag;
int definesflag;
extern int fixed_outfiles;/* JF */
getargs(argc, argv)
int argc;
char *argv[];
{
register int i;
register char *cp;
register int duplicates;
verboseflag = 0;
definesflag = 0;
duplicates = 0;
i = 1;
while (i < argc && *argv[i] == '-')
{
cp = argv[i] + 1;
while (*cp)
{
switch (*cp)
{
case 'y':/* JF this case */
case 'Y':
if(fixed_outfiles)
duplicates = 1;
else
fixed_outfiles = 1;
break;
case 'v':
case 'V':
if (verboseflag)
duplicates = 1;
else
verboseflag = 1;
break;
case 'd':
case 'D':
if (definesflag)
duplicates = 1;
else
definesflag = 1;
break;
case '?':
usage();
exit(0);
default:
fatals("illegal option: %s", argv[i]);
}
cp++;
}
i++;
}
if (duplicates)
fprintf(stderr, "warning: repeated arguments ignored");
if (i == argc)
fatal("grammar file not specified");
else
infile = argv[i];
if (i < argc - 1)
fprintf(stderr, "warning: extra arguments ignored");
}
/* USAGE added by TOM / 29-08-87 */
#define E(txt) fprintf(stderr, txt)
usage()
{
E("Syntax : bison [<opts>] <file>\n");
E("Function : Compiler Compiler similar to YACC\n");
E("Options : -y output file names default to Y.xxxxx\n");
E(" -v generate listing file <file>.output\n");
E(" -d generate include file <file>.tab.h\n");
}
/* E O F */
SHAR_EOF
cat << \SHAR_EOF > gram.c
/* Allocate input grammar variables for bison,
Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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! */
/* comments for these variables are in gram.h */
int nitems;
int nrules;
int nsyms;
int ntokens;
int nvars;
short *ritem;
short *rlhs;
short *rrhs;
short *rprec;
short *sprec;
short *rassoc;
short *sassoc;
short *token_translations;
short *rline;
int start_symbol;
int translations;
int max_user_token_number;
int semantic_parser;
int pure_parser;
int error_token_number;
SHAR_EOF
cat << \SHAR_EOF > gram.h
/* Data definitions for internal representation of bison's input,
Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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! */
/* representation of the grammar rules:
ntokens is the number of tokens, and nvars is the number of variables (nonterminals).
nsyms is the total number, ntokens + nvars.
Each symbol (either token or variable) receives a symbol number.
Numbers 0 to ntokens-1 are for tokens, and ntokens to nsyms-1 are for variables.
Symbol number zero is the end-of-input token. This token is counted in ntokens.
The rules receive rule numbers 1 to nrules in the order they are written.
Actions and guards are accessed via the rule number.
The rules themselves are described by three arrays: rrhs, rlhs and ritems.
rlhs[r] is the symbol number of the left hand side of rule r.
The right hand side is stored as symbol numbers in a portion of ritems.
rrhs[r] contains the index in ritems of the beginning of the portion for rule r.
The length of the portion is one greater
than the number of symbols in the rule's right hand side.
The last element in the portion contains minus r, which
identifies it as the end of a portion and says which rule it is for.
The portions of ritems come in order of increasing rule number and are
followed by an element which is zero to mark the end. nitems is the
total length of ritems, not counting the final zero. Each element of
ritems is called an "item" and its index in ritems is an item number.
Item numbers are used in the finite state machine to represent
places that parsing can get to.
Precedence levels are recorded in the vectors sprec and rprec.
sprec records the precedence level of each symbol,
rprec the precedence level of each rule.
Precedence levels are assigned in increasing order starting with 1
so that numerically higher precedence values mean tighter binding
as they ought to. Zero as a symbol or rule's precedence means none is assigned.
Associativities are recorded similarly in rassoc and sassoc. */
#define ISTOKEN(s) ((s) < ntokens)
#define ISVAR(s) ((s) >= ntokens)
extern int nitems;
extern int nrules;
extern int nsyms;
extern int ntokens;
extern int nvars;
extern short *ritem;
extern short *rlhs;
extern short *rrhs;
extern short *rprec;
extern short *sprec;
extern short *rassoc;
extern short *sassoc;
extern short *rline; /* Source line number of each rule */
extern int start_symbol;
/* associativity values in elements of rassoc, sassoc. */
#define RIGHT_ASSOC 1
#define LEFT_ASSOC 2
#define NON_ASSOC 3
/* token translation table:
indexed by a token number as returned by the user's yylex routine,
it yields the internal token number used by the parser and throughout bison.
If translations is zero, the translation table is not used because
the two kinds of token numbers are the same. */
extern short *token_translations;
extern int translations;
extern int max_user_token_number;
/* semantic_parser is nonzero if the input file says to use the hairy parser
that provides for semantic error recovery. If it is zero, the yacc-compatible
simplified parser is used. */
extern int semantic_parser;
/* pure_parser is nonzero if should generate a parser that is all pure and reentrant. */
extern int pure_parser;
/* error_token_number is the token number of the error token. */
extern int error_token_number;
SHAR_EOF
cat << \SHAR_EOF > lalr.c
/* Compute look-ahead criteria for bison,
Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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! */
/* Compute how to make the finite state machine deterministic;
find which rules need lookahead in each state, and which lookahead tokens they accept.
lalr(), the entry point, builds these data structures:
goto_map, from_state and to_state
record each shift transition which accepts a variable (a nonterminal).
ngotos is the number of such transitions.
from_state[t] is the state number which a transition leads from
and to_state[t] is the state number it leads to.
All the transitions that accept a particular variable are grouped together and
goto_map[i - ntokens] is the index in from_state and to_state of the first of them.
consistent[s] is nonzero if no lookahead is needed to decide what to do in state s.
LAruleno is a vector which records the rules that need lookahead in various states.
The elements of LAruleno that apply to state s are those from
lookaheads[s] through lookaheads[s+1]-1.
Each element of LAruleno is a rule number.
If lr is the length of LAruleno, then a number from 0 to lr-1
can specify both a rule and a state where the rule might be applied.
LA is a lr by ntokens matrix of bits.
LA[l, i] is 1 if the rule LAruleno[l] is applicable in the appropriate state
when the next token is symbol i.
If LA[l, i] and LA[l, j] are both 1 for i != j, it is a conflict.
*/
#include <stdio.h>
#include "machine.h"
#include "types.h"
#include "state.h"
#include "new.h"
#include "gram.h"
extern short **derives;
extern char *nullable;
int tokensetsize;
short *lookaheads;
short *LAruleno;
unsigned *LA;
short *accessing_symbol;
char *consistent;
core **state_table;
shifts **shift_table;
reductions **reduction_table;
short *goto_map;
short *from_state;
short *to_state;
short **transpose();
static int infinity;
static int maxrhs;
static int ngotos;
static unsigned *F;
static short **includes;
static shorts **lookback;
static short **R;
static short *INDEX;
static short *VERTICES;
static int top;
lalr()
{
tokensetsize = WORDSIZE(ntokens);
set_state_table();
set_accessing_symbol();
set_shift_table();
set_reduction_table();
set_maxrhs();
initialize_LA();
set_goto_map();
initialize_F();
build_relations();
compute_FOLLOWS();
compute_lookaheads();
}
set_state_table()
{
register core *sp;
state_table = NEW2(nstates, core *);
for (sp = first_state; sp; sp = sp->next)
state_table[sp->number] = sp;
}
set_accessing_symbol()
{
register core *sp;
accessing_symbol = NEW2(nstates, short);
for (sp = first_state; sp; sp = sp->next)
accessing_symbol[sp->number] = sp->accessing_symbol;
}
set_shift_table()
{
register shifts *sp;
shift_table = NEW2(nstates, shifts *);
for (sp = first_shift; sp; sp = sp->next)
shift_table[sp->number] = sp;
}
set_reduction_table()
{
register reductions *rp;
reduction_table = NEW2(nstates, reductions *);
for (rp = first_reduction; rp; rp = rp->next)
reduction_table[rp->number] = rp;
}
set_maxrhs()
{
register short *itemp;
register int length;
register int max;
length = 0;
max = 0;
for (itemp = ritem; *itemp; itemp++)
{
if (*itemp > 0)
{
length++;
}
else
{
if (length > max) max = length;
length = 0;
}
}
maxrhs = max;
}
initialize_LA()
{
register int i;
register int j;
register int count;
register reductions *rp;
register shifts *sp;
register short *np;
consistent = NEW2(nstates, char);
lookaheads = NEW2(nstates + 1, short);
count = 0;
for (i = 0; i < nstates; i++)
{
register int j;
lookaheads[i] = count;
rp = reduction_table[i];
sp = shift_table[i];
if (rp && (rp->nreds > 1
|| (sp && ! ISVAR(accessing_symbol[sp->shifts[0]]))))
count += rp->nreds;
else
consistent[i] = 1;
if (sp)
for (j = 0; j < sp->nshifts; j++)
{
if (accessing_symbol[sp->shifts[j]] == error_token_number)
{
consistent[i] = 0;
break;
}
}
}
lookaheads[nstates] = count;
LA = NEW2(count * tokensetsize, unsigned);
LAruleno = NEW2(count, short);
lookback = NEW2(count, shorts *);
np = LAruleno;
for (i = 0; i < nstates; i++)
{
if (!consistent[i])
{
if (rp = reduction_table[i])
for (j = 0; j < rp->nreds; j++)
*np++ = rp->rules[j];
}
}
}
set_goto_map()
{
register shifts *sp;
register int i;
register int symbol;
register int k;
register short *temp_map;
register int state2;
register int state1;
goto_map = NEW2(nvars + 1, short) - ntokens;
temp_map = NEW2(nvars + 1, short) - ntokens;
ngotos = 0;
for (sp = first_shift; sp; sp = sp->next)
{
for (i = sp->nshifts - 1; i >= 0; i--)
{
symbol = accessing_symbol[sp->shifts[i]];
if (ISTOKEN(symbol)) break;
if (ngotos == MAXSHORT)
toomany("gotos");
ngotos++;
goto_map[symbol]++;
}
}
k = 0;
for (i = ntokens; i < nsyms; i++)
{
temp_map[i] = k;
k += goto_map[i];
}
for (i = ntokens; i < nsyms; i++)
goto_map[i] = temp_map[i];
goto_map[nsyms] = ngotos;
temp_map[nsyms] = ngotos;
from_state = NEW2(ngotos, short);
to_state = NEW2(ngotos, short);
for (sp = first_shift; sp; sp = sp->next)
{
state1 = sp->number;
for (i = sp->nshifts - 1; i >= 0; i--)
{
state2 = sp->shifts[i];
symbol = accessing_symbol[state2];
if (ISTOKEN(symbol)) break;
k = temp_map[symbol]++;
from_state[k] = state1;
to_state[k] = state2;
}
}
FREE(temp_map + ntokens);
}
/* Map_goto maps a state/symbol pair into its numeric representation. */
int
map_goto(state, symbol)
int state;
int symbol;
{
register int high;
register int low;
register int middle;
register int s;
low = goto_map[symbol];
high = goto_map[symbol + 1];
while (low <= high)
{
middle = (low + high) / 2;
s = from_state[middle];
if (s == state)
return (middle);
else if (s < state)
low = middle + 1;
else
high = middle - 1;
}
berror("map_goto");
/* NOTREACHED */
}
initialize_F()
{
register int i;
register int j;
register int k;
register shifts *sp;
register short *edge;
register unsigned *rowp;
register short *rp;
register short **reads;
register int nedges;
register int stateno;
register int symbol;
register int nwords;
nwords = ngotos * tokensetsize;
F = NEW2(nwords, unsigned);
reads = NEW2(ngotos, short *);
edge = NEW2(ngotos + 1, short);
nedges = 0;
rowp = F;
for (i = 0; i < ngotos; i++)
{
stateno = to_state[i];
sp = shift_table[stateno];
if (sp)
{
k = sp->nshifts;
for (j = 0; j < k; j++)
{
symbol = accessing_symbol[sp->shifts[j]];
if (ISVAR(symbol))
break;
SETBIT(rowp, symbol);
}
for (; j < k; j++)
{
symbol = accessing_symbol[sp->shifts[j]];
if (nullable[symbol])
edge[nedges++] = map_goto(stateno, symbol);
}
if (nedges)
{
reads[i] = rp = NEW2(nedges + 1, short);
for (j = 0; j < nedges; j++)
rp[j] = edge[j];
rp[nedges] = -1;
nedges = 0;
}
}
rowp += tokensetsize;
}
digraph(reads);
for (i = 0; i < ngotos; i++)
{
if (reads[i])
FREE(reads[i]);
}
FREE(reads);
FREE(edge);
}
build_relations()
{
register int i;
register int j;
register int k;
register short *rulep;
register short *rp;
register shifts *sp;
register int length;
register int nedges;
register int done;
register int state1;
register int stateno;
register int symbol1;
register int symbol2;
register short *shortp;
register short *edge;
register short *states;
register short **new_includes;
includes = NEW2(ngotos, short *);
edge = NEW2(ngotos + 1, short);
states = NEW2(maxrhs + 1, short);
for (i = 0; i < ngotos; i++)
{
nedges = 0;
state1 = from_state[i];
symbol1 = accessing_symbol[to_state[i]];
for (rulep = derives[symbol1]; *rulep > 0; rulep++)
{
length = 1;
states[0] = state1;
stateno = state1;
for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
{
symbol2 = *rp;
sp = shift_table[stateno];
k = sp->nshifts;
for (j = 0; j < k; j++)
{
stateno = sp->shifts[j];
if (accessing_symbol[stateno] == symbol2) break;
}
states[length++] = stateno;
}
if (!consistent[stateno])
add_lookback_edge(stateno, *rulep, i);
length--;
done = 0;
while (!done)
{
done = 1;
rp--;
/* JF added rp>=ritem && I hope to god its right! */
if (rp>=ritem && ISVAR(*rp))
{
stateno = states[--length];
edge[nedges++] = map_goto(stateno, *rp);
if (nullable[*rp]) done = 0;
}
}
}
if (nedges)
{
includes[i] = shortp = NEW2(nedges + 1, short);
for (j = 0; j < nedges; j++)
shortp[j] = edge[j];
shortp[nedges] = -1;
}
}
new_includes = transpose(includes, ngotos);
for (i = 0; i < ngotos; i++)
if (includes[i])
FREE(includes[i]);
FREE(includes);
includes = new_includes;
FREE(edge);
FREE(states);
}
add_lookback_edge(stateno, ruleno, gotono)
int stateno;
int ruleno;
int gotono;
{
register int i;
register int k;
register int found;
register shorts *sp;
i = lookaheads[stateno];
k = lookaheads[stateno + 1];
found = 0;
while (!found && i < k)
{
if (LAruleno[i] == ruleno)
found = 1;
else
i++;
}
if (found == 0)
berror("add_lookback_edge");
sp = NEW(shorts);
sp->next = lookback[i];
sp->value = gotono;
lookback[i] = sp;
}
short **
transpose(R, n)
short **R;
int n;
{
register short **new_R;
register short **temp_R;
register short *nedges;
register short *sp;
register int i;
register int k;
nedges = NEW2(n, short);
for (i = 0; i < n; i++)
{
sp = R[i];
if (sp)
{
while (*sp >= 0)
nedges[*sp++]++;
}
}
new_R = NEW2(n, short *);
temp_R = NEW2(n, short *);
for (i = 0; i < n; i++)
{
k = nedges[i];
if (k > 0)
{
sp = NEW2(k + 1, short);
new_R[i] = sp;
temp_R[i] = sp;
sp[k] = -1;
}
}
FREE(nedges);
for (i = 0; i < n; i++)
{
sp = R[i];
if (sp)
{
while (*sp >= 0)
*temp_R[*sp++]++ = i;
}
}
FREE(temp_R);
return (new_R);
}
compute_FOLLOWS()
{
register int i;
digraph(includes);
for (i = 0; i < ngotos; i++)
{
if (includes[i]) FREE(includes[i]);
}
FREE(includes);
}
compute_lookaheads()
{
register int i;
register int n;
register unsigned *fp1;
register unsigned *fp2;
register unsigned *fp3;
register shorts *sp;
register unsigned *rowp;
/* register short *rulep; JF unused */
/* register int count; JF unused */
register shorts *sptmp;/* JF */
rowp = LA;
n = lookaheads[nstates];
for (i = 0; i < n; i++)
{
fp3 = rowp + tokensetsize;
for (sp = lookback[i]; sp; sp = sp->next)
{
fp1 = rowp;
fp2 = F + tokensetsize * sp->value;
while (fp1 < fp3)
*fp1++ |= *fp2++;
}
rowp = fp3;
}
for (i = 0; i < n; i++)
{/* JF removed ref to freed storage */
for (sp = lookback[i]; sp; sp = sptmp) {
sptmp=sp->next;
FREE(sp);
}
}
FREE(lookback);
FREE(F);
}
digraph(relation)
short **relation;
{
register int i;
infinity = ngotos + 2;
INDEX = NEW2(ngotos + 1, short);
VERTICES = NEW2(ngotos + 1, short);
top = 0;
R = relation;
for (i = 0; i < ngotos; i++)
INDEX[i] = 0;
for (i = 0; i < ngotos; i++)
{
if (INDEX[i] == 0 && R[i])
traverse(i);
}
FREE(INDEX);
FREE(VERTICES);
}
traverse(i)
register int i;
{
register unsigned *fp1;
register unsigned *fp2;
register unsigned *fp3;
register int j;
register short *rp;
int height;
unsigned *base;
VERTICES[++top] = i;
INDEX[i] = height = top;
base = F + i * tokensetsize;
fp3 = base + tokensetsize;
rp = R[i];
if (rp)
{
while ((j = *rp++) >= 0)
{
if (INDEX[j] == 0)
traverse(j);
if (INDEX[i] > INDEX[j])
INDEX[i] = INDEX[j];
fp1 = base;
fp2 = F + j * tokensetsize;
while (fp1 < fp3)
*fp1++ |= *fp2++;
}
}
if (INDEX[i] == height)
{
for (;;)
{
j = VERTICES[top--];
INDEX[j] = infinity;
if (i == j)
break;
fp1 = base;
fp2 = F + j * tokensetsize;
while (fp1 < fp3)
*fp2++ = *fp1++;
}
}
}
SHAR_EOF
cat << \SHAR_EOF > lex.c
/* Token-reader for Bison's input parser,
Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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! */
/*
lex() is the entry point. It is called from reader.c.
It returns one of the token-type codes defined in lex.h.
When an identifier is seen, the code IDENTIFIER is returned
and the name is looked up in the symbol table using symtab.c;
symval is set to a pointer to the entry found. */
#include <stdio.h>
#include <ctype.h>
#include "files.h"
#include "symtab.h"
#include "lex.h"
extern int lineno;
extern int translations;
char token_buffer[MAXTOKEN + 1];
bucket *symval;
int numval;
static int unlexed; /* these two describe a token to be reread */
static bucket *unlexed_symval; /* by the next call to lex */
init_lex()
{
unlexed = -1;
}
int
skip_white_space()
{
register int c;
register int inside;
c = getc(finput);
for (;;)
{
switch (c)
{
case '/':
c = getc(finput);
if (c != '*')
fatals("unexpected '/%c' found",c);
c = getc(finput);
inside = 1;
while (inside)
{
if (c == '*')
{
while (c == '*')
c = getc(finput);
if (c == '/')
{
inside = 0;
c = getc(finput);
}
}
else if (c == '\n')
{
lineno++;
c = getc(finput);
}
else if (c == EOF)
fatal("unterminated comment");
else
c = getc(finput);
}
break;
case '\n':
lineno++;
case ' ':
case '\t':
case '\f':
c = getc(finput);
break;
default:
return (c);
}
}
}
unlex(token)
int token;
{
unlexed = token;
unlexed_symval = symval;
}
int
lex()
{
register int c;
register char *p;
if (unlexed >= 0)
{
symval = unlexed_symval;
c = unlexed;
unlexed = -1;
return (c);
}
c = skip_white_space();
switch (c)
{
case EOF:
return (ENDFILE);
case 'A': case 'B': case 'C': case 'D': case 'E':
case 'F': case 'G': case 'H': case 'I': case 'J':
case 'K': case 'L': case 'M': case 'N': case 'O':
case 'P': case 'Q': case 'R': case 'S': case 'T':
case 'U': case 'V': case 'W': case 'X': case 'Y':
case 'Z':
case 'a': case 'b': case 'c': case 'd': case 'e':
case 'f': case 'g': case 'h': case 'i': case 'j':
case 'k': case 'l': case 'm': case 'n': case 'o':
case 'p': case 'q': case 'r': case 's': case 't':
case 'u': case 'v': case 'w': case 'x': case 'y':
case 'z':
case '.': case '_':
p = token_buffer;
while (isalnum(c) || c == '_' || c == '.')
{
if (p < token_buffer + MAXTOKEN)
*p++ = c;
c = getc(finput);
}
*p = 0;
ungetc(c, finput);
symval = getsym(token_buffer);
return (IDENTIFIER);
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
{
numval = 0;
while (isdigit(c))
{
numval = numval*10 + c - '0';
c = getc(finput);
}
ungetc(c, finput);
return (NUMBER);
}
case '\'':
translations = -1;
/* parse the literal token and compute character code in code */
c = getc(finput);
{
register int code = 0;
if (c == '\\')
{
c = getc(finput);
if (c <= '7' && c >= '0')
{
while (c <= '7' && c >= '0')
{
code = (code * 8) + (c - '0');
c = getc(finput);
}
if (code >= 128 || code<0)/* JF this said if(c>=128) */
fatals("malformatted literal token '\\%03o'",code);
}
else
{
if (c == 't')
code = '\t';
else if (c == 'n')
code = '\n';
else if (c == 'r')
code = '\r';
else if (c == 'f')
code = '\f';
else if (c == 'b')
code = '\b';
else if (c == '\\')
code = '\\';
else if (c == '\'')
code = '\'';
else if (c == '\"') /* JF this is a good idea */
code = '\"';
else fatals("invalid literal token '\\%c'",c);
c = getc(finput);
}
}
else
{
code = c;
c = getc(finput);
}
if (c != '\'')
fatal("multicharacter literal tokens NOT supported");
/* now fill token_buffer with the canonical name for this character
as a literal token. Do not use what the user typed,
so that '\012' and '\n' can be interchangeable. */
p = token_buffer;
*p++ = '\'';
if (code == '\\')
{
p = token_buffer + 1;
*p++ = '\\';
*p++ = '\\';
}
else if (code == '\'')
{
p = token_buffer + 1;
*p++ = '\\';
*p++ = '\'';
}
else if (code >= 040 && code != 0177)
*p++ = code;
else if (code == '\t')
{
p = token_buffer + 1;
*p++ = '\\';
*p++ = 't';
}
else if (code == '\n')
{
p = token_buffer + 1;
*p++ = '\\';
*p++ = 'n';
}
else if (code == '\r')
{
p = token_buffer + 1;
*p++ = '\\';
*p++ = 'r';
}
else if (code == '\b')
{
p = token_buffer + 1;
*p++ = '\\';
*p++ = 'b';
}
else if (code == '\f')
{
p = token_buffer + 1;
*p++ = '\\';
*p++ = 'f';
}
else
{
*p++ = code / 0100 + '0';
*p++ = ((code / 010) & 07) + '0';
*p++ = (code & 07) + '0';
}
*p++ = '\'';
*p = 0;
symval = getsym(token_buffer);
symval->class = STOKEN;
if (! symval->user_token_number)
symval->user_token_number = code;
return (IDENTIFIER);
}
case ',':
return (COMMA);
case ':':
return (COLON);
case ';':
return (SEMICOLON);
case '|':
return (BAR);
case '{':
return (LEFT_CURLY);
case '=':
c = getc(finput);
if (c == '{')
return(LEFT_CURLY);
else
{
ungetc(c, finput);
return(ILLEGAL);
}
case '<':
p = token_buffer;
c = getc(finput);
while (c != '>')
{
if (c == '\n' || c == EOF)
fatal("unterminated type name");
if (p >= token_buffer + MAXTOKEN - 1)
fatals("type name too long (%d max)",MAXTOKEN-1);
*p++ = c;
c = getc(finput);
}
*p = 0;
return (TYPENAME);
case '%':
return (parse_percent_token());
default:
return (ILLEGAL);
}
}
/* parse a token which starts with %. Assumes the % has already been read and discarded. */
int
parse_percent_token ()
{
register int c;
register char *p;
p = token_buffer;
c = getc(finput);
switch (c)
{
case '%':
return (TWO_PERCENTS);
case '{':
return (PERCENT_LEFT_CURLY);
case '<':
return (LEFT);
case '>':
return (RIGHT);
case '2':
return (NONASSOC);
case '0':
return (TOKEN);
case '=':
return (PREC);
}
if (!isalpha(c))
return (ILLEGAL);
while (isalpha(c) || c == '_')
{
if (p < token_buffer + MAXTOKEN)
*p++ = c;
c = getc(finput);
}
ungetc(c, finput);
*p = 0;
if (strcmp(token_buffer, "token") == 0
||
strcmp(token_buffer, "term") == 0)
return (TOKEN);
else if (strcmp(token_buffer, "nterm") == 0)
return (NTERM);
else if (strcmp(token_buffer, "type") == 0)
return (TYPE);
else if (strcmp(token_buffer, "guard") == 0)
return (GUARD);
else if (strcmp(token_buffer, "union") == 0)
return (UNION);
else if (strcmp(token_buffer, "start") == 0)
return (START);
else if (strcmp(token_buffer, "left") == 0)
return (LEFT);
else if (strcmp(token_buffer, "right") == 0)
return (RIGHT);
else if (strcmp(token_buffer, "nonassoc") == 0
||
strcmp(token_buffer, "binary") == 0)
return (NONASSOC);
else if (strcmp(token_buffer, "semantic_parser") == 0)
return (SEMANTIC_PARSER);
else if (strcmp(token_buffer, "pure_parser") == 0)
return (PURE_PARSER);
else if (strcmp(token_buffer, "prec") == 0)
return (PREC);
else return (ILLEGAL);
}
SHAR_EOF
cat << \SHAR_EOF > lex.h
/* Token type definitions for bison's input reader,
Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.
Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License. A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities. It
should be in a file named COPYING. Among other things, the copyright
notice and this notice must be preserved on all copies.
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 ENDFILE 0
#define IDENTIFIER 1
#define COMMA 2
#define COLON 3
#define SEMICOLON 4
#define BAR 5
#define LEFT_CURLY 6
#define TWO_PERCENTS 7
#define PERCENT_LEFT_CURLY 8
#define TOKEN 9
#define NTERM 10
#define GUARD 11
#define TYPE 12
#define UNION 13
#define START 14
#define LEFT 15
#define RIGHT 16
#define NONASSOC 17
#define PREC 18
#define SEMANTIC_PARSER 19
#define PURE_PARSER 20
#define TYPENAME 21
#define NUMBER 22
#define ILLEGAL 23
#define MAXTOKEN 1024
SHAR_EOF
# End of shell archive
exit 0
--
Jim Omura, 2A King George's Drive, Toronto, (416) 652-3880
ihnp4!utzoo!lsuc!jimomura
Byte Information eXchange: jimomura