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= 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= 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++);