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