* Copyright (c) 1979 Regents of the University of California.
* All rights reserved. The Berkeley software License Agreement
* specifies the terms and conditions for redistribution.
static char sccsid
[] = "@(#)ey3.c 5.1 (Berkeley) %G%";
cpres(){ /* conpute an array with the beginnings of productions yielding given nonterminals
The array pres points to these lists */
pres
= (int ***)yalloc(nnonter
+1);
fatfl
= 0; /* make undefined symbols nonfatal */
if (*prdptr
[j
] == c
) *mem
++ = (int)(prdptr
[j
]+1);
if(pres
[i
] == (int **)mem
){
error("nonterminal %s not defined!", nontrst
[i
].name
);
/* compute an array with the first of nonterminals */
int i
, ch
, **s
, **t
, changes
, *p
;
pfirst
= (struct looksets
**)yalloc(nnonter
+1);
for (i
=0;i
<=nnonter
;i
++) {
aryfil( wsets
[i
].ws
, tbitset
, 0 );
for( s
=pres
[i
]; s
<t
; ++s
){ /* initially fill the sets */
for( p
= *s
; (ch
= *p
) > 0 ; ++p
) {
wsets
[i
].ws
[ch
>>4] |= (1 << (ch
&017) );
else if( !pempty
[ch
-NTBASE
] ) break;
/* now, reflect transitivity */
for( i
=0; i
<=nnonter
; ++i
){
for( s
=pres
[i
]; s
<t
; ++s
){
for( p
= *s
; ( ch
= (*p
-NTBASE
) ) >= 0; ++p
) {
changes
|= UNION( wsets
[i
].ws
, wsets
[i
].ws
, wsets
[ch
].ws
);
for( i
=0; i
<=nnonter
; i
++ ) pfirst
[i
] = flset( wsets
[i
].ws
);
for( i
=0; i
<=nnonter
; i
++ ){
fprintf( cout
, "\n%s: ", nontrst
[i
].name
);
fprintf( cout
, " %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 */
if( UNION( clset
.lset
, l
->look
->lset
, k
->look
->lset
) ) {
/* register the new set */
l
->look
= flset( &clset
);
if(nstate
+1 >= stsize
) 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
;{
fprintf( cout
, "putitem(%s), state %d\n", writem(&ptr
), nstate
);
for( i
=pstate
[nstate
]; i
<j
; ++i
)
error("yacc error--duplicate item");
if(jip
-mem0
>= memsiz
) error("out of state space");
cempty(){ /* mark nonterminals which derive the empty string */
pempty
= (char *)yalloc( nnonter
/ sizeof(int) + 1 );
aryfil( pempty
, nnonter
+1, 0 );
for( i
=1; i
<nprod
; ++i
) /* loop over productions */
if( prdptr
[i
][1] <= 0 ) /* i is empty production */
pempty
[ *prdptr
[i
]-NTBASE
] = 1;
/* now, all explicitly empty nonterminals marked with pempty = 1 */
/* loop as long as we keep finding nontrivial empty nonterminals */
for( i
=1; i
<nprod
; ++i
){
if( pempty
[ *prdptr
[i
]-NTBASE
]==0 ){ /* not known to be empty */
for( p
=prdptr
[i
]+1; *p
>=NTBASE
&& pempty
[*p
-NTBASE
]!=0 ; ++p
) ;
if( *p
< 0 ){ /* we have a nontrivially empty nonterminal */
pempty
[*prdptr
[i
]-NTBASE
] = 1;
goto again
; /* got one ... try for another */
stagen(){ /* generate the states */
pstate
[0] = pstate
[1] = (struct item
*)mem
;
aryfil( clset
.lset
, tbitset
, 0 );
putitem( prdptr
[0]+1, &clset
);
aryfil( amem
, actsiz
, 0 );
/* now, the main state generation loop */
for( i
=0; i
<nstate
; ++i
){
/* if tystate == 2, set to zero */
if( tystate
[i
] != 1 ) continue;
aryfil( temp1
, nterms
+nnonter
+1, 0 );
/* take state i, close it, and do gotos */
for( j
=0; j
<cwset
; ++j
){ /* generate gotos */
if( wsets
[j
].flag
) continue;
/* if no symbols after the dot (ie empty rule) */
/* if not in kernel then tystate = 2 unless not done with it */
if( pstate
[i
+1]-pstate
[i
] <= j
) tystate
[i
] = (tystate
[i
]==1)?1:2;
for( k
=j
; k
<cwset
; ++k
){
if( c
== *(wsets
[k
].pitem
) ){ /* this item contributes to the goto */
putitem( wsets
[k
].pitem
+ 1, wsets
[k
].ws
);
if( c
< NTBASE
) temp1
[c
] = state(c
);
else temp1
[c
-NTBASE
+nterms
] = state(c
);
fprintf( cout
, "%d: ", i
);
for( j
=1; j
<=nterms
; ++j
){
if( temp1
[j
] != 0 ) fprintf( cout
, "%s %d, ", symnam(j
), temp1
[j
]);
for( j
=1; j
<=nnonter
; ++j
){
if( temp1
[j
+nterms
] ) fprintf( cout
, "%s %d, ", nontrst
[j
].name
, temp1
[j
+nterms
] );
apstate
[i
] = apack( &temp1
[0], nterms
);
indgo
[i
] = apack( &temp1
[nterms
+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 item
*p
;
/* first, copy kernel of state i to wsets */
/* for every item in the kernel */
for( p
=pstate
[i
]; p
<q
; ++p
){
wsets
[cwset
].pitem
= p
->pitem
;
wsets
[cwset
].flag
= 1; /* this item must get closed */
for( k
=0; k
<tbitset
; ++k
) wsets
[cwset
].ws
[k
] = p
->look
->lset
[k
];
/* now, go through the loop, closing each item */
for( j
=0; j
<cwset
; ++j
){
/* for every item in state, if terminal after dot, flag = 0 */
if( wsets
[j
].flag
== 0 ) continue;
/* dot is before c, since pitem of X -> A.B is B */
continue; /* only interesting case is where . is before nonterminal */
/* compute the lookahead */
aryfil( clset
.lset
, tbitset
, 0 );
/* find items involving c */
/* for all the rest of the items in the state */
for( k
=j
; k
<cwset
; ++k
){
if( wsets
[k
].flag
== 1 && *(pi
=wsets
[k
].pitem
) == c
){
if( ch
< NTBASE
){ /* terminal symbol */
clset
.lset
[ch
>>4] |= (1<<(ch
&017));
/* clset <- clset U first(ch) */
UNION( clset
.lset
, clset
.lset
, pfirst
[ch
-NTBASE
] );
/* if ch cannot derive lambda we are done */
if( !pempty
[ch
-NTBASE
] ) break;
/* if end of rule the clset <- clset U (lookahead for LHS) */
if( ch
<=0 ) UNION( clset
.lset
, clset
.lset
, wsets
[k
].ws
);
/* now loop over productions derived from c */
c
-= NTBASE
; /* c is now nonterminal number */
/* for each rule that c derives */
for( s
=pres
[c
]; s
<t
; ++s
){
/* put these items into the closure */
for( k
=0; k
<cwset
; ++k
){ /* is the item there */
if( wsets
[k
].pitem
== *s
){ /* yes, it is there */
/* if something new in ws, set flag = 1 */
if( UNION( wsets
[k
].ws
, wsets
[k
].ws
, clset
.lset
) )
wsets
[k
].flag
= work
= 1;
/* not there; make a new entry */
if( cwset
+1 >= wssize
) error( "working set overflow" );
for( k
=0; k
<tbitset
; ++k
) wsets
[cwset
].ws
[k
] = clset
.lset
[k
];
/* have computed closure; flags are reset; return */
if( cwset
> zzcwset
) zzcwset
= cwset
;
fprintf( cout
, "\nState %d, nolook = %d\n", i
, nolook
);
for( j
=0; j
<cwset
; ++j
){
if( wsets
[j
].flag
) fprintf( cout
, "flag set!\n");
fprintf( cout
, "\t%s", writem(&wsets
[j
].pitem
));
struct looksets
*flset( p
)
/* decide if the lookahead set pointed to by p is known */
/* return pointer to a perminent location for the set */
for( i
=0; i
<nlset
; ++i
){
while( v
<w
) if( *u
++ != *v
++ ) goto more
;
if( nlset
+1 >= lsetsz
)error("too many lookahead sets");
for( j
=0; j
<tbitset
; ++j
){
lkst
[nlset
].lset
[j
] = p
->lset
[j
];
return( & lkst
[nlset
++]);