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 EXPORTS NPGSConDefs = { sInfIndex: CARDINAL _ 0; aliasIndex, lastTerminal: CARDINAL; symString: REF TEXT; aliasText: REF TEXT; sInfo: NPGSTypes.SInfo; pInfo: NPGSTypes.PInfo; rhsText: NPGSTypes.RhsChar; 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-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]; }; 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; 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; }; 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[]; }; 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; }; }. Έ NPGSFormat.mesa Copyright Σ 1985, 1988, 1990 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 shared global state (set by Format, used by PrintGrammar) grammar extraction and source rewriting new symbol text input routines grammar output Κ6– "cedar" style•NewlineDelimiter ™šœ™JšœH™HJšœ.™.Jšœ™Jšœ$™$Jšœ1™1Jšœ™—J™šΟk ˜ Jšœ œΟ˜ΰJšœ œ<˜KJšœœ˜!Jšœœœœ˜)—J˜šΟn œœ˜Jšœ˜"šœ˜J˜—J˜Jšœ9™9Jšœ  œ˜Jšœœ˜#Jšœ œœ˜Jšœ œœ˜J˜J˜J˜J˜J˜Jšœ'™'Jšœ7 œ˜DJšœ œ˜J˜Jšœ œ@˜MJ˜Jšœ œ5˜DJš œ œ œœ œ˜9J˜7J˜šžœœ˜Jšœ œ˜Jšœœ œ˜Jšœ œ˜Jšœ œ˜Jšœ˜J˜—J˜šž œœœœ˜/Jšœ*œ˜NJšœœ˜šœœœ˜,Jšœ<œœœ˜PJšœ˜—Jšœœ˜ J˜—J˜šžœœœœ˜$Jšœœ˜Jš œœœœœœ˜FJ˜ J˜Jšœ'˜-J˜—J˜Jšœ$œ˜(J˜šžœœœœ˜$Jšœ œ˜Jšœ3œœ œ˜NJ˜šœ˜ šœ8œΟc˜OJ˜šœœ˜!Jšœœœ˜'J˜Jš˜Jšœ.œ˜AJš˜—J˜—J˜Jšœ˜—Jšœ ™ J˜/J˜J˜J˜$Jšœ˜J˜7Jšœ˜J˜—J˜š ž œœœ!œœ˜GJ˜šž œœ˜J˜(š˜J˜ Jšœœœ˜PJšœœ˜ J˜Jš˜—J˜—J˜šž œœ˜šœœœ˜J˜6J˜J˜—J˜š˜J˜ Jšœœœ˜$Jš œœœœœ˜IJ˜ J˜(J˜ Jš œœœœœ˜IJ˜ J˜(Jšœ˜—J˜—J˜šž œœ˜Jšœœ˜ J˜J˜ J˜J˜ J˜šœŸB˜EJ˜ Jšœœ˜<šœœ˜&Jšœ œ˜Jšœœ˜5šœ ˜Jš œœœ œœœ˜A—J˜(J˜-Jšœ!˜#šœ$˜(šœ˜Jšœœœ˜1—J˜J˜—J˜Jšœ˜J˜7J˜1Jš˜Jšœ ˜J˜—J˜>Jšœ˜$J˜?J˜Jš˜—J˜—J˜J˜RJ˜^J˜ šœ˜J˜ šœœ˜-Jšœœœ˜0Jšœœœ˜4Jšœœ˜ —Jšœ˜—J˜šœœ˜J˜J˜ J˜J˜J˜—Jšœ ˜ J˜ J˜Jšœœ˜,J˜J˜Jšœœ ˜(Jšœ˜Jšœœ˜,Jšœ ˜ J˜—J˜š žœœœœœ˜@J˜ J˜ Jšœ œœ˜.J˜?J˜8J˜5Jšœ œœ˜Jšœ œœ˜˜=Jšœœœ˜—Jšœ œ˜šœ œ˜J˜!J˜J˜—J˜#J˜%J˜—J˜J˜Jšœ™Jšœ œŸ,˜=Jšž œœœ˜J˜Jšœœ˜Jšœœ˜J˜šžœœ˜Jšœœ˜šœœ ˜Jšœ Ÿœ˜Jšœœ*œ˜RJ˜šœœ˜ Jšœœ œ)œ˜MJ˜2Jšœœœ˜1J˜—J˜ Jšœ˜—J˜šœœœ ˜ J˜J˜6J˜J˜ Jš˜—J˜—J˜šž œœ œœ˜,J˜%J˜—J˜šž œœ˜Jšœœ˜Jšœ œ˜Jš œœœœœŸ˜?Jšžœœœ˜J˜šžœœ˜Jšœœœ˜0J˜J˜J˜ J˜—J˜š˜˜J˜ šœœ ˜Jš œ œ œŸœœœ˜OJšœ˜—Jš œœœ œœœ˜SJšœœ œ œ˜,šœœ ˜Jš œ œ œ Ÿœœœ˜MJšœ˜—Jšœ œœ˜+Jšœ œœ˜+Jšœœ ˜šœœ œ œ Ÿœœœ˜PJšœ˜—Jšœ œœ˜+Jšœ œœ ˜ Jš œœœœœ˜;J˜Jšœœœœœœœœ˜NJ˜IJš œœœœ œ"œ˜fJ˜Jš˜Jš˜˜ Jš œœœ œ"œ˜KJ˜Jšœœ)œ˜UJ˜ J˜—J˜—Jš˜—J˜—J˜šžœœ˜Jšœœ˜ J˜%Jšœœœ ˜!J˜—J˜šžœœ˜J˜ J˜ J˜ J˜—J˜Jšœ™šž œœœ˜Jšœœ˜J˜J˜š ž œœœœ œ˜?šœœœ&˜:J˜$J˜Jšœ˜—J˜—J˜šž œœœ˜"J˜J˜$J˜*J˜—J˜šž œœœ œ˜0J˜!Jšœœœœ˜?J˜?Jšœ.œœœ˜SJšœœœ œ ˜:šœœœ&˜:Jšœ8œ˜@—J˜J˜—J˜J˜dJ˜TJ˜J˜-J˜J˜+Jšœ˜Jš˜Jš œœœœœ˜LJš˜Jšœœœœ˜5J˜FJ˜J˜$J˜šœœ˜%Jšœœ˜5Jšœ˜—J˜šœœ˜J˜#Jšœœ˜J˜(šœœ˜Jšœœ˜šœœ˜J˜J˜ šœœ˜Jšœœ ˜)—J˜—šœœ˜J˜OJ˜5Jšœ˜—Jšœ˜—Jšœœ˜+J˜—J˜J˜2J˜ J˜Cšœœ˜%šœœ˜"J˜>J˜—Jšœ˜—šœ œœ˜'Jšœœœ˜šœœ˜šœœ˜%J˜ Jšœ-˜2J˜—Jšœ˜—Jšœœœ˜Jšœ˜—šœœ˜Jšœ0œ˜IJšœœœœ˜=J˜Jšœ˜—Jšœœ˜ Jšœ œ˜Jšœœ˜ Jšœœ˜ Jšœ œ˜Jšœ œ˜J˜—J˜J˜—J˜—…—+‚;p