Oakland CPM Archive/oakcpm.iso/sigm/sigmv039.ark/LL1P40.PLI

Text File | 1984-04-29 | 5.6 KB | 161 lines

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;