From de223f8eaf1a08557abbe8371c0d45313a37436e Mon Sep 17 00:00:00 2001 From: Alan Cox Date: Wed, 25 Oct 2017 00:03:23 +0100 Subject: [PATCH] v7yacc: Add the V7 yacc as a cross building tool --- Applications/v7yacc/Makefile | 7 + Applications/v7yacc/README | 45 ++ Applications/v7yacc/dextern.h | 264 +++++++++ Applications/v7yacc/prototype.h | 47 ++ Applications/v7yacc/y1.c | 728 ++++++++++++++++++++++++ Applications/v7yacc/y2.c | 971 ++++++++++++++++++++++++++++++++ Applications/v7yacc/y3.c | 449 +++++++++++++++ Applications/v7yacc/y4.c | 380 +++++++++++++ 8 files changed, 2891 insertions(+) create mode 100644 Applications/v7yacc/Makefile create mode 100644 Applications/v7yacc/README create mode 100644 Applications/v7yacc/dextern.h create mode 100644 Applications/v7yacc/prototype.h create mode 100644 Applications/v7yacc/y1.c create mode 100644 Applications/v7yacc/y2.c create mode 100644 Applications/v7yacc/y3.c create mode 100644 Applications/v7yacc/y4.c diff --git a/Applications/v7yacc/Makefile b/Applications/v7yacc/Makefile new file mode 100644 index 00000000..324780c0 --- /dev/null +++ b/Applications/v7yacc/Makefile @@ -0,0 +1,7 @@ +SRCS = y1.c y2.c y3.c y4.c + +CFLAGS = -O2 + +v7yacc: $(SRCS) + gcc $(CFLAGS) -o v7yacc $(SRCS) + \ No newline at end of file diff --git a/Applications/v7yacc/README b/Applications/v7yacc/README new file mode 100644 index 00000000..ca854999 --- /dev/null +++ b/Applications/v7yacc/README @@ -0,0 +1,45 @@ +This is a port of the V7 yacc to produce 16bit int output for crossbuilding +ancient code. + +======================================================================== +The following copyright notice applies to the UNIX Version 7 and +32V UNIX portions of this distribution: + +Copyright (C) Caldera International Inc. 2001-2002. All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions +are met: + +Redistributions of source code and documentation must retain the +above copyright notice, this list of conditions and the following +disclaimer. Redistributions in binary form must reproduce the above +copyright notice, this list of conditions and the following disclaimer +in the documentation and/or other materials provided with the +distribution. + +All advertising materials mentioning features or use of this software +must display the following acknowledgement: + +This product includes software developed or owned by Caldera +International, Inc. + +Neither the name of Caldera International, Inc. nor the names of +other contributors may be used to endorse or promote products derived +from this software without specific prior written permission. + +USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENCE BY CALDERA +INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR +IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT +OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR +BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, +WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE +OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, +EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + +======================================================================== diff --git a/Applications/v7yacc/dextern.h b/Applications/v7yacc/dextern.h new file mode 100644 index 00000000..2dfa6956 --- /dev/null +++ b/Applications/v7yacc/dextern.h @@ -0,0 +1,264 @@ +#include +#include + + /* this file has the location of the parser, and the size of the progam desired */ + /* It may also contain definitions to override various defaults: for example, */ + /* WORD32 tells yacc that there are at least 32 bits per int */ + /* on some systems, notably IBM, the names for the output files and tempfiles must */ + /* also be changed */ + + /* location of the parser text file */ +#define PARSER "/usr/lib/yaccpar" + + /* basic size of the Yacc implementation */ +#define MEDIUM + + /* MANIFEST CONSTANT DEFINITIONS */ + + /* base of nonterminal internal numbers */ +#define NTBASE 010000 + + /* internal codes for error and accept actions */ + +#define ERRCODE 8190 +#define ACCEPTCODE 8191 + + /* sizes and limits */ + +#ifdef HUGE +#define ACTSIZE 12000 +#define MEMSIZE 12000 +#define NSTATES 750 +#define NTERMS 127 +#define NPROD 600 +#define NNONTERM 300 +#define TEMPSIZE 1200 +#define CNAMSZ 5000 +#define LSETSIZE 600 +#define WSETSIZE 350 +#endif + +#ifdef MEDIUM +#define ACTSIZE 4000 +#define MEMSIZE 5200 +#define NSTATES 600 +#define NTERMS 127 +#define NPROD 400 +#define NNONTERM 200 +#define TEMPSIZE 800 +#define CNAMSZ 4000 +#define LSETSIZE 450 +#define WSETSIZE 250 +#endif + +#define NAMESIZE 50 +#define NTYPES 63 + +#ifdef WORD32 +#define TBITSET ((32+NTERMS)/32) + + /* bit packing macros (may be machine dependent) */ +#define BIT(a,i) ((a)[(i)>>5] & (1<<((i)&037))) +#define SETBIT(a,i) ((a)[(i)>>5] |= (1<<((i)&037))) + + /* number of words needed to hold n+1 bits */ +#define NWORDS(n) (((n)+32)/32) + +#else + +#define TBITSET ((16+NTERMS)/16) + + /* bit packing macros (may be machine dependent) */ +#define BIT(a,i) ((a)[(i)>>4] & (1<<((i)&017))) +#define SETBIT(a,i) ((a)[(i)>>4] |= (1<<((i)&017))) + + /* number of words needed to hold n+1 bits */ +#define NWORDS(n) (((n)+16)/16) +#endif + + /* relationships which must hold: + TBITSET ints must hold NTERMS+1 bits... + WSETSIZE >= NNONTERM + LSETSIZE >= NNONTERM + TEMPSIZE >= NTERMS + NNONTERMs + 1 + TEMPSIZE >= NSTATES + */ + + /* associativities */ + +#define NOASC 0 /* no assoc. */ +#define LASC 1 /* left assoc. */ +#define RASC 2 /* right assoc. */ +#define BASC 3 /* binary assoc. */ + + /* flags for state generation */ + +#define DONE 0 +#define MUSTDO 1 +#define MUSTLOOKAHEAD 2 + + /* flags for a rule having an action, and being reduced */ + +#define ACTFLAG 04 +#define REDFLAG 010 + + /* output parser flags */ +#define YYFLAG1 (-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 +#include +#include "dextern.h" +#include "prototype.h" + + /* variables used locally */ + + /* lookahead computations */ + +int tbitset; /* size of lookahead sets */ +struct looksets lkst[LSETSIZE]; +int nlset = 0; /* next lookahead set index */ +int nolook = 0; /* flag to suppress lookahead computations */ +struct looksets clset; /* temporary storage for lookahead computations */ + + /* working set computations */ + +struct wset wsets[WSETSIZE]; +struct wset *cwp; + + /* state information */ + +int nstate = 0; /* number of states */ +struct item *pstate[NSTATES + 2]; /* pointers to the descriptions of the states */ +int tystate[NSTATES]; /* contains type information about the states */ +int indgo[NSTATES]; /* index to the stored goto table */ +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 */ + + /* storage for the actions in the parser */ + +int amem[ACTSIZE]; /* action table storage */ +int *memp = amem; /* next free action table position */ + + /* other storage areas */ + +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 */ + + /* storage for information about the nonterminals */ + +int **pres[NNONTERM + 2]; /* vector of pointers to productions yielding each nonterminal */ +struct looksets *pfirst[NNONTERM + 2]; /* vector of pointers to first sets for each nonterminal */ +int pempty[NNONTERM + 1]; /* vector of nonterminals nontrivially deriving e */ + +int main(int argc, char *argv[]) +{ + + 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(); + exit(0); +} + +void others(void) +{ /* put out other arrays, copy the parsers */ + int c, i, j; + + finput = fopen(PARSER, "r"); + if (finput == NULL) + error("cannot find parser %s", 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] = tokset[i].value; + } + } + NTLOOP(i) { + for (j = ntstates[i]; j != 0; j = mstates[j]) { + temp1[j] = -i; + } + } + warray("yychk", temp1, nstate); + + warray("yydef", defact, nstate); + + /* copy parser text */ + + while ((c = getc(finput)) != EOF) { + if (c == '$') { + if ((c = getc(finput)) != 'A') + putc('$', ftable); + else { /* copy actions */ + faction = fopen(ACTNAME, "r"); + if (faction == NULL) + error("cannot reopen action tempfile"); + while ((c = getc(faction)) != EOF) + putc(c, ftable); + fclose(faction); + ZAPFILE(ACTNAME); + c = getc(finput); + } + } + putc(c, ftable); + } + + fclose(ftable); +} + +char *chcopy(char *p, char *q) +{ + /* copies string q into p, returning next free char ptr */ + while ((*p = *q++) != 0) + ++p; + return (p); +} + +#define ISIZE 400 +char *writem(int *pp) +{ /* creates output string for item pointed to by 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 == pp ? '_' : ' '; + *q = '\0'; + if ((i = *p) <= 0) + break; + q = chcopy(q, symnam(i)); + if (q > &sarr[ISIZE - 30]) + error("item too big"); + } + + if ((i = *pp) < 0) { /* an item calling for a reduction */ + q = chcopy(q, " ("); + sprintf(q, "%d)", -i); + } + + return (sarr); +} + +char *symnam(int i) +{ /* return a pointer to the name of symbol i */ + char *cp; + + cp = (i >= NTBASE) ? nontrst[i - NTBASE].name : tokset[i].name; + if (*cp == ' ') + ++cp; + return (cp); +} + +struct 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; + +void summary(void) +{ /* output the summary on the tty */ + + if (foutput != NULL) { + fprintf(foutput, "\n%d/%d terminals, %d/%d nonterminals\n", ntokens, NTERMS, nnonter, NNONTERM); + fprintf(foutput, "%d/%d grammar rules, %d/%d states\n", nprod, NPROD, nstate, NSTATES); + fprintf(foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n", zzsrconf, zzrrconf); + fprintf(foutput, "%d/%d working sets used\n", (int)(zzcwp - wsets), WSETSIZE); + fprintf(foutput, "memory: states,etc. %d/%d, parser %d/%d\n", (int)(zzmemsz - mem0), MEMSIZE, (int)(memp - amem), ACTSIZE); + fprintf(foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE); + fprintf(foutput, "%d extra closures\n", zzclose - 2 * nstate); + fprintf(foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp); + fprintf(foutput, "%d goto entries\n", zzgoent); + fprintf(foutput, "%d entries saved by goto default\n", zzgobest); + } + if (zzsrconf != 0 || zzrrconf != 0) { + fprintf(stdout, "\nconflicts: "); + if (zzsrconf) + fprintf(stdout, "%d shift/reduce", zzsrconf); + if (zzsrconf && zzrrconf) + fprintf(stdout, ", "); + if (zzrrconf) + fprintf(stdout, "%d reduce/reduce", zzrrconf); + fprintf(stdout, "\n"); + } + + fclose(ftemp); + if (fdefine != NULL) + fclose(fdefine); +} + +/* VARARGS1 */ + +void error(char *s, ...) +{ /* write out error comment */ + + ++nerrors; + fprintf(stderr, "\n fatal error: "); +/*FIXME VARARG*/ fprintf(stderr, s); + fprintf(stderr, ", line %d\n", lineno); + if (!fatfl) + return; + summary(); + exit(1); +} + +void aryfil(int *v, int n, int c) +{ /* set elements 0 through n-1 to c */ + int i; + for (i = 0; i < n; ++i) + v[i] = c; +} + +int setunion(int *a, int *b) +{ + /* set a to the union of a and b */ + /* return 1 if b is not a subset of a, 0 otherwise */ + int i, x, sub; + + sub = 0; + SETLOOP(i) { + *a = (x = *a) | *b++; + if (*a++ != x) + sub = 1; + } + return (sub); +} + +void prlook(struct looksets *p) +{ + int j, *pp; + pp = p->lset; + if (pp == 0) + fprintf(foutput, "\tNULL"); + else { + fprintf(foutput, " { "); + TLOOP(j) { + if (BIT(pp, j)) + fprintf(foutput, "%s ", symnam(j)); + } + fprintf(foutput, "}"); + } +} + +void cpres(void) +{ /* 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 */ + int **pmem; + int c, j, i; + 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(); + exit(1); + } + if (pmem != &pyield[nprod]) + error("internal Yacc error: pyield %d", pmem - &pyield[nprod]); +} + +int indebug = 0; + +void cpfir(void) +{ + /* compute an array with the first of nonterminals */ + int *p, **s, i, **t, ch, changes; + + zzcwp = &wsets[nnonter]; + NTLOOP(i) { + aryfil(wsets[i].ws.lset, tbitset, 0); + t = pres[i + 1]; + for (s = pres[i]; s < t; ++s) { /* initially fill the sets */ + for (p = *s; (ch = *p) > 0; ++p) { + if (ch < NTBASE) { + SETBIT(wsets[i].ws.lset, ch); + break; + } else 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 != NULL)) { + NTLOOP(i) { + fprintf(foutput, "\n%s: ", nontrst[i].name); + prlook(pfirst[i]); + fprintf(foutput, " %d\n", pempty[i]); + } + } +} + +int state(int c) +{ /* sorts last state,and sees if it equals earlier ones. returns state number */ + int size1, size2; + int i; + struct item *p1, *p2, *k, *l, *q1, *q2; + 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; + struct looksets *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++); +} + +int pidebug = 0; /* debugging flag for putitem */ + +void putitem(int *ptr, struct looksets *lptr) +{ + struct item *j; + + if (pidebug && (foutput != NULL)) { + fprintf(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"); + } +} + +void cempty(void) +{ /* mark nonterminals which derive the empty string */ + /* also, look for nonterminals which don't derive any token strings */ + +#define EMPTY 1 +#define WHOKNOWS 0 +#define OK 1 + + 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; + } + if (*p < 0) { /* production can be derived */ + 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(); + exit(1); + } + + /* 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) { + if (pempty[*prdptr[i] - NTBASE] == WHOKNOWS) { /* not known to be empty */ + for (p = prdptr[i] + 1; *p >= NTBASE && pempty[*p - NTBASE] == EMPTY; ++p); + if (*p < 0) { /* we have a nontrivially empty nonterminal */ + pempty[*prdptr[i] - NTBASE] = EMPTY; + goto again; /* got one ... try for another */ + } + } + } + +} + +int gsdebug = 0; + +void stagen(void) +{ +/* generate the states */ + + int i, j; + int c; + struct 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] = (struct 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 */ + + more: + 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); + WSLOOP(wsets, p) { /* generate goto's */ + 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) { + if (c == *(q->pitem)) { /* this item contributes to the goto */ + 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 != NULL)) { + fprintf(foutput, "%d: ", i); + NTLOOP(j) { + if (temp1[j]) + fprintf(foutput, "%s %d, ", nontrst[j].name, temp1[j]); + } + fprintf(foutput, "\n"); + } + indgo[i] = apack(&temp1[1], nnonter - 1) - 1; + goto more; /* we have done one goto; do some more */ + } + /* no more to do... stop */ +} + +int cldebug = 0; /* debugging flag for closure */ + +void closure(int i) +{ /* generate the closure of state i */ + + int c, ch, work, k; + struct wset *u, *v; + int *pi; + int **s, **t; + struct item *q; + struct item *p; + + ++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; + c = *(u->pitem); /* dot is before c */ + + if (c < NTBASE) { + u->flag = 0; + continue; /* only interesting case is where . is before nonterminal */ + } + + /* 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) { + if (ch < NTBASE) { /* terminal symbol */ + 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 -= NTBASE; /* c is now nonterminal number */ + + t = pres[c + 1]; + for (s = pres[c]; s < t; ++s) { + /* put these items into the closure */ + WSLOOP(wsets, v) { /* is the item there */ + if (v->pitem == *s) { /* yes, it is there */ + 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 != NULL)) { + fprintf(foutput, "\nState %d, nolook = %d\n", i, nolook); + WSLOOP(wsets, u) { + if (u->flag) + fprintf(foutput, "flag set!\n"); + u->flag = 0; + fprintf(foutput, "\t%s", writem(u->pitem)); + prlook(&u->ws); + fprintf(foutput, "\n"); + } + } +} + +struct looksets *flset(struct looksets *p) +{ + /* decide if the lookahead set pointed to by p is known */ + /* return pointer to a perminent location for the set */ + + struct looksets *q; + int j, *w; + int *u, *v; + + 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); +} diff --git a/Applications/v7yacc/y2.c b/Applications/v7yacc/y2.c new file mode 100644 index 00000000..365240b8 --- /dev/null +++ b/Applications/v7yacc/y2.c @@ -0,0 +1,971 @@ +/* UNIX V7 source code: see /COPYRIGHT or www.tuhs.org for details. */ + +#include +#include "dextern.h" +#include "prototype.h" + +#define IDENTIFIER 257 +#define MARK 258 +#define TERM 259 +#define LEFT 260 +#define RIGHT 261 +#define BINARY 262 +#define PREC 263 +#define LCURLY 264 +#define C_IDENTIFIER 265 /* name followed by colon */ +#define NUMBER 266 +#define START 267 +#define TYPEDEF 268 +#define TYPENAME 269 +#define UNION 270 +#define ENDFILE 0 + + /* communication variables between various I/O routines */ + +char *infile; /* input file name */ +int numbval; /* value of an input number */ +char tokname[NAMESIZE]; /* input token name */ + + /* 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 = 3; /* number of defined symbols output */ + + /* storage of types */ +int ntypes; /* number of types defined */ +char *typeset[NTYPES]; /* pointers to type tags */ + + /* symbol tables for tokens and nonterminals */ + +int ntokens = 0; +struct toksymb tokset[NTERMS]; +int toklev[NTERMS]; +int nnonter = -1; +struct ntsymb nontrst[NNONTERM]; +int start; /* start symbol */ + + /* assigned token type values */ +int extval = 0; + + /* input and output file descriptors */ + +FILE *finput; /* yacc input file */ +FILE *faction; /* file for saving actions */ +FILE *fdefine; /* file for # defines */ +FILE *ftable; /* y.tab.c file */ +FILE *ftemp; /* tempfile to pass 2 */ +FILE *foutput; /* y.output file */ + + /* storage for grammar rules */ + +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 */ + + +void setup(int argc, char *argv[]) +{ + int i, j, lev, t, ty; + int c; + int *p; + char actname[8]; + + foutput = NULL; + fdefine = NULL; + i = 1; + while (argc >= 2 && argv[1][0] == '-') { + while (*++(argv[1])) { + switch (*argv[1]) { + case 'v': + case 'V': + foutput = fopen(FILEU, "w"); + if (foutput == NULL) + error("cannot open y.output"); + continue; + case 'D': + case 'd': + fdefine = fopen(FILED, "w"); + continue; + case 'o': + case 'O': + fprintf(stderr, "`o' flag now default in yacc\n"); + continue; + + case 'r': + case 'R': + error("Ratfor Yacc is dead: sorry...\n"); + + default: + error("illegal option: %c", *argv[1]); + } + } + argv++; + argc--; + } + + ftable = fopen(OFILE, "w"); + if (ftable == NULL) + error("cannot open table file"); + + ftemp = fopen(TEMPNAME, "w"); + faction = fopen(ACTNAME, "w"); + if (ftemp == NULL || faction == NULL) + error("cannot open temp file"); + + if (argc < 2 || ((finput = fopen(infile = argv[1], "r")) == NULL)) { + error("cannot open input file"); + } + + cnamp = cnames; + defin(0, "$end"); + extval = 0400; + defin(0, "error"); + defin(1, "$accept"); + mem = mem0; + lev = 0; + ty = 0; + i = 0; + + /* sorry -- no yacc parser here..... + we must bootstrap somehow... */ + + for (t = gettok(); t != MARK && t != ENDFILE;) { + switch (t) { + + case ';': + t = gettok(); + break; + + case START: + if ((t = gettok()) != IDENTIFIER) { + error("bad %%start construction"); + } + start = chfind(1, tokname); + t = gettok(); + continue; + + case TYPEDEF: + if ((t = gettok()) != TYPENAME) + error("bad syntax in %%type"); + ty = numbval; + for (;;) { + t = gettok(); + switch (t) { + + case IDENTIFIER: + if ((t = chfind(1, tokname)) < NTBASE) { + j = TYPE(toklev[t]); + if (j != 0 && j != ty) { + error("type redeclaration of token %s", tokset[t].name); + } else + SETTYPE(toklev[t], ty); + } else { + j = nontrst[t - NTBASE].tvalue; + if (j != 0 && j != ty) { + error("type redeclaration of nonterminal %s", nontrst[t - NTBASE].name); + } else + nontrst[t - NTBASE].tvalue = ty; + } + case ',': + continue; + + case ';': + t = gettok(); + break; + default: + break; + } + break; + } + continue; + + case UNION: + /* copy the union declaration to the output */ + cpyunion(); + t = gettok(); + continue; + + case LEFT: + case BINARY: + case RIGHT: + ++i; + case TERM: + lev = t - TERM; /* nonzero means new prec. and assoc. */ + ty = 0; + + /* get identifiers so defined */ + + t = gettok(); + if (t == TYPENAME) { /* there is a type defined */ + ty = numbval; + t = gettok(); + } + + for (;;) { + switch (t) { + + case ',': + t = gettok(); + continue; + + case ';': + break; + + case IDENTIFIER: + j = chfind(0, tokname); + if (lev) { + if (ASSOC(toklev[j])) + error("redeclaration of precedence of %s", tokname); + SETASC(toklev[j], lev); + SETPLEV(toklev[j], i); + } + if (ty) { + if (TYPE(toklev[j])) + error("redeclaration of type of %s", tokname); + SETTYPE(toklev[j], ty); + } + if ((t = gettok()) == NUMBER) { + tokset[j].value = numbval; + if (j < ndefout && j > 2) { + error("please define type number of %s earlier", tokset[j].name); + } + t = gettok(); + } + continue; + + } + + break; + } + + continue; + + case LCURLY: + defout(); + cpycode(); + t = gettok(); + continue; + + default: + error("syntax error"); + + } + + } + + if (t == ENDFILE) { + error("unexpected EOF before %%"); + } + + /* t is MARK */ + + defout(); + + fprintf(ftable, "#define yyclearin yychar = -1\n"); + fprintf(ftable, "#define yyerrok yyerrflag = 0\n"); + fprintf(ftable, "extern int yychar;\nextern short yyerrflag;\n"); + fprintf(ftable, "#ifndef YYMAXDEPTH\n#define YYMAXDEPTH 150\n#endif\n"); + if (!ntypes) + fprintf(ftable, "#ifndef YYSTYPE\n#define YYSTYPE int\n#endif\n"); + fprintf(ftable, "YYSTYPE yylval, yyval;\n"); + + prdptr[0] = mem; + /* added production */ + *mem++ = NTBASE; + *mem++ = start; /* if start is 0, we will overwrite with the lhs of the first rule */ + *mem++ = 1; + *mem++ = 0; + prdptr[1] = mem; + + while ((t = gettok()) == LCURLY) + cpycode(); + + if (t != C_IDENTIFIER) + error("bad syntax on first rule"); + + if (!start) + prdptr[0][1] = chfind(1, tokname); + + /* read rules */ + + while (t != MARK && t != ENDFILE) { + + /* process a rule */ + + if (t == '|') { + *mem++ = *prdptr[nprod - 1]; + } else if (t == C_IDENTIFIER) { + *mem = chfind(1, tokname); + if (*mem < NTBASE) + error("token illegal on LHS of grammar rule"); + ++mem; + } else + error("illegal rule: missing semicolon or | ?"); + + /* read rule body */ + + + t = gettok(); + more_rule: + while (t == IDENTIFIER) { + *mem = chfind(1, tokname); + if (*mem < NTBASE) + levprd[nprod] = toklev[*mem]; + ++mem; + t = gettok(); + } + + + if (t == PREC) { + if (gettok() != IDENTIFIER) + error("illegal %%prec syntax"); + j = chfind(2, tokname); + if (j >= NTBASE) + error("nonterminal %s illegal after %%prec", nontrst[j - NTBASE].name); + levprd[nprod] = toklev[j]; + t = gettok(); + } + + if (t == '=') { + levprd[nprod] |= ACTFLAG; + fprintf(faction, "\ncase %d:", nprod); + cpyact(mem - prdptr[nprod] - 1); + fprintf(faction, " break;"); + if ((t = gettok()) == IDENTIFIER) { + /* action within rule... */ + + sprintf(actname, "$$%d", nprod); + j = chfind(1, actname); /* make it a nonterminal */ + + /* the current rule will become rule number nprod+1 */ + /* move the contents down, and make room for the null */ + + for (p = mem; p >= prdptr[nprod]; --p) + p[2] = *p; + mem += 2; + + /* enter null production for action */ + + p = prdptr[nprod]; + + *p++ = j; + *p++ = -nprod; + + /* update the production information */ + + levprd[nprod + 1] = levprd[nprod] & ~ACTFLAG; + levprd[nprod] = ACTFLAG; + + if (++nprod >= NPROD) + error("more than %d rules", NPROD); + prdptr[nprod] = p; + + /* make the action appear in the original rule */ + *mem++ = j; + + /* get some more of the rule */ + + goto more_rule; + } + + } + + while (t == ';') + t = gettok(); + + *mem++ = -nprod; + + /* check that default action is reasonable */ + + if (ntypes && !(levprd[nprod] & ACTFLAG) && nontrst[*prdptr[nprod] - NTBASE].tvalue) { + /* no explicit action, LHS has value */ + int tempty; + tempty = prdptr[nprod][1]; + if (tempty < 0) + error("must return a value, since LHS has a type"); + else if (tempty >= NTBASE) + tempty = nontrst[tempty - NTBASE].tvalue; + else + tempty = TYPE(toklev[tempty]); + if (tempty != nontrst[*prdptr[nprod] - NTBASE].tvalue) { + error("default action causes potential type clash"); + } + } + + if (++nprod >= NPROD) + error("more than %d rules", NPROD); + prdptr[nprod] = mem; + levprd[nprod] = 0; + + } + + /* end of all rules */ + + finact(); + if (t == MARK) { + fprintf(ftable, "\n# line %d \"%s\"\n", lineno, infile); + while ((c = getc(finput)) != EOF) + putc(c, ftable); + } + fclose(finput); +} + +void finact(void) +{ + /* finish action routine */ + + fclose(faction); + + fprintf(ftable, "# define YYERRCODE %d\n", tokset[2].value); + +} + +int defin(int t, char *s) +{ +/* define s to be a terminal if t=0 + or a nonterminal if t=1 */ + + int val; + + if (t) { + if (++nnonter >= NNONTERM) + error("too many nonterminals, limit %d", NNONTERM); + nontrst[nnonter].name = cstash(s); + return (NTBASE + nnonter); + } + /* must be a token */ + if (++ntokens >= NTERMS) + error("too many terminals, limit %d", NTERMS); + tokset[ntokens].name = cstash(s); + + /* establish value for token */ + + if (s[0] == ' ' && s[2] == '\0') /* single character literal */ + val = s[1]; + else if (s[0] == ' ' && s[1] == '\\') { /* escape sequence */ + if (s[3] == '\0') { /* single character escape sequence */ + switch (s[2]) { + /* character which is escaped */ + case 'n': + val = '\n'; + break; + case 'r': + val = '\r'; + break; + case 'b': + val = '\b'; + break; + case 't': + val = '\t'; + break; + case 'f': + val = '\f'; + break; + case '\'': + val = '\''; + break; + case '"': + val = '"'; + break; + case '\\': + val = '\\'; + break; + default: + error("invalid escape"); + } + } else if (s[2] <= '7' && s[2] >= '0') { /* \nnn sequence */ + if (s[3] < '0' || s[3] > '7' || s[4] < '0' || s[4] > '7' || s[5] != '\0') + error("illegal \\nnn construction"); + val = 64 * s[2] + 8 * s[3] + s[4] - 73 * '0'; + if (val == 0) + error("'\\000' is illegal"); + } + } else { + val = extval++; + } + tokset[ntokens].value = val; + toklev[ntokens] = 0; + return (ntokens); +} + +void defout(void) +{ /* write out the defines (at the end of the declaration section) */ + + int i, c; + char *cp; + + for (i = ndefout; i <= ntokens; ++i) { + + cp = tokset[i].name; + if (*cp == ' ') + ++cp; /* literals */ + + for (; (c = *cp) != '\0'; ++cp) { + + if (islower(c) || isupper(c) || isdigit(c) || c == '_'); /* VOID */ + else + goto nodef; + } + + fprintf(ftable, "# define %s %d\n", tokset[i].name, tokset[i].value); + if (fdefine != NULL) + fprintf(fdefine, "# define %s %d\n", tokset[i].name, tokset[i].value); + + nodef:; + } + + ndefout = ntokens + 1; + +} + +char *cstash(char *s) +{ + char *temp; + + temp = cnamp; + do { + if (cnamp >= &cnames[cnamsz]) + error("too many characters in id's and literals"); + else + *cnamp++ = *s; + } while (*s++); + return (temp); +} + +int gettok(void) +{ + int i, base; + static int peekline; /* number of '\n' seen in lookahead */ + int c, match, reserve; + + begin: + reserve = 0; + lineno += peekline; + peekline = 0; + c = getc(finput); + while (c == ' ' || c == '\n' || c == '\t' || c == '\f') { + if (c == '\n') + ++lineno; + c = getc(finput); + } + if (c == '/') { /* skip comment */ + lineno += skipcom(); + goto begin; + } + + switch (c) { + + case EOF: + return (ENDFILE); + case '{': + ungetc(c, finput); + return ('='); /* action ... */ + case '<': /* get, and look up, a type name (union member name) */ + i = 0; + while ((c = getc(finput)) != '>' && c >= 0 && c != '\n') { + tokname[i] = c; + if (++i >= NAMESIZE) + --i; + } + if (c != '>') + error("unterminated < ... > clause"); + tokname[i] = '\0'; + for (i = 1; i <= ntypes; ++i) { + if (!strcmp(typeset[i], tokname)) { + numbval = i; + return (TYPENAME); + } + } + typeset[numbval = ++ntypes] = cstash(tokname); + return (TYPENAME); + + case '"': + case '\'': + match = c; + tokname[0] = ' '; + i = 1; + for (;;) { + c = getc(finput); + if (c == '\n' || c == EOF) + error("illegal or missing ' or \""); + if (c == '\\') { + c = getc(finput); + tokname[i] = '\\'; + if (++i >= NAMESIZE) + --i; + } else if (c == match) + break; + tokname[i] = c; + if (++i >= NAMESIZE) + --i; + } + break; + + case '%': + case '\\': + + switch (c = getc(finput)) { + + case '0': + return (TERM); + case '<': + return (LEFT); + case '2': + return (BINARY); + case '>': + return (RIGHT); + case '%': + case '\\': + return (MARK); + case '=': + return (PREC); + case '{': + return (LCURLY); + default: + reserve = 1; + } + + default: + + if (isdigit(c)) { /* number */ + numbval = c - '0'; + base = (c == '0') ? 8 : 10; + for (c = getc(finput); isdigit(c); c = getc(finput)) { + numbval = numbval * base + c - '0'; + } + ungetc(c, finput); + return (NUMBER); + } else if (islower(c) || isupper(c) || c == '_' || c == '.' || c == '$') { + i = 0; + while (islower(c) || isupper(c) || isdigit(c) || c == '_' || c == '.' || c == '$') { + tokname[i] = c; + if (reserve && isupper(c)) + tokname[i] += 'a' - 'A'; + if (++i >= NAMESIZE) + --i; + c = getc(finput); + } + } else + return (c); + + ungetc(c, finput); + } + + tokname[i] = '\0'; + + if (reserve) { /* find a reserved word */ + if (!strcmp(tokname, "term")) + return (TERM); + if (!strcmp(tokname, "token")) + return (TERM); + if (!strcmp(tokname, "left")) + return (LEFT); + if (!strcmp(tokname, "nonassoc")) + return (BINARY); + if (!strcmp(tokname, "binary")) + return (BINARY); + if (!strcmp(tokname, "right")) + return (RIGHT); + if (!strcmp(tokname, "prec")) + return (PREC); + if (!strcmp(tokname, "start")) + return (START); + if (!strcmp(tokname, "type")) + return (TYPEDEF); + if (!strcmp(tokname, "union")) + return (UNION); + error("invalid escape, or illegal reserved word: %s", tokname); + } + + /* look ahead to distinguish IDENTIFIER from C_IDENTIFIER */ + + c = getc(finput); + while (c == ' ' || c == '\t' || c == '\n' || c == '\f' || c == '/') { + if (c == '\n') + ++peekline; + else if (c == '/') { /* look for comments */ + peekline += skipcom(); + } + c = getc(finput); + } + if (c == ':') + return (C_IDENTIFIER); + ungetc(c, finput); + return (IDENTIFIER); +} + +int fdtype(int t) +{ /* determine the type of a symbol */ + int v; + if (t >= NTBASE) + v = nontrst[t - NTBASE].tvalue; + else + v = TYPE(toklev[t]); + if (v <= 0) + error("must specify type for %s", (t >= NTBASE) ? nontrst[t - NTBASE].name : tokset[t].name); + return (v); +} + +int chfind(int t, char *s) +{ + int i; + + if (s[0] == ' ') + t = 0; + TLOOP(i) { + if (!strcmp(s, tokset[i].name)) { + return (i); + } + } + NTLOOP(i) { + if (!strcmp(s, nontrst[i].name)) { + return (i + NTBASE); + } + } + /* cannot find name */ + if (t > 1) + error("%s should have been defined earlier", s); + return (defin(t, s)); +} + +void cpyunion(void) +{ + /* copy the union declaration to the output, and the define file if present */ + + int level, c; + fprintf(ftable, "\n# line %d \"%s\"\n", lineno, infile); + fprintf(ftable, "typedef union "); + if (fdefine) + fprintf(fdefine, "\ntypedef union "); + + level = 0; + for (;;) { + if ((c = getc(finput)) < 0) + error("EOF encountered while processing %%union"); + putc(c, ftable); + if (fdefine) + putc(c, fdefine); + + switch (c) { + + case '\n': + ++lineno; + break; + + case '{': + ++level; + break; + + case '}': + --level; + if (level == 0) { /* we are finished copying */ + fprintf(ftable, " YYSTYPE;\n"); + if (fdefine) + fprintf(fdefine, " YYSTYPE;\nextern YYSTYPE yylval;\n"); + return; + } + } + } +} + +void cpycode(void) +{ /* copies code between \{ and \} */ + + int c; + c = getc(finput); + if (c == '\n') { + c = getc(finput); + lineno++; + } + fprintf(ftable, "\n# line %d \"%s\"\n", lineno, infile); + while (c >= 0) { + if (c == '\\') { + if ((c = getc(finput)) == '}') + return; + else + putc('\\', ftable); + } + if (c == '%') { + if ((c = getc(finput)) == '}') + return; + else + putc('%', ftable); + } + putc(c, ftable); + if (c == '\n') + ++lineno; + c = getc(finput); + } + error("eof before %%}"); +} + +int skipcom(void) +{ /* skip over comments */ + int c, i = 0; /* i is the number of lines skipped */ + + /* skipcom is called after reading a / */ + + if (getc(finput) != '*') + error("illegal comment"); + c = getc(finput); + while (c != EOF) { + while (c == '*') { + if ((c = getc(finput)) == '/') + return (i); + } + if (c == '\n') + ++i; + c = getc(finput); + } + error("EOF inside comment"); + /* NOTREACHED */ +} + +void cpyact(int offset) +{ /* copy C action to the next ; or closing } */ + int brac, c, match, j, s, tok; + + fprintf(faction, "\n# line %d \"%s\"\n", lineno, infile); + + brac = 0; + + loop: + c = getc(finput); + swt: + switch (c) { + + case ';': + if (brac == 0) { + putc(c, faction); + return; + } + goto lcopy; + + case '{': + brac++; + goto lcopy; + + case '$': + s = 1; + tok = -1; + c = getc(finput); + if (c == '<') { /* type description */ + ungetc(c, finput); + if (gettok() != TYPENAME) + error("bad syntax on $ clause"); + tok = numbval; + c = getc(finput); + } + if (c == '$') { + fprintf(faction, "yyval"); + if (ntypes) { /* put out the proper tag... */ + if (tok < 0) + tok = fdtype(*prdptr[nprod]); + fprintf(faction, ".%s", typeset[tok]); + } + goto loop; + } + if (c == '-') { + s = -s; + c = getc(finput); + } + if (isdigit(c)) { + j = 0; + while (isdigit(c)) { + j = j * 10 + c - '0'; + c = getc(finput); + } + + j = j * s - offset; + if (j > 0) { + error("Illegal use of $%d", j + offset); + } + + fprintf(faction, "yypvt[-%d]", -j); + if (ntypes) { /* put out the proper tag */ + if (j + offset <= 0 && tok < 0) + error("must specify type of $%d", j + offset); + if (tok < 0) + tok = fdtype(prdptr[nprod][j + offset]); + fprintf(faction, ".%s", typeset[tok]); + } + goto swt; + } + putc('$', faction); + if (s < 0) + putc('-', faction); + goto swt; + + case '}': + if (--brac) + goto lcopy; + putc(c, faction); + return; + + + case '/': /* look for comments */ + putc(c, faction); + c = getc(finput); + if (c != '*') + goto swt; + + /* it really is a comment */ + + putc(c, faction); + c = getc(finput); + while (c != EOF) { + while (c == '*') { + putc(c, faction); + if ((c = getc(finput)) == '/') + goto lcopy; + } + putc(c, faction); + if (c == '\n') + ++lineno; + c = getc(finput); + } + error("EOF inside comment"); + + case '\'': /* character constant */ + match = '\''; + goto string; + + case '"': /* character string */ + match = '"'; + + string: + + putc(c, faction); + /* FIXME 0 or EOF ??? */ + while ((c = getc(finput)) != 0) { + + if (c == '\\') { + putc(c, faction); + c = getc(finput); + if (c == '\n') + ++lineno; + } else if (c == match) + goto lcopy; + else if (c == '\n') + error("newline in string or char. const."); + putc(c, faction); + } + error("EOF in string or character constant"); + + case EOF: + error("action does not terminate"); + + case '\n': + ++lineno; + goto lcopy; + + } + + lcopy: + putc(c, faction); + goto loop; +} diff --git a/Applications/v7yacc/y3.c b/Applications/v7yacc/y3.c new file mode 100644 index 00000000..9764ad9d --- /dev/null +++ b/Applications/v7yacc/y3.c @@ -0,0 +1,449 @@ +/* UNIX V7 source code: see /COPYRIGHT or www.tuhs.org for details. */ + +#include "dextern.h" +#include "prototype.h" + + /* important local variables */ +int lastred; /* the number of the last reduction of a state */ +int defact[NSTATES]; /* the default actions of states */ + +void output(void) +{ /* print the output for the states */ + + int i, k, c; + register struct wset *u, *v; + + fprintf(ftable, "short yyexca[] ={\n"); + + SLOOP(i) { /* output the stuff for state i */ + nolook = !(tystate[i] == MUSTLOOKAHEAD); + closure(i); + /* output actions */ + nolook = 1; + aryfil(temp1, ntokens + nnonter + 1, 0); + WSLOOP(wsets, u) { + c = *(u->pitem); + if (c > 1 && c < NTBASE && temp1[c] == 0) { + WSLOOP(u, v) { + if (c == *(v->pitem)) + putitem(v->pitem + 1, NULL); + } + temp1[c] = state(c); + } else if (c > NTBASE && temp1[(c -= NTBASE) + ntokens] == 0) { + temp1[c + ntokens] = amem[indgo[i] + c]; + } + } + + if (i == 1) + temp1[1] = ACCEPTCODE; + + /* now, we have the shifts; look at the reductions */ + + lastred = 0; + WSLOOP(wsets, u) { + c = *(u->pitem); + if (c <= 0) { /* reduction */ + lastred = -c; + TLOOP(k) { + if (BIT(u->ws.lset, k)) { + if (temp1[k] == 0) + temp1[k] = c; + else if (temp1[k] < 0) { /* reduce/reduce conflict */ + if (foutput != NULL) + fprintf(foutput, "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s", i, -temp1[k], lastred, symnam(k)); + if (-temp1[k] > lastred) + temp1[k] = -lastred; + ++zzrrconf; + } else { /* potential shift/reduce conflict */ + precftn(lastred, k, i); + } + } + } + } + } + wract(i); + } + + fprintf(ftable, "\t};\n"); + + wdef("YYNPROD", nprod); + +} + +int pkdebug = 0; + +int apack(int *p, int n) +{ /* pack state i from temp1 into amem */ + int off; + int *pp, *qq, *rr; + int *q, *r; + + /* we don't need to worry about checking because we + we will only look entries known to be there... */ + + /* eliminate leading and trailing 0's */ + + q = p + n; + for (pp = p, off = 0; *pp == 0 && pp <= q; ++pp, --off) /* VOID */ + ; + if (pp > q) + return (0); /* no actions */ + p = pp; + + /* now, find a place for the elements from p to q, inclusive */ + + r = &amem[ACTSIZE - 1]; + for (rr = amem; rr <= r; ++rr, ++off) { /* try rr */ + for (qq = rr, pp = p; pp <= q; ++pp, ++qq) { + if (*pp != 0) { + if (*pp != *qq && *qq != 0) + goto nextk; + } + } + + /* we have found an acceptable k */ + + if (pkdebug && foutput != NULL) + fprintf(foutput, "off = %d, k = %d\n", off, (int)(rr - amem)); + + for (qq = rr, pp = p; pp <= q; ++pp, ++qq) { + if (*pp) { + if (qq > r) + error("action table overflow"); + if (qq > memp) + memp = qq; + *qq = *pp; + } + } + if (pkdebug && foutput != NULL) { + for (pp = amem; pp <= memp; pp += 10) { + fprintf(foutput, "\t"); + for (qq = pp; qq <= pp + 9; ++qq) + fprintf(foutput, "%d ", *qq); + fprintf(foutput, "\n"); + } + } + return (off); + + nextk:; + } + error("no space in action table"); + /* NOTREACHED */ +} + +void go2out(void) +{ /* output the gotos for the nontermninals */ + int i, j, k, best, count, cbest, times; + + fprintf(ftemp, "$\n"); /* mark begining of gotos */ + + for (i = 1; i <= nnonter; ++i) { + go2gen(i); + + /* find the best one to make default */ + + best = -1; + times = 0; + + for (j = 0; j <= nstate; ++j) { /* is j the most frequent */ + if (tystate[j] == 0) + continue; + if (tystate[j] == best) + continue; + + /* is tystate[j] the most frequent */ + + count = 0; + cbest = tystate[j]; + + for (k = j; k <= nstate; ++k) + if (tystate[k] == cbest) + ++count; + + if (count > times) { + best = cbest; + times = count; + } + } + + /* best is now the default entry */ + + zzgobest += (times - 1); + for (j = 0; j <= nstate; ++j) { + if (tystate[j] != 0 && tystate[j] != best) { + fprintf(ftemp, "%d,%d,", j, tystate[j]); + zzgoent += 1; + } + } + + /* now, the default */ + + zzgoent += 1; + fprintf(ftemp, "%d\n", best); + + } + + + +} + +int g2debug = 0; + +void go2gen(int c) +{ /* output the gotos for nonterminal c */ + + int i, work, cc; + struct item *p, *q; + + + /* first, find nonterminals with gotos on c */ + + aryfil(temp1, nnonter + 1, 0); + temp1[c] = 1; + + work = 1; + while (work) { + work = 0; + PLOOP(0, i) { + if ((cc = prdptr[i][1] - NTBASE) >= 0) { /* cc is a nonterminal */ + if (temp1[cc] != 0) { /* cc has a goto on c */ + cc = *prdptr[i] - NTBASE; /* thus, the left side of production i does too */ + if (temp1[cc] == 0) { + work = 1; + temp1[cc] = 1; + } + } + } + } + } + + /* now, we have temp1[c] = 1 if a goto on c in closure of cc */ + + if (g2debug && foutput != NULL) { + fprintf(foutput, "%s: gotos on ", nontrst[c].name); + NTLOOP(i) if (temp1[i]) + fprintf(foutput, "%s ", nontrst[i].name); + fprintf(foutput, "\n"); + } + + /* now, go through and put gotos into tystate */ + + aryfil(tystate, nstate, 0); + SLOOP(i) { + ITMLOOP(i, p, q) { + if ((cc = *p->pitem) >= NTBASE) { + if (temp1[cc -= NTBASE]) { /* goto on c is possible */ + tystate[i] = amem[indgo[i] + c]; + break; + } + } + } + } +} + +void precftn(int r, int t, int s) +{ /* decide a shift/reduce conflict by precedence. */ + /* r is a rule number, t a token number */ + /* the conflict is in state s */ + /* temp1[t] is changed to reflect the action */ + + int lp, lt, action; + + lp = levprd[r]; + lt = toklev[t]; + if (PLEVEL(lt) == 0 || PLEVEL(lp) == 0) { + /* conflict */ + if (foutput != NULL) + fprintf(foutput, "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s", s, temp1[t], r, symnam(t)); + ++zzsrconf; + return; + } + if (PLEVEL(lt) == PLEVEL(lp)) + action = ASSOC(lt); + else if (PLEVEL(lt) > PLEVEL(lp)) + action = RASC; /* shift */ + else + action = LASC; /* reduce */ + + switch (action) { + + case BASC: /* error action */ + temp1[t] = ERRCODE; + return; + + case LASC: /* reduce */ + temp1[t] = -r; + return; + + } +} + +void wract(int i) +{ /* output state i */ + /* temp1 has the actions, lastred the default */ + int p, p0, p1; + int ntimes, tred, count, j; + int flag; + + /* find the best choice for lastred */ + + lastred = 0; + ntimes = 0; + TLOOP(j) { + if (temp1[j] >= 0) + continue; + if (temp1[j] + lastred == 0) + continue; + /* count the number of appearances of temp1[j] */ + count = 0; + tred = -temp1[j]; + levprd[tred] |= REDFLAG; + TLOOP(p) { + if (temp1[p] + tred == 0) + ++count; + } + if (count > ntimes) { + lastred = tred; + ntimes = count; + } + } + + /* for error recovery, arrange that, if there is a shift on the */ + /* error recovery token, `error', that the default be the error action */ + if (temp1[1] > 0) + lastred = 0; + + /* clear out entries in temp1 which equal lastred */ + TLOOP(p) if (temp1[p] + lastred == 0) + temp1[p] = 0; + + wrstate(i); + defact[i] = lastred; + + flag = 0; + TLOOP(p0) { + if ((p1 = temp1[p0]) != 0) { + if (p1 < 0) { + p1 = -p1; + goto exc; + } else if (p1 == ACCEPTCODE) { + p1 = -1; + goto exc; + } else if (p1 == ERRCODE) { + p1 = 0; + goto exc; + exc: + if (flag++ == 0) + fprintf(ftable, "-1, %d,\n", i); + fprintf(ftable, "\t%d, %d,\n", tokset[p0].value, p1); + ++zzexcp; + } else { + fprintf(ftemp, "%d,%d,", tokset[p0].value, p1); + ++zzacent; + } + } + } + if (flag) { + defact[i] = -2; + fprintf(ftable, "\t-2, %d,\n", lastred); + } + fprintf(ftemp, "\n"); + return; +} + +void wrstate(int i) +{ /* writes state i */ + int j0, j1; + struct item *pp, *qq; + struct wset *u; + + if (foutput == NULL) + return; + fprintf(foutput, "\nstate %d\n", i); + ITMLOOP(i, pp, qq) fprintf(foutput, "\t%s\n", writem(pp->pitem)); + if (tystate[i] == MUSTLOOKAHEAD) { + /* print out empty productions in closure */ + WSLOOP(wsets + (pstate[i + 1] - pstate[i]), u) { + if (*(u->pitem) < 0) + fprintf(foutput, "\t%s\n", writem(u->pitem)); + } + } + + /* check for state equal to another */ + + TLOOP(j0) if ((j1 = temp1[j0]) != 0) { + fprintf(foutput, "\n\t%s ", symnam(j0)); + if (j1 > 0) { /* shift, error, or accept */ + if (j1 == ACCEPTCODE) + fprintf(foutput, "accept"); + else if (j1 == ERRCODE) + fprintf(foutput, "error"); + else + fprintf(foutput, "shift %d", j1); + } else + fprintf(foutput, "reduce %d", -j1); + } + + /* output the final production */ + + if (lastred) + fprintf(foutput, "\n\t. reduce %d\n\n", lastred); + else + fprintf(foutput, "\n\t. error\n\n"); + + /* now, output nonterminal actions */ + + j1 = ntokens; + for (j0 = 1; j0 <= nnonter; ++j0) { + if (temp1[++j1]) + fprintf(foutput, "\t%s goto %d\n", symnam(j0 + NTBASE), temp1[j1]); + } + +} + +void wdef(char *s, int n) +{ /* output a definition of s to the value n */ + fprintf(ftable, "# define %s %d\n", s, n); +} + +void warray(char *s, int *v, int n) +{ + + int i; + + fprintf(ftable, "short %s[]={\n", s); + for (i = 0; i < n;) { + if (i % 10 == 0) + fprintf(ftable, "\n"); + fprintf(ftable, "%4d", v[i]); + if (++i == n) + fprintf(ftable, " };\n"); + else + fprintf(ftable, ","); + } +} + +void hideprod(void) +{ + /* in order to free up the mem and amem arrays for the optimizer, */ + /* and still be able to output yyr1, etc., after the sizes of */ + /* the action array is known, we hide the nonterminals */ + /* derived by productions in levprd. + */ + + int i, j; + + j = 0; + levprd[0] = 0; + PLOOP(1, i) { + if (!(levprd[i] & REDFLAG)) { + ++j; + if (foutput != NULL) { + fprintf(foutput, "Rule not reduced: %s\n", writem(prdptr[i])); + } + } + levprd[i] = *prdptr[i] - NTBASE; + } + if (j) + fprintf(stdout, "%d rules never reduced\n", j); +} diff --git a/Applications/v7yacc/y4.c b/Applications/v7yacc/y4.c new file mode 100644 index 00000000..ceabd8d4 --- /dev/null +++ b/Applications/v7yacc/y4.c @@ -0,0 +1,380 @@ +/* UNIX V7 source code: see /COPYRIGHT or www.tuhs.org for details. */ + +#include +#include +#include "dextern.h" +#include "prototype.h" + +#define a amem +#define mem mem0 +#define pa indgo +#define yypact temp1 +#define greed tystate + +int *ggreed; +int *pgo; +int *yypgo; + +int maxspr = 0; /* maximum spread of any entry */ +int maxoff = 0; /* maximum offset into a array */ +int *pmem = mem; +int *maxa; +#define NOMORE -1000 + +int nxdb = 0; +int adb = 0; + +void optinit(void) +{ + ggreed = &lkst[0].lset[0]; + pgo = &wsets[0].ws.lset[0]; + yypgo = &nontrst[0].tvalue; +} + +void callopt(void) +{ + + int i, *p, j, k, *q; + + /* read the arrays from tempfile and set parameters */ + + if ((finput = fopen(TEMPNAME, "r")) == NULL) + error("optimizer cannot open tempfile"); + + pgo[0] = 0; + yypact[0] = 0; + nstate = 0; + nnonter = 0; + for (;;) { + switch (gtnm()) { + + case '\n': + yypact[++nstate] = (--pmem) - mem; + case ',': + continue; + + case '$': + break; + + default: + error("bad tempfile"); + } + break; + } + + yypact[nstate] = yypgo[0] = (--pmem) - mem; + + for (;;) { + switch (gtnm()) { + + case '\n': + yypgo[++nnonter] = pmem - mem; + case ',': + continue; + + case EOF: + break; + + default: + error("bad tempfile"); + } + break; + } + + yypgo[nnonter--] = (--pmem) - mem; + + + + for (i = 0; i < nstate; ++i) { + + k = 32000; + j = 0; + q = mem + yypact[i + 1]; + for (p = mem + yypact[i]; p < q; p += 2) { + if (*p > j) + j = *p; + if (*p < k) + k = *p; + } + if (k <= j) { /* nontrivial situation */ + /* temporarily, kill this for compatibility */ + j -= k; /* j is now the range */ + if (k > maxoff) + maxoff = k; + } + greed[i] = (yypact[i + 1] - yypact[i]) + 2 * j; + if (j > maxspr) + maxspr = j; + } + + /* initialize ggreed table */ + + for (i = 1; i <= nnonter; ++i) { + ggreed[i] = 1; + j = 0; + /* minimum entry index is always 0 */ + q = mem + yypgo[i + 1] - 1; + for (p = mem + yypgo[i]; p < q; p += 2) { + ggreed[i] += 2; + if (*p > j) + j = *p; + } + ggreed[i] = ggreed[i] + 2 * j; + if (j > maxoff) + maxoff = j; + } + + + /* now, prepare to put the shift actions into the a array */ + + for (i = 0; i < ACTSIZE; ++i) + a[i] = 0; + maxa = a; + + for (i = 0; i < nstate; ++i) { + if (greed[i] == 0 && adb > 1) + fprintf(ftable, "State %d: null\n", i); + pa[i] = YYFLAG1; + } + + while ((i = nxti()) != NOMORE) { + if (i >= 0) + stin(i); + else + gin(-i); + + } + + if (adb > 2) { /* print a array */ + for (p = a; p <= maxa; p += 10) { + fprintf(ftable, "%4d ", (int)(p - a)); + for (i = 0; i < 10; ++i) + fprintf(ftable, "%4d ", p[i]); + fprintf(ftable, "\n"); + } + } + /* write out the output appropriate to the language */ + + aoutput(); + + osummary(); + ZAPFILE(TEMPNAME); +} + +void gin(int i) +{ + + int *p, *r, *s, *q1, *q2; + + /* enter gotos on nonterminal i into array a */ + + ggreed[i] = 0; + + q2 = mem + yypgo[i + 1] - 1; + q1 = mem + yypgo[i]; + + /* now, find a place for it */ + + for (p = a; p < &a[ACTSIZE]; ++p) { + if (*p) + continue; + for (r = q1; r < q2; r += 2) { + s = p + *r + 1; + if (*s) + goto nextgp; + if (s > maxa) { + if ((maxa = s) > &a[ACTSIZE]) + error("a array overflow"); + } + } + /* we have found a spot */ + + *p = *q2; + if (p > maxa) { + if ((maxa = p) > &a[ACTSIZE]) + error("a array overflow"); + } + for (r = q1; r < q2; r += 2) { + s = p + *r + 1; + *s = r[1]; + } + + pgo[i] = p - a; + if (adb > 1) + fprintf(ftable, "Nonterminal %d, entry at %d\n", i, pgo[i]); + goto nextgi; + + nextgp:; + } + + error("cannot place goto %d\n", i); + + nextgi:; +} + +void stin(int i) +{ + int *r, *s, n, flag, j, *q1, *q2; + + greed[i] = 0; + + /* enter state i into the a array */ + + q2 = mem + yypact[i + 1]; + q1 = mem + yypact[i]; + /* find an acceptable place */ + + for (n = -maxoff; n < ACTSIZE; ++n) { + + flag = 0; + for (r = q1; r < q2; r += 2) { + if ((s = *r + n + a) < a) + goto nextn; + if (*s == 0) + ++flag; + else if (*s != r[1]) + goto nextn; + } + + /* check that the position equals another only if the states are identical */ + + for (j = 0; j < nstate; ++j) { + if (pa[j] == n) { + if (flag) + goto nextn; /* we have some disagreement */ + if (yypact[j + 1] + yypact[i] == yypact[j] + yypact[i + 1]) { + /* states are equal */ + pa[i] = n; + if (adb > 1) + fprintf(ftable, "State %d: entry at %d equals state %d\n", i, n, j); + return; + } + goto nextn; /* we have some disagreement */ + } + } + + for (r = q1; r < q2; r += 2) { + if ((s = *r + n + a) >= &a[ACTSIZE]) + error("out of space in optimizer a array"); + if (s > maxa) + maxa = s; + if (*s != 0 && *s != r[1]) + error("clobber of a array, pos'n %d, by %d", s - a, r[1]); + *s = r[1]; + } + pa[i] = n; + if (adb > 1) + fprintf(ftable, "State %d: entry at %d\n", i, pa[i]); + return; + + nextn:; + } + + error("Error; failure to place state %d\n", i); + +} + +int nxti(void) +{ /* finds the next i */ + int i, max, maxi; + + max = 0; + + for (i = 1; i <= nnonter; ++i) + if (ggreed[i] >= max) { + max = ggreed[i]; + maxi = -i; + } + + for (i = 0; i < nstate; ++i) + if (greed[i] >= max) { + max = greed[i]; + maxi = i; + } + + if (nxdb) + fprintf(ftable, "nxti = %d, max = %d\n", maxi, max); + if (max == 0) + return (NOMORE); + else + return (maxi); +} + +void osummary(void) +{ + /* write summary */ + + int i, *p; + + if (foutput == NULL) + return; + i = 0; + for (p = maxa; p >= a; --p) { + if (*p == 0) + ++i; + } + + fprintf(foutput, "Optimizer space used: input %d/%d, output %d/%d\n", (int)(pmem - mem + 1), MEMSIZE, (int)(maxa - a + 1), ACTSIZE); + fprintf(foutput, "%d table entries, %d zero\n", (int)(maxa - a) + 1, i); + fprintf(foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff); + +} + +void aoutput(void) +{ /* this version is for C */ + + + /* write out the optimized parser */ + + fprintf(ftable, "# define YYLAST %d\n", (int)(maxa - a + 1)); + + arout("yyact", a, (maxa - a) + 1); + arout("yypact", pa, nstate); + arout("yypgo", pgo, nnonter + 1); + +} + +void arout(char *s, int *v, int n) +{ + int i; + + fprintf(ftable, "short %s[]={\n", s); + for (i = 0; i < n;) { + if (i % 10 == 0) + fprintf(ftable, "\n"); + fprintf(ftable, "%4d", v[i]); + if (++i == n) + fprintf(ftable, " };\n"); + else + fprintf(ftable, ","); + } +} + + +int gtnm(void) +{ + + int s, val, c; + + /* read and convert an integer from the standard input */ + /* return the terminating character */ + /* blanks, tabs, and newlines are ignored */ + + s = 1; + val = 0; + + while ((c = getc(finput)) != EOF) { + if (isdigit(c)) { + val = val * 10 + c - '0'; + } else if (c == '-') + s = -1; + else + break; + } + + *pmem++ = s * val; + if (pmem > &mem[MEMSIZE]) + error("out of space"); + return (c); + +} -- 2.34.1