NPGSTab.mesa
Copyright Ó 1985, 1988 by Xerox Corporation. All rights reserved.
Satterthwaite, October 18, 1985 10:24:14 am PDT
Maxwell, August 10, 1983 10:39 am
Wyatt, March 20, 1984 4:48:28 pm PST
Russ Atkinson (RRA) March 28, 1988 5:08:41 pm PST
JKF February 6, 1989 3:44:47 pm PST
DIRECTORY
BasicTime USING [Now],
ConvertUnsafe USING [ToRope],
IO USING [Put, PutChar, PutF, PutF1, PutRope, STREAM],
NPGSConDefs,
NPGSTypes USING [Column, ErrorType, HashTab, HashTabRec, ItemRec, NTab, NTDefaults, nullItemRec, nullProdEntry, ProdEntry, Renumber, StateData, StateDataRec, TTab, VocabIndex],
Rope USING [ROPE];
NPGSTab: CEDAR PROGRAM
IMPORTS BasicTime, ConvertUnsafe, IO, NPGSConDefs
EXPORTS NPGSConDefs = {
ROPE: TYPE = Rope.ROPE;
STREAM: TYPE = IO.STREAM;
linewidth, hashval, lastntstate, vocabspace, nlim, tlim: CARDINAL ← 0;
hashtab: NPGSTypes.HashTab;
ttab: NPGSTypes.TTab;
ntab: NPGSTypes.NTab;
statedata: NPGSTypes.StateData;
ntdefaults: NPGSTypes.NTDefaults;
column: NPGSTypes.Column;
renumber: NPGSTypes.Renumber;
vocabindex: NPGSTypes.VocabIndex;
scantab: REF ScanTabArray ← NIL;
ScanTabArray: TYPE = ARRAY ScanTabIndex OF CARDINAL;
ScanTabIndex: TYPE = [40b..177b];
errMsgStr: ARRAY NPGSTypes.ErrorType OF ROPE = ["MAgg", "MCalled", "MDotLB", "MExpr", "MId", "MOpd", "MOptn", "MRArrow", "MThe", "MTxt", "MTypeId", "MFieldTypeId", "CloseIconExpr", "CopyIconExpr", "MoveIconExpr", "SelectIconExpr", "IconExpr", "Stmt", "MSecs", "tl"];
WordPtr: TYPE = LONG POINTER TO WORD;
splitTrigger: NAT ← 500;
OutString: PROC [s: LONG STRING] = {
NPGSConDefs.outstring[ConvertUnsafe.ToRope[s]];
};
TabGen: PUBLIC PROC [cedar: BOOL, cusp: BOOL] RETURNS [success: BOOLTRUE] = {
Error: PROC [sel: CARDINAL] = {
OutString["\nFAIL - "];
OutString[SELECT sel FROM
1 => "more than 255 terminal symbols",
2 => "more than 254 nonterminal symbols",
3 => "more than 2047 states or productions",
4 => "more than 15 symbols in a production right part",
ENDCASE => "NPGS error"];
NPGSConDefs.outeol[1]; success ← FALSE;
};
PrefixItem: PROC [init: CARDINAL, nItems: CARDINAL] = {
IO.PutF1[st, " i: CARDINAL ← %d;\n", [cardinal[init]] ];
IO.PutRope[st, " dup: PROC = {tab[i] ← tab[i-1]; i ← i + 1};\n"];
IO.PutRope[st, " app0: PROC [transition: CARDINAL] = {\n"];
IO.PutRope[st, " tab[i] ← [[FALSE, 0], transition];\n"];
IO.PutRope[st, " i ← i + 1;\n"];
IO.PutRope[st, " };\n"];
IO.PutRope[st, " app1: PROC [pLength: CARDINAL, transition: CARDINAL] = {\n"];
IO.PutRope[st, " tab[i] ← [[FALSE, pLength], transition];\n"];
IO.PutRope[st, " i ← i + 1;\n"];
IO.PutRope[st, " };\n"];
IO.PutRope[st, " app1t: PROC [transition: CARDINAL] = {\n"];
IO.PutRope[st, " tab[i] ← [[FALSE, 1], transition];\n"];
IO.PutRope[st, " i ← i + 1;\n"];
IO.PutRope[st, " };\n"];
IO.PutRope[st, " app2: PROC [pLength: CARDINAL, transition: CARDINAL] = {\n"];
IO.PutRope[st, " tab[i] ← [[TRUE, pLength], transition];\n"];
IO.PutRope[st, " i ← i + 1;\n"];
IO.PutRope[st, " };\n"];
lagItem ← NPGSTypes.nullItemRec;
needSplits ← nItems >= splitTrigger;
splitNum ← 0;
};
PutItem: PROC [i: CARDINAL, item: NPGSTypes.ItemRec, first: CARDINAL] = {
IF (i MOD 5) = 0 OR i = first THEN {
IF needSplits THEN
IF i = first OR sinceSplit >= splitTrigger THEN {
IF splitNum # 0 THEN IO.PutRope[st, "\n };"];
IO.PutF1[st, "\n split%d: PROC = {", [cardinal[splitNum]]];
sinceSplit ← 0;
splitNum ← splitNum + 1;
};
IO.PutRope[st, "\n"];
};
IF needSplits THEN IO.PutRope[st, " "] ELSE IO.PutRope[st, " "];
IF (i MOD 20) = 0 THEN {
IO.PutF1[st, "-- %d\n", [cardinal[i]] ];
IF needSplits THEN IO.PutRope[st, " "] ELSE IO.PutRope[st, " "];
};
SELECT TRUE FROM
item = NPGSTypes.nullItemRec => IO.PutRope[st, "i ← i + 1;"];
item = lagItem => IO.PutRope[st, "dup[];"];
ENDCASE =>
SELECT item.tag FROM
0 =>
IO.PutF1[st, "app0[%d];", [cardinal[item.pss]] ];
1 =>
IF item.jf = 1
THEN IO.PutF1[st, "app1t[%d];", [cardinal[item.pss]] ]
ELSE IO.PutF[st, "app1[%d, %d];", [cardinal[item.jf]], [cardinal[item.pss]] ];
2 =>
IO.PutF[st, "app2[%d, %d];", [cardinal[item.jf]], [cardinal[item.pss]] ];
ENDCASE => ERROR;
lagItem ← item;
sinceSplit ← sinceSplit + 1;
};
PostfixItem: PROC = {
IF needSplits THEN {
IO.PutRope[st, "\n };"];
FOR i: NAT IN [0..splitNum) DO
IO.PutF1[st, "\n split%d[];", [cardinal[i]]];
ENDLOOP;
};
IO.PutRope[st, "\n RETURN [tab];\n };\n"];
};
PutProc: PROC [type: ROPE] = {
IO.PutRope[st, "\nInit"];
IO.PutRope[st, type];
IF cedar
THEN IO.PutRope[st, ": PUBLIC PROC RETURNS ["]
ELSE IO.PutRope[st, ": PUBLIC PROC [uz: UNCOUNTED ZONE] RETURNS ["];
IO.PutRope[st, type];
IO.PutRope[st, "Ref] = {\n"];
};
PutAlloc: PROC [type: ROPE, cons: BOOLFALSE, count: CARDINAL ← 0, all: ROPENIL] = {
IO.PutF[st, " tab: %gRef ← %gNEW[%g", [rope[type]], [rope[zone]], [rope[type]] ];
IF cons THEN {
IO.PutRope[st, " ← [\n"];
IF count # 0 THEN IO.PutF1[st, " -- %d entries\n", [cardinal[count]] ];
RETURN;
};
IF all = NIL
THEN {
IF count # 0 THEN IO.PutF1[st, "[%d]", [cardinal[count]] ];
IO.PutRope[st, "];\n"];
}
ELSE {
IO.PutF1[st, " ← ALL[%g]];\n", [rope[all]] ];
IF count # 0 THEN IO.PutF1[st, " -- %d entries\n", [cardinal[count]] ];
};
};
PutRtn: PROC [cons: BOOLTRUE] = {
IF cons THEN IO.PutRope[st, "]];\n"];
IO.PutRope[st, " RETURN [tab];\n };\n"];
};
PutWord: PROC [i: CARDINAL, w: WORD] = {
IF i # 0 THEN IO.PutChar[st, ',];
IF (i MOD 10) = 0 THEN IO.PutF1[st, "\n -- %d\n ", [cardinal[i]]]
ELSE IO.PutChar[st, ' ];
IO.Put[st, [cardinal[w]]];
};
PutErrorMsg: PROC [i: CARDINAL, e: NPGSTypes.ErrorType] = {
IF i # 0 THEN IO.PutChar[st, ',];
IF (i MOD 10) = 0 THEN IO.PutF1[st, "\n -- %d\n ", [cardinal[i]]]
ELSE IO.PutChar[st, ' ];
IO.PutRope[st, errMsgStr[e]];
};
st: IO.STREAM;
defaultLim: CARDINAL;
lagItem: NPGSTypes.ItemRec;
needSplits: BOOLFALSE;
sinceSplit: CARDINAL ← 0;
splitNum: CARDINAL ← 0;
zone: ROPEIF cedar THEN NIL ELSE "uz.";
IF NPGSConDefs.eofMark > 255 THEN Error[1];
defaultLim ← NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1;
IF defaultLim > 255 THEN Error[2];
IF NPGSConDefs.pssLim > 2047 THEN Error[3];
IF NPGSConDefs.rhsLim > 15 THEN Error[4];
IF ~success THEN RETURN [success];
ntab ← NPGSConDefs.MakeTab[NPGSConDefs.ntEntries];
ttab ← NPGSConDefs.MakeTab[NPGSConDefs.tEntries];
statedata ← NPGSConDefs.MakeStateData[NPGSConDefs.sLim];
ntdefaults ← NPGSConDefs.MakeNTDefaults[defaultLim+1];
column ← NPGSConDefs.MakeColumn[NPGSConDefs.ntEntries+1];
TableSetup[]; NPGSConDefs.closewordstream[]; SquashNTab[];
OutString["\nParse Table Data\n"];
IF NPGSConDefs.flags[printLALR] THEN {PrintNDef[]; TableOverlays[]};
vocabindex ← NPGSConDefs.MakeVocabIndex[NPGSConDefs.eofMark+1];
hashval ← 3*NPGSConDefs.eofMark/2;
hashval ← MIN[251, IF hashval MOD 2 = 0 THEN hashval+1 ELSE hashval];
hashtab ← NPGSConDefs.MakeHashTab[hashval+1];
HashTabSetup[];
start output file
NPGSConDefs.openwordstream[scratch: FALSE];
Output header of the implementation file
st ← NPGSConDefs.tabStream;
IO.PutF1[st, "-- %gImpl.mesa\n", [rope[NPGSConDefs.typeName]] ];
IO.PutF[st, " -- an NPGS production from %g, %g.\n\n",
[rope[NPGSConDefs.sourceName]], [time[BasicTime.Now[]]] ];
IO.PutF1[st, "DIRECTORY %g;\n\n", [rope[NPGSConDefs.typeName]] ];
IO.PutF1[st, "%gImpl: ", [rope[NPGSConDefs.typeName]]];
IF cedar THEN IO.PutF1[st, "CEDAR "];
IO.PutF1[st, "PROGRAM\n EXPORTS %g\n", [rope[NPGSConDefs.typeName]] ];
IO.PutF1[st, " = { OPEN %g;\n", [rope[NPGSConDefs.typeName]] ];
StatePartition[]; -- compute lastntstate
PutProc["ScanTable"];
PutAlloc[type: "ScanTable", count: ScanTabIndex.LAST-ScanTabIndex.FIRST-1, all: "0"];
FOR i: ScanTabIndex IN ScanTabIndex DO
w: WORD ← scantab[i];
IF w # 0 THEN IO.PutF[st, " tab[%bC] ← %d;\n", [cardinal[i]], [cardinal[w]]];
ENDLOOP;
PutRtn[FALSE];
PutProc["HashTable"];
IO.PutRope[st, " null: VocabHashEntry = [0, 0];\n"];
PutAlloc[type: "HashTable", count: hashval+1, all: "null"];
FOR i: CARDINAL IN [0..hashval] DO
w: NPGSTypes.HashTabRec ← hashtab[i];
IF w # [0, 0] THEN
IO.PutF[st, " tab[%d] ← [%d, %d];\n",
[cardinal[i]], [cardinal[w.symPtr]], [cardinal[w.link]]];
ENDLOOP;
PutRtn[FALSE];
PutProc["IndexTable"];
PutAlloc[type: "IndexTable", cons: TRUE, count: NPGSConDefs.eofMark+1];
IO.PutF1[st, " %d", [cardinal[vocabindex[0]]]];
FOR i: CARDINAL IN [1..NPGSConDefs.eofMark] DO
w: WORD ← vocabindex[i];
PutWord[i, w];
ENDLOOP;
PutRtn[];
PutProc["Vocabulary"];
IO.PutRope[st, " i: CARDINAL ← 0;\n"];
IF cedar
THEN IO.PutRope[st, " appText: PROC [r: REF TEXT] = {\n"]
ELSE IO.PutRope[st, " appText: PROC [r: STRING] = {\n"];
IO.PutRope[st, " FOR k: NAT IN [0..r.length) DO tab[i+k] ← r[k]; ENDLOOP;\n"];
IO.PutRope[st, " i ← i + r.length;\n"];
IO.PutRope[st, " };\n"];
PutAlloc[type: "Vocabulary", count: vocabspace];
IO.PutF1[st, " -- %d chars\n", [cardinal[vocabspace]]];
FOR i: CARDINAL IN [0..vocabspace) DO
c: CHAR ← NPGSConDefs.symTab[i];
IF (i MOD 50) = 0 THEN {
IF i # 0 THEN IO.PutRope[st, "\"];\n"];
IO.PutF1[st, " -- %d\n", [cardinal[i]]];
IO.PutRope[st, " appText[\""];
};
SELECT c FROM
< 10C => IO.PutF1[st, "\\00%b", [cardinal[c.ORD]]];
< 40C => IO.PutF1[st, "\\0%b", [cardinal[c.ORD]]];
< 177C => IO.PutChar[st, c];
ENDCASE => IO.PutF1[st, "\\%b", [cardinal[c.ORD]]];
ENDLOOP;
IO.PutRope[st, "\"];\n tab.length ← i;\n"];
PutRtn[FALSE];
hashtab ← NIL;
vocabindex ← NIL;
NPGSConDefs.symInfo ← NIL;
renumber ← NPGSConDefs.MakeRenumber[NPGSConDefs.sLim];
StateRenumber[cusp];
PutProc["ProdData"];
IO.PutRope[st, " i: CARDINAL ← 1;\n"];
IO.PutRope[st, " lag: ProductionInfo ← [0, 0];\n"];
IO.PutRope[st, " dup: PROC = {tab[i] ← lag; i ← i + 1};\n"];
IO.PutRope[st, " appR: PROC [r: CARDINAL] = {lag.rule ← r; tab[i] ← lag; i ← i + 1};\n"];
IO.PutRope[st, " appL: PROC [lhs: CARDINAL] = {lag.lhs ← lhs; tab[i] ← lag; i ← i + 1};\n"];
IO.PutRope[st, " appRL: PROC [r, lhs: CARDINAL] = {tab[i] ← lag ← [r, lhs]; i ← i + 1};\n"];
PutAlloc[type: "ProdData", count: NPGSConDefs.numProd+1, all: "lag"];
IO.PutRope[st, " "];
{
lag: NPGSTypes.ProdEntry ← NPGSTypes.nullProdEntry;
FOR i: CARDINAL IN [1..NPGSConDefs.numProd] DO
w: NPGSTypes.ProdEntry = NPGSConDefs.prodInfo[i];
wr: CARDINAL ← w.rule;
wl: CARDINAL ← w.lhs-NPGSConDefs.eofMark+1;
IF i MOD 5 = 0 THEN
IO.PutF1[st, "\n -- %d\n ", [cardinal[i]] ];
SELECT TRUE FROM
lag.rule # w.rule AND lag.lhs # w.lhs =>
IO.PutF[st, " appRL[%d, %d];", [cardinal[wr]], [cardinal[wl]] ];
lag.rule # w.rule =>
IO.PutF1[st, " appR[%d];", [cardinal[wr]] ];
lag.lhs # w.lhs =>
IO.PutF1[st, " appL[%d];", [cardinal[wl]] ];
ENDCASE =>
IO.PutRope[st, " dup[];"];
lag ← w;
ENDLOOP;
};
PutRtn[FALSE];
PutProc["NStarts"];
PutAlloc[type: "NStarts", cons: TRUE, count: lastntstate+1];
IO.PutF1[st, " %d", [cardinal[0]]];
FOR i: CARDINAL IN [1..lastntstate] DO
w: WORD = statedata[i].ntIndex;
PutWord[i, w];
ENDLOOP;
PutRtn[];
PutProc["NLengths"];
PutAlloc[type: "NLengths", cons: TRUE, count: lastntstate+1];
IO.PutF1[st, " %d", [cardinal[0]] ];
FOR i: CARDINAL IN [1..lastntstate] DO
w: WORD = statedata[i].ntLink;
PutWord[i, w];
ENDLOOP;
PutRtn[];
PutProc["NSymbols"];
PutAlloc[type: "NSymbols", cons: TRUE, count: nlim];
IO.PutF1[st, " %d", [cardinal[ntab[0].symbol]]];
FOR i: CARDINAL IN [1..nlim) DO
w: WORD ← ntab[i].symbol;
PutWord[i, w];
ENDLOOP;
PutRtn[];
PutProc["NActions"];
PrefixItem[0, nlim];
IO.PutRope[st, " null: ActionEntry ← [[FALSE, 0], 0];\n"];
PutAlloc[type: "NActions", count: nlim, all: "null"];
FOR i: CARDINAL IN [0..nlim) DO
PutItem[i, ntab[i].item, 0];
ENDLOOP;
PostfixItem[];
PutProc["NTDefaults"];
PrefixItem[2, defaultLim+1];
IO.PutRope[st, " null: ActionEntry ← [[FALSE, 0], 0];\n"];
PutAlloc[type: "NTDefaults", count: defaultLim+1, all: "null"];
<<IO.PutF1[st, " -- %d entries", [cardinal[defaultLim+1]]];>>
FOR i: CARDINAL IN [2..defaultLim] DO
PutItem[i, ntdefaults[i].item, 2];
ENDLOOP;
PostfixItem[];
PutProc["TStarts"];
PutAlloc[type: "TStarts", cons: TRUE, count: NPGSConDefs.sLim];
IO.PutRope[st, " 0"];
FOR i: CARDINAL IN [1..NPGSConDefs.sLim) DO
w: WORD ← statedata[i].tIndex;
PutWord[i, w];
ENDLOOP;
PutRtn[];
PutProc["TLengths"];
PutAlloc[type: "TLengths", cons: TRUE, count: NPGSConDefs.sLim];
IO.PutRope[st, " 0"];
FOR i: CARDINAL IN [1..NPGSConDefs.sLim) DO
w: WORD ← statedata[i].tLink;
PutWord[i, w];
ENDLOOP;
PutRtn[];
-- new for CUSP
IF cusp THEN {
PutProc["ErrorMsgs"];
PutAlloc[type: "ErrorMsgs", cons: TRUE, count: NPGSConDefs.sLim];
IO.PutRope[st, " tl"];
FOR i: CARDINAL IN [1..NPGSConDefs.sLim) DO
e: NPGSTypes.ErrorType ← NPGSConDefs.CuspPreGetErrorMsg[i];
PutErrorMsg[i, e];
ENDLOOP;
NPGSConDefs.CuspPreClearErrorMsgArray[];
PutRtn[];
};
-- end of CUSP additions
PutProc["TSymbols"];
PutAlloc[type: "TSymbols", cons: TRUE, count: tlim];
IO.PutF1[st, " %d", [cardinal[ttab[0].symbol]]];
FOR i: CARDINAL IN [1..tlim) DO
w: WORD ← ttab[i].symbol;
PutWord[i, w];
ENDLOOP;
PutRtn[];
PutProc["TActions"];
PrefixItem[0, tlim];
IO.PutRope[st, " null: ActionEntry ← [[FALSE, 0], 0];\n"];
PutAlloc[type: "TActions", count: tlim, all: "null"];
FOR i: CARDINAL IN [0..tlim) DO
PutItem[i, ttab[i].item, 0];
ENDLOOP;
PostfixItem[];
IO.PutRope[st, "\n}.\n"];
NPGSConDefs.prodInfo ← NIL; ntab ← NIL;
ntdefaults ← NIL; renumber ← NIL;
statedata ← NIL; ttab ← NIL;
scantab ← NIL;
};
TableSetup: PROC = {
defaultitem, item: NPGSTypes.ItemRec;
defaultprod, i, j, k, symbol, ttix, ntix, six, index, ptr: CARDINAL;
ColumnEntry: PROC = {
j: INTEGER;
lastptr: CARDINAL ← 0;
ptr ← ntdefaults[symbol].count;
DO
IF ptr=0 THEN GOTO insert;
j ← item.jf-column[ptr].item.jf;
IF j=0 THEN j ← item.pss-column[ptr].item.pss;
IF j=0 THEN GOTO countup;
IF j<0 THEN GOTO insert;
lastptr ← ptr; ptr ← column[ptr].link;
REPEAT
countup => column[ptr].count ← column[ptr].count+1;
insert => {
column[index].item ← item;
IF lastptr=0 THEN { --head of list for column "symbol"
column[index].link ← ntdefaults[symbol].count;
ntdefaults[symbol].count ← index
}
ELSE {
column[index].link ← column[lastptr].link;
column[lastptr].link ← index
};
index ← index+1
};
ENDLOOP
};
ntix ← ttix ← 0; index ← 1; statedata[1] ← [0,0,0,0];
FOR six IN [1..NPGSConDefs.sLim) DO
defaultprod ← NPGSConDefs.inword[]; statedata[six] ← [ttix,ntix,0,0];
THROUGH [1..NPGSConDefs.inword[]] DO --set up entries for state six in ttab and ntab
symbol ← NPGSConDefs.inword[]; k ← NPGSConDefs.inword[];
item ← [k MOD 4, k/4, NPGSConDefs.inword[]];
IF item.tag=2 AND item.pss=defaultprod THEN defaultitem ← item ELSE
IF symbol<=NPGSConDefs.eofMark THEN {ttab[ttix] ← [symbol, item]; ttix ← ttix+1}
ELSE {
symbol ← symbol-NPGSConDefs.eofMark+1; ntab[ntix] ← [symbol, item]; ntix ← ntix+1;
ColumnEntry[]
};
ENDLOOP;
IF defaultprod # 0 THEN {
ttab[ttix] ← [NPGSConDefs.defaultMarker, defaultitem]; ttix ← ttix+1
};
statedata[six].tLink ← ttix-statedata[six].tIndex; --length
statedata[six].ntLink ← ntix-statedata[six].ntIndex; --length
now see if these terminal entries match those of an existing state
FOR i IN [1..six) DO
k ← statedata[six].tIndex-statedata[i].tIndex;
IF statedata[six].tLink=statedata[i].tLink THEN -- same length
FOR j IN [statedata[i].tIndex..statedata[i].tIndex+statedata[i].tLink) DO
IF ttab[j]#ttab[j+k] THEN EXIT;
REPEAT FINISHED => { --there is a matching set of entries
statedata[six].tLink ← -i; -- point state six at state i
ttix ← statedata[six].tIndex; -- back up index
EXIT
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
tlim ← ttix;
ttab contains terminal entries; statedata[i].tindex indexes state i entries if
statedata[i].link>0, otherwise statedata[-statedata[i].link].tindex indexes them.
the following code leaves the most frequently occurring item in column "symbol"
of the lalr tables in the appropriate entry of ntdefaults
FOR symbol IN [0..NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1] DO
IF (ptr ← ntdefaults[symbol].count)=0 THEN LOOP;
k ← 0; ntdefaults[symbol].item ← column[ptr].item;
WHILE ptr#0 DO
IF column[ptr].count>k THEN {
k ← column[ptr].count; ntdefaults[symbol].item ← column[ptr].item
};
ptr ← column[ptr].link;
ENDLOOP;
ntdefaults[symbol].count ← k;
ENDLOOP
};
SquashNTab: PROC = {
nlim ← 0;
FOR six: CARDINAL IN [1..NPGSConDefs.sLim) DO
k: CARDINAL ← nlim;
FOR ntix: CARDINAL IN [statedata[six].ntIndex..statedata[six].ntIndex+statedata[six].ntLink) DO
IF ntab[ntix].item # ntdefaults[ntab[ntix].symbol].item THEN {
ntab[nlim] ← ntab[ntix];
nlim ← nlim+1;
};
ENDLOOP;
statedata[six].ntIndex ← k;
k ← nlim-k;
statedata[six].ntLink ← k;
IF k # 0 THEN
FOR i: CARDINAL IN [1..six) DO --do these entries match those of an existing state
k ← statedata[six].ntIndex-statedata[i].ntIndex;
IF statedata[six].ntLink=statedata[i].ntLink THEN -- same length
FOR j: CARDINAL IN [statedata[i].ntIndex..statedata[i].ntIndex+statedata[i].ntLink) DO
IF ntab[j]#ntab[j+k] THEN EXIT;
REPEAT FINISHED => { --there is a matching set of entries
statedata[six].ntLink ← -i; -- point state six at state i
nlim ← statedata[six].ntIndex; -- back up index
EXIT;
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
PrintNDef: PROC = {
j: CARDINAL ← 0;
item: NPGSTypes.ItemRec;
OutString["\nNonterminal Default Actions\n"];
linewidth ← 0;
FOR i: CARDINAL IN [2..NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1] DO
IF (linewidth ← linewidth+NPGSConDefs.tokenSize+8)>NPGSConDefs.outbufLim THEN {
NPGSConDefs.outeol[1];
linewidth ← NPGSConDefs.tokenSize+8;
};
item ← ntdefaults[i].item; j ← j+ntdefaults[i].count;
NPGSConDefs.outnum[IF item.tag=0 THEN item.pss ELSE -item.pss, 5]; NPGSConDefs.outchar[' ,1];
NPGSConDefs.outchar[' , NPGSConDefs.tokenSize+2-NPGSConDefs.OutToken[i+NPGSConDefs.eofMark-1]];
ENDLOOP;
OutString["\nEntries removed = "];
NPGSConDefs.outnum[j,5];
NPGSConDefs.outeol[1];
};
TableOverlays: PROC = {
j, k: INTEGER;
OutString["\nTable Overlays\n row ttab ntab\n"];
FOR i: CARDINAL IN [1..NPGSConDefs.sLim) DO
j ← statedata[i].tLink; k ← statedata[i].ntLink;
IF j<0 OR k<0 THEN {
NPGSConDefs.outnum[i,4];
IF j<0 THEN NPGSConDefs.outnum[-j, 5] ELSE NPGSConDefs.outchar[' ,5];
IF k<0 THEN NPGSConDefs.outnum[-k, 5];
NPGSConDefs.outeol[1]
};
ENDLOOP
};
HashTabSetup: PROC = {
i, j, k, h, p, count, freeptr, code: CARDINAL;
null: CHAR = '\000;
OutString["\nScanner hashtable probe counts (terminal symbol, probecount, hashcode)\n"];
vocabspace ← vocabindex[0] ← 0; freeptr ← hashval; linewidth ← 0;
scantab ← NEW[ScanTabArray ← ALL[0]];
FOR i IN [1..NPGSConDefs.eofMark] DO -- strip quotes, Repack, build vocabindex, scantab and hashtab
p ← i*NPGSConDefs.tokenSize; k ← NPGSConDefs.symInfo[i].length;
IF k=2 AND NPGSConDefs.symTab[p]=''
THEN {p ← p+1; k ← 1}
ELSE IF k>2 AND NPGSConDefs.symTab[p]='" AND NPGSConDefs.symTab[p+k-1]='" THEN {p←p+1; k←k-2};
IF k=1 AND ~(NPGSConDefs.symTab[p] IN ['a..'z] OR NPGSConDefs.symTab[p] IN ['A..'Z]) THEN {
scantab[CARDINAL[NPGSConDefs.symTab[p]-null]] ← i;
the next two statements are redundant, they keep the new tables identical to the old
NPGSConDefs.symTab[vocabspace] ← NPGSConDefs.symTab[p]; vocabspace ← vocabspace+1;
vocabindex[i] ← vocabspace
}
ELSE {
FOR j IN [0..k) DO
NPGSConDefs.symTab[vocabspace] ← NPGSConDefs.symTab[p+j]; vocabspace ← vocabspace+1;
ENDLOOP;
vocabindex[i] ← vocabspace;
IF i=NPGSConDefs.eofMark THEN LOOP;
count ← 1;
code ← h ← (((NPGSConDefs.symTab[p]-null)*127+(NPGSConDefs.symTab[p+k-1]-null)) MOD hashval) + 1;
IF hashtab[h].symPtr#0 THEN {
WHILE h#0 DO j ← h; h ← hashtab[h].link; count ← count+1 ENDLOOP;
WHILE hashtab[freeptr].symPtr#0 DO freeptr ← freeptr-1 ENDLOOP;
hashtab[j].link ← h ← freeptr
};
hashtab[h].symPtr ← i;
IF (linewidth ← linewidth+NPGSConDefs.tokenSize+8)>NPGSConDefs.outbufLim THEN {
NPGSConDefs.outeol[1]; linewidth ← NPGSConDefs.tokenSize+8
};
FOR j IN [vocabindex[i-1]..vocabindex[i]) DO NPGSConDefs.outchar[NPGSConDefs.symTab[j],1] ENDLOOP;
NPGSConDefs.outchar[' ,NPGSConDefs.tokenSize-k]; NPGSConDefs.outnum[count,2];
NPGSConDefs.outnum[code,4]; NPGSConDefs.outchar[' ,2]
};
ENDLOOP;
IF (j ← vocabspace MOD NPGSConDefs.cpw)#0 THEN -- pad to word boundary
THROUGH [j..NPGSConDefs.cpw) DO NPGSConDefs.symTab[vocabspace] ← null ENDLOOP;
NPGSConDefs.outeol[1];
};
StatePartition: PROC = {
i: CARDINAL ← 2;
j: CARDINAL ← NPGSConDefs.sLim-1;
DO
WHILE statedata[j].ntLink=0 AND i<=j DO j←j-1 ENDLOOP; -- j indexes an ntstate
WHILE statedata[i].ntLink#0 AND i<j DO i←i+1 ENDLOOP; -- i, a tstate unless i>=j
IF i>=j THEN EXIT
ELSE {i←i+1; j←j-1}; -- simulate renumbering
ENDLOOP;
lastntstate←j;
};
StateRenumber: PROC [cusp: BOOL] = {
i: CARDINAL ← 2;
j: CARDINAL ← NPGSConDefs.sLim-1;
k: INTEGER;
swaprec: NPGSTypes.StateDataRec;
DO
WHILE statedata[j].ntLink=0 AND i<=j DO j←j-1 ENDLOOP; -- j indexes an ntstate
WHILE statedata[i].ntLink#0 AND i<j DO i←i+1 ENDLOOP; -- i, a tstate unless i>=j
IF i>=j THEN EXIT;
renumber[i]←j;
renumber[j]←i;
i←i+1;
j←j-1;
if j<i now, j indexes the renumbered nstate
ENDLOOP;
IF lastntstate # j THEN ERROR;
renumber the transition entries
FOR i IN [0..tlim) DO
IF ttab[i].item.tag=0 AND (j←renumber[ttab[i].item.pss])#0 THEN ttab[i].item.pss←j;
ENDLOOP;
FOR i IN [0..nlim) DO
IF ntab[i].item.tag=0 AND (j←renumber[ntab[i].item.pss])#0 THEN ntab[i].item.pss←j;
ENDLOOP;
FOR i IN [2..NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1] DO
IF ntdefaults[i].item.tag=0 AND (j←renumber[ntdefaults[i].item.pss])#0 THEN
ntdefaults[i].item.pss←j;
ENDLOOP;
remove links and renumber states
FOR i IN [1..NPGSConDefs.sLim) DO
k ← statedata[i].tLink;
IF k<0 THEN {
statedata[i].tLink ← statedata[-k].tLink;
statedata[i].tIndex ← statedata[-k].tIndex
};
k ← statedata[i].ntLink;
IF k<0 THEN {
statedata[i].ntLink ← statedata[-k].ntLink;
statedata[i].ntIndex ← statedata[-k].ntIndex
};
ENDLOOP;
FOR i IN [2..lastntstate] DO
IF (j←renumber[i])#0 THEN {
swaprec ← statedata[i]; statedata[i] ← statedata[j]; statedata[j] ← swaprec
};
ENDLOOP;
IF cusp THEN NPGSConDefs.CuspPreRenumber[lastntstate, renumber]; -- new for CUSP
IF NPGSConDefs.flags[printLALR] THEN {
OutString["\nRenumbered States\n"];
FOR i IN [2..lastntstate] DO
IF renumber[i]#0 THEN {
NPGSConDefs.outnum[i,4]; OutString[" swapped with"]; NPGSConDefs.outnum[renumber[i],4]; NPGSConDefs.outeol[1]
};
ENDLOOP
}
};
OutModule: PUBLIC PROC [cedar: BOOL, cusp: BOOL] = {
i,j,k: CARDINAL;
OutCuspErrorType: PROC = {
OutString[" ErrorType: TYPE = {MAgg, MCalled, MDotLB, MExpr, MId, MOpd,\n"];
OutString[" MOptn, MRArrow, MThe, MTxt, MTypeId, MFieldTypeId, CloseIconExpr,\n"];
OutString[" CopyIconExpr, MoveIconExpr, SelectIconExpr, IconExpr,\n"];
OutString[" Stmt, MSecs, tl};\n"];
};
OutRange: PROC [id, cover: Rope.ROPE, ulim: CARDINAL] = {
NPGSConDefs.outchar[' ,2]; NPGSConDefs.outstring[id]; OutString[": TYPE = "];
IF cover = NIL THEN OutString["CARDINAL"] ELSE NPGSConDefs.outstring[cover];
OutString["[0.."]; NPGSConDefs.outnum[ulim,1]; OutString["];\n"];
};
OutArray: PROC [id, index, range: Rope.ROPE] = {
NPGSConDefs.outchar[' ,2]; NPGSConDefs.outstring[id]; OutString[": TYPE = ARRAY "];
NPGSConDefs.outstring[index]; OutString[" OF "]; NPGSConDefs.outstring[range];
NPGSConDefs.outchar[';,1]; NPGSConDefs.outeol[1];
};
OutRefProc: PROC [referent: Rope.ROPE] = {
First, output the type definition
NPGSConDefs.outchar[' ,2];
NPGSConDefs.outstring[referent];
IF cedar
THEN OutString["Ref: TYPE = REF "]
ELSE OutString["Ref: TYPE = LONG POINTER TO "];
NPGSConDefs.outstring[referent];
OutString[";"];
NPGSConDefs.outeol[1];
Second output the procedure to call for initialization
NPGSConDefs.outchar[' ,2];
OutString["Init"];
NPGSConDefs.outstring[referent];
IF cedar
THEN OutString[": PROC RETURNS ["]
ELSE OutString[": PROC [uz: UNCOUNTED ZONE] RETURNS ["];
NPGSConDefs.outstring[referent];
OutString["Ref];"];
NPGSConDefs.outeol[2];
};
Output header of the definitions file
OutString["-- "];
NPGSConDefs.outstring[NPGSConDefs.modName];
NPGSConDefs.outeol[1];
OutString["-- an NPGS production from "];
NPGSConDefs.outstring[NPGSConDefs.sourceName];
OutString[", "];
NPGSConDefs.outtime[];
NPGSConDefs.outeol[2];
NPGSConDefs.outstring[NPGSConDefs.typeName];
IF cedar
THEN OutString[": CEDAR DEFINITIONS = {\n\n"]
ELSE OutString[": DEFINITIONS = {\n\n"];
OutRange["Symbol", NIL, NPGSConDefs.maxSymbolIndex];
OutRange["TSymbol", "Symbol", NPGSConDefs.eofMark];
OutRange["NTSymbol", "Symbol", NPGSConDefs.totalTokens-NPGSConDefs.eofMark+1];
OutString["\n-- Token indices for the scanner and parser\n"];
FOR i IN [0..NPGSConDefs.nextAlias) DO
NPGSConDefs.outchar[' ,2]; k ← NPGSConDefs.aliases[i].alias*NPGSConDefs.tokenSize;
FOR j IN [k..k+NPGSConDefs.tokenSize) WHILE NPGSConDefs.symTab[j]#0c DO NPGSConDefs.outchar[NPGSConDefs.symTab[j],1] ENDLOOP;
OutString[": TSymbol ="]; NPGSConDefs.outnum[NPGSConDefs.aliases[i].terminal,3]; NPGSConDefs.outchar[';,1]; NPGSConDefs.outeol[1];
ENDLOOP;
NPGSConDefs.symTab ← NIL; NPGSConDefs.aliases ← NIL;
OutString["\n defaultMarker: TSymbol = TSymbol.FIRST;"];
OutString["\n endMarker: TSymbol = TSymbol.LAST;"];
NPGSConDefs.outeol[2];
OutRange["HashIndex", NIL, hashval];
OutRange["VIndex", NIL, vocabspace-1];
NPGSConDefs.outeol[1];
OutString["\n VocabHashEntry: TYPE = RECORD ["];
OutString["\n symbol: TSymbol, -- symbol index"];
OutString["\n link: HashIndex]; -- link to next entry"];
NPGSConDefs.outeol[2];
OutRange["State", NIL, NPGSConDefs.sLim-1];
OutRange["NTState", "State", lastntstate];
OutRange["TIndex", NIL, tlim-1];
OutRange["NTIndex", NIL, nlim-1];
OutRange["Production", NIL, NPGSConDefs.numProd];
OutRange["Rule", NIL, NPGSConDefs.numRules];
IF cusp THEN OutCuspErrorType[]; -- New for CUSP
OutString["\n ActionTag: TYPE = RECORD ["];
OutString["\n reduce: BOOL, -- TRUE iff reduce entry"];
OutString["\n pLength: [0..15]]; -- number of symbols in production rhs\n"];
OutString["\n ActionEntry: TYPE = RECORD ["];
OutString["\n tag: ActionTag, -- [FALSE,0] if a shift entry"];
OutString["\n transition: [0..2047]]; -- production number / next state\n"];
OutString["\n ProductionInfo: TYPE = RECORD ["];
OutString["\n rule: Rule, -- reduction rule"];
OutString["\n lhs: NTSymbol]; -- production lhs symbol\n\n"];
OutArray["ScanTable", "CHAR['\\040..'\\177]", "TSymbol"];
OutArray["HashTable", "HashIndex", "VocabHashEntry"];
OutArray["IndexTable", "TSymbol", "CARDINAL"];
OutString[" Vocabulary: TYPE = TEXT;\n"];
OutArray["ProdData","Production","ProductionInfo"];
OutArray["NStarts", "NTState", "NTIndex"];
OutArray["NLengths", "NTState", "CARDINAL"];
OutArray["NSymbols", "NTIndex", "NTSymbol"];
OutArray["NActions", "NTIndex", "ActionEntry"];
OutArray["NTDefaults", "NTSymbol", "ActionEntry"];
OutArray["TStarts", "State", "TIndex"];
OutArray["TLengths", "State", "CARDINAL"];
IF cusp THEN OutArray["ErrorMsgs", "State", "ErrorType"];
OutArray["TSymbols", "TIndex", "TSymbol"];
OutArray["TActions", "TIndex", "ActionEntry"];
NPGSConDefs.outeol[1];
OutString[" initialState: State = "]; NPGSConDefs.outnum[1,1]; NPGSConDefs.outchar[';,1];
NPGSConDefs.outeol[1];
OutString[" finalState: State = "]; NPGSConDefs.outnum[0,1]; NPGSConDefs.outchar[';,1];
NPGSConDefs.outeol[2];
OutRefProc["ScanTable"];
OutRefProc["HashTable"];
OutRefProc["IndexTable"];
OutRefProc["Vocabulary"];
OutRefProc["ProdData"];
OutRefProc["NStarts"];
OutRefProc["NLengths"];
OutRefProc["NSymbols"];
OutRefProc["NActions"];
OutRefProc["NTDefaults"];
OutRefProc["TStarts"];
OutRefProc["TLengths"];
IF cusp THEN OutRefProc["ErrorMsgs"];
OutRefProc["TSymbols"];
OutRefProc["TActions"];
OutString["\n}.\n"];
};
}.
Russ Atkinson (RRA) March 16, 1988 8:52:44 pm PST
Changed to output Cedar/Mesa programs instead of bcd tables.