<> <> <> <> <> <> DIRECTORY PGSConDefs: TYPE, PGSTypes: TYPE, Rope: TYPE USING [ROPE]; 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 - "]; 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 => "PGS error"]; 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 _ MakeTab[ntEntries]; ttab _ MakeTab[tEntries]; packedProdInfo _ (numRules <= 255); statedata _ MakeStateData[sLim]; ntdefaults _ MakeNTDefaults[totalTokens-eofMark+2]; column _ MakeColumn[ntEntries+1]; TableSetup[]; closewordstream[]; SquashNTab[]; outstring["\nParse Table Data\n"]; IF flags[printLALR] THEN {PrintNDef[]; TableOverlays[]}; vocabindex _ MakeVocabIndex[eofMark+1]; hashval _ 3*eofMark/2; hashval _ MIN[251, IF hashval MOD 2 = 0 THEN hashval+1 ELSE hashval]; hashtab _ MakeHashTab[hashval+1]; HashTabSetup[]; <> openwordstream[scratch:FALSE]; IF prefix # NIL THEN prefix[]; <

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

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

> outblock[scantab.BASE, 96]; outblock[LOOPHOLE[hashtab], hashval+1, PGSTypes.HashTabSeq[0].SIZE]; outblock[LOOPHOLE[vocabindex], eofMark+1, PGSTypes.CardinalsSeq[0].SIZE]; outword[vocabspace]; outword[vocabspace]; outblock[LOOPHOLE[symTab], (vocabspace+cpw-1)/cpw, PGSTypes.SymTabSeq[0].SIZE]; hashtab _ NIL; vocabindex _ NIL; symInfo _ NIL; renumber _ MakeRenumber[sLim]; 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]; prodInfo _ NIL; ntab _ NIL; ntdefaults _ NIL; renumber _ NIL; statedata _ NIL; ttab _ NIL; 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 <> 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; <> <0, otherwise statedata[-statedata[i].link].tindex indexes them.>> <> <> 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"]; 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 = "]; outnum[j,5]; outeol[1]}; TableOverlays: PROC = { j, k: INTEGER; outstring["\nTable Overlays\n row ttab ntab\n"]; 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"]; 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; <> 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 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 IF i>=j THEN EXIT ELSE {renumber[i]_j; renumber[j]_i; i_i+1; j_j-1}; <> ENDLOOP; IF lastntstate # j THEN ERROR; <> 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; <> 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"]; FOR i IN [2..lastntstate] DO IF renumber[i]#0 THEN { outnum[i,4]; outstring[" swapped with"]; outnum[renumber[i],4]; outeol[1]}; ENDLOOP } }; OutModule: PUBLIC PROC[typename, modfname: Rope.ROPE, long: BOOL] = { i,j,k: CARDINAL; OutRange: PROC[id, cover: Rope.ROPE, ulim: CARDINAL] = { outchar[' ,2]; outstring[id]; outstring[": TYPE = "]; outstring[cover]; outstring["[0.."]; outnum[ulim,3]; outstring["];\n"]}; OutArray: PROC[id, index, range: Rope.ROPE] = { outchar[' ,2]; outstring[id]; outstring[": TYPE = ARRAY "]; outstring[index]; outstring[" OF "]; outstring[range]; outchar[';,1]; outeol[1]}; OutRefType: PROC[referent: Rope.ROPE, base: BOOL_FALSE] = { outchar[' ,2]; outstring[referent]; outstring["Ref: TYPE = "]; IF long THEN outstring["LONG "]; IF base THEN outstring["BASE "]; outstring["POINTER TO "]; outstring[referent]; outchar[';,1]; outeol[1]}; outstring["-- file "]; outstring[modfname]; outstring["\n-- created by PGS from "]; outstring[sourceName]; outstring[", "]; outtime[]; outeol[2]; outstring[typename]; outstring[": DEFINITIONS = {\n\n"]; OutRange["Symbol","",maxCharCode]; OutRange["TSymbol","Symbol",eofMark]; OutRange["NTSymbol","Symbol",totalTokens-eofMark+1]; outstring["\n-- token indices for the scanner and parser\n"]; 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 ="]; outnum[aliases[i].terminal,3]; outchar[';,1]; outeol[1]; ENDLOOP; symTab _ NIL; aliases _ NIL; outstring["\n default"]; outstring["Marker: TSymbol = TSymbol"]; outstring[".FIRST;\n"]; outstring[" end"]; outstring["Marker: TSymbol = TSymbol"]; outstring[".LAST;\n\n"]; OutRange["HashIndex","",hashval]; OutRange["VIndex","",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"]; OutRange["State","",sLim-1]; OutRange["NTState","State",lastntstate]; OutRange["TIndex","",tlim-1]; OutRange["NTIndex","",nlim-1]; OutRange["Production","",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"]; 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"] ELSE outstring[" ProductionInfo: TYPE = MACHINE DEPENDENT RECORD [ rule(0): CARDINAL, -- reduction rule lhs(1): Symbol]; -- production lhs symbol (NTSymbol)\n\n"]; OutArray["ScanTable","CHAR['\\040..'\\177]","TSymbol"]; OutArray["HashTable","HashIndex","VocabHashEntry"]; OutArray["IndexTable","TSymbol","CARDINAL"]; outstring[" Vocabulary: TYPE = MACHINE DEPENDENT RECORD [\n"]; outstring[" length(0), maxlength(1): CARDINAL,\n"]; outstring[" text(2): PACKED ARRAY VIndex OF CHAR];\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"]; OutArray["TSymbols","TIndex","TSymbol"]; OutArray["TActions","TIndex","ActionEntry"]; outeol[1]; outstring[" initial"]; outstring["State: State = "]; outnum[1,1]; outchar[';,1]; outeol[1]; outstring[" final"]; outstring["State: State = "]; 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"]; OutRefType["Table", TRUE]; OutRefType["ScanTable"]; OutRefType["HashTable"]; OutRefType["IndexTable"]; OutRefType["Vocabulary"]; OutRefType["ProdData"]; OutRefType["NStarts"]; OutRefType["NLengths"]; OutRefType["NSymbols"]; OutRefType["NActions"]; OutRefType["NTDefaults"]; OutRefType["TStarts"]; OutRefType["TLengths"]; OutRefType["TSymbols"]; OutRefType["TActions"]; outstring["\n }.\n"]}; 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 }; }.