-- file PGSLALR.mesa
-- last modified by Satterthwaite, June 23, 1982 10:10 am
DIRECTORY
PGSConDefs: TYPE USING [
maxContexts, maxTabEntries, maxStateNum, outbufLim, pssLim,
stateExt, tabExt, tokenSize, wordLength,
bitstrsize, eofile, flags, ntentries, orCount, prodinfo, rhschar,
slim, tentries, tokeninfo, totalTokens, warningsLogged,
AcquireZone, closeoutstream, closewordstream, Expand, FindBit,
FreeArray, InsertBit, MakeArray, openwordstream, OrBits,
outchar, outeol, outnum, outstring, OutToken, outword, ReleaseZone,
seterrstream, setoutstream, PGSFail],
PGSTypes: TYPE USING [
AttrVec, BackChain, BitsInfo, BitString, ChainRec, ChainStack, ContextRec,
FirstBits, HashHeads, HashHeadsRef, ItemRec, LongDes, ProdEntry, Stack,
StateInfo, StateInfoRec, Table, TokenEntry];
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.FirstBits;
LALRGen: PUBLIC PROC RETURNS [BOOL] = {
zone: UNCOUNTED ZONE ← AcquireZone[];
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 "L]; 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"L];};
IF ~conflictFlag THEN {conflictFlag ← TRUE; lineWidth ← 0; PrintHeader[]}};
lalrSuccess ← TRUE; orCount ← 0;
-- make arrays with all entries zeroed
stateInfo ← LOOPHOLE[MakeArray[maxStateNum+2,SIZE[PGSTypes.StateInfoRec]]];
table ← LOOPHOLE[MakeArray[maxTabEntries+1,SIZE[PGSTypes.ItemRec]]];
hashHead ← zone.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"L]; outstring["\nLR(0) TABLES"L]};
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 ← LOOPHOLE[MakeArray[totalShifts+1, SIZE[PGSTypes.ChainRec]]];
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 ← (eofile+wordLength-1)/wordLength;
firstBits ← LOOPHOLE[MakeArray[totalTokens-eofile+1,bitstrsize]];
FirstSet[]; firstOrCount ← orCount;
hashHead↑ ← ALL[0]; -- used by find
bitsInfo ← LOOPHOLE[MakeArray[maxContexts, SIZE[PGSTypes.ContextRec]]]; rlim ← 1;
bitString ← LOOPHOLE[MakeArray[maxContexts, bitstrsize]];
stack ← LOOPHOLE[MakeArray[30,SIZE[CARDINAL]]]; top ← 0;
chainStack ← LOOPHOLE[MakeArray[90,SIZE[CARDINAL]]];
conflicts ← LOOPHOLE[MakeArray[totalTokens+1,SIZE[PGSTypes.ItemRec]]];
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]};
k ← k*bitstrsize; -- @bitString[k] points at the LALR(1) lookahead for this reduce
reduceFlag ← FALSE; redEntries ← 0;
FOR j IN [1..eofile] DO
IF FindBit[j,@bitString[k]] 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 "L];
outnum[table[i].pss,4]; outstring[" conflicts with "L]; 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/ "L]; warningsLogged ← TRUE}
ELSE {
outnum[conflicts[j].pss,5]; outstring["/ "L]; 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"L];
outstring["\nStates ="L]; outnum[slim-1, 4];
outstring["\nTerminal entries ="L]; outnum[tentries, 5];
outstring["\nNonterminal entries ="L]; outnum[ntentries, 5];
outstring["\nFirst OR operation count ="L]; outnum[firstOrCount, 5];
outstring["\nTotal OR operation count ="L]; outnum[orCount, 5];
outstring["\nMaximum number of contexts ="L]; outnum[rlim-1, 5];
outeol[1];
FreeArray[conflicts]; FreeArray[chainStack];
FreeArray[stack]; FreeArray[bitString];
FreeArray[bitsInfo]; FreeArray[firstBits];
FreeArray[backChain];
FreeArray[table]; FreeArray[stateInfo];
FreeArray[rhschar]; FreeArray[tokeninfo];
zone.FREE[@hashHead]; ReleaseZone[zone];
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 = {
i: CARDINAL; new: PGSTypes.LongDes;
new ← LOOPHOLE[MakeArray[LENGTH[table]+tabExt,SIZE[PGSTypes.ItemRec]]];
FOR i IN [0..entryLim) DO new[i] ← table[i] ENDLOOP;
FOR i IN (stateInfo[slim].nucleus..LENGTH[table]) DO
new[i+tabExt] ← table[i] ENDLOOP;
FOR i IN [1..slim] DO stateInfo[i].nucleus ← stateInfo[i].nucleus+tabExt ENDLOOP;
FreeArray[table]; 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 LENGTH[hashHead↑];
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 = LENGTH[stateInfo] THEN
stateInfo ← LOOPHOLE[Expand[stateInfo, SIZE[PGSTypes.StateInfoRec], 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"L];
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>eofile THEN { -- nonterminal scan
t: PGSTypes.TokenEntry = tokeninfo[sym-eofile];
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 <= eofile 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 > eofile 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 <= eofile THEN {InsertBit[w,@firstBits[nonterm*bitstrsize]]; EXIT};
w ← w-eofile; 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]]*bitstrsize],
@firstBits[nonterm*bitstrsize]];
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*bitstrsize], @firstBits[nonterm*bitstrsize]];
w ← vertices[top]; top ← top-1; discrim[w] ← listindex;
ENDLOOP;
vertices[listindex] ← nonterm}};
discrim ← LOOPHOLE[MakeArray[totalTokens-eofile+1, SIZE[CARDINAL]]];
vertices ← LOOPHOLE[MakeArray[totalTokens-eofile+1, SIZE[CARDINAL]]];
listindex ← totalTokens-eofile+1; top ← 0; -- initialise stack and list of heads
FOR i IN [1..totalTokens-eofile] DO IF discrim[i] = 0 THEN First[i] ENDLOOP;
FOR i IN [1..totalTokens-eofile] DO -- copy head bitStrings to other scc vertices
IF i # vertices[discrim[i]] THEN
OrBits[@firstBits[vertices[discrim[i]]*bitstrsize], @firstBits[i*bitstrsize]];
ENDLOOP;
FreeArray[discrim]; FreeArray[vertices];
IF flags[first] THEN {
setoutstream[".first"L]; outstring["\nFIRST SETS\n\n"L];
FOR i IN [1..totalTokens-eofile] DO
[] ← OutToken[i+eofile]; lineWidth ← outbufLim;
FOR j IN [1..eofile] DO
IF FindBit[j,@firstBits[i*bitstrsize]] 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 LENGTH[hashHead↑]; 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>=LENGTH[bitsInfo] THEN {
bitsInfo ← LOOPHOLE[Expand[bitsInfo,SIZE[PGSTypes.ContextRec],LENGTH[bitsInfo]/8]];
bitString ← LOOPHOLE[Expand[bitString,bitstrsize,LENGTH[bitString]/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 = LENGTH[stack] THEN stack ← LOOPHOLE[Expand[stack,SIZE[CARDINAL],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] >= LENGTH[chainStack] THEN
chainStack ← LOOPHOLE[Expand[chainStack,SIZE[CARDINAL],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]) <= eofile THEN {
-- X[q.v]<=eofile
InsertBit[symbol, @bitString[index*bitstrsize] ]; EXIT}
ELSE {
symbol ← symbol-eofile;
OrBits[ @firstBits[symbol*bitstrsize], @bitString[index*bitstrsize] ];
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*bitstrsize], @bitString[index*bitstrsize] ]};
ENDLOOP;
ENDLOOP;
REPEAT quit => NULL
ENDLOOP;
IF index = stack[bitsInfo[index].status] THEN { --scc head
k ← top; i ← stack[top]; bitsInfo[i].status ← LAST[CARDINAL];
FOR top ← top-1, top-1 WHILE i#index DO
OrBits[ @bitString[i*bitstrsize], @bitString[index*bitstrsize] ];
i ← stack[top]; bitsInfo[i].status ← LAST[CARDINAL];
ENDLOOP;
FOR k IN [top+2..k] DO
OrBits[ @bitString[index*bitstrsize], @bitString[stack[k]*bitstrsize] ];
ENDLOOP}};
}.