PGSLALR:
PROGRAM
IMPORTS PGSConDefs
EXPORTS PGSConDefs = {
OPEN PGSConDefs;
stateInfo: PGSTypes.StateInfo;
table: PGSTypes.Table;
lineWidth: CARDINAL;
lalrSuccess: BOOL;
entryLim: CARDINAL; -- index into table
six: CARDINAL; -- six, the current state; sLim in PGScon the next state number allocated
hashHead: PGSTypes.HashHeadsRef;
variables of the lookahead set calculation
top, rlim: CARDINAL; -- global to all incarnations of the recursive procedure context
predState, symbol: CARDINAL; -- local variables of context shared by all incarnations
backChain: PGSTypes.BackChain;
stack: PGSTypes.Stack;
chainStack: PGSTypes.ChainStack;
bitsInfo: PGSTypes.BitsInfo;
bitString: PGSTypes.BitString;
firstBits: PGSTypes.BitString;
LALRGen:
PUBLIC
PROC
RETURNS[BOOL] = {
i, j, k, totalShifts, totalReduces, oldEntries, firstOrCount: CARDINAL;
redEntries, maxRedEntries, defaultProd: CARDINAL;
conflictFlag, reduceFlag, messageFlag: BOOL;
conflicts: PGSTypes.Table;
PrintHeader:
PROC = {
j, p: CARDINAL;
outeol[2];
FOR i:
CARDINAL
DECREASING
IN (stateInfo[six+1].nucleus..stateInfo[six].nucleus]
DO
[,j,p] ← table[i];
IF lineWidth = 0
THEN {
outnum[six,4]; outchar[' ,1]; lineWidth ← tokenSize+5;
IF p>0 THEN outchar[' ,tokenSize-OutToken[rhsChar[prodInfo[p].index+j-1]]]};
IF lineWidth+9 > outbufLim THEN {outeol[1]; outchar[' ,lineWidth ← tokenSize+5]};
outnum[p,4]; outnum[j,3]; outchar['/,1]; outchar[' ,1];
ENDLOOP;
outeol[1]};
PrintEntry:
PROC[
item: PGSTypes.ItemRec, symmark: CARDINAL, sign: CHAR←'-] = {
i: INTEGER; p, j: CARDINAL;
IF item.tag = 2
THEN {
outstring[" Reduce with "]; outnum[item.pss,5,sign]; outeol[1]}
ELSE {
i ← item.pss; IF item.tag # 0 THEN i ← -i;
IF symmark = 0
THEN {
[,j,p] ← IF item.tag=0 THEN table[stateInfo[item.pss].nucleus] ELSE item;
symmark ← rhsChar[prodInfo[p].index+j-1]};
lineWidth ← lineWidth+tokenSize+8;
IF lineWidth > outbufLim THEN {outeol[1]; lineWidth ← tokenSize+8};
outnum[i,5,sign]; outchar[' ,1]; outchar[' ,tokenSize+2-OutToken[symmark]]}
PrintState:
PROC = {
i, j: CARDINAL;
lineWidth ← 0; PrintHeader[]; lineWidth ← 0;
i ← stateInfo[six].entries; WHILE i <stateInfo[six+1].entries
DO
IF table[i].tag # 3 THEN {PrintEntry[table[i],0]; i ← i+1}
ELSE {
FOR j ← i+1, j+1 WHILE table[j].tag = 3 DO NULL ENDLOOP;
FOR k: CARDINAL IN [i..j) DO PrintEntry[table[j], table[k].pss] ENDLOOP;
i ← j+1};
ENDLOOP
LalrHeader:
PROC = {
IF ~messageFlag
THEN {
messageFlag ← TRUE; seterrstream[]; outstring["\nLALR(1) Tables\n"];};
IF ~conflictFlag THEN {conflictFlag ← TRUE; lineWidth ← 0; PrintHeader[]}};
lalrSuccess ← TRUE; orCount ← 0;
make arrays with all entries zeroed
stateInfo ← MakeStateInfo[maxStateNum+2];
table ← MakeTable[maxTabEntries+1];
hashHead ← NEW[PGSTypes.HashHeads ← ALL[0]];
stateInfo[0].nucleus←maxTabEntries; table[maxTabEntries] ← [0,1,0]; --final state
stateInfo[1].nucleus←maxTabEntries-1; table[maxTabEntries-1] ← [0,0,0];--initial state
stateInfo[2].nucleus←maxTabEntries-2; sLim ← 2;
the sets of p,j components defining the LR(0) states are built at the end of table;
the nucleus field of each state indexes the appropriate set.
the entries for states 1,2,... are built at the beginning of table
stateInfo[1].entries ← entryLim ← totalShifts ← totalReduces ← 0;
IF flags[printLR] THEN {setoutstream[".lr"]; outstring["\nLR(0) TABLES"]};
FOR six ← 1, six+1
WHILE six < sLim
DO
ProcessState[]; stateInfo[six+1].entries ← entryLim;
IF flags[printLR] THEN PrintState[]; -- LR(0) tables are only a testing aid
FOR i
IN [stateInfo[six].entries..stateInfo[six+1].entries)
DO
SELECT table[i].tag
FROM
0 => totalShifts ← totalShifts+1;
2 => totalReduces ← totalReduces+1;
ENDCASE;
ENDLOOP
ENDLOOP;
IF flags[printLR] THEN outeol[1];
closeoutstream[];
IF ~flags[lists] AND ~flags[printLALR] THEN RETURN[FALSE];
now form inverse of shift transitions for the lookahead sets caculation
backChain ← MakeBackChain[totalShifts+1];
FOR six IN [0..sLim) DO stateInfo[six].link ← 0 ENDLOOP;
k ← 1;
FOR six
IN [1..sLim)
DO
FOR i
IN [stateInfo[six].entries..stateInfo[six+1].entries)
DO
IF table[i].tag = 0
THEN {
-- transition from six to table[i].pss
backChain[k].state ← six; backChain[k].link ← stateInfo[table[i].pss].link;
stateInfo[table[i].pss].link ← k; k ← k+1};
ENDLOOP;
ENDLOOP;
LALR(1) calculation begins here
bitstrSize ← (eofMark+wordLength-1)/wordLength;
firstBits ← MakeBitString[(totalTokens-eofMark+1), bitstrSize];
FirstSet[]; firstOrCount ← orCount;
hashHead^ ← ALL[0]; -- used by find
bitsInfo ← MakeBitsInfo[maxContexts]; rlim ← 1;
bitString ← MakeBitString[maxContexts, bitstrSize];
stack ← MakeStack[30]; top ← 0;
chainStack ← MakeStack[90];
conflicts ← MakeTable[totalTokens+1];
messageFlag ← FALSE;
tEntries ← ntEntries ← oldEntries ← 0;
IF flags[lists] THEN openwordstream[];
FOR six
IN [1..sLim)
DO
FOR i IN [1..totalTokens] DO conflicts[i] ← [0,0,0] ENDLOOP;
i ← stateInfo[six].entries;
WHILE i < stateInfo[six+1].entries
DO
insert scan and scan reduce entries in conflicts array
SELECT table[i].tag
FROM
0 => {
j, p: CARDINAL;
[,j,p] ← table[stateInfo[table[i].pss].nucleus];
conflicts[rhsChar[prodInfo[p].index+j-1]] ← table[i]; i ← i+1;
tEntries ← tEntries+1};
1 => {
j, p: CARDINAL;
[,j,p] ← table[i];
conflicts[rhsChar[prodInfo[p].index+j-1]] ← table[i]; i ← i+1;
tEntries ← tEntries+1};
2 => i ← i+1;
3 => {conflicts[table[i].pss] ← table[i+1]; i ← i+2; ntEntries ← ntEntries+1};
ENDCASE;
ENDLOOP;
compute lookaheads, insert reduce entries and output as necessary
conflictFlag ← FALSE; maxRedEntries ← defaultProd ← 0;
FOR i
IN [stateInfo[six].entries..stateInfo[six+1].entries)
WHILE table[i].tag = 2
DO
IF (k ← Find[six,[0,table[i].jf,table[i].pss]]) = rlim
THEN {
rlim ← rlim +1; Context[k,1]};
bitString[k] points at the LALR(1) lookahead for this reduce
reduceFlag ← FALSE; redEntries ← 0;
FOR j
IN [1..eofMark]
DO
IF FindBit[bitString,k,j]
THEN {
IF conflicts[j] = [0,0,0]
THEN {
conflicts[j] ← table[i]; tEntries ← tEntries+1; redEntries ← redEntries+1}
ELSE {
--we have conflicts
LalrHeader[];
IF ~reduceFlag
THEN {
reduceFlag ← TRUE; outstring[" REDUCE with "];
outnum[table[i].pss,4]; outstring[" conflicts with "]; outchar[' ,40];
outchar['*,10]; lineWidth ← outbufLim};
IF (lineWidth ← lineWidth+tokenSize+7) > outbufLim
THEN {
outeol[1]; outchar[' ,4]; lineWidth ← tokenSize+11};
outchar[' ,tokenSize-OutToken[j]];
IF conflicts[j].tag # 2
THEN {
outstring[" SCAN/ "]; warningsLogged ← TRUE}
ELSE {
outnum[conflicts[j].pss,5]; outstring["/ "]; lalrSuccess ← FALSE;
IF flags[lists]
THEN {
-- turn off binary output
flags[lists] ← FALSE; closewordstream[]}}}};
ENDLOOP;
IF reduceFlag THEN outeol[1];
IF redEntries > maxRedEntries
THEN {
maxRedEntries ← redEntries; defaultProd ← table[i].pss};
ENDLOOP;
IF flags[printLALR] THEN LalrHeader[];
IF flags[lists]
THEN {
outword[defaultProd]; outword[tEntries+ntEntries-oldEntries];
oldEntries ← tEntries+ntEntries};
lineWidth ← 0;
FOR j
IN [1..totalTokens]
DO
IF conflicts[j] # [0,0,0]
THEN {
item: PGSTypes.ItemRec ← conflicts[j];
grab entries for tabgen here
IF flags[lists]
THEN {
outword[j];
outword[IF item.tag=0 THEN 0 ELSE 4*item.jf+item.tag]; outword[item.pss]};
IF flags[printLALR]
OR conflictFlag
THEN {
IF item.tag = 2 THEN {item.tag ← 1; PrintEntry[item,j,'*]}
ELSE PrintEntry[item,j]}};
ENDLOOP;
ENDLOOP;
seterrstream[]; outstring["\nLALR(1) Statistics"];
outstring["\nStates ="]; outnum[sLim-1, 4];
outstring["\nTerminal entries ="]; outnum[tEntries, 5];
outstring["\nNonterminal entries ="]; outnum[ntEntries, 5];
outstring["\nFirst OR operation count ="]; outnum[firstOrCount, 5];
outstring["\nTotal OR operation count ="]; outnum[orCount, 5];
outstring["\nMaximum number of contexts ="]; outnum[rlim-1, 5];
outeol[1];
conflicts ← NIL; chainStack ← NIL;
stack ← NIL; bitString ← NIL;
bitsInfo ← NIL; firstBits ← NIL;
backChain ← NIL;
table ← NIL; stateInfo ← NIL;
rhsChar ← NIL; tokenInfo ← NIL;
hashHead ← NIL;
RETURN[lalrSuccess]};
ProcessState:
PROC = {
k1, k2, nmark, entrymark: CARDINAL; -- indexes into table
p, j, n: CARDINAL;
sym, nsym: CARDINAL;
procedures called by ProcessState
Sort:
PROC[index:
CARDINAL] = {
k1, k2: CARDINAL; item: PGSTypes.ItemRec; noswap: BOOL;
Compare:
PROC
RETURNS[BOOL] =
INLINE {
RETURN[table[k1+1].pss > table[k1+3].pss
OR
(table[k1+1].pss = table[k1+3].pss AND table[k1+1].jf > table[k1+3].jf)]
FOR k2 ← entryLim-2, k2-2
WHILE k2>=index
DO
noswap ← TRUE;
FOR k1 ← index, k1+2
WHILE k1<k2
DO
IF (table[k1].pss > table[k1+2].pss
OR table[k1].pss = table[k1+2].pss
AND Compare[])
THEN {
item ← table[k1]; table[k1] ← table[k1+2]; table[k1+2] ← item;
item ← table[k1+1]; table[k1+1] ← table[k1+3]; table[k1+3] ← item;
noswap ← FALSE};
ENDLOOP;
IF noswap THEN RETURN;
ENDLOOP
ExpandTable:
PROC = {
new: PGSTypes.Table ~ MakeTable[table.length+tabExt];
FOR i:
CARDINAL
IN [0..entryLim)
DO
new[i] ← table[i] ENDLOOP;
FOR i:
CARDINAL
IN (stateInfo[sLim].nucleus..table.length)
DO
new[i+tabExt] ← table[i] ENDLOOP;
FOR i:
CARDINAL
IN [1..sLim]
DO
stateInfo[i].nucleus ← stateInfo[i].nucleus+tabExt ENDLOOP;
table ← new};
LocateState:
PROC[index, n:
CARDINAL]
RETURNS[CARDINAL] = {
i, j, k, r: CARDINAL;
IF table[index+1] = [0,1,0] THEN RETURN[0]; -- final state, n=2 in this case
r ← (63*n+LOOPHOLE[table[index+1],CARDINAL]) MOD hashHead^.LENGTH;
FOR i ← hashHead[r], stateInfo[i].link
WHILE i # 0
DO
IF n = 2*(stateInfo[i].nucleus-stateInfo[i+1].nucleus)
THEN {
k ← index+1;
FOR j
DECREASING
IN (stateInfo[i+1].nucleus..stateInfo[i].nucleus]
DO
IF table[j] # table[k] THEN EXIT; k ← k+2;
REPEAT FINISHED => RETURN[i]
ENDLOOP};
ENDLOOP;
a new state
IF hashHead[r] # 0 THEN stateInfo[sLim].link ← hashHead[r]; hashHead[r] ← sLim;
IF sLim+1 = stateInfo.length
THEN
stateInfo ← ExpandStateInfo[stateInfo, stateExt];
IF entryLim+n/2 > stateInfo[sLim].nucleus THEN ExpandTable[];
insert new nucleus
r ← stateInfo[sLim].nucleus;
FOR i ← index+1, i+2 WHILE i<index+n DO table[r] ← table[i]; r ← r-1 ENDLOOP;
sLim ← sLim+1; stateInfo[sLim].nucleus ← r;
IF sLim <= pssLim+1
THEN
RETURN[sLim-1]
ELSE {
seterrstream[];
outstring["\n\nERROR - Internal field will overflow - increase PSSLIM\n"];
ERROR PGSFail[]}
end of local procedures
k1 ← stateInfo[six].nucleus;
IF (k1-stateInfo[six+1].nucleus)*2 > stateInfo[sLim].nucleus-entryLim+1
THEN
ExpandTable[];
copy nucleus to entries
FOR k1
DECREASING
IN (stateInfo[six+1].nucleus..k1]
DO
table[entryLim+1] ← table[k1]; entryLim ← entryLim+2 ENDLOOP;
compute closure
entrymark ← entryLim;
FOR k2 ← stateInfo[six].entries, k2+2
WHILE k2<entryLim
DO
p ← table[k2+1].pss; j ← table[k2+1].jf; table[k2] ← [0,0,0];
IF j # prodInfo[p].count
THEN {
--not a reduce
sym ← rhsChar[prodInfo[p].index+j]; table[k2].pss ← sym;
IF sym>eofMark
THEN {
-- nonterminal scan
t: PGSTypes.TokenEntry = tokenInfo[sym-eofMark];
FOR p
IN [t.index..t.index+t.count)
DO
FOR k1 ← entrymark, k1+2
WHILE k1<entryLim
DO
IF table[k1+1] = [0,0,p] THEN EXIT
REPEAT
FINISHED => {
IF entryLim+2 > stateInfo[sLim].nucleus THEN ExpandTable[];
table[entryLim+1] ← [0,0,p]; entryLim ← entryLim+2};
ENDLOOP;
ENDLOOP}};
ENDLOOP;
Sort[stateInfo[six].entries];
IF flags[chain]
THEN {
-- extend closure
k2 ← stateInfo[six].entries;
WHILE k2 < entryLim AND table[k2].pss <= eofMark DO k2 ← k2+2 ENDLOOP;
IF k2 < entryLim
THEN {
entrymark ← k2; --first nonterminal entry
WHILE k2 < entryLim
DO
p ← table[k2+1].pss;
IF prodInfo[p].chain
THEN {
sym ← table[k2].pss; nsym ← prodInfo[p].lhs; -- now search for lhs entry
k1 ← entrymark; WHILE nsym # table[k1].pss DO k1 ← k1+2 ENDLOOP;
now overwrite chain entry with first chained entry
table[k2+1] ← table[k1+1];
k2 ← k2-2; -- back up k2 in case first chained entry is also a chain entry
now append the other chained entries
FOR k1 ← k1+2, k1+2
WHILE k1 < entryLim
DO
IF nsym = table[k1].pss
THEN {
IF entryLim+2 > stateInfo[sLim].nucleus THEN ExpandTable[];
table[entryLim].pss ← sym; table[entryLim+1] ← table[k1+1];
entryLim ← entryLim+2};
ENDLOOP};
k2 ← k2+2;
ENDLOOP;
Sort[entrymark]}};
pack up reduce entries
k1 ← k2 ← stateInfo[six].entries;
WHILE k2 < entryLim
AND table[k2].pss = 0
DO
table[k1] ← table[k2+1]; table[k1].tag ← 2; k1 ← k1+1; k2 ← k2+2 ENDLOOP;
form new states and pack up entries
entrymark ← k2; nmark ← 0;
WHILE entrymark < entryLim
DO
k2 ← entrymark+2;
WHILE k2 < entryLim
AND table[k2].pss = table[entrymark].pss
DO
table[k2+1].jf ← table[k2+1].jf+1; k2 ← k2+2 ENDLOOP;
table[entrymark+1].jf ← table[entrymark+1].jf+1;
n ← k2-entrymark; -- 2*number of elements in this state
IF n#2
OR table[entrymark+1].jf # prodInfo[table[entrymark+1].pss].count
THEN
table[entrymark+1] ← [0,1,LocateState[entrymark,n]] -- make shift
ELSE table[entrymark+1].tag ← 1; -- make scan reduce
IF table[entrymark].pss > eofMark
THEN {
-- insert symbol
IF nmark = 0 THEN nmark ← k1;
table[k1] ← [3,0,table[entrymark].pss]; k1 ← k1+1};
table[k1] ← table[entrymark+1]; k1 ← k1+1; --insert shift or scan reduce
entrymark ← k2;
ENDLOOP;
entryLim ← k1}; -- entryLim-1 => last entry, nmark => first nonterminal entry or is 0
FirstSet:
PROC = {
i, j, top, listindex: CARDINAL;
discrim, vertices: PGSTypes.AttrVec;
t: PGSTypes.TokenEntry;
p: PGSTypes.ProdEntry;
First:
PROC[nonterm:
CARDINAL] = {
prix, chix, w: CARDINAL;
discrim[nonterm] ← top ← top+1; vertices[top] ← nonterm;
t ← tokenInfo[nonterm];
FOR prix
IN [t.index..t.index+t.count)
DO
p ← prodInfo[prix];
FOR chix
IN [p.index..p.index+p.count)
DO
w ← rhsChar[chix];
IF w <= eofMark THEN {InsertBit[firstBits, nonterm, w]; EXIT};
w ← w-eofMark; IF discrim[w] = 0 THEN First[w];
IF discrim[w] <= top THEN discrim[nonterm] ← MIN[discrim[nonterm], discrim[w]]
ELSE OrBits[firstBits, vertices[discrim[w]], firstBits, nonterm];
IF ~tokenInfo[w].empty THEN EXIT;
ENDLOOP;
ENDLOOP;
IF nonterm = vertices[discrim[nonterm]]
THEN {
listindex ← listindex-1;
w ← vertices[top]; top ← top-1; discrim[w] ← listindex;
WHILE w # nonterm
DO
OrBits[firstBits, w, firstBits, nonterm];
w ← vertices[top]; top ← top-1; discrim[w] ← listindex;
ENDLOOP;
vertices[listindex] ← nonterm}
discrim ← MakeAttrVec[totalTokens-eofMark+1];
vertices ← MakeAttrVec[totalTokens-eofMark+1];
listindex ← totalTokens-eofMark+1; top ← 0; -- initialise stack and list of heads
FOR i IN [1..totalTokens-eofMark] DO IF discrim[i] = 0 THEN First[i] ENDLOOP;
FOR i
IN [1..totalTokens-eofMark]
DO
-- copy head bitStrings to other scc vertices
IF i # vertices[discrim[i]]
THEN
OrBits[firstBits, vertices[discrim[i]], firstBits, i];
ENDLOOP;
discrim ← NIL; vertices ← NIL;
IF flags[first]
THEN {
setoutstream[".first"]; outstring["\nFIRST SETS\n\n"];
FOR i
IN [1..totalTokens-eofMark]
DO
[] ← OutToken[i+eofMark]; lineWidth ← outbufLim;
FOR j
IN [1..eofMark]
DO
IF FindBit[firstBits,i,j]
THEN {
IF (lineWidth ← lineWidth+tokenSize+1) > outbufLim
THEN {
outeol[1]; outchar[' ,4]; lineWidth ← tokenSize+5};
outchar[' ,tokenSize+1-OutToken[j]]};
ENDLOOP;
outeol[2];
ENDLOOP;
closeoutstream[]}
Find:
PROC[state:
CARDINAL, item: PGSTypes.ItemRec]
RETURNS[CARDINAL] = {
i, r: CARDINAL;
r ← (state + LOOPHOLE[item,CARDINAL]) MOD hashHead^.LENGTH; i ← hashHead[r];
WHILE i # 0
DO
IF state = bitsInfo[i].state AND item = bitsInfo[i].item THEN RETURN[i];
i ← bitsInfo[i].link;
ENDLOOP;
new context
IF rlim>=bitsInfo.length
THEN {
bitsInfo ← ExpandBitsInfo[bitsInfo, bitsInfo.length/8];
bitString ← ExpandBitString[bitString, bitString.length/8];
};
IF hashHead[r] # 0 THEN bitsInfo[rlim].link ← hashHead[r];
hashHead[r] ← rlim;
bitsInfo[rlim].state ← state; bitsInfo[rlim].item ← item;
RETURN[rlim]};
Context:
PROC[index, base:
CARDINAL] = {
cj, j: CARDINAL; -- displacements relative to base into chainStack
i: CARDINAL; -- used locally but also indexes current (q,k+1) across recursive calls
k: CARDINAL; -- used locally but also indexes current state across recursive calls
top ← top+1;
IF top = stack.length THEN stack ← ExpandStack[stack, 15];
bitsInfo[index].status ← top; stack[top] ← index; -- initialise for transitive closure
j ← bitsInfo[index].item.jf; -- want the jth predecessor state
IF base+MAX[1,j] >= chainStack.length THEN chainStack ← ExpandStack[chainStack, 45];
cj ← 1; chainStack[base+cj] ← stateInfo[bitsInfo[index].state].link; --index 1st predec
DO
-- for each jth predecessor state
IF j=0
THEN {
predState ← bitsInfo[index].state; -- zeroth predecessor
j ← 1; chainStack[base+cj] ← 0} --ensure no more zeroth predecessors
ELSE
DO
IF chainStack[base+cj] = 0
THEN {
IF (cj ← cj-1) =0 THEN GOTO quit} -- no more jth predecessors
ELSE {
[predState, chainStack[base+cj]] ← backChain[chainStack[base+cj]];
IF cj=j THEN EXIT;
cj ← cj+1; chainStack[base+cj] ← stateInfo[predState].link};
ENDLOOP;
locate the (q,k+1) in each jth predecessor state
FOR i
IN [stateInfo[predState].entries..stateInfo[predState+1].entries)
DO
IF table[i] = [3,0,prodInfo[bitsInfo[index].item.pss].lhs] THEN EXIT;
REPEAT FINISHED => ERROR -- nonterminal not found
ENDLOOP;
i ← i+1; -- index the associated item
IF table[i].tag # 0
THEN k ← i-1
ELSE {
k ← stateInfo[table[i].pss+1].nucleus; i ← stateInfo[table[i].pss].nucleus};
FOR i
DECREASING
IN (k..i]
DO
--select each (q,k+1) s.t. X[q,k+1] = A[p]
FOR k
IN [table[i].jf..prodInfo[table[i].pss].count)
DO
--all v s.t. k+2<=v<= n[q]
IF (symbol ← rhsChar[prodInfo[table[i].pss].index+k]) <= eofMark
THEN {
X[q.v]<=eofMark
InsertBit[bitString, index, symbol]; EXIT}
ELSE {
symbol ← symbol-eofMark;
OrBits[firstBits, symbol, bitString, index];
IF ~tokenInfo[symbol].empty THEN EXIT};
now the core of the transitive closure algorithm
REPEAT
FINISHED => {
IF (k ← Find[predState, [0,table[i].jf-1,table[i].pss]]) = rlim
THEN {
rlim ← rlim+1; Context[k,base+j]};
IF bitsInfo[k].status <= top
THEN
bitsInfo[index].status ← MIN[bitsInfo[index].status,bitsInfo[k].status]
ELSE OrBits[bitString, k, bitString, index]};
ENDLOOP;
ENDLOOP;
REPEAT quit => NULL
ENDLOOP;
IF index = stack[bitsInfo[index].status]
THEN {
--scc head
k ← top; i ← stack[top]; bitsInfo[i].status ← CARDINAL.LAST;
FOR top ← top-1, top-1
WHILE i#index
DO
OrBits[bitString, i, bitString, index];
i ← stack[top]; bitsInfo[i].status ← CARDINAL.LAST;
ENDLOOP;
FOR k
IN [top+2..k]
DO
OrBits[bitString, index, bitString, stack[k]];
ENDLOOP
}
}.