LL1P40: PROC;
/****************************************************************
* LL(1) GRAMMAR ANALYZER - PHASE 4 *
*PURPOSE: *
* THIS PROGRAM ANALYZES A LL(1) GRAMMAR GIVEN IN MODIFIED *
* BNF FORMAT AND FINDS THE RELATION, BEGINS-DIRECTLY-WITH *
* AND BEGINS-WITH FOR SYMBOLS. ALSO, IT CALCULATES THE RE- *
* LATION FIRST FOR PRODUCTIONS. *
*INPUT: *
* 1) BASIC GRAMMAR TABLES *
* 2) NULLABLE NON-TERMINALS AND PRODUCTIONS TABLES *
*OUTPUT: *
* 1) FILE, $1.T01, CONTAINS THE BEGINS-WITH RELATION. *
* 2) FILE, $1.T02, CONTAINS THE FIRST RELATION. *
*OUTLINE: *
*REMARKS: *
****************************************************************/
/****************************************************************
* * * * * * * * * * * COMMON DATA DEFINITIONS * * * * * * * * * *
****************************************************************/
/* * * * COMMON REPLACEMENTS * * * */
%REPLACE TRUE BY '1'B;
%REPLACE FALSE BY '0'B;
%INCLUDE 'LL1CMN.DCL'; /* GET COMMON AREAS. */
/****************************************************************
* * * * * * * * * * * COMMON PROCUDURES * * * * * * * * * * * * *
****************************************************************/
%INCLUDE 'LL1PRC.DCL';
/****************************************************************
* * * * * * * * * * GRAMMAR ANALYSIS PROCEDURES * * * * * * * * *
****************************************************************/
CALC_BDW: PROC;
/*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE RELATION*/
/*BEGINS-DIRECTLY-WITH. WE SAY THAT <A> BEGINS-DIRECTLY- */
/*WITH B IF A SEQUENCE BEGINNING WITH B CAN BE OBTAINED */
/*FROM A BY APPLYING EXACTLY ONE PRODUCTION AND THEN OP- */
/*TIONALLY REPLACING NON-TERMINALS WITH EPSILON. THUS, WE*/
/*BUILD THE RELATIONSHIP FOR ALL NON-TERMINALS WHICH HAVE */
/*A NONE NULL RIGHT-HAND-SIDE. FIRST, THE FIRST SYMBOL ON*/
/*THE RIGHT-HAND-SIDE IS PART OF THE RELATIONSHIP. ALSO, */
/*THE FOLLOWING SYMBOL IS PART OF IT AS LONG AS THE CUR- */
/*RENT ONE IS A NULLABLE NON-TERMINAL. */
DCL I BIN(15); /* INDEXES */
DCL J BIN(15);
/* CALCULATE THE RELATION. */
DO I=1 TO NUMPRD; /* LOOP THRU ALL PRODUCTIONS. */
IF LENGTH(RHS(I))=0 THEN /*EPSILON PRODUCTION*/
;
ELSE
DO J=1 TO LENGTH(RHS(I));
CALL SETBIT(CHRNUM(LHS(I)),
CHRNUM(SUBSTR(RHS(I),J,1)),ADDR(ARRAY1));
IF ISNLNT(SUBSTR(RHS(I),J,1)) THEN
;
ELSE
J=LENGTH(RHS(I));
END;
END;
/* RETURN TO CALLER. */
END CALC_BDW;
CALC_BW: PROC;
/*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE RELATION*/
/*BEGINS-WITH. BEGINS-WITH IS THE REFLEXIVE TRANSITIVE */
/*CLOSURE OF THE RELATION, BEGINS-DIRECTLY-WITH. */
/* CALCULATE IT. */
CALL CLOSUR(ADDR(ARRAY1));
/* RETURN TO CALLER. */
END CALC_BW;
CALC_FIRST: PROC;
/*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE RELATION*/
/*FIRST FOR PROCUTIONS. WE SAY THAT THE FIRST RELATION */
/*FOR A PRODUCTION IS THE UNION OF THE FIRST SYMBOL RELA- */
/*TION INCLUDING AND UNTIL THE FIRST NON-NULLABLE NON- */
/*TERMINAL IS FOUND OR A TERMINAL IS FOUND. THE FIRST */
/*SYMBOL RELATION IS SIMPLY THE PORTION OF THE BEGINS-WITH*/
/*MATRIX FOR NON-TERMINALS HORIZONTALLY AND TERMINALS */
/*VERTICALLY. */
DCL I BIN(15); /* INDEXES */
DCL J BIN(15);
DCL K BIN(15);
/* CALCULATE THE RELATION. */
DO I=1 TO NUMPRD; /* LOOP THRU ALL PRODUCTIONS. */
IF LENGTH(RHS(I))=0 THEN /*EPSILON PRODUCTION*/
;
ELSE
DO J=1 TO LENGTH(RHS(I));
IF ISTRM(SUBSTR(RHS(I),J,1)) THEN /**TERMINAL**/
DO;
CALL SETBIT(I,CHRNUM(SUBSTR(RHS(I),J,1)),
ADDR(ARRAY2));
J=LENGTH(RHS(I)); /*FORCE END OF LOOP.*/
END;
ELSE /**NON-TERMINAL**/
DO;
DO K=LENGTH(NTRM)+1 TO LENGTH(NTRM)+LENGTH(TRM);
IF TSTBIT(CHRNUM(SUBSTR(RHS(I),J,1)),
K,ADDR(ARRAY1)) THEN
CALL SETBIT(I,K,ADDR(ARRAY2));
END;
IF ISNLNT(SUBSTR(RHS(I),J,1)) THEN /**NULLABLE**/
;
ELSE
J=LENGTH(RHS(I)); /*FORCE END OF LOOP.*/
END;
END;
END;
/* RETURN TO CALLER. */
END CALC_FIRST;
/****************************************************************
* * * * * * * * * * * MAIN LINE PROCEDURE * * * * * * * * * * * *
****************************************************************/
/* ANALYZE THE GRAMMAR. */
PUT SKIP LIST('BEGINNING PHASE 4 PROCESSING.');
CALL ZEROAR(ADDR(ARRAY1));
CALL ZEROAR(ADDR(ARRAY2));
PUT SKIP LIST('CALCULATING BEGINS-DIRECTLY-WITH...');
CALL CALC_BDW; /*CALCULATE THE RELATION BEGINS-
DIRECTLY-WITH. */
CALL PRTARY('*** BEGINS-DIRECTLY-WITH RELATION ***',TRUE,
NUMVOC,NUMVOC,ADDR(ARRAY1));
PUT SKIP LIST('CALCULATING BEGINS-WITH...');
CALL CALC_BW; /*CALCULATE THE RELATION BEGINS-WITH.*/
CALL PRTARY('*** BEGINS-WITH RELATION ***',TRUE,
NUMVOC,NUMVOC,ADDR(ARRAY1));
PUT SKIP LIST('CALCULATING FIRST...');
CALL CALC_FIRST; /*CALCULATE THE RELATION FIRST.*/
CALL PRTARY('*** FIRST PRODUCTION RELATION ***',FALSE,
NUMPRD,NUMVOC,ADDR(ARRAY2));
PUT SKIP LIST('SAVING BEGINS-WITH...');
CALL SAVARY(ADDR(ARRAY1),'T01');
PUT SKIP LIST('SAVING FIRST...');
CALL SAVARY(ADDR(ARRAY2),'T02');
PUT SKIP LIST('PHASE 4 PROCESSING COMPLETE.');
END LL1P40;
