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;
make arrays with all entries zeroed
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;
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 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];
now form inverse of shift transitions for the lookahead sets caculation
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;
LALR(1) calculation begins here
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
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[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;
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]
};
bitString[k] points at the LALR(1) lookahead for this reduce
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];
grab entries for tabgen here
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;
procedures called by ProcessState
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;
a new state
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[];
insert new nucleus
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[]
}
};
end of local procedures
k1 ← stateInfo[six].nucleus;
IF (k1-stateInfo[six+1].nucleus)*2 > stateInfo[NPGSConDefs.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 # 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;
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[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]
}
};
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
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;
jf ← table[entrymark+1].jf;
table[entrymark+1].jf ← jf + 1;
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 # 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[]
}
};
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;
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,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 {
X[q.v]<=eofMark
NPGSConDefs.InsertBit[bitString, index, symbol]; EXIT
}
ELSE {
symbol ← symbol-NPGSConDefs.eofMark;
NPGSConDefs.OrBits[firstBits, symbol, bitString, index];
IF ~NPGSConDefs.tokenInfo[symbol].empty THEN EXIT
};
now the core of the transitive closure algorithm
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
};
};