<<>> <> <> <> <> <> <> <> <<>> DIRECTORY NPGSConDefs, NPGSTypes; NPGSLALR: CEDAR PROGRAM IMPORTS NPGSConDefs EXPORTS NPGSConDefs = { stateInfo: NPGSTypes.StateInfo; table: NPGSTypes.Table; lineWidth: CARDINAL; lalrSuccess: BOOL; entryLim: CARDINAL; -- index into table six: CARDINAL; -- six, the current state; sLim in NPGScan the next state number allocated hashHead: NPGSTypes.HashHeadsRef; <> top, rlim: CARDINAL; -- global to all incarnations of the recursive procedure context predState, symbol: CARDINAL; -- local variables of context shared by all incarnations backChain: NPGSTypes.BackChain; stack: NPGSTypes.Stack; chainStack: NPGSTypes.ChainStack; bitsInfo: NPGSTypes.BitsInfo; bitString: NPGSTypes.BitString; firstBits: NPGSTypes.BitString; LALRGen: PUBLIC PROC [cusp: BOOL] RETURNS[BOOL] = { i, j, k, totalShifts, totalReduces, oldEntries, firstOrCount: CARDINAL; redEntries, maxRedEntries, defaultProd: CARDINAL; conflictFlag, reduceFlag, messageFlag: BOOL; conflicts: NPGSTypes.Table; PrintHeader: PROC = { j, p: CARDINAL; NPGSConDefs.outeol[2]; FOR i: CARDINAL DECREASING IN (stateInfo[six+1].nucleus..stateInfo[six].nucleus] DO [,j,p] Ź table[i]; IF lineWidth = 0 THEN { NPGSConDefs.outnum[six,4]; NPGSConDefs.outchar[' ,1]; lineWidth Ź NPGSConDefs.tokenSize+5; IF p>0 THEN NPGSConDefs.outchar[' ,NPGSConDefs.tokenSize-NPGSConDefs.OutToken[NPGSConDefs.rhsChar[NPGSConDefs.prodInfo[p].index+j-1]]] }; IF lineWidth+9 > NPGSConDefs.outbufLim THEN {NPGSConDefs.outeol[1]; NPGSConDefs.outchar[' ,lineWidth Ź NPGSConDefs.tokenSize+5]}; NPGSConDefs.outnum[p,4]; NPGSConDefs.outnum[j,3]; NPGSConDefs.outchar['/,1]; NPGSConDefs.outchar[' ,1]; ENDLOOP; NPGSConDefs.outeol[1] }; PrintEntry: PROC[ item: NPGSTypes.ItemRec, symmark: CARDINAL, sign: CHARŹ'-] = { i: INTEGER; p, j: CARDINAL; IF item.tag = 2 THEN { NPGSConDefs.outstring[" Reduce with "]; NPGSConDefs.outnum[item.pss,5,sign]; NPGSConDefs.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 Ź NPGSConDefs.rhsChar[NPGSConDefs.prodInfo[p].index+j-1] }; lineWidth Ź lineWidth+NPGSConDefs.tokenSize+8; IF lineWidth > NPGSConDefs.outbufLim THEN {NPGSConDefs.outeol[1]; lineWidth Ź NPGSConDefs.tokenSize+8}; NPGSConDefs.outnum[i,5,sign]; NPGSConDefs.outchar[' ,1]; NPGSConDefs.outchar[' ,NPGSConDefs.tokenSize+2-NPGSConDefs.OutToken[symmark]] } }; PrintState: PROC = { i, j: CARDINAL; lineWidth Ź 0; PrintHeader[]; lineWidth Ź 0; i Ź stateInfo[six].entries; WHILE i > stateInfo Ź NPGSConDefs.MakeStateInfo[NPGSConDefs.maxStateNum+2]; table Ź NPGSConDefs.MakeTable[NPGSConDefs.maxTabEntries+1]; hashHead Ź NEW[NPGSTypes.HashHeads Ź ALL[0]]; stateInfo[0].nucleusŹNPGSConDefs.maxTabEntries; table[NPGSConDefs.maxTabEntries] Ź [0,1,0]; --final state stateInfo[1].nucleusŹNPGSConDefs.maxTabEntries-1; table[NPGSConDefs.maxTabEntries-1] Ź [0,0,0];--initial state stateInfo[2].nucleusŹNPGSConDefs.maxTabEntries-2; NPGSConDefs.sLim Ź 2; <> <> <> stateInfo[1].entries Ź entryLim Ź totalShifts Ź totalReduces Ź 0; IF NPGSConDefs.flags[printLR] THEN {NPGSConDefs.setoutstream[".lr"]; NPGSConDefs.outstring["\nLR(0) TABLES"]}; FOR six Ź 1, six+1 WHILE six < NPGSConDefs.sLim DO ProcessState[]; stateInfo[six+1].entries Ź entryLim; IF NPGSConDefs.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 NPGSConDefs.flags[printLR] THEN NPGSConDefs.outeol[1]; NPGSConDefs.closeoutstream[]; IF ~NPGSConDefs.flags[lists] AND ~NPGSConDefs.flags[printLALR] THEN RETURN[FALSE]; <> backChain Ź NPGSConDefs.MakeBackChain[totalShifts+1]; FOR six IN [0..NPGSConDefs.sLim) DO stateInfo[six].link Ź 0 ENDLOOP; k Ź 1; FOR six IN [1..NPGSConDefs.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; <> NPGSConDefs.bitstrSize Ź (NPGSConDefs.eofMark+NPGSConDefs.wordLength-1)/NPGSConDefs.wordLength; firstBits Ź NPGSConDefs.MakeBitString[(NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1), NPGSConDefs.bitstrSize]; FirstSet[]; firstOrCount Ź NPGSConDefs.orCount; hashHead Ź ALL[0]; -- used by find bitsInfo Ź NPGSConDefs.MakeBitsInfo[NPGSConDefs.maxContexts]; rlim Ź 1; bitString Ź NPGSConDefs.MakeBitString[NPGSConDefs.maxContexts, NPGSConDefs.bitstrSize]; stack Ź NPGSConDefs.MakeStack[30]; top Ź 0; chainStack Ź NPGSConDefs.MakeStack[90]; conflicts Ź NPGSConDefs.MakeTable[NPGSConDefs.totalTokens+1]; messageFlag Ź FALSE; NPGSConDefs.tEntries Ź NPGSConDefs.ntEntries Ź oldEntries Ź 0; IF NPGSConDefs.flags[lists] THEN NPGSConDefs.openwordstream[]; FOR six IN [1..NPGSConDefs.sLim) DO FOR i IN [1..NPGSConDefs.totalTokens] DO conflicts[i] Ź [0,0,0] ENDLOOP; i Ź stateInfo[six].entries; WHILE i < stateInfo[six+1].entries DO <> SELECT table[i].tag FROM 0 => { j, p: CARDINAL; [,j,p] Ź table[stateInfo[table[i].pss].nucleus]; conflicts[NPGSConDefs.rhsChar[NPGSConDefs.prodInfo[p].index+j-1]] Ź table[i]; i Ź i+1; NPGSConDefs.tEntries Ź NPGSConDefs.tEntries+1 }; 1 => { j, p: CARDINAL; [,j,p] Ź table[i]; conflicts[NPGSConDefs.rhsChar[NPGSConDefs.prodInfo[p].index+j-1]] Ź table[i]; i Ź i+1; NPGSConDefs.tEntries Ź NPGSConDefs.tEntries+1 }; 2 => i Ź i+1; 3 => {conflicts[table[i].pss] Ź table[i+1]; i Ź i+2; NPGSConDefs.ntEntries Ź NPGSConDefs.ntEntries+1}; ENDCASE; ENDLOOP; <> 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] }; <> reduceFlag Ź FALSE; redEntries Ź 0; FOR j IN [1..NPGSConDefs.eofMark] DO IF NPGSConDefs.FindBit[bitString,k,j] THEN { IF conflicts[j] = [0,0,0] THEN { conflicts[j] Ź table[i]; NPGSConDefs.tEntries Ź NPGSConDefs.tEntries+1; redEntries Ź redEntries+1 } ELSE { --we have conflicts LalrHeader[]; IF ~reduceFlag THEN { reduceFlag Ź TRUE; NPGSConDefs.outstring[" REDUCE with "]; NPGSConDefs.outnum[table[i].pss,4]; NPGSConDefs.outstring[" conflicts with "]; NPGSConDefs.outchar[' ,40]; NPGSConDefs.outchar['*,10]; lineWidth Ź NPGSConDefs.outbufLim }; IF (lineWidth Ź lineWidth+NPGSConDefs.tokenSize+7) > NPGSConDefs.outbufLim THEN { NPGSConDefs.outeol[1]; NPGSConDefs.outchar[' ,4]; lineWidth Ź NPGSConDefs.tokenSize+11 }; NPGSConDefs.outchar[' ,NPGSConDefs.tokenSize-NPGSConDefs.OutToken[j]]; IF conflicts[j].tag # 2 THEN { NPGSConDefs.outstring[" SCAN/ "]; NPGSConDefs.warningsLogged Ź TRUE } ELSE { NPGSConDefs.outnum[conflicts[j].pss,5]; NPGSConDefs.outstring["/ "]; lalrSuccess Ź FALSE; IF NPGSConDefs.flags[lists] THEN { -- turn off binary output NPGSConDefs.flags[lists] Ź FALSE; NPGSConDefs.closewordstream[] } } } }; ENDLOOP; IF reduceFlag THEN NPGSConDefs.outeol[1]; IF redEntries > maxRedEntries THEN { maxRedEntries Ź redEntries; defaultProd Ź table[i].pss }; ENDLOOP; IF NPGSConDefs.flags[printLALR] THEN LalrHeader[]; IF NPGSConDefs.flags[lists] THEN { NPGSConDefs.outword[defaultProd]; NPGSConDefs.outword[NPGSConDefs.tEntries+NPGSConDefs.ntEntries-oldEntries]; oldEntries Ź NPGSConDefs.tEntries+NPGSConDefs.ntEntries }; lineWidth Ź 0; -- New for CUSP: IF cusp THEN { NPGSConDefs.CuspPreClearTokensUsedArray[]; [,j,k] Ź table[stateInfo[six].nucleus]; IF k > 0 THEN NPGSConDefs.CuspPreSetHeaderUsed[NPGSConDefs.rhsChar[NPGSConDefs.prodInfo[k].index+j-1]]; }; -- end of new stuff FOR j IN [1..NPGSConDefs.totalTokens] DO IF conflicts[j] # [0,0,0] THEN { item: NPGSTypes.ItemRec Ź conflicts[j]; <> IF NPGSConDefs.flags[lists] THEN { NPGSConDefs.outword[j]; NPGSConDefs.outword[IF item.tag=0 THEN 0 ELSE 4*item.jf+item.tag]; NPGSConDefs.outword[item.pss] }; IF NPGSConDefs.flags[printLALR] OR conflictFlag THEN { IF item.tag = 2 THEN {item.tag Ź 1; PrintEntry[item,j,'*]} ELSE PrintEntry[item,j] }; IF cusp THEN NPGSConDefs.CuspPreSetNextTokenUsed[j]; -- new for CUSP }; ENDLOOP; IF cusp THEN NPGSConDefs.CuspPreSetNextErrorMsgElement[six]; -- new for CUSP ENDLOOP; NPGSConDefs.seterrstream[]; NPGSConDefs.outstring["\nLALR(1) Statistics"]; NPGSConDefs.outstring["\nStates ="]; NPGSConDefs.outnum[NPGSConDefs.sLim-1, 4]; NPGSConDefs.outstring["\nTerminal entries ="]; NPGSConDefs.outnum[NPGSConDefs.tEntries, 5]; NPGSConDefs.outstring["\nNonterminal entries ="]; NPGSConDefs.outnum[NPGSConDefs.ntEntries, 5]; NPGSConDefs.outstring["\nFirst OR operation count ="]; NPGSConDefs.outnum[firstOrCount, 5]; NPGSConDefs.outstring["\nTotal OR operation count ="]; NPGSConDefs.outnum[NPGSConDefs.orCount, 5]; NPGSConDefs.outstring["\nMaximum number of contexts ="]; NPGSConDefs.outnum[rlim-1, 5]; NPGSConDefs.outeol[1]; conflicts Ź NIL; chainStack Ź NIL; stack Ź NIL; bitString Ź NIL; bitsInfo Ź NIL; firstBits Ź NIL; backChain Ź NIL; table Ź NIL; stateInfo Ź NIL; NPGSConDefs.rhsChar Ź NIL; NPGSConDefs.tokenInfo Ź NIL; hashHead Ź NIL; RETURN[lalrSuccess] }; ProcessState: PROC = { k1, k2, nmark, entrymark: CARDINAL; -- indexes into table p, j, n: CARDINAL; sym, nsym: CARDINAL; <> Sort: PROC[index: CARDINAL] = { k1, k2: CARDINAL; item: NPGSTypes.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 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: NPGSTypes.Table ~ NPGSConDefs.MakeTable[table.length+NPGSConDefs.tabExt]; FOR i: CARDINAL IN [0..entryLim) DO new[i] Ź table[i] ENDLOOP; FOR i: CARDINAL IN (stateInfo[NPGSConDefs.sLim].nucleus..table.length) DO new[i+NPGSConDefs.tabExt] Ź table[i] ENDLOOP; FOR i: CARDINAL IN [1..NPGSConDefs.sLim] DO stateInfo[i].nucleus Ź stateInfo[i].nucleus+NPGSConDefs.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], CARD16]) 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; <> IF hashHead[r] # 0 THEN stateInfo[NPGSConDefs.sLim].link Ź hashHead[r]; hashHead[r] Ź NPGSConDefs.sLim; IF NPGSConDefs.sLim+1 = stateInfo.length THEN stateInfo Ź NPGSConDefs.ExpandStateInfo[stateInfo, NPGSConDefs.stateExt]; IF entryLim+n/2 > stateInfo[NPGSConDefs.sLim].nucleus THEN ExpandTable[]; <> r Ź stateInfo[NPGSConDefs.sLim].nucleus; FOR i Ź index+1, i+2 WHILE i> k1 Ź stateInfo[six].nucleus; IF (k1-stateInfo[six+1].nucleus)*2 > stateInfo[NPGSConDefs.sLim].nucleus-entryLim+1 THEN ExpandTable[]; <> FOR k1 DECREASING IN (stateInfo[six+1].nucleus..k1] DO table[entryLim+1] Ź table[k1]; entryLim Ź entryLim+2 ENDLOOP; <> entrymark Ź entryLim; FOR k2 Ź stateInfo[six].entries, k2+2 WHILE k2NPGSConDefs.eofMark THEN { -- nonterminal scan t: NPGSTypes.TokenEntry = NPGSConDefs.tokenInfo[sym-NPGSConDefs.eofMark]; FOR p IN [t.index..t.index+t.count) DO FOR k1 Ź entrymark, k1+2 WHILE k1 { IF entryLim+2 > stateInfo[NPGSConDefs.sLim].nucleus THEN ExpandTable[]; table[entryLim+1] Ź [0,0,p]; entryLim Ź entryLim+2 }; ENDLOOP; ENDLOOP } }; ENDLOOP; Sort[stateInfo[six].entries]; IF NPGSConDefs.flags[chain] THEN { -- extend closure k2 Ź stateInfo[six].entries; WHILE k2 < entryLim AND table[k2].pss <= NPGSConDefs.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 NPGSConDefs.prodInfo[p].chain THEN { sym Ź table[k2].pss; nsym Ź NPGSConDefs.prodInfo[p].lhs; -- now search for lhs entry k1 Ź entrymark; WHILE nsym # table[k1].pss DO k1 Ź k1+2 ENDLOOP; <> table[k2+1] Ź table[k1+1]; k2 Ź k2-2; -- back up k2 in case first chained entry is also a chain entry <> FOR k1 Ź k1+2, k1+2 WHILE k1 < entryLim DO IF nsym = table[k1].pss THEN { IF entryLim+2 > stateInfo[NPGSConDefs.sLim].nucleus THEN ExpandTable[]; table[entryLim].pss Ź sym; table[entryLim+1] Ź table[k1+1]; entryLim Ź entryLim+2 }; ENDLOOP }; k2 Ź k2+2; ENDLOOP; Sort[entrymark] } }; <> 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; <

> entrymark Ź k2; nmark Ź 0; WHILE entrymark < entryLim DO jf: CARDINAL Ź 0; k2 Ź entrymark+2; WHILE k2 < entryLim AND table[k2].pss = table[entrymark].pss DO jf Ź table[k2+1].jf; table[k2+1].jf Ź jf+1; k2 Ź k2+2 ENDLOOP; jf Ź table[entrymark+1].jf; table[entrymark+1].jf Ź jf + 1; <> n Ź k2-entrymark; -- 2*number of elements in this state IF n#2 OR table[entrymark+1].jf # NPGSConDefs.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 > NPGSConDefs.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: NPGSTypes.AttrVec; t: NPGSTypes.TokenEntry; p: NPGSTypes.ProdEntry; First: PROC[nonterm: CARDINAL] = { prix, chix, w: CARDINAL; discrim[nonterm] Ź top Ź top+1; vertices[top] Ź nonterm; t Ź NPGSConDefs.tokenInfo[nonterm]; FOR prix IN [t.index..t.index+t.count) DO p Ź NPGSConDefs.prodInfo[prix]; FOR chix IN [p.index..p.index+p.count) DO w Ź NPGSConDefs.rhsChar[chix]; IF w <= NPGSConDefs.eofMark THEN {NPGSConDefs.InsertBit[firstBits, nonterm, w]; EXIT}; w Ź w-NPGSConDefs.eofMark; IF discrim[w] = 0 THEN First[w]; IF discrim[w] <= top THEN discrim[nonterm] Ź MIN[discrim[nonterm], discrim[w]] ELSE NPGSConDefs.OrBits[firstBits, vertices[discrim[w]], firstBits, nonterm]; IF ~NPGSConDefs.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 NPGSConDefs.OrBits[firstBits, w, firstBits, nonterm]; w Ź vertices[top]; top Ź top-1; discrim[w] Ź listindex; ENDLOOP; vertices[listindex] Ź nonterm } }; discrim Ź NPGSConDefs.MakeAttrVec[NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1]; vertices Ź NPGSConDefs.MakeAttrVec[NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1]; listindex Ź NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1; top Ź 0; -- initialise stack and list of heads FOR i IN [1..NPGSConDefs.totalTokens-NPGSConDefs.eofMark] DO IF discrim[i] = 0 THEN First[i] ENDLOOP; FOR i IN [1..NPGSConDefs.totalTokens-NPGSConDefs.eofMark] DO -- copy head bitStrings to other scc vertices IF i # vertices[discrim[i]] THEN NPGSConDefs.OrBits[firstBits, vertices[discrim[i]], firstBits, i]; ENDLOOP; discrim Ź NIL; vertices Ź NIL; IF NPGSConDefs.flags[first] THEN { NPGSConDefs.setoutstream[".first"]; NPGSConDefs.outstring["\nFIRST SETS\n\n"]; FOR i IN [1..NPGSConDefs.totalTokens-NPGSConDefs.eofMark] DO [] Ź NPGSConDefs.OutToken[i+NPGSConDefs.eofMark]; lineWidth Ź NPGSConDefs.outbufLim; FOR j IN [1..NPGSConDefs.eofMark] DO IF NPGSConDefs.FindBit[firstBits,i,j] THEN { IF (lineWidth Ź lineWidth+NPGSConDefs.tokenSize+1) > NPGSConDefs.outbufLim THEN { NPGSConDefs.outeol[1]; NPGSConDefs.outchar[' ,4]; lineWidth Ź NPGSConDefs.tokenSize+5 }; NPGSConDefs.outchar[' ,NPGSConDefs.tokenSize+1-NPGSConDefs.OutToken[j]] }; ENDLOOP; NPGSConDefs.outeol[2]; ENDLOOP; NPGSConDefs.closeoutstream[] } }; Find: PROC[state: CARDINAL, item: NPGSTypes.ItemRec] RETURNS[CARDINAL] = { i, r: CARDINAL; r Ź (state + LOOPHOLE[item, CARD16]) 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; <> IF rlim>=bitsInfo.length THEN { bitsInfo Ź NPGSConDefs.ExpandBitsInfo[bitsInfo, bitsInfo.length/8]; bitString Ź NPGSConDefs.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] = { jf: CARDINAL[0..15] Ź 0; pss: CARDINAL[0..NPGSTypes.pssLim] Ź 0; tempItem: NPGSTypes.ItemRec Ź NPGSTypes.nullItemRec; 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 Ź NPGSConDefs.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 Ź NPGSConDefs.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; <> FOR i IN [stateInfo[predState].entries..stateInfo[predState+1].entries) DO IF table[i] = [3,0,NPGSConDefs.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 { temp: CARDINAL Ź table[i].pss; k Ź stateInfo[temp+1].nucleus; i Ź stateInfo[temp].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..NPGSConDefs.prodInfo[table[i].pss].count) DO --all v s.t. k+2<=v<= n[q] IF (symbol Ź NPGSConDefs.rhsChar[NPGSConDefs.prodInfo[table[i].pss].index+k]) <= NPGSConDefs.eofMark THEN { <> NPGSConDefs.InsertBit[bitString, index, symbol]; EXIT } ELSE { symbol Ź symbol-NPGSConDefs.eofMark; NPGSConDefs.OrBits[firstBits, symbol, bitString, index]; IF ~NPGSConDefs.tokenInfo[symbol].empty THEN EXIT }; <> REPEAT FINISHED => { jf Ź table[i].jf; jf Ź jf-1; pss Ź table[i].pss; tempItem Ź [0, jf, pss]; k Ź Find[predState, tempItem]; IF k = 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 NPGSConDefs.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 NPGSConDefs.OrBits[bitString, i, bitString, index]; i Ź stack[top]; bitsInfo[i].status Ź CARDINAL.LAST; ENDLOOP; FOR k IN [top+2..k] DO NPGSConDefs.OrBits[bitString, index, bitString, stack[k]]; ENDLOOP }; }; }.