NPGSFormat.mesa
Copyright Ó 1985, 1988, 1990, 1992 by Xerox Corporation. All rights reserved.
Satterthwaite, October 16, 1985 5:38:49 pm PDT
Maxwell, August 9, 1983 9:38 am
Wyatt, March 29, 1984 2:45:26 pm PST
Russ Atkinson (RRA) March 17, 1988 9:56:03 am PST
JKF May 24, 1990 3:38:56 pm PDT
Michael Plass, December 10, 1992 9:51 pm PST
DIRECTORY
NPGSConDefs USING [ExpandPInfo, ExpandRhsChar, ExpandSInfo, inchar, MakePInfo, MakeRhsChar, MakeSInfo, maxProd, maxRhsSymbols, outchar, outeol, outnum, outstring, outtime, NPGSFail, query, sourceName, symTabSize, tokenSize],
NPGSTypes USING [HashHeads, HashHeadsRef, PInfo, RhsChar, SInfo, SInfoRec],
RefText USING [InlineAppendChar],
Rope: TYPE USING [Fetch, FromProc, ROPE];
NPGSFormat:
CEDAR
PROGRAM
IMPORTS NPGSConDefs, RefText, Rope
shared global state (set by Format, used by PrintGrammar)
sInfIndex: CARDINAL ¬ 0;
aliasIndex, lastTerminal: CARDINAL;
symString: REF TEXT;
aliasText: REF TEXT;
sInfo: NPGSTypes.SInfo;
pInfo: NPGSTypes.PInfo;
rhsText: NPGSTypes.RhsChar;
grammar extraction and source rewriting
leftIndex, symIndex, nextProd, nextRhsChar, topSymbol: CARDINAL ¬ 0;
rule, nextRule: CARDINAL ¬ 0;
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 = {
rhsText ¬ NIL;
sInfo ¬ NIL; pInfo ¬ NIL;
symString ¬ NIL;
aliasText ¬ NIL;
ERROR NPGSConDefs.NPGSFail[];
};
Directive:
PROC[key: KeyWord]
RETURNS[
BOOL] = {
IF symIndex # textKeys[key].len+leftIndex+1 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];
};
GetItem:
PROC
RETURNS[Rope.
ROPE] = {
i: NAT;
p: SAFE PROC RETURNS[c: CHAR] ~ TRUSTED { c ¬ symString[i]; i ¬ i+1 };
GetText[];
i ¬ leftIndex;
RETURN[Rope.FromProc[symIndex-leftIndex, p]];
};
hashChain: NPGSTypes.HashHeadsRef ¬ NIL;
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 => {symString.length ¬ 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 ¬ NPGSConDefs.ExpandSInfo[sInfo, sInfo.length/8];
RETURN[sInfIndex-1];
};
Formatter:
PROC
RETURNS[tableId, typeId, exportId: Rope.
ROPE ¬
NIL] = {
DoTerminals:
PROC ~ {
symString.length ¬ symIndex ¬ leftIndex;
DO
GetText[];
IF symString[symIndex-1] = ': AND (Directive[aliases] OR Directive[productions])
THEN EXIT;
[] ¬ FindText[];
ENDLOOP
};
DoAliases:
PROC ~ {
append:
PROC[char:
CHAR] ~ {
aliasText ¬ RefText.InlineAppendChar[aliasText, char];
aliasIndex ¬ aliasIndex+1;
};
SetTextLength[leftIndex];
DO
GetText[];
IF Directive[productions] THEN EXIT;
FOR i: CARDINAL IN [leftIndex..symIndex) DO append[symString[i]] ENDLOOP;
append[' ];
symString.length ¬ symIndex ¬ leftIndex;
GetText[];
FOR i: CARDINAL IN [leftIndex..symIndex) DO append[symString[i]] ENDLOOP;
append[' ];
symString.length ¬ symIndex ¬ leftIndex;
ENDLOOP;
};
DoProductions:
PROC ~ {
chain: BOOL;
SetTextLength[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;
symString.length ¬ 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 ¬ NPGSConDefs.ExpandPInfo[pInfo, pInfo.length/8];
topSymbol ¬ 0; GetText[]; topSymbol ¬ FindText[];
LOOP
EXITS notlhs => NULL
};
rhsText[nextRhsChar] ¬ topSymbol; nextRhsChar ¬ nextRhsChar+1;
IF nextRhsChar = rhsText.length THEN
rhsText ¬ NPGSConDefs.ExpandRhsChar[rhsText, rhsText.length/8];
topSymbol ¬ FindText[];
ENDLOOP
};
NPGSConDefs.outstring["-- file "]; NPGSConDefs.outstring[NPGSConDefs.sourceName];
NPGSConDefs.outstring[" rewritten by NPGS, "]; NPGSConDefs.outtime[]; NPGSConDefs.outeol[1];
ScanInit[];
DO
GetText[];
IF Directive[$table]
THEN tableId ¬ GetItem[]
ELSE IF Directive[$type] THEN typeId ¬ GetItem[]
ELSE IF Directive[$export] THEN exportId ¬ GetItem[]
ELSE EXIT;
ENDLOOP;
IF Directive[$goal]
THEN {
SetTextLength[0];
GetText[];
sInfIndex ¬ 1;
[] ¬ FindText[];
}
ELSE Error[];
GetText[];
IF Directive[$terminals] THEN DoTerminals[];
lastTerminal ¬ sInfIndex-1;
aliasIndex ¬ 0;
IF Directive[$aliases] THEN DoAliases[];
IF Directive[$productions]
THEN DoProductions[ ! EndOfFile => CONTINUE]
ELSE Error[];
};
Format:
PUBLIC
PROC
RETURNS [table, type, export: Rope.
ROPE] = {
nextRule ¬ 0;
symIndex ¬ 0;
hashChain ¬ NEW[NPGSTypes.HashHeads ¬ ALL[0]];
rhsText ¬ NPGSConDefs.MakeRhsChar[NPGSConDefs.maxRhsSymbols+1];
sInfo ¬ NPGSConDefs.MakeSInfo[NPGSConDefs.symTabSize+1];
pInfo ¬ NPGSConDefs.MakePInfo[NPGSConDefs.maxProd+1];
symString ¬ NEW[TEXT[500]];
aliasText ¬ NEW[TEXT[100]];
[tableId: table, typeId: type, exportId: export] ¬ Formatter[
! UNWIND => hashChain ¬ NIL];
hashChain ¬ NIL;
IF topSymbol#0
THEN {
rhsText[nextRhsChar] ¬ topSymbol;
nextRhsChar ¬ nextRhsChar+1;
};
sInfo[sInfIndex].symPtr ¬ symIndex;
pInfo[nextProd].rhsPtr ¬ nextRhsChar;
};
text input routines
char: CHAR ¬ 0C; -- current (most recently scanned) character
EndOfFile: SIGNAL = CODE;
cr: CHAR = 015C;
nl: CHAR = 012C;
GetText:
PROC = {
c: CHAR;
WHILE char
IN ['\000..' ]
DO
IF char='\032--Z-- THEN
WHILE (char#cr) AND (char#nl) DO NPGSConDefs.outchar[char,1]; NextChar[]; ENDLOOP;
NPGSConDefs.outchar[char,1];
IF (char=cr) OR (char=nl)
THEN {
WHILE char IN ['\000..' ] DO NextChar[]; NPGSConDefs.outchar[char,1] ENDLOOP;
c ¬ char; NextChar[]; NPGSConDefs.outchar[char,1];
IF c#char OR c#'- THEN {NextChar[]; FindHeader[]}
};
NextChar[];
ENDLOOP;
leftIndex ¬ symIndex;
WHILE char
NOT
IN ['\000..' ]
DO
NPGSConDefs.outchar[char,1];
symString ¬ RefText.InlineAppendChar[symString, char];
symIndex ¬ symIndex+1;
NextChar[];
ENDLOOP
};
SetTextLength:
PROC [newLen:
NAT] =
INLINE {
symString.length ¬ symIndex ¬ newLen;
};
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 = cr OR char = nl OR char = '\032 --Z-- THEN GOTO copyline; PutChar[];
ENDLOOP;
IF char NOT IN ['0..'9] AND char # NPGSConDefs.query THEN GOTO copyline; PutChar[];
WHILE char IN ['0..'9] DO PutChar[] ENDLOOP;
WHILE char
IN ['\000..' ]
DO
IF char = cr OR char = nl 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 = cr
OR char = nl
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;
NPGSConDefs.outnum[nextRule,k-2]; rule ¬ nextRule; nextRule ¬ nextRule+1;
NPGSConDefs.outchar[' ,2]; FOR j: CARDINAL IN [i..bIndex) DO NPGSConDefs.outchar[buffer[j],1] ENDLOOP;
NPGSConDefs.outchar['-,1];
RETURN
EXITS
copyline => {
FOR i: CARDINAL IN [0..bIndex) DO NPGSConDefs.outchar[buffer[i],1] ENDLOOP;
NPGSConDefs.outchar[char,1];
WHILE (char # cr) AND (char # nl) DO NextChar[]; NPGSConDefs.outchar[char,1] ENDLOOP;
NextChar[];
};
};
ENDLOOP
};
NextChar:
PROC = {
ended: BOOL;
[char, ended] ¬ NPGSConDefs.inchar[];
IF ended THEN SIGNAL EndOfFile[];
};
ScanInit:
PROC = {
[char, ] ¬ NPGSConDefs.inchar[];
FindHeader[];
NextChar[];
};
grammar output
PrintGrammar:
PUBLIC
PROC = {
i, p, s, listIndex: CARDINAL;
list: NPGSTypes.SInfo;
PrintToken:
PROC [i:
CARDINAL]
RETURNS [length:
CARDINAL¬0] = {
FOR j:
CARDINAL
IN [sInfo[i].symPtr..sInfo[i+1].symPtr)
DO
NPGSConDefs.outchar[symString[j],1];
length ¬ length+1;
ENDLOOP;
};
PrintSymbol:
PROC[i:
CARDINAL] = {
NPGSConDefs.outnum[s, 3];
s ¬ s+1; NPGSConDefs.outchar[' , 2];
[] ¬ PrintToken[i]; NPGSConDefs.outeol[1];
};
PrintProd:
PROC[i, p:
CARDINAL, first:
BOOL] = {
NPGSConDefs.outnum[s,3]; s ¬ s+1;
NPGSConDefs.outstring[IF pInfo[p].chain THEN " C " ELSE " "];
NPGSConDefs.outnum[pInfo[p].rule,3]; NPGSConDefs.outchar[' ,2];
NPGSConDefs.outchar[' ,NPGSConDefs.tokenSize-(IF first THEN PrintToken[i] ELSE 0)];
NPGSConDefs.outstring[IF first THEN " ::= " ELSE " | "];
FOR j:
CARDINAL
IN [pInfo[p].rhsPtr..pInfo[p+1].rhsPtr)
DO
[] ¬ PrintToken[rhsText[j]]; NPGSConDefs.outchar[' , 1] ENDLOOP;
NPGSConDefs.outeol[1];
};
NPGSConDefs.outstring["-- grammar extracted from "]; NPGSConDefs.outstring[NPGSConDefs.sourceName];
NPGSConDefs.outstring[" by NPGS, "]; NPGSConDefs.outtime[]; NPGSConDefs.outeol[2];
NPGSConDefs.outstring["||CHAIN ||LISTS\n\n"];
NPGSConDefs.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;
NPGSConDefs.outnum[s, 3]; s ¬ s+1; NPGSConDefs.outstring[" eof\n\n"];
NPGSConDefs.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;
NPGSConDefs.outstring["\n\n||TABLE3\n"];
FOR i
IN [0..aliasIndex)
DO
c: CHAR = aliasText[i];
IF c # '
THEN {
NPGSConDefs.outchar[c, 1];
nc ¬ nc+1;
state ¬
SELECT state
FROM
init => id1, sp => id2, ENDCASE => state;
}
ELSE
SELECT state
FROM
id1 => {NPGSConDefs.outchar[' , NPGSConDefs.tokenSize-nc]; nc ¬ 0; state ¬ sp};
id2 => {NPGSConDefs.outeol[1]; nc ¬ 0; state ¬ init};
ENDCASE;
ENDLOOP;
IF state # init THEN NPGSConDefs.outeol[1];
};
NPGSConDefs.outstring["\n\n||TABLE4\n\n"]; s ¬ 1;
list ¬ NPGSConDefs.MakeSInfo[p];
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: NPGSTypes.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;
NPGSConDefs.outeol[1];
ENDLOOP;
list ¬ NIL;
rhsText ¬ NIL;
sInfo ¬ NIL;
pInfo ¬ NIL;
symString ¬ NIL;
aliasText ¬ NIL;
};
}.