Trailing-Edge
-
PDP-10 Archives
-
decuslib10-03
-
43,50306/graph.imc
There are 2 other files named graph.imc in the archive. Click here to see a list.
TWOSEG;
#THIS IS FILE GRAPH.I10, GRAPH CREATION AND ACCESS MODULE FOR IMP COMPILERS.
THE SYNTAX GRAPH IS KEPT IN NODES OF NS WORDS EACH IN A FREE STORAGE ARRAY
POINTED TO BY GA. THE FIRST NODE IS AT 1, THE LAST NODE IS AT NG. THE ARRAY
IS INITIALIZED WITH A FREE NODE, SO THAT NG>0 IS ALWAYS TRUE.
IN ORDER TO REFER TO NODES BY INTEGERS 1,2,3... (FOR THE CONNECTIVITY
MATRICES) THE NODE AT 1+NS*(N-1) IS ASSIGNED THE NODE NUMBER N.
THE FORMAT FOR GRAPH NODES IS:
WD. 0 BITS 0-17 INDEX OF SCR (SUCCESSOR, RIGHT LINK) OR 0.
BITS 18-35 INDEX OF ALT (ALTERNATE, DOWN LINK) OR 0
WD. 1 BITS 0-2 TYPE: 0=NONTERMINAL NODE
1=TERMINAL NODE
2=CIRCLED NONTERMINAL NODE
3=BOXED PRODUCTION NODE
5=NODE ON CHAIN OF TERMINAL ENTRY POINTS
BITS 3-17 FOR CIRCLED NONTERMINAL NODES, AND NONTERMINAL AND
TERMINAL NODES IMMEDIATELY FOLLOWING A CIRCLED NT NODE,
A ROW INDEX FOR THAT NODE IN THE BIT MATRIX NBITM.
BITS 18-35 PRODUCTION NODES: NUMBER OF PRODUCTION
NONTERMINAL AND TERMINAL NODES: DIR INDEX OF NAME
THE GRAPH ENTRY SUBROUTINE, GENT, ASSIGNS THE 15-BIT PROPERTY 'NODE' TO
ALL TERMINALS AND NON-TERMINALS IT ENCOUNTERS. FOR THE NON-TERMINALS,
IT IS JUST A SERIAL NUMBER; NTGENT HOLDS THE NEXT ONE TO BE ASSIGNED.
FOR THE TERMINALS, IT IS A POINTER TO AN ENTRY IN THE FREE STORAGE ARRAY
POINTED TO BY NODES (AND NUMBERED BY NNODES). 0 IS NOT USED FOR 'NODE'
TO ALLOW THE ABSENCE OF THE PROPERTY TO BE DISTINGUISHED.
GENT ALSO ASSIGNS THE 18-BIT PROPERTY 'ENTRY' WHICH IS THE GA INDEX OF THE
ENTRY POINT (FOR TERMINALS WHICH HAVE ONE) OR CIRCLED NODE (FOR NON-TERMS).
NODES HOLDS INFORMATION TELLING AT WHICH GRAPH NODE A TERMINAL MAY BE REQUIRED.
BITS 18-35 HOLD THE NODE INDEX OF A NODE REQUIRING THE TERMINAL,
BITS 0-17, IF NE 0, ARE THE INDEX IN NODES OF NEXT ENTRY FOR THE TERMINAL.
THE ROUTINES WHICH FIDDLE WITH THE GRAPH ARE:
GRAPH(SYNT,NSYNT,PN) - ENTERS A PRODUCTION IN THE GRAPH. SYNT IS A FREE
STORAGE ARRAY CONTAINING NSYNT DIR INDICES. PN IS THE PRODUCTION
NUMBER (OR 0 IF NONE NEEDED.) SYNT[0] IS THE NON-TERMINAL PRODUCED,
AND SYNT[1]-SYNT[NSYNT] ARE THE TERMINALS AND NON-TERMINALS OF THE
PRODUCTION.
GMATR() - REMAKES THE CONNECTIVITY MATRIX NBITM AND ASSIGNS INDEXES.
BITM<N,CN> INDICATES WHETHER YOU CAN GET TO CIRCLED NODE CN FROM
NODE N (NODE NUMBERS, NOT INDICES). NBITM INDICATES THE SAME
THING, EXCEPT THE PATH MUST BE VIA ONLY CIRCLED OR BOXED NODES,
AND N IS THE SPECIAL NBITM INDEX FOR THE NODE. CN IS A NT NUMBER.
GGOAL(NT) - MAKES A SPECIAL NODE FOR NONTERMINAL WITH DIR INDEX NT,
POINTING TO ITSELF. ONLY ONE SUCH WILL BE AROUND AT ANY TIME.
THE PARSER NEEDS SUCH A NODE TO START OFF.
GTYPE(N) - TYPE OF GRAPH NODE INDEX N
GVAL(N) - THE VALUE (NAME) OF NODE N
GNB(N) - THE NBITM ROW INDEX (BITS 3-17) OF NODE N
GALT(N,GOAL) - THE NEXT ALTERNATE OF NODE N LEADING TO THE NONTERMINAL
GOAL (OR 0 IF NONE).
GNEXT(N,GOAL) - EITHER N OR ITS FIRST ALTERNATE LEADING TO GOAL
GCONN(N,GOAL) - 0 OR 1; WHETHER NODE N CONNECTS TO NT GOAL
GMADE(C,GO) - 0 OR 1; WHETHER AT CIRCLED NODE C WE HAVE MADE GOAL GO.
GNT2T(NT,NI,GOAL,NODE) - SETS NODE TO THE NEXT GRAPH NODE WHERE THE
TERMINAL SYMBOL IS REQUIRED IMMEDIATELY FOLLOWING THE CIRCLED NODE OF
NONTERMINAL NT. NI IS THE POINTER INTO THE CHAIN OF REFERENCES
FOR THE TERMINAL IN NODES, AND IS UPDATED (MAYBE TO 0).
GNT2TX(NT,NI,GOAL,NODE) - IS A SPEEDED-UP VERSION OF GNT2T.
GLEAP(NT,NO) - 1 IF TERMINAL NODE NO IMMEDIATELY FOLLOWS NONTERMINAL .
NT'S CIRCLED NODE.
GENTRY(0) - START OF THE CHAIN OF TERMINAL ENTRY POINTS
SCR(N) - SUCCESSOR OF NODE N.
ALT(N) - ALTERNATE OF NODE N.
GPOUT1 AND GPOUT2 - PUT OUT PRODUCTION NUMBERS ALONG A PATH WHICH THE
PARSER KNOWS EXISTS AND, THEREFORE, DOESN'T TRAVERSE ITSELF.#
<ATOM>::=NS::="2"; #NS IS SIZE OF A GRAPH NODE #
<EXP> ::= <A>/NS::="A RS 1";
SUBR GRAPH(SYNT,NSYNT,PNQ) IS (PNR_PNQ;
NPRODS_PNR;
INIT=0=>(INIT_1;
FRELOT(GA,'GRAPH',1300,GORGFIX); FINCSET(GA,50);
FREES(GA+2,700000000000B);
NG_NTGENT_NNODES_NBITN_1;
FRELOT(NODES,'NODES',100,0);
BITM,NBITM ARE 3 LONG;
BITM[1]_625; NBITM[1]_150;
GEPT_0);
MAKING_NEWNO(0,0,2,FREE(SYNT));
MAKENT_DPROP('NODE',FREE(SYNT));
#COMMENCE BY LOOKING FOR ENTRY POINT/CIRCLED NODE FOR FIRST SYMBOL.#
ENT_0;
HOOK_DPROP('ENTRY',FREE(SYNT+1)); HOOKN_1;
HOOK=>(J_GTYPE(HOOK); J=2=>ENT_HOOK);
#IF NO ENTRY POINT, WE WILL HAVE TO ENTER THE WHOLE PRODUCTION - SO MAKE
AN ENTRY POINT, AND THAT BECOMES THE HOOK-ON POINT.#
HOOK=0=>(HOOK_NEWNO(0,0,6,FREE(SYNT+1));
J_GTYPE(HOOK); J=1=>(GEPT_NEWNO(GEPT,HOOK,5,0))
ELSE(GMARK(HOOK); ENT_HOOK);
DPROPS('ENTRY',FREE(SYNT+1),HOOK); GO TO MAKEIT);
#CHECK IF WE CAN EXTEND HOOK-ON POINT FURTHER DOWN PRODUCTION#
CHOOK: GMARK(HOOK);
HOOKN=NSYNT=>GO TO CHECKIT;
NHOOK_SCR(HOOK);
LHOOK: NHOOK=0=>GO TO MAKEIT;
SQ_GVAL(NHOOK);
J_FREE(SYNT+HOOKN+1);
J NE SQ=>(L3:NHOOK_ALT(NHOOK);
GO TO LHOOK);
J_GTYPE(NHOOK); J>1=>GO TO L3;
HOOK_NHOOK; HOOKN_HOOKN+1; GO TO CHOOK;
#CHECK IF DUPLICATE PRODUCTION #
CHECKIT: J_SCR(HOOK);
CK1: J=0=>GO TO MAKEIT;
JJ_GTYPE(J);
JJ=2=>(KK_GVAL(J); GO TO L22);
JJ=3=>(KK_GVAL(SCR(J));
L22: K_FREE(SYNT);
KK=K=>(ERROR(2,'PRODUCTION DUPLICATES ONE ALREADY IN SYNTAX **');
JJ=2=>(# NEEDS PRODUCTION #
# THIS OK BECAUSE CIRCLED NODES CANT HAVE OR BE ALT #
SETSCR(HOOK,NEWNO(J,0,3,PNR));
GO TO GRAPHEX);
NPRODS_GVAL(J);
NPRODS=1=>(FREES(GA+J+1,300000000000B OR PNR); NPRODS_PNR);
GO TO GRAPHEX));
J_ALT(J);
GO TO CK1;
#NOW MAKE A STRING OF NODES OUT OF SYNT[0], PROD. NR., AND SYNT ENTRIES
FROM HOOKN+1 TO NSYNT, IF ANY. CONNECT STRING AS SCR TO HOOK. DONE.#
MAKEIT:
# INSERT PROD'N 1 NODE IF NEEDED TO AVOID ALT TO TYPE 2 NODE #
(HOOKN=NSYNT=>PNR=0=>SCR(HOOK)=>PNR_1);
J_MAKING;
PNR=>(J_NEWNO(0,J,3,PNR));
HOOKN<NSYNT=>((J_NEWNO(0,J,4,FREE(SYNT+K))) FOR K IN NSYNT,-1,HOOKN+1);
SETALT(J,SCR(HOOK));
SETSCR(HOOK,J);
# IF FIRST NODE IN PRODN WAS CIRCLED NODE, WE MUST UPDATE CONNECTIVITY
MATRIX FOR ALL NODES THAT GET TO IT. #
ENT=>(COL_DPROP('NODE',GVAL(ENT));
ROW_1+ENT/NS;
J_1+NG/NS; #G_(GGOAL1 => 1+GGOAL1/NS ELSE 0);#
(#NN NE G=>#BIT(BITM,NN,COL)=>(BIT(BITM,NN,MAKENT);
BITOR(BITM,NN,ROW))) FOR NN IN 1,1,J);
GRAPHEX: FINAM IS COMMON;
FINAM[5] AND 20B => (
PRINT STG 0,'PRODUCTION ENTERED IN GRAPH: ';
PNAME(FREE(SYNT)); PRINT STG 0,' [',OCT 0,NPRODS,STG 0,'] ';
PNAME(FREE(SYNT+I)) FOR I IN 1,1,NSYNT; PRINT /);
NPRODS);
SUBR GORGFIX() IS (GORG,GORG1,GBYPTY,GBYPNB ARE COMMON,1 LONG;
GORG_GA; GORG1_GORG+1;
GBYPTY_BYTEP [GORG1]<3,33>;
GBYPNB_BYTEP [GORG1]<15,18>);
SUBR GPRINT() IS (
LOC(GPRIN1) => J_GPRIN1(NPRODS,GA,NS,NG,NODES,BITM,NTGENT,NBITM,NBITN)
ELSE (GPR0CNT=0=>(GPR0CNT_1; J_0;
ERROR(2,'GPRIN1 DEBUGGING PGM NOT PRESENT')));
J);
SUBR SETSCR(SV,VV) IS (SQ_ALT(SV); FREES(GA+SV,VV OR SQ LS 18));
SUBR SETALT(SV,VV) IS (SQ_SCR(SV); FREES(GA+SV,SQ OR VV LS 18));
SUBR GENTRY() IS GEPT;
SUBR GCONN(Q,QGOAL) IS (QV_0; Q=>QV_BIT(BITM,1+Q/NS,QGOAL); QV);
SUBR GMADE(Q,QGOAL) IS (NBITM[2]=0 => 1 AND FREE(NBITM+GNB(Q)) RS QGOAL
ELSE BIT(NBITM,GNB(Q),QGOAL));
SUBR GGOAL(NT) IS (
GGOAL1_NEWNO(0,0,0,0); SETSCR(GGOAL1,GGOAL1);
BITS(BITM,1+GGOAL1/NS,DPROP('NODE',NT));
FREES(GA+GGOAL1+1,NT); GGOAL1);
SUBR GALT(Q,QGOAL) IS (QQ_Q;
#RETURNS NEXT GRAPH NODE ALT TO Q WHICH CAN REACH GOAL QGOAL#
L8: QQ_ALT(QQ); QQ=>BIT(BITM,1+QQ/NS,QGOAL)=0=>GO TO L8; QQ);
SUBR GNT2T(NT,NI,GL,NO) IS (
L7: NI=0=>(NO_0; GO TO G2X);
J_FREE(NODES+NI); NO_J AND 777777B;
NI_J RS 18;
BIT(BITM,1+NO/NS,GL)=0=>GO TO L7;
GLEAP(NT,NO)=0=>GO TO L7;
G2X: NO);
SUBR GNT2TX(NT,NI,GL,NO) IS (
(MSK1_1 LS GL)=>(MSK2_1 LS NT)=>GO TO GNT1;
GNT2T(NT,NI,GL,NO); GO TO GNTX;
GNT1: NI=0 => (NO_0; GO TO GNTX);
J_FREE(NODES+NI);
NO_J AND 777777B; NI_J RS 18;
(MSK1 AND FREE((BITM+NO RS 1)+1))=0 => GO TO GNT1;
(MSK2 AND FREE(NBITM+GNB(NO)))=0 => GO TO GNT1;
GNTX: NO);
SUBR GLEAP(NT,NO) IS (BIT(NBITM,GNB(NO),NT));
SUBR GNEXT(Q,QGOAL) IS (
(Q0_Q)=0 => RETURN 0;
BITM[2]=0 => (MASK_1 LS QGOAL;
GNE1: Q0 => ((MASK AND FREE((BITM+Q0 RS 1)+1))=0
=> (Q0_ALT(Q0); GO TO GNE1)))
ELSE (GCONN(Q0,QGOAL)=0 => (Q0_GALT(Q0,QGOAL)));
Q0);
SUBR NEWNO(DS,RTS,TYP,ID) IS (
#MAKES A NEW NODE GIVEN DOWN-SUCCESSOR, RIGHT-SUCCESSOR, TYPE AND
DIR INDEX OF NAME. FOR CIRCLED NODE, RETURNS EXISTING ONE IF ANY.
TY=4=>DECIDE FROM NAME IF TYPE SHOULD BE 0 OR 1. TY=6=>DECIDE BETWEEN
1 AND 2.#
TY_TYP;
(TY AND 5)=4=>(NR_DNAME(ID,0); TY_TY AND 3;
(NR AND 774000000000B) NE '#' => TY_1);
PTRS_RTS OR DS LS 18;
(TY AND 1)=0=>(#WE HAVE NONTERMINAL - CHECK IT HAS CIRCLED NODE #
N1_DPROP('ENTRY',ID);
N1=0=>(DPROPS('NODE',ID,NTGENT);
NTGENT_NTGENT+1;
N1_MAKENO((TY=0=>0 ELSE PTRS),2,NBITN,ID);
NBITN_NBITN+1;
DPROPS('ENTRY',ID,N1));
TY=0=>(#WE WANT NON-CIRCLED NODE#
N1_MAKENO(PTRS,TY,0,ID));
GO TO NEWEX);
N1_MAKENO(PTRS,TY,0,ID);
NEWEX: N1);
SUBR MAKENO(MW1,MTY,MNO,MID) IS (
MW2_MID OR (MTY LS 33) OR (MNO LS 18);
MG_NG; FADD(GA,NG,MW1); FADD(GA,NG,MW2);
MTY NE 2=>GMARK(MG) ELSE BITS(BITM,1+MG/NS,DPROP('NODE',MID));
MG);
SUBR GMARK(NO) IS (
IM_1+NO/NS;
BITS(BITM,IM,MAKENT);
BITOR(BITM,IM,1+MAKING/NS));
SUBR GMATR(TFL) IS (
TIN_CALLI(27B,0);
TFL<0=>GO TO GMTRX;
BITZ(NBITM);
NNODES_1;
(J_FREE(GA+NN+1);
(J RS 33)=1=>DPROPS('NODE',J AND 777777B,0)) FOR NN IN 1,NS,NG;
(NN=GGOAL1=>GO TO M2;
J_FREE(GA+NN+1); (J RS 33) NE 2 =>GO TO M2;
PUSHMI(-1);
COL_DPROP('NODE',J AND 777777B);
ROW_77777B AND J RS 18;
BITS(NBITM,ROW,COL);
BITS(BITM,1+NN/NS,COL);
NO_SCR(NN);
M1: NO=0=>(NO_PULLYU(0); NO=-1=>GO TO M2;
ALTERM: NO_ALT(NO); GO TO M1);
NODA_FREE(GA+NO+1); NOTY_NODA RS 33; NOID_NODA AND 777777B;
NOTY=2=>(BITS(NBITM,ROW,DPROP('NODE',NOID));
NO=NN=>GO TO ALTERM);
NOTY=1=>(GRREQ(NOID,NO,NO);
GO TO ALTERM);
NOTY = 0 => (NTNR_DPROP('NODE',NOID);
GNT2B(NO);
K_GEPT;
M3: K=>(J_SCR(K);
BIT(BITM,1+J/NS,NTNR)=>GRREQ(
777777B AND FREE(GA+J+1),NO,J);
K_ALT(K); GO TO M3);
GO TO ALTERM);
PUSHMI(NO);
NO_SCR(NO); GO TO M1;
M2: 0) FOR NN IN 1,NS,NG;
GMTRX: NN_CALLI(27B,0);
TIM_TIM+NN-TIN; TIN_TIM;
TFL<0=>TIM_0;
TIN);
SUBR GRAPHF() IS (
FALLOT(GA,0); FALLOT(NODES,0));
SUBR GRREQ(TN,NNR,ND) IS (
GNT2B(ND);
S_SS_DPROP('NODE',TN);
L9: S=>(S_FREE(NODES+S);
(S AND 777777B)=NNR=>GO TO GRREX;
S_S RS 18; GO TO L9);
DPROPS('NODE',TN,NNODES);
FADD(NODES,NNODES,NNR OR SS LS 18);
GRREX: 0);
SUBR GNT2B(ND) IS (
NDA_FREE(GA+ND+1); NON_77777B AND NDA RS 18;
NON=0=>(NON_NBITN; NBITN_NBITN+1;
FREES(GA+ND+1,NDA OR NON LS 18));
BITS(NBITM,NON,COL));
SUBR GPOUT1(CNODE,NNODE,PUT) IS (
# PUTS OUT THE PRODUCTION NUMBERS ALONG A PATH FROM CNODE TO NNODE
WHICH CONSISTS ONLY OF TYPE 2 AND 3 NODES. NNODE IS A TERMINAL-
OR NONTERMINAL-REQUIRED NODE APPEARING AFTER A CIRCLED NODE. #
NNODE0_NNODE; PUT0_PUT;
BITROW_FREE(NBITM+GNB(NNODE0));
K_SCR(CNODE);
GP1: K=NNODE0 => GO TO GPX;
GO TO (GP6,GP6,GP2,GP3,GP6) GTYPE(K);
GP2: VAL_0; L_K; GO TO GP4;
GP3: VAL_GVAL(K); L_SCR(K);
GP4: NTN_DPROP('NODE',GVAL(L));
(I_1 LS NTN)=0 => (GLEAP(NTN,NNODE) => GO TO GP5; GO TO GP6);
(BITROW AND I) => (GP5: K_SCR(L);
VAL => POUT(PUT0,VAL);
GO TO GP1);
GP6: (K_ALT(K)) => GO TO GP1;
GPX: 0);
SUBR GPOUT2(CNODE,GOAL,PUT) IS (
# PUTS OUT THE PRODUCTION NUMBERS ALONG A PATH FROM CNODE TO GOAL
WHICH CONSISTS ONLY OF TYPE 2 AND 3 NODES. GOAL IS A NONTERMINAL
NUMBER WHICH REPRESENTS THE CORRESPONDING CIRCLED NODE. #
GOAL0_GOAL; PUT0_PUT;
NTN_DPROP('NODE',GVAL(CNODE));
NTN=GOAL0 => GO TO GPXX;
MASK_1 LS GOAL0;
K_SCR(CNODE);
GP7: GO TO (GP12,GP12,GP8,GP9,GP12) GTYPE(K);
GP8: VL_0; L_K; GO TO GP10;
GP9: VL_GVAL(K); L_SCR(K);
GP10: NBITM[2] => (GMADE(L,GOAL0) => GO TO GP11; GO TO GP12);
(MASK AND FREE(NBITM+GNB(L))) => (GP11: K_SCR(L);
VL => POUT(PUT0,VL);
NTN_DPROP('NODE',GVAL(L));
NTN=GOAL0 => GO TO GPXX;
GO TO GP7);
GP12: (K_ALT(K)) => GO TO GP7;
GPXX: 0) %%%