<<>> <> <> <> <> <> <> <> <<>> 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 }; }; }.