DIRECTORY
ConvertUnsafe: TYPE USING [ToRope],
PGSConDefs:
TYPE
USING [
query,
cpw, maxProd, maxRhsSymbols, symTabSize, tokenSize,
sourceName, zone,
Expand, FreeArray, inchar, MakeArray,
outchar, outeol, outnum, outstring, outtime, PGSFail],
PGSTypes:
TYPE
USING [
HashHeads, HashHeadsRef, RhsChar, PInfo, PInfoRec, SymTab, SInfo, SInfoRec],
Rope: TYPE USING [Fetch, ROPE];
leftIndex, symIndex, nextProd, nextRhsChar, topSymbol: CARDINAL;
rule, nextRule: CARDINAL;
KeyWord: TYPE = {table, type, export, goal, terminals, aliases, productions};
text: Rope.ROPE = "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.Fetch[textKeys[key].index+i] THEN RETURN [FALSE]
ENDLOOP;
RETURN [TRUE]};
ExtractKeyItem:
PROC [key: KeyWord]
RETURNS [directive:
BOOL, value: Rope.
ROPE] = {
IF ~Directive[key]
THEN
RETURN [
FALSE,
NIL]
ELSE {
j: CARDINAL ← 0;
string: STRING = [40];
GetText[];
FOR i:
CARDINAL
IN [leftIndex..symIndex)
DO
string[j] ← symString[i]; j ← j + 1;
ENDLOOP;
string.length ← j;
value ← ConvertUnsafe.ToRope[string]};
RETURN [TRUE, value]};
hashChain: PGSTypes.HashHeadsRef;
FindText:
PROC
RETURNS [
CARDINAL] = {
h, i, j, k: CARDINAL;
h ← (256*(symIndex-leftIndex)+symString[leftIndex].ORD) MOD hashChain^.LENGTH;
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=sInfo.
LENGTH
THEN
sInfo ← LOOPHOLE[Expand[sInfo,PGSTypes.SInfoRec.SIZE,sInfo.LENGTH/8]];
RETURN [sInfIndex-1]};
Formatter:
PROC [tableId, typeId, exportId: Rope.
ROPE] = {
chain: BOOL;
outstring["-- file "]; outstring[sourceName];
outstring[" rewritten by PGS, "]; outtime[]; outeol[1];
ScanInit[];
DO
directive: BOOLEAN ← FALSE;
GetText[];
[directive, tableId] ← ExtractKeyItem[table];
IF ~directive THEN [directive, tableId] ← ExtractKeyItem[type];
IF ~directive THEN [directive, typeId] ← ExtractKeyItem[type];
IF ~directive THEN [directive, exportId] ← ExtractKeyItem[export];
IF ~directive THEN 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]*aliasText.
LENGTH
THEN aliasText ←
LOOPHOLE[
Expand[LOOPHOLE[aliasText],CARDINAL.SIZE,aliasText.LENGTH/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]*aliasText.
LENGTH
THEN aliasText ←
LOOPHOLE[
Expand[LOOPHOLE[aliasText],CARDINAL.SIZE,aliasText.LENGTH/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=pInfo.
LENGTH
THEN
pInfo ← LOOPHOLE[Expand[pInfo,PGSTypes.PInfoRec.SIZE,pInfo.LENGTH/8]];
topSymbol ← 0; GetText[]; topSymbol ← FindText[];
LOOP
EXITS notlhs => NULL};
rhsText[nextRhsChar] ← topSymbol; nextRhsChar ← nextRhsChar+1;
IF nextRhsChar = rhsText.
LENGTH
THEN
rhsText ← LOOPHOLE[Expand[rhsText, CARDINAL.SIZE, rhsText.LENGTH/8] ];
topSymbol ← FindText[];
ENDLOOP};
Format:
PUBLIC
PROC [table, type, export: Rope.
ROPE] = {
nextRule ← 0; symIndex ← 0;
hashChain ← zone.NEW[PGSTypes.HashHeads ← ALL[0]];
rhsText ← LOOPHOLE[MakeArray[maxRhsSymbols+1,CARDINAL.SIZE]];
sInfo ← LOOPHOLE[MakeArray[symTabSize+1,PGSTypes.SInfoRec.SIZE]];
pInfo ← LOOPHOLE[MakeArray[maxProd+1,PGSTypes.PInfoRec.SIZE]];
symString ← LOOPHOLE[MakeArray[500,CARDINAL.SIZE]];
aliasText ← LOOPHOLE[MakeArray[100,CARDINAL.SIZE]];
Formatter[table, type, export
! EndOfFile => {
CONTINUE};
-- always returns via catchphrase
UNWIND => {zone.FREE[@hashChain]}];
zone.FREE[@hashChain];
IF topSymbol#0
THEN {
rhsText[nextRhsChar] ← topSymbol; nextRhsChar ← nextRhsChar+1};
sInfo[sInfIndex].symPtr ← symIndex;
pInfo[nextProd].rhsPtr ← nextRhsChar};
char: CHAR; -- current (most recently scanned) character
EndOfFile: SIGNAL = CODE;
GetText:
PROC = {
c: CHAR;
WHILE char
IN ['\000..' ]
DO
IF char='\032
--^Z--
THEN
WHILE char#'\n DO outchar[char,1]; NextChar[]; ENDLOOP;
outchar[char,1];
IF char='\n
THEN {
WHILE char IN ['\000..' ] 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 ['\000..' ]
DO
outchar[char,1];
IF symIndex=
CARDINAL[cpw]*symString.
LENGTH
THEN symString ←
LOOPHOLE[
Expand[LOOPHOLE[symString],CARDINAL.SIZE,symString.LENGTH/8]];
symString[symIndex] ← char; symIndex ← symIndex+1; NextChar[];
ENDLOOP};
FindHeader:
PROC = {
bIndex, i, k: CARDINAL;
maxLength: CARDINAL = 2000;
buffer: REF TEXT ← NEW[TEXT[maxLength]]; -- line assembly area
BufferOverflow: ERROR = CODE;
PutChar:
PROC = {
IF bIndex = maxLength THEN ERROR BufferOverflow;
buffer[bIndex] ← char; bIndex ← bIndex+1; NextChar[]};
DO {
bIndex ← 0;
WHILE char
IN ['\000..' ]
DO
IF char = '\n OR char = '\032 --^Z-- 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 ['\000..' ]
DO
IF char='\n OR char='\032 --^Z-- THEN GOTO copyline; PutChar[];
ENDLOOP;
IF char # '= THEN GOTO copyline; PutChar[];
IF char # '> THEN GOTO copyline; PutChar[];
WHILE char
IN ['\000..' ]
DO IF char='\n OR char='\032 --^Z-- 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[]};
PrintGrammar:
PUBLIC
PROC = {
i, p, s, listIndex: CARDINAL;
list: PGSTypes.SInfo;
PrintToken:
PROC [i:
CARDINAL]
RETURNS [length:
CARDINAL𡤀] = {
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 " ELSE " "];
outnum[pInfo[p].rule,3]; outchar[' ,2];
outchar[' ,tokenSize-(IF first THEN PrintToken[i] ELSE 0)];
outstring[IF first THEN " ::= " ELSE " | "];
FOR j:
CARDINAL
IN [pInfo[p].rhsPtr..pInfo[p+1].rhsPtr)
DO
[] ← PrintToken[rhsText[j]]; outchar[' , 1] ENDLOOP;
outeol[1]};
outstring["-- grammar extracted from "]; outstring[sourceName];
outstring[" by PGS, "]; outtime[]; outeol[2];
outstring["||CHAIN ||LISTS\n\n"];
outstring["||TABLE1\n"]; 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"];
outstring["||TABLE2\n"];
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"];
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"]; s ← 1;
list ← MakeArray[p,PGSTypes.SInfoRec.SIZE];
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..list.
LENGTH)
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..list.
LENGTH)
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]]};
}.