LR states algorithm


#define NSTATES 20
#define NSETS NSTATES*5

#define RULENO(x)	entry[x].ruleno
#define INDEX(x)	entry[x].index
#define ACTION(x)	entry[x].action
#define VALUE(x)	entry[x].value

#define SHIFT	1
#define	REDUCE	2
#define	IGNORE	4

struct entry {
	char	ruleno,index,action,value;
	} entry[NSETS];

int stateindex[NSTATES+1],curstate,curindex,newstate;

dolr subroutine
# initialize set 0 with rule #0, index #1 (set 0 has length of 1)
	INDEX(0)=1;
	stateindex[1]=1;
# generate set 0 and find first set of the start symbol
	expand();
# close and save set 0
	newstate++;
	stateindex[newstate+1]=stateindex[newstate];
# loop through each entry in all of the sets and make sure that we don't
# fall off the end of our table
	while(curindex < stateindex[newstate+1] && stateindex[newstate+1] < (NSETS)){
# keep track of which state/set we are currently in
		if(curindex == stateindex[curstate+1]) curstate++;
# skip entries that we have ready processed
		if(ACTION(curindex) == IGNORE);
# are we beyond the end of the rule?  (REDUCE)
		else if(INDEX(curindex)>=RHSLEN(RULENO(curindex))){
# make sure that we don't already have a REDUCE in the current set
			for(i=stateindex(curstate) ; i<curindex ; i++)
				if(ACTION(i)==REDUCE)
					print REDUCE/REDUCE ERROR RULE(i) and RULE(curindex);
			ACTION(i)=REDUCE;
			}
# not beyond the end of the rule, SHIFT
		else {
# copy each rule from the current set that has the same current symbol
# as current entry to a new state/set
			copy();
# expand the new state/set to include all the rules defining each
# non-terminal current symbol
			expand();
# set the action of the current entry to SHIFT
			ACTION(curindex)=SHIFT;
# check to see if the new state/set is a duplicate of one that we
# already have.  if it is, delete the new one and return number of the
# old one
			VALUE(curindex)=compare();
			}
# proceed on to the next entry
		curindex++;
		}
# print the states/set entries
	prstate();
# build the state table from the sets
	bldtab();

# include the rules that define each non-terminal current symbol in the
# new state/set
expand subroutine
# for each entry in the new state (Note that the new state is expanding)
	for(i=stateindex[newstate] ; i<stateindex[newstate+1] ; i++){
# skip to the next entry if we beyond the end of the rule
		if( RHSLEN(RULENO(i)) <= INDEX(i)) continue;
# skip to the next entry if the current symbol is a terminal symbol
		if(RHS(RULENO(i),INDEX(i)) >= nnt) continue;
# the current symbol of the current entry is a non-terminal.  Bring in
# all of the rules that define this non-terminal from the original
# grammer, but only once
		for j = each rule{
# skip rule j if the LHS of j is not equal to the current symbol for
# entry i
			if( RHS(RULENO(i),INDEX(i)) != LHS(j)) continue;
# we have found a rule that defines the current non-terminal
# is it already in the current set?
			for(k=stateindex[newstate] ; k<stateindex[newstate+1] ; k++)
				if(RULENO(k)==j && INDEX(k)==1) break;
# skip to the next rule if rule j is already in the current set with an
# index of 1
			if(k!=stateindex[newstate+1]) continue;
# add rule j to the end of the new set with its current symbol being the
# first RHS symbol (Note that the new set is lengthened by one also)
			RULENO(stateindex[newstate+1])=j;
			INDEX(stateindex[newstate+1]++)=1;
			}
		}

# copies all entries from the current set to the new set that have the
# same current symbol as the current entry.  It also increments the
# index past the current symbol
copy subroutine
# get the current symbol from the current entry (j)
	j=RHS(RULENO(curindex),INDEX(curindex));
# for each remaining entry in the current set
	for(i=curindex ; i<stateindex[curstate+1] ; i++){
# if entry i has the same current symbol as j and we are not beyond the
# end of the rule
		if(RHS(RULENO(i),INDEX(i)) == j && INDEX(i) <RHSLEN(RULENO(i))){
# copy entry i to the new set and increment the index
			k=stateindex[newstate+1]++;
			RULENO(k)=RULENO(i);
			INDEX(k)=INDEX(i)+1;
#set the action for the current entry being copied to IGNORE
			ACTION(i)=IGNORE;
			}
		}

# compare the new set with each previous set to see if we have a
# duplicate set
compare function
# get the starting index and length of the new state (begin,length)
	begin=stateindex[newstate];
	length=stateindex[newstate+1]-begin;
# check for a single entry in the new set and that it is beyond the end
# of the rule (Shift/Reduce Case)
	if(length==1 && INDEX(begin) >= RHSLEN(RULENO(begin))){
# set action to SHIFT/REDUCE
		ACTION(curindex)=SHIFT|REDUCE;
# delete the contents of the new set
		stateindex[newstate+1]=begin;
		return(0);
		}
# does each previous set match the new one?
	for i is each state (0 ... newstate-1){
# if the length of set i doesn't match the length of the new set, then
# they aren't the same
		if((stateindex[i+1]-stateindex[i]) != length)continue;
		old=stateindex[i];
		new=stateindex[newstate];
# check each entry in both sets to see if they have the same ruleno's
# and indecies
		while(old < stateindex[i+1]){
			if(RULENO(old)!=RULENO(new) || INDEX(old) != INDEX(new))break;
			old++,new++;
			}
# if they don't match go check the next set
		if(old!=stateindex[i+1])continue;
# if they do match, delete the new state and return the old set #
		stateindex[newstate+1]=stateindex[newstate];
		return(old);
		}
# we did not find a duplicate so keep newstate and generate a new empty
# set at the end
	stateindex[newstate+2]=stateindex[newstate+1];
	return(newstate++);