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[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; NPGSConDefs.seterrstream[]; NPGSConDefs.outstring["\nLALR(1) Tables\n"];
};
IF ~conflictFlag THEN {conflictFlag _ TRUE; lineWidth _ 0; PrintHeader[]}
};

lalrSuccess _ TRUE; NPGSConDefs.orCount _ 0;
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<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: 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<index+n DO table[r] _ table[i]; r _ r-1 ENDLOOP;
NPGSConDefs.sLim _ NPGSConDefs.sLim+1; stateInfo[NPGSConDefs.sLim].nucleus _ r;
IF NPGSConDefs.sLim <= NPGSConDefs.pssLim+1 THEN RETURN[NPGSConDefs.sLim-1] ELSE {
NPGSConDefs.seterrstream[];
NPGSConDefs.outstring["\n\nERROR - Internal field will overflow - increase PSSLIM\n"];
ERROR NPGSConDefs.NPGSFail[]
}
};


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 k2<entryLim DO
p _ table[k2+1].pss; j _ table[k2+1].jf; table[k2] _ [0,0,0];
IF j # NPGSConDefs.prodInfo[p].count THEN { --not a reduce
sym _ NPGSConDefs.rhsChar[NPGSConDefs.prodInfo[p].index+j]; table[k2].pss _ sym;
IF sym>NPGSConDefs.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<entryLim DO
IF table[k1+1] = [0,0,p] THEN EXIT
REPEAT FINISHED => {
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
};
};

}.

J
NPGSLALR.mesa
Copyright Ó 1985, 1988 by Xerox Corporation.  All rights reserved.
Satterthwaite, October 16, 1985 5:47:23 pm PDT 
Maxwell, August 10, 1983 10:22 am
Wyatt, March 21, 1984 10:28:38 am PST
Russ Atkinson (RRA) March 14, 1988 5:00:54 pm PST
JKF February 6, 1989 11:50:29 am PST

variables of the lookahead set calculation
make arrays with all entries zeroed
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
now form inverse of shift transitions for the lookahead sets caculation
LALR(1) calculation begins here
insert scan and scan reduce entries in conflicts array
compute lookaheads, insert reduce entries and output as necessary
bitString[k] points at the LALR(1) lookahead for this reduce
grab entries for tabgen here
procedures called by ProcessState
a new state
insert new nucleus
end of local procedures
copy nucleus to entries
compute closure
now overwrite chain entry with first chained entry
now append the other chained entries
pack up reduce entries
form new states and pack up entries
table[entrymark+1].jf _ table[entrymark+1].jf+1;
new context
locate the (q,k+1) in each jth predecessor state
X[q.v]<=eofMark
now the core of the transitive closure algorithm
�Ê|•NewlineDelimiter

™Jš
œ
™
Jš
œB™BJš
œ/™/Jš
œ!™!Jš
œ%™%Jš
œ1™1Jš
œ$™$J™š
Ïk	˜	Jš
œ˜Jš
œ
˜
—J˜š�œ�œ
�˜Jš�œ
˜š�œ˜J˜—J˜J˜J˜J˜Jšœ�œ
˜Jšœ
�œ
˜Jšœ
�œÏc˜'Jšœ�œžJ˜YJ˜!J˜Jš
œ*™*Jšœ�œž@˜UJšœ�œž8˜UJ˜J˜J˜J˜!J˜J˜J˜J˜šÏnœ�œ
�œ�œ�œ
�œ˜3Jšœ>�œ
˜GJšœ(�œ
˜1Jšœ'�œ
˜,J˜J˜šŸœ�œ˜Jšœ�œ
˜J˜š	�œ�œ
�
œ
�œ4�˜SJ˜š�œ�œ˜J˜ZJš�œ�œ{˜†
J˜—Jš�œ%�œV˜�
J˜gJš�œ
˜—J˜J˜—J˜šŸ
œ�œ
˜Jšœ"�œ�œ˜>Jšœ�œ	�œ
˜š�œ�œ˜J˜eJ˜
—š�œ˜Jšœ�œ�œ˜*š�œ
�œ˜Jšœ	�œ�œ$�œ˜IJ˜@J˜—J˜.Jš�œ#�œ>˜gJ˜†
J˜
—J˜—J˜šŸ
œ�œ˜Jšœ�œ
˜J˜,Jšœ�œ˜=š
�˜Jš�œ�œ"˜:š�œ˜Jš
�œ�œ�œ
�œ
�œ
˜8Jš
�œ�œ
�œ�œ$�œ
˜HJ˜J˜—Jš
�˜—J˜—J˜šŸ
œ�œ˜š�œ�œ˜Jšœ�œJ˜\J˜—Jš�œ�œ�œ˜IJ˜—J˜Jšœ�œ˜,Jš
œ#™#J˜AJ˜;Jšœ�œ�œ˜-Jšœ\ž
˜iJšœ_ž˜nJ˜GJš
œS™SJš
œ<™<Jš
œC™CJ˜AJš�œ�œL˜nš�œ�œ�˜2J˜4Jš�œ�œž&˜Wš�œ�œ4�˜>š�œ�˜J˜!J˜#Jš�œ
˜—Jš
�˜—Jš�œ
˜—Jš�œ�œ˜9J˜Jš
�œ�œ�œ
�œ
�œ˜RJ˜Jš
œG™GJ˜5Jš�œ�œ�œ�œ
˜DJ˜š�œ�œ�˜#š�œ�œ4�˜>š�œ�œž&˜AJ˜LJ˜)J˜—Jš�œ
˜—Jš�œ
˜—J˜Jš
œ™J˜_J˜oJ˜/Jšœ�œž˜#J˜GJ˜WJ˜+J˜'J˜=Jšœ�œ
˜J˜>Jš�œ�œ˜>J˜š�œ�œ�˜#Jš�œ�œ�œ�œ
˜HJ˜š�œ�˜%Jš
œ6™6š�œ�˜˜Jšœ�œ
˜J˜0J˜VJ˜-J˜—˜Jšœ�œ
˜J˜J˜VJ˜-J˜—J˜
J˜gJš�œ
˜—Jš�œ
˜—J˜Jš
œA™AJšœ�œ"˜6š�œ�œ4�œ�œ
˜Vš�œ5�œ˜=J˜J˜—Jš
œ<™<Jšœ
�œ˜#š�œ�œ�˜$š�œ$�œ˜,š�œ�œ˜ J˜bJ˜
—š�œž˜J˜
š�œ
�œ˜Jšœ
�œ,˜=J˜jJ˜=J˜—š�œI�œ˜QJ˜VJ˜—J˜Fš�œ�œ˜Jšœ?�˜CJ˜
—š�œ˜JšœS�œ
˜Yš�œ�œž˜<Jšœ�œ˜?J˜
—J˜
—J˜
—J˜—Jš�œ
˜—Jš�œ�œ˜)š�œ�œ˜$J˜6J˜—Jš�œ
˜—J˜Jš�œ�œ˜2š�œ�œ˜"J˜mJ˜7J˜—J˜J˜J˜š
œ˜Jš
œ*˜*Jš
œ'˜'Jš
œg˜gJ˜—J˜J˜š�œ�œ�˜(š�œ�œ˜ J˜'Jš
œ™š�œ�œ˜"J˜Jšœ�œ�œ�œ3˜`J˜—š�œ�œ�œ˜6Jš�œ�œ&˜:Jš�œ˜J˜—Jš
œE˜EJ˜—Jš�œ
˜Jš
œL˜L—Jš�œ
˜—J˜J˜JJ˜OJ˜[J˜_J˜[J˜bJ˜WJ˜J˜Jšœ�œ�œ
˜"Jšœ�œ�œ
˜Jšœ�œ�œ
˜ Jšœ�œ
˜Jšœ�œ�œ
˜Jšœ�œ�œ
˜7Jšœ�œ
˜Jš�œ
˜J˜—J˜šŸœ�œ˜Jšœ�œž˜9Jšœ	�œ
˜Jšœ�œ
˜J˜Jš
œ!™!J˜šŸœ�œ�œ˜Jšœ�œ#�œ
˜8J˜š
Ÿœ�œ
�œ
�œ�œ˜&š�œ#�˜+Jšœ#�œ"˜H—J˜—J˜š�œ�œ�˜,Jšœ	�œ
˜š�œ�œ�˜#Jš�œ"�œ!�œ˜Uš�œ˜J˜>J˜BJšœ	�˜J˜—Jš�œ
˜—Jš�œ�œ
�œ
˜Jš
�˜—J˜—J˜šŸœ�œ˜J˜Nš�œ�œ
�œ�˜#Jšœ�œ
˜—š�œ�œ
�œ5�˜IJšœ%�œ
˜-—š�œ�œ
�œ�˜+Jšœ?�œ
˜G—J˜J˜—J˜š
Ÿœ�œ�œ�œ
�œ˜;Jšœ�œ
˜Jš�œ�œ
�œž ˜LJš	œ
�œ�œ�œ�œ
˜Aš�œ$�œ�˜5Jš�œ5�œ˜=J˜š�œ�
œ
�œ0�˜EJš�œ�œ
�œ
˜*Jš�œ
�œ�œ˜Jš
�˜—J˜Jš�œ
˜—Jš
œ™Jš�œ�œP˜gJš�œ'�˜-J˜IJš�œ4�œ˜IJš
œ™J˜(Jš�œ�œ�œ�œ
˜MJ˜Oš�œ*�œ
�œ�œ˜RJ˜J˜VJš�œ˜J˜
—J˜—J˜Jš
œ™J˜J˜Jš�œR�˜XJ˜Jš
œ™š�œ�
œ
�œ �˜6Jšœ5�œ
˜=—J˜Jš
œ™J˜š�œ#�œ
�˜:J˜=š�œ#�œž˜:J˜Pš�œ�œž˜5J˜Iš�œ�œ�˜&š�œ�œ
�˜-Jš�œ�œ
�˜"š�œ
�œ˜Jš�œ2�œ˜GJ˜2J˜—Jš�œ
˜—Jš
�˜—J˜
—J˜—Jš�œ
˜—J˜J˜š�œ�œž˜5J˜Jš�œ�œ&�œ�œ
˜Rš�œ�œ˜Jšœž˜)š�œ�˜J˜š�œ�œ˜'Jšœ9ž˜TJšœ�œ�œ�œ
˜@Jš
œ2™2J˜Jšœž?˜JJš
œ$™$š�œ�œ�˜*Jš�œ�œ˜Jš�œ2�œ˜GJ˜;J˜J˜Jš
�˜—J˜—J˜
Jš�œ
˜—J˜J˜
—J˜—J˜Jš
œ™J˜!š�œ�œ�˜,JšœA�œ
˜I—J˜Jš
œ#™#J˜š�œ�˜Jšœ�œ˜J˜š�œ�œ&�˜?J˜J˜˜
Jš�œ
˜——J˜J˜Jš
œ0™0Jšœž%˜7Jš�œ�œL�˜Yšœ5ž
˜BJš�œž˜4—š�œ,�œž˜EJš�œ�œ˜J˜1J˜—Jšœ+ž˜HJ˜Jš�œ
˜—J˜
JšœžE˜H—J˜šŸœ�œ˜Jšœ�œ
˜J˜%J˜J˜J˜šŸœ�œ
�œ˜"Jšœ�œ
˜J˜8J˜#š�œ�œ�˜)J˜š�œ�œ�˜)J˜Jš�œ�œ0�œ˜VJšœ�œ�œ
˜;š�œ�œ�œ˜NJš�œI˜M—Jš�œ!�œ
�œ
˜-Jš�œ
˜—Jš�œ
˜—š�œ&�œ˜.J˜J˜7š�œ
�˜J˜5J˜7Jš�œ
˜—J˜J˜
—J˜—J˜J˜QJ˜RJšœDž%˜iJš�œ�œ2�œ
�œ�œ
�œ
˜eš�œ�œ2�œž-˜kJš�œ�˜ J˜BJš�œ
˜—Jšœ
�œ
�œ
˜š�œ�œ˜"J˜Nš�œ�œ2�˜<J˜Tš�œ�œ�˜$š�œ$�œ˜,š�œI�œ˜QJ˜UJ˜—J˜GJ˜—Jš�œ
˜—J˜Jš�œ
˜—J˜J˜
—J˜—J˜š
Ÿœ�œ�œ�œ
�œ˜JJšœ�œ
˜Jš	œ
�œ�œ�œ�œ˜Kš�œ�˜Jš�œ�œ�œ
�œ˜HJ˜Jš�œ
˜—Jš
œ™š�œ�œ˜J˜CJ˜GJ˜—Jš�œ�œ#˜:J˜J˜9Jš�œ˜
J˜—J˜šŸœ�œ�œ˜(Jšœ�œ˜Jšœ�œ˜'J˜4Jšœ�œž1˜BJšœ�œžG˜TJšœ�œžE˜RJ˜Jš�œ�œ,˜FJšœ2ž$˜VJšœž!˜>Jš�œ�œ�œ6˜`JšœEž˜Wš�œ
ž!˜$š�œ�œ˜
Jšœ#ž˜8J˜Jšœž$˜'—Jš
�˜š
�˜š�œ�œ˜!Jš�œ�œ
�œ˜ Jšœž˜—š�œ˜J˜BJš�œ�œ
�œ
˜J˜:J˜—Jš�œ
˜—Jš
œ0™0š�œ�œ@�˜JJš�œE�œ
�œ
˜QJš�œ
�œ�œž˜2Jš�œ
˜—Jšœ	ž˜%š�œ�œ	�œ˜'Jšœ�œ˜J˜J˜J˜—š	�œ�
œ
�œ�œ
ž*˜Hš�œ�œ9�œ
ž˜^š�œc�œ˜kJš
œ™Jšœ1�˜5J˜
—š�œ˜J˜$J˜8Jš�œ&�œ
�˜1J˜—Jš
œ0™0š�œ
�œ˜J˜J˜
J˜J˜J˜š�œ
�œ˜J˜J˜J˜—Jš�œ�˜!šœ�œ,˜HJš�œ3˜7—J˜—Jš�œ
˜—Jš�œ
˜—Jš�œ	�˜Jš�œ
˜—š�œ'�œž
˜:Jšœ.�œ
�œ
˜<š�œ�œ	�˜'J˜3Jšœ%�œ
�œ
˜3Jš�œ
˜—š�œ�œ�˜J˜:Jš
�˜—J˜—J˜—J˜J˜—J˜—…—Qjj0