static char sccsid
[] = "@(#)y1.c 4.1 (Berkeley) %G%";
/* 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
];
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 */
main(argc
,argv
) 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 */
others(){ /* put out other arrays, copy the parsers */
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 );
for( j
=tstates
[i
]; j
!=0; j
=mstates
[j
] ){
temp1
[j
] = tokset
[i
].value
;
for( j
=ntstates
[i
]; j
!=0; j
=mstates
[j
] ){
warray( "yychk", temp1
, nstate
);
warray( "yydef", defact
, nstate
);
while( (c
=getc(finput
) ) != EOF
){
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
);
char *chcopy( p
, q
) char *p
, *q
; {
/* copies string q into p, returning next free char ptr */
char *writem(pp
) int *pp
; { /* creates output string for item pointed to by pp */
for( p
=pp
; *p
>0 ; ++p
) ;
q
= chcopy( sarr
, nontrst
[*p
-NTBASE
].name
);
*q
++ = ++p
==pp
? '_' : ' ';
q
= chcopy( q
, symnam(i
) );
if( q
> &sarr
[ISIZE
-30] ) error( "item too big" );
if( (i
= *pp
) < 0 ){ /* an item calling for a reduction */
char *symnam(i
){ /* return a pointer to the name of symbol i */
cp
= (i
>=NTBASE
) ? nontrst
[i
-NTBASE
].name
: tokset
[i
].name
;
struct wset
*zzcwp
= wsets
;
summary(){ /* output the summary on the tty */
fprintf( foutput
, "\n%d/%d terminals, %d/%d nonterminals\n", ntokens
, NTERMS
,
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", zzcwp
-wsets
, WSETSIZE
);
fprintf( foutput
, "memory: states,etc. %d/%d, parser %d/%d\n", zzmemsz
-mem0
, MEMSIZE
,
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
);
if( fdefine
!= NULL
) fclose( fdefine
);
error(s
,a1
) char *s
; { /* write out error comment */
fprintf( stderr
, "\n fatal error: ");
fprintf( stderr
, ", line %d\n", lineno
);
aryfil( v
, n
, c
) int *v
,n
,c
; { /* set elements 0 through n-1 to c */
for( i
=0; i
<n
; ++i
) v
[i
] = c
;
setunion( a
, b
) register *a
, *b
; {
/* set a to the union of a and b */
/* return 1 if b is not a subset of a, 0 otherwise */
prlook( p
) struct looksets
*p
;{
if( pp
== 0 ) fprintf( foutput
, "\tNULL");
fprintf( foutput
, " { " );
if( BIT(pp
,j
) ) fprintf( foutput
, "%s ", symnam(j
) );
cpres(){ /* 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 */
static int * pyield
[NPROD
];
fatfl
= 0; /* make undefined symbols nonfatal */
if (*prdptr
[j
] == c
) *pmem
++ = prdptr
[j
]+1;
error("nonterminal %s not defined!", nontrst
[i
].name
);
if( pmem
!= &pyield
[nprod
] ) error( "internal Yacc error: pyield %d", pmem
-&pyield
[nprod
] );
/* compute an array with the first of nonterminals */
register *p
, **s
, i
, **t
, ch
, changes
;
aryfil( wsets
[i
].ws
.lset
, tbitset
, 0 );
for( s
=pres
[i
]; s
<t
; ++s
){ /* initially fill the sets */
for( p
= *s
; (ch
= *p
) > 0 ; ++p
) {
SETBIT( wsets
[i
].ws
.lset
, ch
);
else if( !pempty
[ch
-NTBASE
] ) break;
/* now, reflect transitivity */
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
);
NTLOOP(i
) pfirst
[i
] = flset( &wsets
[i
].ws
);
fprintf( foutput
, "\n%s: ", nontrst
[i
].name
);
fprintf( foutput
, " %d\n", pempty
[i
] );
state(c
){ /* sorts last state,and sees if it equals earlier ones. returns state number */
struct item
*p1
, *p2
, *k
, *l
, *q1
, *q2
;
if(p1
==p2
) return(0); /* null state */
for(k
=p2
-1;k
>p1
;k
--) { /* make k the biggest */
for(l
=k
-1;l
>=p1
;--l
)if( l
->pitem
> k
->pitem
){
size1
= p2
- p1
; /* size of state */
for( i
= (c
>=NTBASE
)?ntstates
[c
-NTBASE
]:tstates
[c
]; i
!= 0; i
= mstates
[i
] ) {
if (size1
!= size2
) continue;
if( l
->pitem
!= k
->pitem
) break;
pstate
[nstate
+1] = pstate
[nstate
]; /* delete last state */
for( l
=q1
,k
=p1
; l
<q2
; ++l
,++k
){
SETLOOP(s
) clset
.lset
[s
] = l
->look
->lset
[s
];
if( setunion( clset
.lset
, k
->look
->lset
) ) {
/* register the new set */
l
->look
= flset( &clset
);
if( nolook
) error( "yacc state/nolook error" );
if(nstate
+1 >= NSTATES
) error("too many states" );
mstates
[ nstate
] = ntstates
[ c
-NTBASE
];
ntstates
[ c
-NTBASE
] = nstate
;
mstates
[ nstate
] = tstates
[ c
];
int pidebug
= 0; /* debugging flag for putitem */
putitem( ptr
, lptr
) int *ptr
; struct looksets
*lptr
; {
if( pidebug
&& (foutput
!=NULL
) ) {
fprintf( foutput
, "putitem(%s), state %d\n", writem(ptr
), nstate
);
if( !nolook
) j
->look
= flset( lptr
);
if( (int *)j
> zzmemsz
){
if( zzmemsz
>= &mem0
[MEMSIZE
] ) error( "out of state space" );
cempty(){ /* mark nonterminals which derive the empty string */
/* also, look for nonterminals which don't derive any token strings */
/* 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 */
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
;
/* now, look at the nonterminals, to see if they are all OK */
/* the added production rises or falls as the start symbol ... */
if( pempty
[ i
] != OK
) {
error( "nonterminal %s never derives any token string", nontrst
[i
].name
);
/* 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 */
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 */
stagen(){ /* generate the states */
register struct wset
*p
, *q
;
/* 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
/* 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
);
aryfil( amem
, ACTSIZE
, 0 );
/* now, the main state generation loop */
if( tystate
[i
] != MUSTDO
) continue;
aryfil( temp1
, nnonter
+1, 0 );
/* take state i, close it, and do gotos */
WSLOOP(wsets
,p
){ /* generate goto's */
if( pstate
[i
+1]-pstate
[i
] <= p
-wsets
) tystate
[i
] = MUSTLOOKAHEAD
;
if( c
== *(q
->pitem
) ){ /* this item contributes to the goto */
putitem( q
->pitem
+ 1, &q
->ws
);
state(c
); /* register new state */
temp1
[c
-NTBASE
] = state(c
);
if( gsdebug
&& (foutput
!=NULL
) ){
fprintf( foutput
, "%d: ", i
);
if( temp1
[j
] ) fprintf( foutput
, "%s %d, ", nontrst
[j
].name
, temp1
[j
] );
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 */
closure(i
){ /* generate the closure of state i */
register struct wset
*u
, *v
;
/* first, copy kernel of state i to wsets */
cwp
->flag
= 1; /* this item must get closed */
SETLOOP(k
) cwp
->ws
.lset
[k
] = p
->look
->lset
[k
];
/* now, go through the loop, closing each item */
if( u
->flag
== 0 ) continue;
c
= *(u
->pitem
); /* dot is before c */
continue; /* only interesting case is where . is before nonterminal */
/* compute the lookahead */
aryfil( clset
.lset
, tbitset
, 0 );
/* find items involving c */
if( v
->flag
== 1 && *(pi
=v
->pitem
) == c
){
if( ch
< NTBASE
){ /* terminal symbol */
SETBIT( clset
.lset
, ch
);
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 */
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( setunion( v
->ws
.lset
, clset
.lset
) ) v
->flag
= work
= 1;
/* not there; make a new entry */
if( cwp
-wsets
+1 >= WSETSIZE
) error( "working set overflow" );
SETLOOP(k
) cwp
->ws
.lset
[k
] = clset
.lset
[k
];
/* 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
);
if( u
->flag
) fprintf( foutput
, "flag set!\n");
fprintf( foutput
, "\t%s", writem(u
->pitem
));
fprintf( foutput
, "\n" );
struct looksets
*flset( p
) struct looksets
*p
; {
/* decide if the lookahead set pointed to by p is known */
/* return pointer to a perminent location for the set */
register struct looksets
*q
;
for( q
= &lkst
[nlset
]; q
-- > lkst
; ){
while( v
<w
) if( *u
++ != *v
++ ) goto more
;
if( nlset
>= LSETSIZE
)error("too many lookahead sets" );