2994 lines
58 KiB
C
2994 lines
58 KiB
C
|
#include <u.h>
|
||
|
#include <libc.h>
|
||
|
#include <bio.h>
|
||
|
#include <ctype.h>
|
||
|
|
||
|
#define Bungetrune Bungetc /* ok for now. */
|
||
|
|
||
|
/*
|
||
|
* all these are 32 bit
|
||
|
*/
|
||
|
#define TBITSET ((32+NTERMS)/32) /* BOTCH?? +31 */
|
||
|
#define BIT(a,i) ((a)[(i)>>5] & (1<<((i)&037)))
|
||
|
#define SETBIT(a,i) ((a)[(i)>>5] |= (1<<((i)&037)))
|
||
|
#define NWORDS(n) (((n)+32)/32)
|
||
|
|
||
|
char *PARSER = "#9/lib/yaccpar";
|
||
|
char *PARSERS = "#9/lib/yaccpars";
|
||
|
|
||
|
#define TEMPNAME "y.tmp.XXXXXX"
|
||
|
#define ACTNAME "y.acts.XXXXXX"
|
||
|
#define OFILE "tab.c"
|
||
|
#define FILEU "output"
|
||
|
#define FILED "tab.h"
|
||
|
#define FILEDEBUG "debug"
|
||
|
|
||
|
enum
|
||
|
{
|
||
|
/*
|
||
|
* the following are adjustable
|
||
|
* according to memory size
|
||
|
*/
|
||
|
ACTSIZE = 40000,
|
||
|
MEMSIZE = 40000,
|
||
|
NSTATES = 2000,
|
||
|
NTERMS = 511,
|
||
|
NPROD = 1600,
|
||
|
NNONTERM = 600,
|
||
|
TEMPSIZE = 2000,
|
||
|
CNAMSZ = 10000,
|
||
|
LSETSIZE = 2400,
|
||
|
WSETSIZE = 350,
|
||
|
|
||
|
NAMESIZE = 50,
|
||
|
NTYPES = 63,
|
||
|
ISIZE = 400,
|
||
|
|
||
|
PRIVATE = 0xE000, /* unicode private use */
|
||
|
|
||
|
/* relationships which must hold:
|
||
|
TBITSET ints must hold NTERMS+1 bits...
|
||
|
WSETSIZE >= NNONTERM
|
||
|
LSETSIZE >= NNONTERM
|
||
|
TEMPSIZE >= NTERMS + NNONTERM + 1
|
||
|
TEMPSIZE >= NSTATES
|
||
|
*/
|
||
|
|
||
|
NTBASE = 010000,
|
||
|
ERRCODE = 8190,
|
||
|
ACCEPTCODE = 8191,
|
||
|
|
||
|
NOASC = 0, /* no assoc. */
|
||
|
LASC = 1, /* left assoc. */
|
||
|
RASC = 2, /* right assoc. */
|
||
|
BASC = 3, /* binary assoc. */
|
||
|
|
||
|
/* flags for state generation */
|
||
|
|
||
|
DONE = 0,
|
||
|
MUSTDO = 1,
|
||
|
MUSTLOOKAHEAD = 2,
|
||
|
|
||
|
/* flags for a rule having an action, and being reduced */
|
||
|
|
||
|
ACTFLAG = 04,
|
||
|
REDFLAG = 010,
|
||
|
|
||
|
/* output parser flags */
|
||
|
YYFLAG1 = -1000,
|
||
|
|
||
|
/* parse tokens */
|
||
|
IDENTIFIER = PRIVATE,
|
||
|
MARK,
|
||
|
TERM,
|
||
|
LEFT,
|
||
|
RIGHT,
|
||
|
BINARY,
|
||
|
PREC,
|
||
|
LCURLY,
|
||
|
IDENTCOLON,
|
||
|
NUMBER,
|
||
|
START,
|
||
|
TYPEDEF,
|
||
|
TYPENAME,
|
||
|
UNION,
|
||
|
|
||
|
ENDFILE = 0,
|
||
|
|
||
|
EMPTY = 1,
|
||
|
WHOKNOWS = 0,
|
||
|
OK = 1,
|
||
|
NOMORE = -1000
|
||
|
};
|
||
|
|
||
|
/* macros for getting associativity and precedence levels */
|
||
|
|
||
|
#define ASSOC(i) ((i)&03)
|
||
|
#define PLEVEL(i) (((i)>>4)&077)
|
||
|
#define TYPE(i) (((i)>>10)&077)
|
||
|
|
||
|
/* macros for setting associativity and precedence levels */
|
||
|
|
||
|
#define SETASC(i,j) i |= j
|
||
|
#define SETPLEV(i,j) i |= (j<<4)
|
||
|
#define SETTYPE(i,j) i |= (j<<10)
|
||
|
|
||
|
/* looping macros */
|
||
|
|
||
|
#define TLOOP(i) for(i=1; i<=ntokens; i++)
|
||
|
#define NTLOOP(i) for(i=0; i<=nnonter; i++)
|
||
|
#define PLOOP(s,i) for(i=s; i<nprod; i++)
|
||
|
#define SLOOP(i) for(i=0; i<nstate; i++)
|
||
|
#define WSBUMP(x) x++
|
||
|
#define WSLOOP(s,j) for(j=s; j<cwp; j++)
|
||
|
#define ITMLOOP(i,p,q) for(q=pstate[i+1], p=pstate[i]; p<q; p++)
|
||
|
#define SETLOOP(i) for(i=0; i<tbitset; i++)
|
||
|
|
||
|
/* command to clobber tempfiles after use */
|
||
|
|
||
|
#define ZAPFILE(x) if(x) remove(x)
|
||
|
|
||
|
/* I/O descriptors */
|
||
|
|
||
|
Biobuf* faction; /* file for saving actions */
|
||
|
Biobuf* fdefine; /* file for #defines */
|
||
|
Biobuf* fdebug; /* y.debug for strings for debugging */
|
||
|
Biobuf* ftable; /* y.tab.c file */
|
||
|
Biobuf* ftemp; /* tempfile to pass 2 */
|
||
|
Biobuf* finput; /* input file */
|
||
|
Biobuf* foutput; /* y.output file */
|
||
|
|
||
|
/* communication variables between various I/O routines */
|
||
|
|
||
|
char* infile; /* input file name */
|
||
|
int numbval; /* value of an input number */
|
||
|
char tokname[NAMESIZE+4]; /* input token name, slop for runes and 0 */
|
||
|
|
||
|
/* structure declarations */
|
||
|
|
||
|
typedef
|
||
|
struct
|
||
|
{
|
||
|
int lset[TBITSET];
|
||
|
} Lkset;
|
||
|
|
||
|
typedef
|
||
|
struct
|
||
|
{
|
||
|
int* pitem;
|
||
|
Lkset* look;
|
||
|
} Item;
|
||
|
|
||
|
typedef
|
||
|
struct
|
||
|
{
|
||
|
char* name;
|
||
|
int value;
|
||
|
} Symb;
|
||
|
|
||
|
typedef
|
||
|
struct
|
||
|
{
|
||
|
int* pitem;
|
||
|
int flag;
|
||
|
Lkset ws;
|
||
|
} Wset;
|
||
|
|
||
|
/* storage of names */
|
||
|
|
||
|
char cnames[CNAMSZ]; /* place where token and nonterminal names are stored */
|
||
|
int cnamsz = CNAMSZ; /* size of cnames */
|
||
|
char* cnamp = cnames; /* place where next name is to be put in */
|
||
|
int ndefout = 4; /* number of defined symbols output */
|
||
|
char* tempname;
|
||
|
char* actname;
|
||
|
char ttempname[] = TEMPNAME;
|
||
|
char tactname[] = ACTNAME;
|
||
|
char* parser;
|
||
|
char* yydebug;
|
||
|
int yyarg;
|
||
|
int yyline = 1;
|
||
|
|
||
|
/* storage of types */
|
||
|
int ntypes; /* number of types defined */
|
||
|
char* typeset[NTYPES]; /* pointers to type tags */
|
||
|
|
||
|
/* token information */
|
||
|
|
||
|
int ntokens = 0 ; /* number of tokens */
|
||
|
Symb tokset[NTERMS];
|
||
|
int toklev[NTERMS]; /* vector with the precedence of the terminals */
|
||
|
|
||
|
/* nonterminal information */
|
||
|
|
||
|
int nnonter = -1; /* the number of nonterminals */
|
||
|
Symb nontrst[NNONTERM];
|
||
|
int start; /* start symbol */
|
||
|
|
||
|
/* assigned token type values */
|
||
|
int extval = 0;
|
||
|
|
||
|
char* ytabc = OFILE; /* name of y.tab.c */
|
||
|
|
||
|
/* grammar rule information */
|
||
|
|
||
|
int mem0[MEMSIZE] ; /* production storage */
|
||
|
int* mem = mem0;
|
||
|
int nprod = 1; /* number of productions */
|
||
|
int* prdptr[NPROD]; /* pointers to descriptions of productions */
|
||
|
int levprd[NPROD]; /* precedence levels for the productions */
|
||
|
int rlines[NPROD]; /* line number for this rule */
|
||
|
|
||
|
/* state information */
|
||
|
|
||
|
int nstate = 0; /* number of states */
|
||
|
Item* pstate[NSTATES+2]; /* pointers to the descriptions of the states */
|
||
|
int tystate[NSTATES]; /* contains type information about the states */
|
||
|
int defact[NSTATES]; /* the default actions of states */
|
||
|
int tstates[NTERMS]; /* states generated by terminal gotos */
|
||
|
int ntstates[NNONTERM]; /* states generated by nonterminal gotos */
|
||
|
int mstates[NSTATES]; /* chain of overflows of term/nonterm generation lists */
|
||
|
int lastred; /* the number of the last reduction of a state */
|
||
|
|
||
|
/* lookahead set information */
|
||
|
|
||
|
Lkset lkst[LSETSIZE];
|
||
|
int nolook; /* flag to turn off lookahead computations */
|
||
|
int tbitset; /* size of lookahead sets */
|
||
|
int nlset = 0; /* next lookahead set index */
|
||
|
int nolook = 0; /* flag to suppress lookahead computations */
|
||
|
Lkset clset; /* temporary storage for lookahead computations */
|
||
|
|
||
|
/* working set information */
|
||
|
|
||
|
Wset wsets[WSETSIZE];
|
||
|
Wset* cwp;
|
||
|
|
||
|
/* storage for action table */
|
||
|
|
||
|
int amem[ACTSIZE]; /* action table storage */
|
||
|
int* memp = amem; /* next free action table position */
|
||
|
int indgo[NSTATES]; /* index to the stored goto table */
|
||
|
|
||
|
/* temporary vector, indexable by states, terms, or ntokens */
|
||
|
|
||
|
int temp1[TEMPSIZE]; /* temporary storage, indexed by terms + ntokens or states */
|
||
|
int lineno = 1; /* current input line number */
|
||
|
int fatfl = 1; /* if on, error is fatal */
|
||
|
int nerrors = 0; /* number of errors */
|
||
|
|
||
|
/* statistics collection variables */
|
||
|
|
||
|
int zzgoent;
|
||
|
int zzgobest;
|
||
|
int zzacent;
|
||
|
int zzexcp;
|
||
|
int zzclose;
|
||
|
int zzrrconf;
|
||
|
int zzsrconf;
|
||
|
|
||
|
int* ggreed = lkst[0].lset;
|
||
|
int* pgo = wsets[0].ws.lset;
|
||
|
int* yypgo = &nontrst[0].value;
|
||
|
|
||
|
int maxspr = 0; /* maximum spread of any entry */
|
||
|
int maxoff = 0; /* maximum offset into a array */
|
||
|
int* pmem = mem0;
|
||
|
int* maxa;
|
||
|
int nxdb = 0;
|
||
|
int adb = 0;
|
||
|
|
||
|
|
||
|
/* storage for information about the nonterminals */
|
||
|
|
||
|
int** pres[NNONTERM+2]; /* vector of pointers to productions yielding each nonterminal */
|
||
|
Lkset* pfirst[NNONTERM+2]; /* vector of pointers to first sets for each nonterminal */
|
||
|
int pempty[NNONTERM+1]; /* vector of nonterminals nontrivially deriving e */
|
||
|
|
||
|
/* random stuff picked out from between functions */
|
||
|
|
||
|
int indebug = 0;
|
||
|
Wset* zzcwp = wsets;
|
||
|
int zzgoent = 0;
|
||
|
int zzgobest = 0;
|
||
|
int zzacent = 0;
|
||
|
int zzexcp = 0;
|
||
|
int zzclose = 0;
|
||
|
int zzsrconf = 0;
|
||
|
int* zzmemsz = mem0;
|
||
|
int zzrrconf = 0;
|
||
|
int pidebug = 0; /* debugging flag for putitem */
|
||
|
int gsdebug = 0;
|
||
|
int cldebug = 0; /* debugging flag for closure */
|
||
|
int pkdebug = 0;
|
||
|
int g2debug = 0;
|
||
|
|
||
|
struct
|
||
|
{
|
||
|
char* name;
|
||
|
long value;
|
||
|
} resrv[] =
|
||
|
{
|
||
|
"binary", BINARY,
|
||
|
"left", LEFT,
|
||
|
"nonassoc", BINARY,
|
||
|
"prec", PREC,
|
||
|
"right", RIGHT,
|
||
|
"start", START,
|
||
|
"term", TERM,
|
||
|
"token", TERM,
|
||
|
"type", TYPEDEF,
|
||
|
"union", UNION,
|
||
|
0,
|
||
|
};
|
||
|
|
||
|
/* define functions */
|
||
|
|
||
|
void main(int, char**);
|
||
|
void others(void);
|
||
|
char* chcopy(char*, char*);
|
||
|
char* writem(int*);
|
||
|
char* symnam(int);
|
||
|
void summary(void);
|
||
|
void error(char*, ...);
|
||
|
void aryfil(int*, int, int);
|
||
|
int setunion(int*, int*);
|
||
|
void prlook(Lkset*);
|
||
|
void cpres(void);
|
||
|
void cpfir(void);
|
||
|
int state(int);
|
||
|
void putitem(int*, Lkset*);
|
||
|
void cempty(void);
|
||
|
void stagen(void);
|
||
|
void closure(int);
|
||
|
Lkset* flset(Lkset*);
|
||
|
void cleantmp(void);
|
||
|
void intr(void);
|
||
|
void setup(int, char**);
|
||
|
void finact(void);
|
||
|
int defin(int, char*);
|
||
|
void defout(int);
|
||
|
char* cstash(char*);
|
||
|
int isvalidchar(long);
|
||
|
long gettok(void);
|
||
|
int fdtype(int);
|
||
|
int chfind(int, char*);
|
||
|
void cpyunion(void);
|
||
|
void cpycode(void);
|
||
|
int skipcom(void);
|
||
|
void cpyact(int);
|
||
|
void openup(char*, int, int, int, char*);
|
||
|
void output(void);
|
||
|
int apack(int*, int);
|
||
|
void go2out(void);
|
||
|
void go2gen(int);
|
||
|
void precftn(int, int, int);
|
||
|
void wract(int);
|
||
|
void wrstate(int);
|
||
|
void warray(char*, int*, int);
|
||
|
void hideprod(void);
|
||
|
void callopt(void);
|
||
|
void gin(int);
|
||
|
void stin(int);
|
||
|
int nxti(void);
|
||
|
void osummary(void);
|
||
|
void aoutput(void);
|
||
|
void arout(char*, int*, int);
|
||
|
int gtnm(void);
|
||
|
|
||
|
void
|
||
|
main(int argc, char *argv[])
|
||
|
{
|
||
|
PARSER = unsharp(PARSER);
|
||
|
PARSERS = unsharp(PARSERS);
|
||
|
parser = PARSER;
|
||
|
|
||
|
setup(argc, argv); /* initialize and read productions */
|
||
|
tbitset = NWORDS(ntokens);
|
||
|
cpres(); /* make table of which productions yield a given nonterminal */
|
||
|
cempty(); /* make a table of which nonterminals can match the empty string */
|
||
|
cpfir(); /* make a table of firsts of nonterminals */
|
||
|
stagen(); /* generate the states */
|
||
|
output(); /* write the states and the tables */
|
||
|
go2out();
|
||
|
hideprod();
|
||
|
summary();
|
||
|
callopt();
|
||
|
others();
|
||
|
exits(0);
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* put out other arrays, copy the parsers
|
||
|
*/
|
||
|
void
|
||
|
others(void)
|
||
|
{
|
||
|
int c, i, j;
|
||
|
|
||
|
finput = Bopen(parser, OREAD);
|
||
|
if(finput == 0)
|
||
|
error("cannot open parser %s: %r", parser);
|
||
|
warray("yyr1", levprd, nprod);
|
||
|
aryfil(temp1, nprod, 0);
|
||
|
PLOOP(1, i)
|
||
|
temp1[i] = prdptr[i+1]-prdptr[i]-2;
|
||
|
warray("yyr2", temp1, nprod);
|
||
|
|
||
|
aryfil(temp1, nstate, -1000);
|
||
|
TLOOP(i)
|
||
|
for(j=tstates[i]; j!=0; j=mstates[j])
|
||
|
temp1[j] = i;
|
||
|
NTLOOP(i)
|
||
|
for(j=ntstates[i]; j!=0; j=mstates[j])
|
||
|
temp1[j] = -i;
|
||
|
warray("yychk", temp1, nstate);
|
||
|
warray("yydef", defact, nstate);
|
||
|
|
||
|
/* put out token translation tables */
|
||
|
/* table 1 has 0-256 */
|
||
|
aryfil(temp1, 256, 0);
|
||
|
c = 0;
|
||
|
TLOOP(i) {
|
||
|
j = tokset[i].value;
|
||
|
if(j >= 0 && j < 256) {
|
||
|
if(temp1[j]) {
|
||
|
print("yacc bug -- cant have 2 different Ts with same value\n");
|
||
|
print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name);
|
||
|
nerrors++;
|
||
|
}
|
||
|
temp1[j] = i;
|
||
|
if(j > c)
|
||
|
c = j;
|
||
|
}
|
||
|
}
|
||
|
warray("yytok1", temp1, c+1);
|
||
|
|
||
|
/* table 2 has PRIVATE-PRIVATE+256 */
|
||
|
aryfil(temp1, 256, 0);
|
||
|
c = 0;
|
||
|
TLOOP(i) {
|
||
|
j = tokset[i].value - PRIVATE;
|
||
|
if(j >= 0 && j < 256) {
|
||
|
if(temp1[j]) {
|
||
|
print("yacc bug -- cant have 2 different Ts with same value\n");
|
||
|
print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name);
|
||
|
nerrors++;
|
||
|
}
|
||
|
temp1[j] = i;
|
||
|
if(j > c)
|
||
|
c = j;
|
||
|
}
|
||
|
}
|
||
|
warray("yytok2", temp1, c+1);
|
||
|
|
||
|
/* table 3 has everything else */
|
||
|
Bprint(ftable, "static\tconst\tlong yytok3[] =\n{\n");
|
||
|
c = 0;
|
||
|
TLOOP(i) {
|
||
|
j = tokset[i].value;
|
||
|
if(j >= 0 && j < 256)
|
||
|
continue;
|
||
|
if(j >= PRIVATE && j < 256+PRIVATE)
|
||
|
continue;
|
||
|
|
||
|
Bprint(ftable, "%4d,%4d,", j, i);
|
||
|
c++;
|
||
|
if(c%5 == 0)
|
||
|
Bprint(ftable, "\n");
|
||
|
}
|
||
|
Bprint(ftable, "%4d\n};\n", 0);
|
||
|
|
||
|
/* copy parser text */
|
||
|
while((c=Bgetrune(finput)) != Beof) {
|
||
|
if(c == '$') {
|
||
|
if((c = Bgetrune(finput)) != 'A')
|
||
|
Bputrune(ftable, '$');
|
||
|
else { /* copy actions */
|
||
|
faction = Bopen(actname, OREAD);
|
||
|
if(faction == 0)
|
||
|
error("cannot reopen action tempfile");
|
||
|
while((c=Bgetrune(faction)) != Beof)
|
||
|
Bputrune(ftable, c);
|
||
|
Bterm(faction);
|
||
|
ZAPFILE(actname);
|
||
|
c = Bgetrune(finput);
|
||
|
}
|
||
|
}
|
||
|
Bputrune(ftable, c);
|
||
|
}
|
||
|
Bterm(ftable);
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* copies string q into p, returning next free char ptr
|
||
|
*/
|
||
|
char*
|
||
|
chcopy(char* p, char* q)
|
||
|
{
|
||
|
int c;
|
||
|
|
||
|
while(c = *q) {
|
||
|
if(c == '"')
|
||
|
*p++ = '\\';
|
||
|
*p++ = c;
|
||
|
q++;
|
||
|
}
|
||
|
*p = 0;
|
||
|
return p;
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* creates output string for item pointed to by pp
|
||
|
*/
|
||
|
char*
|
||
|
writem(int *pp)
|
||
|
{
|
||
|
int i,*p;
|
||
|
static char sarr[ISIZE];
|
||
|
char* q;
|
||
|
|
||
|
for(p=pp; *p>0; p++)
|
||
|
;
|
||
|
p = prdptr[-*p];
|
||
|
q = chcopy(sarr, nontrst[*p-NTBASE].name);
|
||
|
q = chcopy(q, ": ");
|
||
|
for(;;) {
|
||
|
*q = ' ';
|
||
|
p++;
|
||
|
if(p == pp)
|
||
|
*q = '.';
|
||
|
q++;
|
||
|
*q = '\0';
|
||
|
i = *p;
|
||
|
if(i <= 0)
|
||
|
break;
|
||
|
q = chcopy(q, symnam(i));
|
||
|
if(q > &sarr[ISIZE-30])
|
||
|
error("item too big");
|
||
|
}
|
||
|
|
||
|
/* an item calling for a reduction */
|
||
|
i = *pp;
|
||
|
if(i < 0 ) {
|
||
|
q = chcopy(q, " (");
|
||
|
sprint(q, "%d)", -i);
|
||
|
}
|
||
|
return sarr;
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* return a pointer to the name of symbol i
|
||
|
*/
|
||
|
char*
|
||
|
symnam(int i)
|
||
|
{
|
||
|
char* cp;
|
||
|
|
||
|
cp = (i >= NTBASE)? nontrst[i-NTBASE].name: tokset[i].name;
|
||
|
if(*cp == ' ')
|
||
|
cp++;
|
||
|
return cp;
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* output the summary on y.output
|
||
|
*/
|
||
|
void
|
||
|
summary(void)
|
||
|
{
|
||
|
|
||
|
if(foutput != 0) {
|
||
|
Bprint(foutput, "\n%d/%d terminals, %d/%d nonterminals\n",
|
||
|
ntokens, NTERMS, nnonter, NNONTERM);
|
||
|
Bprint(foutput, "%d/%d grammar rules, %d/%d states\n",
|
||
|
nprod, NPROD, nstate, NSTATES);
|
||
|
Bprint(foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n",
|
||
|
zzsrconf, zzrrconf);
|
||
|
Bprint(foutput, "%d/%d working sets used\n",
|
||
|
(int)(zzcwp-wsets), WSETSIZE);
|
||
|
Bprint(foutput, "memory: states,etc. %d/%d, parser %d/%d\n",
|
||
|
(int)(zzmemsz-mem0), MEMSIZE, (int)(memp-amem), ACTSIZE);
|
||
|
Bprint(foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE);
|
||
|
Bprint(foutput, "%d extra closures\n", zzclose - 2*nstate);
|
||
|
Bprint(foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp);
|
||
|
Bprint(foutput, "%d goto entries\n", zzgoent);
|
||
|
Bprint(foutput, "%d entries saved by goto default\n", zzgobest);
|
||
|
}
|
||
|
if(zzsrconf != 0 || zzrrconf != 0) {
|
||
|
print("\nconflicts: ");
|
||
|
if(zzsrconf)
|
||
|
print("%d shift/reduce", zzsrconf);
|
||
|
if(zzsrconf && zzrrconf)
|
||
|
print(", ");
|
||
|
if(zzrrconf)
|
||
|
print("%d reduce/reduce", zzrrconf);
|
||
|
print("\n");
|
||
|
}
|
||
|
if(ftemp != 0) {
|
||
|
Bterm(ftemp);
|
||
|
ftemp = 0;
|
||
|
}
|
||
|
if(fdefine != 0) {
|
||
|
Bterm(fdefine);
|
||
|
fdefine = 0;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* write out error comment -- NEEDS WORK
|
||
|
*/
|
||
|
void
|
||
|
error(char *s, ...)
|
||
|
{
|
||
|
va_list arg;
|
||
|
|
||
|
nerrors++;
|
||
|
fprint(2, "\n fatal error:");
|
||
|
va_start(arg, s);
|
||
|
vfprint(2, s, arg);
|
||
|
va_end(arg);
|
||
|
fprint(2, ", %s:%d\n", infile, lineno);
|
||
|
if(!fatfl)
|
||
|
return;
|
||
|
summary();
|
||
|
cleantmp();
|
||
|
exits("error");
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* set elements 0 through n-1 to c
|
||
|
*/
|
||
|
void
|
||
|
aryfil(int *v, int n, int c)
|
||
|
{
|
||
|
int i;
|
||
|
|
||
|
for(i=0; i<n; i++)
|
||
|
v[i] = c;
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* set a to the union of a and b
|
||
|
* return 1 if b is not a subset of a, 0 otherwise
|
||
|
*/
|
||
|
int
|
||
|
setunion(int *a, int *b)
|
||
|
{
|
||
|
int i, x, sub;
|
||
|
|
||
|
sub = 0;
|
||
|
SETLOOP(i) {
|
||
|
x = *a;
|
||
|
*a |= *b;
|
||
|
if(*a != x)
|
||
|
sub = 1;
|
||
|
a++;
|
||
|
b++;
|
||
|
}
|
||
|
return sub;
|
||
|
}
|
||
|
|
||
|
void
|
||
|
prlook(Lkset* p)
|
||
|
{
|
||
|
int j, *pp;
|
||
|
|
||
|
pp = p->lset;
|
||
|
if(pp == 0)
|
||
|
Bprint(foutput, "\tNULL");
|
||
|
else {
|
||
|
Bprint(foutput, " { ");
|
||
|
TLOOP(j)
|
||
|
if(BIT(pp,j))
|
||
|
Bprint(foutput, "%s ", symnam(j));
|
||
|
Bprint(foutput, "}");
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* compute an array with the beginnings of productions yielding given nonterminals
|
||
|
* The array pres points to these lists
|
||
|
* the array pyield has the lists: the total size is only NPROD+1
|
||
|
*/
|
||
|
void
|
||
|
cpres(void)
|
||
|
{
|
||
|
int c, j, i, **pmem;
|
||
|
static int *pyield[NPROD];
|
||
|
|
||
|
pmem = pyield;
|
||
|
NTLOOP(i) {
|
||
|
c = i+NTBASE;
|
||
|
pres[i] = pmem;
|
||
|
fatfl = 0; /* make undefined symbols nonfatal */
|
||
|
PLOOP(0, j)
|
||
|
if(*prdptr[j] == c)
|
||
|
*pmem++ = prdptr[j]+1;
|
||
|
if(pres[i] == pmem)
|
||
|
error("nonterminal %s not defined!", nontrst[i].name);
|
||
|
}
|
||
|
pres[i] = pmem;
|
||
|
fatfl = 1;
|
||
|
if(nerrors) {
|
||
|
summary();
|
||
|
cleantmp();
|
||
|
exits("error");
|
||
|
}
|
||
|
if(pmem != &pyield[nprod])
|
||
|
error("internal Yacc error: pyield %d", pmem-&pyield[nprod]);
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* compute an array with the first of nonterminals
|
||
|
*/
|
||
|
void
|
||
|
cpfir(void)
|
||
|
{
|
||
|
int *p, **s, i, **t, ch, changes;
|
||
|
|
||
|
zzcwp = &wsets[nnonter];
|
||
|
NTLOOP(i) {
|
||
|
aryfil(wsets[i].ws.lset, tbitset, 0);
|
||
|
t = pres[i+1];
|
||
|
/* initially fill the sets */
|
||
|
for(s=pres[i]; s<t; ++s)
|
||
|
for(p = *s; (ch = *p) > 0; ++p) {
|
||
|
if(ch < NTBASE) {
|
||
|
SETBIT(wsets[i].ws.lset, ch);
|
||
|
break;
|
||
|
}
|
||
|
if(!pempty[ch-NTBASE])
|
||
|
break;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/* now, reflect transitivity */
|
||
|
changes = 1;
|
||
|
while(changes) {
|
||
|
changes = 0;
|
||
|
NTLOOP(i) {
|
||
|
t = pres[i+1];
|
||
|
for(s = pres[i]; s < t; ++s)
|
||
|
for(p = *s; (ch = (*p-NTBASE)) >= 0; ++p) {
|
||
|
changes |= setunion(wsets[i].ws.lset, wsets[ch].ws.lset);
|
||
|
if(!pempty[ch])
|
||
|
break;
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
NTLOOP(i)
|
||
|
pfirst[i] = flset(&wsets[i].ws);
|
||
|
if(!indebug)
|
||
|
return;
|
||
|
if(foutput != 0)
|
||
|
NTLOOP(i) {
|
||
|
Bprint(foutput, "\n%s: ", nontrst[i].name);
|
||
|
prlook(pfirst[i]);
|
||
|
Bprint(foutput, " %d\n", pempty[i]);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* sorts last state,and sees if it equals earlier ones. returns state number
|
||
|
*/
|
||
|
int
|
||
|
state(int c)
|
||
|
{
|
||
|
Item *p1, *p2, *k, *l, *q1, *q2;
|
||
|
int size1, size2, i;
|
||
|
|
||
|
p1 = pstate[nstate];
|
||
|
p2 = pstate[nstate+1];
|
||
|
if(p1 == p2)
|
||
|
return 0; /* null state */
|
||
|
/* sort the items */
|
||
|
for(k = p2-1; k > p1; k--) /* make k the biggest */
|
||
|
for(l = k-1; l >= p1; --l)
|
||
|
if(l->pitem > k->pitem) {
|
||
|
int *s;
|
||
|
Lkset *ss;
|
||
|
|
||
|
s = k->pitem;
|
||
|
k->pitem = l->pitem;
|
||
|
l->pitem = s;
|
||
|
ss = k->look;
|
||
|
k->look = l->look;
|
||
|
l->look = ss;
|
||
|
}
|
||
|
size1 = p2 - p1; /* size of state */
|
||
|
|
||
|
for(i = (c>=NTBASE)? ntstates[c-NTBASE]: tstates[c]; i != 0; i = mstates[i]) {
|
||
|
/* get ith state */
|
||
|
q1 = pstate[i];
|
||
|
q2 = pstate[i+1];
|
||
|
size2 = q2 - q1;
|
||
|
if(size1 != size2)
|
||
|
continue;
|
||
|
k = p1;
|
||
|
for(l = q1; l < q2; l++) {
|
||
|
if(l->pitem != k->pitem)
|
||
|
break;
|
||
|
k++;
|
||
|
}
|
||
|
if(l != q2)
|
||
|
continue;
|
||
|
/* found it */
|
||
|
pstate[nstate+1] = pstate[nstate]; /* delete last state */
|
||
|
/* fix up lookaheads */
|
||
|
if(nolook)
|
||
|
return i;
|
||
|
for(l = q1, k = p1; l < q2; ++l, ++k ) {
|
||
|
int s;
|
||
|
|
||
|
SETLOOP(s)
|
||
|
clset.lset[s] = l->look->lset[s];
|
||
|
if(setunion(clset.lset, k->look->lset)) {
|
||
|
tystate[i] = MUSTDO;
|
||
|
/* register the new set */
|
||
|
l->look = flset( &clset );
|
||
|
}
|
||
|
}
|
||
|
return i;
|
||
|
}
|
||
|
/* state is new */
|
||
|
if(nolook)
|
||
|
error("yacc state/nolook error");
|
||
|
pstate[nstate+2] = p2;
|
||
|
if(nstate+1 >= NSTATES)
|
||
|
error("too many states");
|
||
|
if(c >= NTBASE) {
|
||
|
mstates[nstate] = ntstates[c-NTBASE];
|
||
|
ntstates[c-NTBASE] = nstate;
|
||
|
} else {
|
||
|
mstates[nstate] = tstates[c];
|
||
|
tstates[c] = nstate;
|
||
|
}
|
||
|
tystate[nstate] = MUSTDO;
|
||
|
return nstate++;
|
||
|
}
|
||
|
|
||
|
void
|
||
|
putitem(int *ptr, Lkset *lptr)
|
||
|
{
|
||
|
Item *j;
|
||
|
|
||
|
if(pidebug && foutput != 0)
|
||
|
Bprint(foutput, "putitem(%s), state %d\n", writem(ptr), nstate);
|
||
|
j = pstate[nstate+1];
|
||
|
j->pitem = ptr;
|
||
|
if(!nolook)
|
||
|
j->look = flset(lptr);
|
||
|
pstate[nstate+1] = ++j;
|
||
|
if((int*)j > zzmemsz) {
|
||
|
zzmemsz = (int*)j;
|
||
|
if(zzmemsz >= &mem0[MEMSIZE])
|
||
|
error("out of state space");
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* mark nonterminals which derive the empty string
|
||
|
* also, look for nonterminals which don't derive any token strings
|
||
|
*/
|
||
|
void
|
||
|
cempty(void)
|
||
|
{
|
||
|
|
||
|
int i, *p;
|
||
|
|
||
|
/* first, use the array pempty to detect productions that can never be reduced */
|
||
|
/* set pempty to WHONOWS */
|
||
|
aryfil(pempty, nnonter+1, WHOKNOWS);
|
||
|
|
||
|
/* now, look at productions, marking nonterminals which derive something */
|
||
|
more:
|
||
|
PLOOP(0, i) {
|
||
|
if(pempty[*prdptr[i] - NTBASE])
|
||
|
continue;
|
||
|
for(p = prdptr[i]+1; *p >= 0; ++p)
|
||
|
if(*p >= NTBASE && pempty[*p-NTBASE] == WHOKNOWS)
|
||
|
break;
|
||
|
/* production can be derived */
|
||
|
if(*p < 0) {
|
||
|
pempty[*prdptr[i]-NTBASE] = OK;
|
||
|
goto more;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/* now, look at the nonterminals, to see if they are all OK */
|
||
|
NTLOOP(i) {
|
||
|
/* the added production rises or falls as the start symbol ... */
|
||
|
if(i == 0)
|
||
|
continue;
|
||
|
if(pempty[i] != OK) {
|
||
|
fatfl = 0;
|
||
|
error("nonterminal %s never derives any token string", nontrst[i].name);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
if(nerrors) {
|
||
|
summary();
|
||
|
cleantmp();
|
||
|
exits("error");
|
||
|
}
|
||
|
|
||
|
/* now, compute the pempty array, to see which nonterminals derive the empty string */
|
||
|
/* set pempty to WHOKNOWS */
|
||
|
aryfil( pempty, nnonter+1, WHOKNOWS);
|
||
|
|
||
|
/* loop as long as we keep finding empty nonterminals */
|
||
|
|
||
|
again:
|
||
|
PLOOP(1, i) {
|
||
|
/* not known to be empty */
|
||
|
if(pempty[*prdptr[i]-NTBASE] == WHOKNOWS) {
|
||
|
for(p = prdptr[i]+1; *p >= NTBASE && pempty[*p-NTBASE] == EMPTY ; ++p)
|
||
|
;
|
||
|
/* we have a nontrivially empty nonterminal */
|
||
|
if(*p < 0) {
|
||
|
pempty[*prdptr[i]-NTBASE] = EMPTY;
|
||
|
/* got one ... try for another */
|
||
|
goto again;
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* generate the states
|
||
|
*/
|
||
|
void
|
||
|
stagen(void)
|
||
|
{
|
||
|
|
||
|
int c, i, j, more;
|
||
|
Wset *p, *q;
|
||
|
|
||
|
/* initialize */
|
||
|
nstate = 0;
|
||
|
|
||
|
/* THIS IS FUNNY from the standpoint of portability
|
||
|
* it represents the magic moment when the mem0 array, which has
|
||
|
* been holding the productions, starts to hold item pointers, of a
|
||
|
* different type...
|
||
|
* someday, alloc should be used to allocate all this stuff... for now, we
|
||
|
* accept that if pointers don't fit in integers, there is a problem...
|
||
|
*/
|
||
|
|
||
|
pstate[0] = pstate[1] = (Item*)mem;
|
||
|
aryfil(clset.lset, tbitset, 0);
|
||
|
putitem(prdptr[0]+1, &clset);
|
||
|
tystate[0] = MUSTDO;
|
||
|
nstate = 1;
|
||
|
pstate[2] = pstate[1];
|
||
|
|
||
|
aryfil(amem, ACTSIZE, 0);
|
||
|
|
||
|
/* now, the main state generation loop */
|
||
|
for(more=1; more;) {
|
||
|
more = 0;
|
||
|
SLOOP(i) {
|
||
|
if(tystate[i] != MUSTDO)
|
||
|
continue;
|
||
|
tystate[i] = DONE;
|
||
|
aryfil(temp1, nnonter+1, 0);
|
||
|
/* take state i, close it, and do gotos */
|
||
|
closure(i);
|
||
|
/* generate goto's */
|
||
|
WSLOOP(wsets, p) {
|
||
|
if(p->flag)
|
||
|
continue;
|
||
|
p->flag = 1;
|
||
|
c = *(p->pitem);
|
||
|
if(c <= 1) {
|
||
|
if(pstate[i+1]-pstate[i] <= p-wsets)
|
||
|
tystate[i] = MUSTLOOKAHEAD;
|
||
|
continue;
|
||
|
}
|
||
|
/* do a goto on c */
|
||
|
WSLOOP(p, q)
|
||
|
/* this item contributes to the goto */
|
||
|
if(c == *(q->pitem)) {
|
||
|
putitem(q->pitem+1, &q->ws);
|
||
|
q->flag = 1;
|
||
|
}
|
||
|
if(c < NTBASE)
|
||
|
state(c); /* register new state */
|
||
|
else
|
||
|
temp1[c-NTBASE] = state(c);
|
||
|
}
|
||
|
if(gsdebug && foutput != 0) {
|
||
|
Bprint(foutput, "%d: ", i);
|
||
|
NTLOOP(j)
|
||
|
if(temp1[j])
|
||
|
Bprint(foutput, "%s %d, ",
|
||
|
nontrst[j].name, temp1[j]);
|
||
|
Bprint(foutput, "\n");
|
||
|
}
|
||
|
indgo[i] = apack(&temp1[1], nnonter-1) - 1;
|
||
|
/* do some more */
|
||
|
more = 1;
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* generate the closure of state i
|
||
|
*/
|
||
|
void
|
||
|
closure(int i)
|
||
|
{
|
||
|
|
||
|
Wset *u, *v;
|
||
|
Item *p, *q;
|
||
|
int c, ch, work, k, *pi, **s, **t;
|
||
|
|
||
|
zzclose++;
|
||
|
|
||
|
/* first, copy kernel of state i to wsets */
|
||
|
cwp = wsets;
|
||
|
ITMLOOP(i, p, q) {
|
||
|
cwp->pitem = p->pitem;
|
||
|
cwp->flag = 1; /* this item must get closed */
|
||
|
SETLOOP(k)
|
||
|
cwp->ws.lset[k] = p->look->lset[k];
|
||
|
WSBUMP(cwp);
|
||
|
}
|
||
|
|
||
|
/* now, go through the loop, closing each item */
|
||
|
work = 1;
|
||
|
while(work) {
|
||
|
work = 0;
|
||
|
WSLOOP(wsets, u) {
|
||
|
if(u->flag == 0)
|
||
|
continue;
|
||
|
/* dot is before c */
|
||
|
c = *(u->pitem);
|
||
|
if(c < NTBASE) {
|
||
|
u->flag = 0;
|
||
|
/* only interesting case is where . is before nonterminal */
|
||
|
continue;
|
||
|
}
|
||
|
|
||
|
/* compute the lookahead */
|
||
|
aryfil(clset.lset, tbitset, 0);
|
||
|
|
||
|
/* find items involving c */
|
||
|
WSLOOP(u, v)
|
||
|
if(v->flag == 1 && *(pi=v->pitem) == c) {
|
||
|
v->flag = 0;
|
||
|
if(nolook)
|
||
|
continue;
|
||
|
while((ch = *++pi) > 0) {
|
||
|
/* terminal symbol */
|
||
|
if(ch < NTBASE) {
|
||
|
SETBIT(clset.lset, ch);
|
||
|
break;
|
||
|
}
|
||
|
/* nonterminal symbol */
|
||
|
setunion(clset.lset, pfirst[ch-NTBASE]->lset);
|
||
|
if(!pempty[ch-NTBASE])
|
||
|
break;
|
||
|
}
|
||
|
if(ch <= 0)
|
||
|
setunion(clset.lset, v->ws.lset);
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* now loop over productions derived from c
|
||
|
* c is now nonterminal number
|
||
|
*/
|
||
|
c -= NTBASE;
|
||
|
t = pres[c+1];
|
||
|
for(s = pres[c]; s < t; ++s) {
|
||
|
/*
|
||
|
* put these items into the closure
|
||
|
* is the item there
|
||
|
*/
|
||
|
WSLOOP(wsets, v)
|
||
|
/* yes, it is there */
|
||
|
if(v->pitem == *s) {
|
||
|
if(nolook)
|
||
|
goto nexts;
|
||
|
if(setunion(v->ws.lset, clset.lset))
|
||
|
v->flag = work = 1;
|
||
|
goto nexts;
|
||
|
}
|
||
|
|
||
|
/* not there; make a new entry */
|
||
|
if(cwp-wsets+1 >= WSETSIZE)
|
||
|
error( "working set overflow");
|
||
|
cwp->pitem = *s;
|
||
|
cwp->flag = 1;
|
||
|
if(!nolook) {
|
||
|
work = 1;
|
||
|
SETLOOP(k) cwp->ws.lset[k] = clset.lset[k];
|
||
|
}
|
||
|
WSBUMP(cwp);
|
||
|
|
||
|
nexts:;
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/* have computed closure; flags are reset; return */
|
||
|
if(cwp > zzcwp)
|
||
|
zzcwp = cwp;
|
||
|
if(cldebug && foutput != 0) {
|
||
|
Bprint(foutput, "\nState %d, nolook = %d\n", i, nolook);
|
||
|
WSLOOP(wsets, u) {
|
||
|
if(u->flag)
|
||
|
Bprint(foutput, "flag set!\n");
|
||
|
u->flag = 0;
|
||
|
Bprint(foutput, "\t%s", writem(u->pitem));
|
||
|
prlook(&u->ws);
|
||
|
Bprint(foutput, "\n");
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
* decide if the lookahead set pointed to by p is known
|
||
|
* return pointer to a perminent location for the set
|
||
|
*/
|
||
|
Lkset*
|
||
|
flset(Lkset *p)
|
||
|
{
|
||
|
Lkset *q;
|
||
|
int *u, *v, *w, j;
|
||
|
|
||
|
for(q = &lkst[nlset]; q-- > lkst;) {
|
||
|
u = p->lset;
|
||
|
v = q->lset;
|
||
|
w = &v[tbitset];
|
||
|
while(v < w)
|
||
|
if(*u++ != *v++)
|
||
|
goto more;
|
||
|
/* we have matched */
|
||
|
return q;
|
||
|
more:;
|
||
|
}
|
||
|
/* add a new one */
|
||
|
q = &lkst[nlset++];
|
||
|
if(nlset >= LSETSIZE)
|
||
|
error("too many lookahead sets");
|
||
|
SETLOOP(j)
|
||
|
q->lset[j] = p->lset[j];
|
||
|
return q;
|
||
|
}
|
||
|
|
||
|
void
|
||
|
cleantmp(void)
|
||
|
{
|
||
|
ZAPFILE(actname);
|
||
|
ZAPFILE(tempname);
|
||
|
}
|
||
|
|
||
|
void
|
||
|
intr(void)
|
||
|
{
|
||
|
cleantmp();
|
||
|
exits("interrupted");
|
||
|
}
|
||
|
|
||
|
void
|
||
|
setup(int argc, char *argv[])
|
||
|
{
|
||
|
long c, t;
|
||
|
int i, j, fd, lev, ty, ytab, *p;
|
||
|
int vflag, dflag, stem;
|
||
|
char actnm[8], *stemc, *s, dirbuf[128];
|
||
|
Biobuf *fout;
|
||
|
|
||
|
ytab = 0;
|
||
|
vflag = 0;
|
||
|
dflag = 0;
|
||
|
stem = 0;
|
||
|
stemc = "y";
|
||
|
foutput = 0;
|
||
|
fdefine = 0;
|
||
|
fdebug = 0;
|
||
|
ARGBEGIN{
|
||
|
case 'v':
|
||
|
case 'V':
|
||
|
vflag++;
|
||
|
break;
|
||
|
case 'D':
|
||
|
yydebug = ARGF();
|
||
|
break;
|
||
|
case 'a':
|
||
|
yyarg = 1;
|
||
|
break;
|
||
|
case 'd':
|