-- file PGSFormat.mesa
-- last modified by Satterthwaite, July 6, 1982 10:23 am
DIRECTORY
PGSConDefs: TYPE USING [
ControlZ, query,
cpw, maxProd, maxRhsSymbols, symTabSize, tokenSize,
sourceName,
AcquireZone, Expand, FreeArray, inchar, MakeArray,
outchar, outeol, outnum, outstring, outtime, PGSFail, ReleaseZone],
PGSTypes: TYPE USING [
HashHeads, HashHeadsRef, RhsChar, PInfo, PInfoRec, SymTab, SInfo, SInfoRec],
Strings: TYPE USING [String];
PGSFormat: PROGRAM
IMPORTS PGSConDefs
EXPORTS PGSConDefs = {
OPEN PGSConDefs;
leftIndex, symIndex, nextProd, sInfIndex, nextRhsChar, topSymbol: CARDINAL;
rule, nextRule, aliasIndex, lastTerminal: CARDINAL;
symString, aliasText: PGSTypes.SymTab;
sInfo: PGSTypes.SInfo;
pInfo: PGSTypes.PInfo;
rhsText: PGSTypes.RhsChar;
KeyWord: TYPE = {table, type, export, goal, terminals, aliases, productions};
text: STRING = "TABLETYPEEXPORTSGOALTERMINALSALIASESPRODUCTIONS";
textKeys: ARRAY KeyWord OF RECORD [index, len: CARDINAL] =
[[0,5], [5,4], [9,7], [16,4], [20,9], [29,7], [36,11]];
Error: PROC = {
FreeArray[rhsText];
FreeArray[sInfo]; FreeArray[pInfo];
FreeArray[LOOPHOLE[symString]]; FreeArray[LOOPHOLE[aliasText]];
ERROR PGSFail[]};
Directive: PROC [key: KeyWord] RETURNS [BOOL] = {
IF symIndex-leftIndex-1 # textKeys[key].len OR symString[symIndex-1] # ': THEN
RETURN [FALSE];
FOR i: CARDINAL IN [0..textKeys[key].len) DO
IF symString[leftIndex+i] # text[textKeys[key].index+i] THEN RETURN [FALSE]
ENDLOOP;
RETURN [TRUE]};
ExtractKeyItem: PROC [key: KeyWord, value: Strings.String] RETURNS [BOOL] = {
i,j: CARDINAL;
IF ~Directive[key] THEN RETURN [FALSE] ELSE {
GetText[]; j ← 0;
FOR i IN [leftIndex..symIndex) DO value[j] ← symString[i]; j ← j+1 ENDLOOP};
value.length ← j; RETURN [TRUE]};
hashChain: PGSTypes.HashHeadsRef;
FindText: PROC RETURNS [CARDINAL] = {
h, i, j, k: CARDINAL;
h ← (256*(symIndex-leftIndex)+(symString[leftIndex]-0c)) MOD LENGTH[hashChain↑];
j ← hashChain[h];
WHILE j#0 DO
IF symIndex-leftIndex = sInfo[j+1].symPtr-sInfo[j].symPtr THEN { -- same length
i ← sInfo[j].symPtr;
FOR k IN [leftIndex..symIndex) DO
IF symString[k]#symString[i] THEN EXIT;
i ← i+1;
REPEAT
FINISHED => {symIndex ← leftIndex; RETURN [j]};
ENDLOOP};
j ← sInfo[j].link;
ENDLOOP;
-- new symbol
sInfo[sInfIndex] ← [leftIndex,hashChain[h],0];
hashChain[h] ← sInfIndex; sInfIndex ← sInfIndex+1;
sInfo[sInfIndex].symPtr ← symIndex;
IF sInfIndex=LENGTH[sInfo] THEN
sInfo ← LOOPHOLE[Expand[sInfo,SIZE[PGSTypes.SInfoRec],LENGTH[sInfo]/8]];
RETURN [sInfIndex-1]};
Formatter: PROC [tableId, typeId, exportId: Strings.String] = {
chain: BOOL;
outstring["-- file "L]; outstring[sourceName];
outstring[" rewritten by PGS, "L]; outtime[]; outeol[1];
ScanInit[];
DO
GetText[];
SELECT TRUE FROM
ExtractKeyItem[table, tableId] => NULL;
ExtractKeyItem[type, typeId] => NULL;
ExtractKeyItem[export, exportId] => NULL;
ENDCASE => EXIT;
ENDLOOP;
IF ~Directive[goal] THEN Error[] ELSE {
symIndex ← 0; GetText[]; sInfIndex ← 1; [] ← FindText[]};
GetText[];
IF Directive[terminals] THEN {
symIndex ← leftIndex;
DO
GetText[];
IF symString[symIndex-1] = ': AND (Directive[aliases] OR Directive[productions])
THEN EXIT;
[] ← FindText[];
ENDLOOP};
lastTerminal ← sInfIndex-1;
aliasIndex ← 0;
IF Directive[aliases] THEN {
symIndex ← leftIndex;
DO
GetText[];
IF Directive[productions] THEN EXIT;
FOR i: CARDINAL IN [leftIndex..symIndex) DO
IF aliasIndex=CARDINAL[cpw]*LENGTH[aliasText] THEN aliasText ← LOOPHOLE[
Expand[LOOPHOLE[aliasText],SIZE[CARDINAL],LENGTH[aliasText]/8]];
aliasText[aliasIndex] ← symString[i]; aliasIndex ← aliasIndex+1;
ENDLOOP;
aliasText[aliasIndex] ← ' ; aliasIndex ← aliasIndex+1; symIndex ← leftIndex;
GetText[];
FOR i: CARDINAL IN [leftIndex..symIndex) DO
IF aliasIndex=CARDINAL[cpw]*LENGTH[aliasText] THEN aliasText ← LOOPHOLE[
Expand[LOOPHOLE[aliasText],SIZE[CARDINAL],LENGTH[aliasText]/8]];
aliasText[aliasIndex] ← symString[i]; aliasIndex ← aliasIndex+1;
ENDLOOP;
aliasText[aliasIndex] ← ' ; aliasIndex ← aliasIndex+1; symIndex ← leftIndex;
ENDLOOP};
IF ~Directive[productions] THEN Error[];
symIndex ← leftIndex; nextProd ← 1; nextRhsChar ← 0;
GetText[]; topSymbol ← FindText[];
DO -- exit from this loop on EndOfFIle, topSymbol distinguishes cases
GetText[];
IF symString[leftIndex] = ': AND symString[leftIndex+1] = ':
AND symString[leftIndex+2] = '= THEN {
i, oldi: CARDINAL ← 0;
IF symIndex-leftIndex=4 AND symString[leftIndex+3]='C THEN chain ← TRUE
ELSE IF symIndex-leftIndex=3 THEN chain ← FALSE ELSE GOTO notlhs;
symIndex ← leftIndex;
pInfo[nextProd] ← [rule,chain,0,nextRhsChar];
IF (i ← sInfo[topSymbol].lhsHead)=0 THEN sInfo[topSymbol].lhsHead ← nextProd ELSE {
WHILE i#0 DO oldi ← i; i ← pInfo[i].link ENDLOOP;
pInfo[oldi].link ← nextProd};
nextProd ← nextProd+1;
IF nextProd=LENGTH[pInfo] THEN
pInfo ← LOOPHOLE[Expand[pInfo,SIZE[PGSTypes.PInfoRec],LENGTH[pInfo]/8]];
topSymbol ← 0; GetText[]; topSymbol ← FindText[];
LOOP
EXITS notlhs => NULL};
rhsText[nextRhsChar] ← topSymbol; nextRhsChar ← nextRhsChar+1;
IF nextRhsChar = LENGTH[rhsText] THEN
rhsText ← LOOPHOLE[Expand[rhsText, SIZE[CARDINAL], LENGTH[rhsText]/8] ];
topSymbol ← FindText[];
ENDLOOP};
Format: PUBLIC PROC [table, type, export: Strings.String] = {
zone: UNCOUNTED ZONE ← AcquireZone[];
nextRule ← 0; symIndex ← 0;
hashChain ← zone.NEW[PGSTypes.HashHeads ← ALL[0]];
rhsText ← LOOPHOLE[MakeArray[maxRhsSymbols+1,SIZE[CARDINAL]]];
sInfo ← LOOPHOLE[MakeArray[symTabSize+1,SIZE[PGSTypes.SInfoRec]]];
pInfo ← LOOPHOLE[MakeArray[maxProd+1,SIZE[PGSTypes.PInfoRec]]];
symString ← LOOPHOLE[MakeArray[500,SIZE[CARDINAL]]];
aliasText ← LOOPHOLE[MakeArray[100,SIZE[CARDINAL]]];
Formatter[table, type, export
! EndOfFile => {CONTINUE}; -- always returns via catchphrase
UNWIND => {zone.FREE[@hashChain]; ReleaseZone[zone]}];
zone.FREE[@hashChain];
IF topSymbol#0 THEN {
rhsText[nextRhsChar] ← topSymbol; nextRhsChar ← nextRhsChar+1};
sInfo[sInfIndex].symPtr ← symIndex;
pInfo[nextProd].rhsPtr ← nextRhsChar;
ReleaseZone[zone]};
PrintGrammar: PUBLIC PROC = {
i, p, s, listIndex: CARDINAL;
list: PGSTypes.SInfo;
PrintToken: PROC [i: CARDINAL] RETURNS [length: CARDINAL←0] = {
FOR j: CARDINAL IN [sInfo[i].symPtr..sInfo[i+1].symPtr) DO
outchar[symString[j],1]; length ← length+1 ENDLOOP;
RETURN};
PrintSymbol: PROC [i: CARDINAL] = {
outnum[s, 3]; s ← s+1; outchar[' , 2]; [] ← PrintToken[i]; outeol[1]};
PrintProd: PROC [i, p: CARDINAL, first: BOOL] = {
outnum[s,3]; s ← s+1;
outstring[IF pInfo[p].chain THEN " C "L ELSE " "L];
outnum[pInfo[p].rule,3]; outchar[' ,2];
outchar[' ,tokenSize-(IF first THEN PrintToken[i] ELSE 0)];
outstring[IF first THEN " ::= "L ELSE " | "L];
FOR j: CARDINAL IN [pInfo[p].rhsPtr..pInfo[p+1].rhsPtr) DO
[] ← PrintToken[rhsText[j]]; outchar[' , 1] ENDLOOP;
outeol[1]};
outstring["-- grammar extracted from "L]; outstring[sourceName];
outstring[" by PGS, "L]; outtime[]; outeol[2];
outstring["||CHAIN ||LISTS\n\n"L];
outstring["||TABLE1\n"L]; s ← 1;
IF lastTerminal=1 THEN
FOR i IN [2..sInfIndex) DO IF sInfo[i].lhsHead=0 THEN PrintSymbol[i] ENDLOOP
ELSE
FOR i IN [2..lastTerminal] DO PrintSymbol[i] ENDLOOP;
outnum[s, 3]; s ← s+1; outstring[" eof\n\n"L];
outstring["||TABLE2\n"L];
PrintSymbol[1]; p ← 1;
FOR i IN (lastTerminal..sInfIndex) DO
IF sInfo[i].lhsHead#0 THEN {PrintSymbol[i]; p ← p+1} ENDLOOP;
IF aliasIndex # 0 THEN {
state: {init, id1, sp, id2} ← init;
nc: CARDINAL ← 0;
outstring["\n\n||TABLE3\n"L];
FOR i IN [0..aliasIndex) DO
c: CHAR = aliasText[i];
IF c # ' THEN {
outchar[c, 1]; nc ← nc+1;
state ← SELECT state FROM
init => id1, sp => id2, ENDCASE => state}
ELSE SELECT state FROM
id1 => {outchar[' , tokenSize-nc]; nc ← 0; state ← sp};
id2 => {outeol[1]; nc ← 0; state ← init};
ENDCASE;
ENDLOOP;
IF state # init THEN outeol[1]};
outstring["\n\n||TABLE4\n\n"L]; s ← 1;
list ← MakeArray[p,SIZE[PGSTypes.SInfoRec]];
p ← sInfo[1].lhsHead; list[0] ← [1,pInfo[p].rule,p]; listIndex ← 1;
FOR i IN (lastTerminal..sInfIndex) DO
IF (p ← sInfo[i].lhsHead)#0 THEN {
list[listIndex] ← [i,pInfo[p].rule,p]; listIndex ← listIndex+1};
ENDLOOP;
FOR i DECREASING IN [0..LENGTH[list]) DO
noSwap: BOOL ← TRUE;
FOR p IN [0..i) DO
IF list[p].link>list[p+1].link THEN {
t: PGSTypes.SInfoRec ← list[p];
list[p] ← list[p+1]; list[p+1] ← t; noSwap ← FALSE};
ENDLOOP;
IF noSwap THEN EXIT;
ENDLOOP;
FOR i IN [0..LENGTH[list]) DO
p ← list[i].lhsHead; PrintProd[list[i].symPtr,p,TRUE]; p ← pInfo[p].link;
WHILE p#0 DO PrintProd[0,p,FALSE]; p ← pInfo[p].link ENDLOOP;
outeol[1];
ENDLOOP;
FreeArray[list]; FreeArray[rhsText];
FreeArray[sInfo]; FreeArray[pInfo];
FreeArray[LOOPHOLE[symString]]; FreeArray[LOOPHOLE[aliasText]]};
-- text input routines
char: CHAR; -- current (most recently scanned) character
EndOfFile: SIGNAL = CODE;
GetText: PROC = {
c: CHAR;
WHILE char IN [0c..' ] DO
IF char=ControlZ THEN
WHILE char#'\n DO outchar[char,1]; NextChar[]; ENDLOOP;
outchar[char,1];
IF char='\n THEN {
WHILE char IN [0c..' ] DO NextChar[]; outchar[char,1] ENDLOOP;
c ← char; NextChar[]; outchar[char,1];
IF c#char OR c#'- THEN {NextChar[]; FindHeader[]}};
NextChar[];
ENDLOOP;
leftIndex ← symIndex;
WHILE char NOT IN [0c..' ] DO
outchar[char,1];
IF symIndex=CARDINAL[cpw]*LENGTH[symString] THEN symString ← LOOPHOLE[
Expand[LOOPHOLE[symString],SIZE[CARDINAL],LENGTH[symString]/8]];
symString[symIndex] ← char; symIndex ← symIndex+1; NextChar[];
ENDLOOP};
FindHeader: PROC = {
bIndex, i, k: CARDINAL;
buffer: STRING = [2000]; -- line assembly area
BufferOverflow: ERROR = CODE;
PutChar: PROC = {
IF bIndex = buffer.maxlength THEN ERROR BufferOverflow;
buffer[bIndex] ← char; bIndex ← bIndex+1; NextChar[]};
DO {
bIndex ← 0;
WHILE char IN [0c..' ] DO
IF char = '\n OR char = ControlZ THEN GOTO copyline; PutChar[];
ENDLOOP;
IF char NOT IN ['0..'9] AND char # query THEN GOTO copyline; PutChar[];
WHILE char IN ['0..'9] DO PutChar[] ENDLOOP;
WHILE char IN [0c..' ] DO
IF char = '\n OR char = ControlZ THEN GOTO copyline; PutChar[];
ENDLOOP;
IF char # '= THEN GOTO copyline; PutChar[];
IF char # '> THEN GOTO copyline; PutChar[];
WHILE char IN [0c..' ]
DO IF char='\n OR char=ControlZ THEN GOTO copyline; PutChar[];
ENDLOOP;
IF char # '- THEN GOTO copyline; PutChar[];
IF char # '- THEN GOTO copyline;
FOR i ← bIndex-1, i-1 WHILE buffer[i] # '= DO NULL ENDLOOP;
k ← 0;
FOR j: CARDINAL IN [0..i) DO k ← IF buffer[j] = '\t THEN k+8 ELSE k+1 ENDLOOP;
outnum[nextRule,k-2]; rule ← nextRule; nextRule ← nextRule+1;
outchar[' ,2]; FOR j: CARDINAL IN [i..bIndex) DO outchar[buffer[j],1] ENDLOOP;
outchar['-,1];
RETURN
EXITS
copyline => {
FOR i: CARDINAL IN [0..bIndex) DO outchar[buffer[i],1] ENDLOOP;
outchar[char,1];
WHILE char # '\n DO NextChar[]; outchar[char,1] ENDLOOP;
NextChar[]}};
ENDLOOP};
NextChar: PROC = {
ended: BOOL;
[char, ended] ← inchar[];
IF ended THEN SIGNAL EndOfFile[]};
ScanInit: PROC = {
[char, ] ← inchar[];
FindHeader[]; NextChar[]};
}.