-- file PGSTab.mesa -- last modified by Satterthwaite, January 7, 1983 12:27 pm DIRECTORY PGSConDefs: TYPE USING [ cpw, defaultMarker, maxCharCode, outbufLim, pssLim, rhsLim, tokenSize, aliases, eofMark, flags, nextAlias, numProd, numRules, ntEntries, prodInfo, sLim, sourceName, symInfo, symTab, tEntries, totalTokens, closewordstream, MakeArray, FreeArray, inword, openwordstream, outblock, outchar, outeol, outnum, outstring, outtime, OutToken, outword], PGSTypes: TYPE USING [ Column, ColumnRec, HashTab, HashTabRec, ItemRec, NTab, NTDefaultRec, NTDefaults, Renumber, StateData, StateDataRec, TabRec, TTab, VocabIndex], Strings: TYPE USING [String]; PGSTab: PROGRAM IMPORTS PGSConDefs EXPORTS PGSConDefs = { OPEN PGSConDefs; linewidth, hashval, lastntstate, vocabspace, nlim, tlim: CARDINAL; offset: CARDINAL; hashtab: PGSTypes.HashTab; ttab: PGSTypes.TTab; ntab: PGSTypes.NTab; packedProdInfo: BOOL; statedata: PGSTypes.StateData; ntdefaults: PGSTypes.NTDefaults; column: PGSTypes.Column; renumber: PGSTypes.Renumber; vocabindex: PGSTypes.VocabIndex; scantab: ARRAY [40b..177b] OF CARDINAL; TabGen: PUBLIC PROC [prefix, suffix: PROC] RETURNS [success: BOOL←TRUE] = { Error: PROC [sel: CARDINAL] = { outstring["\nFAIL - "L]; outstring[SELECT sel FROM 1 => "more than 255 terminal symbols"L, 2 => "more than 254 nonterminal symbols"L, 3 => "more than 2047 states or productions"L, 4 => "more than 15 symbols in a production right part"L, ENDCASE => "PGS error"L]; outeol[1]; success ← FALSE}; IF eofMark > 255 THEN Error[1]; IF totalTokens-eofMark+1 > 255 THEN Error[2]; IF pssLim > 2047 THEN Error[3]; IF rhsLim > 15 THEN Error[4]; IF ~success THEN RETURN [success]; ntab ← LOOPHOLE[MakeArray[ntEntries, PGSTypes.TabRec.SIZE]]; ttab ← LOOPHOLE[MakeArray[tEntries, PGSTypes.TabRec.SIZE]]; packedProdInfo ← (numRules <= 255); statedata ← LOOPHOLE[MakeArray[sLim, PGSTypes.StateDataRec.SIZE]]; ntdefaults ← LOOPHOLE[MakeArray[totalTokens-eofMark+2, PGSTypes.NTDefaultRec.SIZE]]; column ← LOOPHOLE[MakeArray[ntEntries+1, PGSTypes.ColumnRec.SIZE]]; TableSetup[]; closewordstream[]; SquashNTab[]; outstring["\nParse Table Data\n"L]; IF flags[printLALR] THEN {PrintNDef[]; TableOverlays[]}; vocabindex ← LOOPHOLE[MakeArray[eofMark+1, CARDINAL.SIZE]]; hashval ← 3*eofMark/2; hashval ← MIN[251, IF hashval MOD 2 = 0 THEN hashval+1 ELSE hashval]; hashtab ← LOOPHOLE[MakeArray[hashval+1, PGSTypes.HashTabRec.SIZE]]; HashTabSetup[]; -- start output file openwordstream[scratch:FALSE]; IF prefix # NIL THEN prefix[]; -- output scanner table relative offsets (see table output below) offset ← 14; -- number of tables outword[offset]; offset ← offset + 96; outword[offset]; offset ← offset + (hashval+1); outword[offset]; offset ← offset + (eofMark+1); outword[offset]; offset ← offset + (2 + (vocabspace+cpw-1)/cpw); -- output parser table relative offsets (see table output below) StatePartition[]; -- compute lastntstate outword[offset]; offset ← offset + (numProd+1)*(IF packedProdInfo THEN 1 ELSE 2); outword[offset]; offset ← offset + (lastntstate+1); outword[offset]; offset ← offset + (lastntstate+1); outword[offset]; offset ← offset + nlim; outword[offset]; offset ← offset + nlim; outword[offset]; offset ← offset + (totalTokens-eofMark+2); outword[offset]; offset ← offset + sLim; outword[offset]; offset ← offset + sLim; outword[offset]; offset ← offset + tlim; outword[offset]; -- output scanner tables outblock[scantab.BASE, 96]; outblock[hashtab.BASE, hashval+1]; outblock[vocabindex.BASE, eofMark+1]; outword[vocabspace]; outword[vocabspace]; outblock[symTab.BASE, (vocabspace+cpw-1)/cpw]; FreeArray[hashtab]; FreeArray[vocabindex]; FreeArray[symInfo]; renumber ← LOOPHOLE[MakeArray[sLim, CARDINAL.SIZE]]; StateRenumber[]; --now output parser tables OutArray[1,numProd, IF packedProdInfo THEN ProdDataItem1 ELSE ProdDataItem2]; OutArray[1,lastntstate, NStateItem]; OutArray[1,lastntstate, NLenItem]; OutArray[0,nlim-1, NSymItem]; OutArray[0,nlim-1, NActionItem]; OutArray[2,totalTokens-eofMark+1, NTDefaultItem]; OutArray[1,sLim-1, TStateItem]; OutArray[1,sLim-1, TLenItem]; OutArray[0,tlim-1, TSymItem]; OutArray[0,tlim-1, TActionItem]; FreeArray[prodInfo]; FreeArray[ntab]; FreeArray[ntdefaults]; FreeArray[renumber]; FreeArray[statedata]; FreeArray[ttab]; IF suffix # NIL THEN suffix[]}; TableSetup: PROC = { defaultitem, item: PGSTypes.ItemRec; defaultprod, i, j, k, symbol, ttix, ntix, six, index, ptr: CARDINAL; ColumnEntry: PROC = { j: INTEGER; lastptr: CARDINAL; lastptr ← 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..sLim) DO defaultprod ← inword[]; statedata[six] ← [ttix,ntix,0,0]; THROUGH [1..inword[]] DO --set up entries for state six in ttab and ntab symbol ← inword[]; k ← inword[]; item ← [k MOD 4, k/4, inword[]]; IF item.tag=2 AND item.pss=defaultprod THEN defaultitem ← item ELSE IF symbol<=eofMark THEN {ttab[ttix] ← [symbol, item]; ttix ← ttix+1} ELSE { symbol ← symbol-eofMark+1; ntab[ntix] ← [symbol, item]; ntix ← ntix+1; ColumnEntry[]}; ENDLOOP; IF defaultprod # 0 THEN { ttab[ttix] ← [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..totalTokens-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 = { i, j, k, six, ntix: CARDINAL; nlim ← 0; FOR six IN [1..sLim) DO k ← nlim; FOR ntix 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 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 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; item: PGSTypes.ItemRec; outstring["\nNonterminal Default Actions\n"L]; linewidth ← 0; j ← 0; FOR i: CARDINAL IN [2..totalTokens-eofMark+1] DO IF (linewidth ← linewidth+tokenSize+8)>outbufLim THEN { outeol[1]; linewidth ← tokenSize+8}; item ← ntdefaults[i].item; j ← j+ntdefaults[i].count; outnum[IF item.tag=0 THEN item.pss ELSE -item.pss, 5]; outchar[' ,1]; outchar[' , tokenSize+2-OutToken[i+eofMark-1]]; ENDLOOP; outstring["\nEntries removed = "L]; outnum[j,5]; outeol[1]}; TableOverlays: PROC = { j, k: INTEGER; outstring["\nTable Overlays\n row ttab ntab\n"L]; FOR i: CARDINAL IN [1..sLim) DO j ← statedata[i].tLink; k ← statedata[i].ntLink; IF j<0 OR k<0 THEN { outnum[i,4]; IF j<0 THEN outnum[-j, 5] ELSE outchar[' ,5]; IF k<0 THEN outnum[-k, 5]; 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"L]; vocabspace ← vocabindex[0] ← 0; freeptr ← hashval; linewidth ← 0; scantab ← ALL[0]; FOR i IN [1..eofMark] DO -- strip quotes, Repack, build vocabindex, scantab and hashtab p ← i*tokenSize; k ← symInfo[i].length; IF k=2 AND symTab[p]='' THEN {p ← p+1; k ← 1} ELSE IF k>2 AND symTab[p]='" AND symTab[p+k-1]='" THEN {p←p+1; k←k-2}; IF k=1 AND ~(symTab[p] IN ['a..'z] OR symTab[p] IN ['A..'Z]) THEN { scantab[CARDINAL[symTab[p]-null]] ← i; -- the next two statements are redundant, they keep the new tables identical to the old symTab[vocabspace] ← symTab[p]; vocabspace ← vocabspace+1; vocabindex[i] ← vocabspace} ELSE { FOR j IN [0..k) DO symTab[vocabspace] ← symTab[p+j]; vocabspace ← vocabspace+1; ENDLOOP; vocabindex[i] ← vocabspace; IF i=eofMark THEN LOOP; count ← 1; code ← h ← (((symTab[p]-null)*127+(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+tokenSize+8)>outbufLim THEN { outeol[1]; linewidth ← tokenSize+8}; FOR j IN [vocabindex[i-1]..vocabindex[i]) DO outchar[symTab[j],1] ENDLOOP; outchar[' ,tokenSize-k]; outnum[count,2]; outnum[code,4]; outchar[' ,2]}; ENDLOOP; IF (j ← vocabspace MOD cpw)#0 THEN -- pad to word boundary THROUGH [j..cpw) DO symTab[vocabspace] ← null ENDLOOP; outeol[1]}; StatePartition: PROC = { i, j: CARDINAL; i←2; j←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 = { i, j: CARDINAL; k: INTEGER; swaprec: PGSTypes.StateDataRec; i←2; j←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 {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..totalTokens-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..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 flags[printLALR] THEN { outstring["\nRenumbered States\n"L]; FOR i IN [2..lastntstate] DO IF renumber[i]#0 THEN { outnum[i,4]; outstring[" swapped with"L]; outnum[renumber[i],4]; outeol[1]}; ENDLOOP}}; OutModule: PUBLIC PROC [typename, modfname: Strings.String, long: BOOL] = { i,j,k: CARDINAL; OutRange: PROC [id, cover: STRING, ulim: CARDINAL] = { outchar[' ,2]; outstring[id]; outstring[": TYPE = "L]; outstring[cover]; outstring["[0.."L]; outnum[ulim,3]; outstring["];\n"L]}; OutArray: PROC [id, index, range: STRING] = { outchar[' ,2]; outstring[id]; outstring[": TYPE = ARRAY "L]; outstring[index]; outstring[" OF "L]; outstring[range]; outchar[';,1]; outeol[1]}; OutRefType: PROC [referent: STRING, base: BOOL ← FALSE] = { outchar[' ,2]; outstring[referent]; outstring["Ref: TYPE = "L]; IF long THEN outstring["LONG "L]; IF base THEN outstring["BASE "L]; outstring["POINTER TO "L]; outstring[referent]; outchar[';,1]; outeol[1]}; outstring["-- file "L]; outstring[modfname]; outstring["\n-- created by PGS from "L]; outstring[sourceName]; outstring[", "L]; outtime[]; outeol[2]; outstring[typename]; outstring[": DEFINITIONS = {\n\n"L]; OutRange["Symbol"L,""L,maxCharCode]; OutRange["TSymbol"L,"Symbol"L,eofMark]; OutRange["NTSymbol"L,"Symbol"L,totalTokens-eofMark+1]; outstring["\n-- token indices for the scanner and parser\n"L]; FOR i IN [0..nextAlias) DO outchar[' ,2]; k ← aliases[i].alias*tokenSize; FOR j IN [k..k+tokenSize) WHILE symTab[j]#0c DO outchar[symTab[j],1] ENDLOOP; outstring[": TSymbol ="L]; outnum[aliases[i].terminal,3]; outchar[';,1]; outeol[1]; ENDLOOP; FreeArray[LOOPHOLE[symTab]]; FreeArray[aliases]; outstring["\n default"L]; outstring["Marker: TSymbol = TSymbol"L]; outstring[".FIRST;\n"L]; outstring[" end"L]; outstring["Marker: TSymbol = TSymbol"L]; outstring[".LAST;\n\n"L]; OutRange["HashIndex"L,""L,hashval]; OutRange["VIndex"L,""L,vocabspace-1]; outstring[" VocabHashEntry: TYPE = MACHINE DEPENDENT RECORD [ symbol(0: 0..7): TSymbol, -- symbol index link(0: 8..15): HashIndex]; -- link to next entry\n\n"L]; OutRange["State"L,""L,sLim-1]; OutRange["NTState"L,"State"L,lastntstate]; OutRange["TIndex"L,""L,tlim-1]; OutRange["NTIndex"L,""L,nlim-1]; OutRange["Production"L,""L,numProd]; outstring[" ActionTag: TYPE = MACHINE DEPENDENT RECORD [ reduce(0: 0..0): BOOL, -- TRUE iff reduce entry pLength(0: 1..4): [0..15]]; -- number of symbols in production rhs ActionEntry: TYPE = MACHINE DEPENDENT RECORD [ tag(0: 0..4): ActionTag, -- [FALSE,0] if a shift entry transition(0: 5..15): [0..2047]]; -- production number / next state"L]; IF packedProdInfo THEN outstring[" ProductionInfo: TYPE = MACHINE DEPENDENT RECORD [ rule(0: 0..7): [0..256), -- reduction rule lhs(0: 8..15): NTSymbol]; -- production lhs symbol\n\n"L] ELSE outstring[" ProductionInfo: TYPE = MACHINE DEPENDENT RECORD [ rule(0): CARDINAL, -- reduction rule lhs(1): Symbol]; -- production lhs symbol (NTSymbol)\n\n"L]; OutArray["ScanTable"L,"CHAR['\\040..'\\177]"L,"TSymbol"L]; OutArray["HashTable"L,"HashIndex"L,"VocabHashEntry"L]; OutArray["IndexTable"L,"TSymbol"L,"CARDINAL"L]; outstring[" Vocabulary: TYPE = MACHINE DEPENDENT RECORD [\n"L]; outstring[" length(0), maxlength(1): CARDINAL,\n"L]; outstring[" text(2): PACKED ARRAY VIndex OF CHAR];\n"L]; OutArray["ProdData"L,"Production"L,"ProductionInfo"L]; OutArray["NStarts"L,"NTState"L,"NTIndex"L]; OutArray["NLengths"L,"NTState"L,"CARDINAL"L]; OutArray["NSymbols"L,"NTIndex"L,"NTSymbol"L]; OutArray["NActions"L,"NTIndex"L,"ActionEntry"L]; OutArray["NTDefaults"L,"NTSymbol"L,"ActionEntry"L]; OutArray["TStarts"L,"State"L,"TIndex"L]; OutArray["TLengths"L,"State"L,"CARDINAL"L]; OutArray["TSymbols"L,"TIndex"L,"TSymbol"L]; OutArray["TActions"L,"TIndex"L,"ActionEntry"L]; outeol[1]; outstring[" initial"L]; outstring["State: State = "L]; outnum[1,1]; outchar[';,1]; outeol[1]; outstring[" final"L]; outstring["State: State = "L]; outnum[0,1]; outchar[';,1]; outeol[1]; outstring[" Table: TYPE = MACHINE DEPENDENT RECORD [ scanTable: RECORD [ scanTab: TableRef RELATIVE POINTER TO ScanTable, hashTab: TableRef RELATIVE POINTER TO HashTable, vocabIndex: TableRef RELATIVE POINTER TO IndexTable, vocabBody: TableRef RELATIVE POINTER TO Vocabulary], parseTable: RECORD [ prodData: TableRef RELATIVE POINTER TO ProdData, nStart: TableRef RELATIVE POINTER TO NStarts, nLength: TableRef RELATIVE POINTER TO NLengths, nSymbol: TableRef RELATIVE POINTER TO NSymbols, nAction: TableRef RELATIVE POINTER TO NActions, ntDefaults: TableRef RELATIVE POINTER TO NTDefaults, tStart: TableRef RELATIVE POINTER TO TStarts, tLength: TableRef RELATIVE POINTER TO TLengths, tSymbol: TableRef RELATIVE POINTER TO TSymbols, tAction: TableRef RELATIVE POINTER TO TActions]];\n\n"L]; OutRefType["Table"L, TRUE]; OutRefType["ScanTable"L]; OutRefType["HashTable"L]; OutRefType["IndexTable"L]; OutRefType["Vocabulary"L]; OutRefType["ProdData"L]; OutRefType["NStarts"L]; OutRefType["NLengths"L]; OutRefType["NSymbols"L]; OutRefType["NActions"L]; OutRefType["NTDefaults"L]; OutRefType["TStarts"L]; OutRefType["TLengths"L]; OutRefType["TSymbols"L]; OutRefType["TActions"L]; outstring["\n }.\n"L]}; IProc: TYPE = PROC [index: CARDINAL]; OutArray: PROC [llim, ulim: CARDINAL, p: IProc] = { THROUGH [0..llim) DO outword[0] ENDLOOP; FOR i: CARDINAL IN [llim..ulim] DO p[i] ENDLOOP}; ProdDataItem1: IProc = { outword[prodInfo[index].rule*256+(prodInfo[index].lhs-eofMark+1)]}; ProdDataItem2: IProc = { outword[prodInfo[index].rule]; outword[prodInfo[index].lhs-eofMark+1]}; NStateItem: IProc = {outword[statedata[index].ntIndex]}; NLenItem: IProc = {outword[statedata[index].ntLink]}; NSymItem: IProc = {outword[ntab[index].symbol]}; NActionItem: IProc = {Repack[ntab[index].item]}; NTDefaultItem: IProc = {Repack[ntdefaults[index].item]}; TStateItem: IProc = {outword[statedata[index].tIndex]}; TLenItem: IProc = {outword[statedata[index].tLink]}; TSymItem: IProc = {outword[ttab[index].symbol]}; TActionItem: IProc = {Repack[ttab[index].item]}; Repack: PROC [item: PGSTypes.ItemRec] = { SELECT item.tag FROM 0 => outword[item.pss]; 1 => outword[item.jf*2048+item.pss]; 2 => outword[(16+item.jf)*2048+item.pss]; ENDCASE}; }.