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

}.

P
NPGSLALR.mesa
Copyright Σ 1985, 1988, 1992 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
Κ—–
"cedarcode" style•NewlineDelimiter

™š
œ
™
Jšœ
Οe
œ=™HJš
œ/™/Jš
œ!™!Jš
œ%™%Jš
œ1™1Jš
œ$™$J™—
codeš
Οk	˜	Kš
œ˜Kš
œ
˜
—K˜šžœžœ
ž˜Kšžœ
˜šžœ˜K˜—K˜K˜K˜K˜Kšœžœ
˜Kšœ
žœ
˜Kšœ
žœΟc˜'KšœžœŸJ˜YK˜!K˜Jš
œ*™*KšœžœŸ@˜UKšœžœŸ8˜UK˜K˜K˜K˜!K˜K˜K˜K˜šΟnœžœ
žœžœžœ
žœ˜3Kšœ>žœ
˜GKšœ(žœ
˜1Kšœ'žœ
˜,K˜K˜š œžœ˜Kšœžœ
˜K˜š	žœžœ
ž
œ
žœ4ž˜SK˜šžœžœ˜K˜ZKšžœžœ{˜†
K˜—Kšžœ%žœV˜
K˜gKšžœ
˜—K˜K˜—K˜š 
œžœ
˜Kšœ"žœžœ˜>Kšœžœ	žœ
˜šžœžœ˜K˜eK˜
—šžœ˜Kšœžœžœ˜*šžœ
žœ˜Kšœ	žœžœ$žœ˜IK˜@K˜—K˜.Kšžœ#žœ>˜gK˜†
K˜
—K˜—K˜š 
œžœ˜Kšœžœ
˜K˜,Kšœžœ˜=š
ž˜Kšžœžœ"˜:šžœ˜Kš
žœžœžœ
žœ
žœ
˜8Kš
žœžœ
žœžœ$žœ
˜HK˜K˜—Kš
ž˜—K˜—K˜š 
œžœ˜šžœžœ˜KšœžœJ˜\K˜—Kšžœžœžœ˜IK˜—K˜Kšœžœ˜,Jš
œ#™#K˜AK˜;Kšœžœžœ˜-Kšœ\Ÿ
˜iKšœ_Ÿ˜nK˜GJš
œS™SJš
œ<™<Jš
œC™CK˜AKšžœžœL˜nšžœžœž˜2K˜4KšžœžœŸ&˜Wšžœžœ4ž˜>šžœž˜K˜!K˜#Kšžœ
˜—Kš
ž˜—Kšžœ
˜—Kšžœžœ˜9K˜Kš
žœžœžœ
žœ
žœ˜RK˜Jš
œG™GK˜5Kšžœžœžœžœ
˜DK˜šžœžœž˜#šžœžœ4ž˜>šžœžœŸ&˜AK˜LK˜)K˜—Kšžœ
˜—Kšžœ
˜—K˜Jš
œ™K˜_K˜oK˜/KšœžœŸ˜#K˜GK˜WK˜+K˜'K˜=Kšœžœ
˜K˜>Kšžœžœ˜>K˜šžœžœž˜#Kšžœžœžœžœ
˜HK˜šžœž˜%Jš
œ6™6šžœž˜˜Kšœžœ
˜K˜0K˜VK˜-K˜—˜Kšœžœ
˜K˜K˜VK˜-K˜—K˜
K˜gKšžœ
˜—Kšžœ
˜—K˜Jš
œA™AKšœžœ"˜6šžœžœ4žœžœ
˜Všžœ5žœ˜=K˜K˜—Jš
œ<™<Kšœ
žœ˜#šžœžœž˜$šžœ$žœ˜,šžœžœ˜ K˜bK˜
—šžœŸ˜K˜
šžœ
žœ˜Kšœ
žœ,˜=K˜jK˜=K˜—šžœIžœ˜QK˜VK˜—K˜Fšžœžœ˜Kšœ?ž˜CK˜
—šžœ˜KšœSžœ
˜YšžœžœŸ˜<Kšœžœ˜?K˜
—K˜
—K˜
—K˜—Kšžœ
˜—Kšžœžœ˜)šžœžœ˜$K˜6K˜—Kšžœ
˜—K˜Kšžœžœ˜2šžœžœ˜"K˜mK˜7K˜—K˜K˜K˜š
œ˜Kš
œ*˜*K˜'Kš
œg˜gK˜—K˜K˜šžœžœž˜(šžœžœ˜ K˜'Jš
œ™šžœžœ˜"K˜Kšœžœžœžœ3˜`K˜—šžœžœžœ˜6Kšžœžœ&˜:Kšžœ˜K˜—Kš
œE˜EK˜—Kšžœ
˜Kš
œL˜L—Kšžœ
˜—K˜K˜JK˜OK˜[K˜_K˜[K˜bK˜WK˜K˜Kšœžœžœ
˜"Kšœžœžœ
˜Kšœžœžœ
˜ Kšœžœ
˜Kšœžœžœ
˜Kšœžœžœ
˜7Kšœžœ
˜Kšžœ
˜K˜—K˜š œžœ˜KšœžœŸ˜9Kšœ	žœ
˜Kšœžœ
˜K˜Jš
œ!™!K˜š œžœžœ˜Kšœžœ#žœ
˜8K˜š
 œžœ
žœ
žœžœ˜&šžœ#ž˜+Kšœ#žœ"˜H—K˜—K˜šžœžœž˜,Kšœ	žœ
˜šžœžœž˜#Kšžœ"žœ!žœ˜Ušžœ˜K˜>K˜BKšœ	ž˜K˜—Kšžœ
˜—Kšžœžœ
žœ
˜Kš
ž˜—K˜—K˜š œžœ˜K˜Nšžœžœ
žœž˜#Kšœžœ
˜—šžœžœ
žœ5ž˜IKšœ%žœ
˜-—šžœžœ
žœž˜+Kšœ?žœ
˜G—K˜K˜—K˜š
 œžœžœžœ
žœ˜;Kšœžœ
˜Kšžœžœ
žœŸ ˜LKš	œ
žœžœžœžœ
˜Ašžœ$žœž˜5Kšžœ5žœ˜=K˜šžœž
œ
žœ0ž˜EKšžœžœ
žœ
˜*Kšžœ
žœžœ˜Kš
ž˜—K˜Kšžœ
˜—Jš
œ™KšžœžœP˜gKšžœ'ž˜-K˜IKšžœ4žœ˜IJš
œ™K˜(Kšžœžœžœžœ
˜MK˜Ošžœ*žœ
žœžœ˜RK˜K˜VKšžœ˜K˜
—K˜—K˜Jš
œ™K˜K˜KšžœRž˜XK˜Jš
œ™šžœž
œ
žœ ž˜6Kšœ5žœ
˜=—K˜Jš
œ™K˜šžœ#žœ
ž˜:K˜=šžœ#žœŸ˜:K˜PšžœžœŸ˜5K˜Išžœžœž˜&šžœžœ
ž˜-Kšžœžœ
ž˜"šžœ
žœ˜Kšžœ2žœ˜GK˜2K˜—Kšžœ
˜—Kš
ž˜—K˜
—K˜—Kšžœ
˜—K˜K˜šžœžœŸ˜5K˜Kšžœžœ&žœžœ
˜Ršžœžœ˜KšœŸ˜)šžœž˜K˜šžœžœ˜'Kšœ9Ÿ˜TKšœžœžœžœ
˜@Jš
œ2™2K˜KšœŸ?˜JJš
œ$™$šžœžœž˜*Kšžœžœ˜Kšžœ2žœ˜GK˜;K˜K˜Kš
ž˜—K˜—K˜
Kšžœ
˜—K˜K˜
—K˜—K˜Jš
œ™K˜!šžœžœž˜,KšœAžœ
˜I—K˜Jš
œ#™#K˜šžœž˜Kšœžœ˜K˜šžœžœ&ž˜?K˜K˜˜
Kšžœ
˜——K˜K˜Jš
œ0™0KšœŸ%˜7KšžœžœLž˜Yšœ5Ÿ
˜BKšžœŸ˜4—šžœ,žœŸ˜EKšžœžœ˜K˜1K˜—Kšœ+Ÿ˜HK˜Kšžœ
˜—K˜
KšœŸE˜H—K˜š œžœ˜Kšœžœ
˜K˜%K˜K˜K˜š œžœ
žœ˜"Kšœžœ
˜K˜8K˜#šžœžœž˜)K˜šžœžœž˜)K˜Kšžœžœ0žœ˜VKšœžœžœ
˜;šžœžœžœ˜NKšžœI˜M—Kšžœ!žœ
žœ
˜-Kšžœ
˜—Kšžœ
˜—šžœ&žœ˜.K˜K˜7šžœ
ž˜K˜5K˜7Kšžœ
˜—K˜K˜
—K˜—K˜K˜QK˜RKšœDŸ%˜iKšžœžœ2žœ
žœžœ
žœ
˜ešžœžœ2žœŸ-˜kKšžœž˜ K˜BKšžœ
˜—Kšœ
žœ
žœ
˜šžœžœ˜"K˜Nšžœžœ2ž˜<K˜Tšžœžœž˜$šžœ$žœ˜,šžœIžœ˜QK˜UK˜—K˜GK˜—Kšžœ
˜—K˜Kšžœ
˜—K˜K˜
—K˜—K˜š
 œžœžœžœ
žœ˜JKšœžœ
˜Kš	œ
žœžœžœžœ˜Kšžœž˜Kšžœžœžœ
žœ˜HK˜Kšžœ
˜—Jš
œ™šžœžœ˜K˜CK˜GK˜—Kšžœžœ#˜:K˜K˜9Kšžœ˜
K˜—K˜š œžœžœ˜(Kšœžœ˜Kšœžœ˜'K˜4KšœžœŸ1˜BKšœžœŸG˜TKšœžœŸE˜RK˜Kšžœžœ,˜FKšœ2Ÿ$˜VKšœŸ!˜>Kšžœžœžœ6˜`KšœEŸ˜Wšžœ
Ÿ!˜$šžœžœ˜
Kšœ#Ÿ˜8K˜KšœŸ$˜'—Kš
ž˜š
ž˜šžœžœ˜!Kšžœžœ
žœ˜ KšœŸ˜—šžœ˜K˜BKšžœžœ
žœ
˜K˜:K˜—Kšžœ
˜—Jš
œ0™0šžœžœ@ž˜JKšžœEžœ
žœ
˜QKšžœ
žœžœŸ˜2Kšžœ
˜—Kšœ	Ÿ˜%šžœžœ	žœ˜'Kšœžœ˜K˜K˜K˜—š	žœž
œ
žœžœ
Ÿ*˜Hšžœžœ9žœ
Ÿ˜^šžœcžœ˜kJš
œ™Kšœ1ž˜5K˜
—šžœ˜K˜$K˜8Kšžœ&žœ
ž˜1K˜—Jš
œ0™0šžœ
žœ˜K˜K˜
K˜K˜K˜šžœ
žœ˜K˜K˜K˜—Kšžœž˜!šœžœ,˜HKšžœ3˜7—K˜—Kšžœ
˜—Kšžœ
˜—Kšžœ	ž˜Kšžœ
˜—šžœ'žœŸ
˜:Kšœ.žœ
žœ
˜<šžœžœ	ž˜'K˜3Kšœ%žœ
žœ
˜3Kšžœ
˜—šžœžœž˜K˜:Kš
ž˜—K˜—K˜—K˜K˜—K˜—…—QjjQ