home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / simtel / sigm / vols000 / vol039 / ll1p40.pli < prev    next >
Text File  |  1984-04-29  |  6KB  |  161 lines
  1. LL1P40: PROC;
  2. /****************************************************************
  3. *               LL(1) GRAMMAR ANALYZER - PHASE 4        *
  4. *PURPOSE:                                                       *
  5. *    THIS PROGRAM ANALYZES A LL(1) GRAMMAR GIVEN IN MODIFIED    *
  6. *    BNF FORMAT AND FINDS THE RELATION, BEGINS-DIRECTLY-WITH    *
  7. *    AND BEGINS-WITH FOR SYMBOLS.  ALSO, IT CALCULATES THE RE-  *
  8. *    LATION FIRST FOR PRODUCTIONS.                *
  9. *INPUT:                                                         *
  10. *    1) BASIC GRAMMAR TABLES                    *
  11. *    2) NULLABLE NON-TERMINALS AND PRODUCTIONS TABLES        *
  12. *OUTPUT:                                                        *
  13. *    1) FILE, $1.T01, CONTAINS THE BEGINS-WITH RELATION.    *
  14. *    2) FILE, $1.T02, CONTAINS THE FIRST RELATION.        *
  15. *OUTLINE:                                                       *
  16. *REMARKS:                                                       *
  17. ****************************************************************/
  18.  
  19. /****************************************************************
  20. * * * * * * * * * * * COMMON DATA DEFINITIONS * * * * * * * * * *
  21. ****************************************************************/
  22.  
  23. /*    * * *  COMMON REPLACEMENTS  * * *    */
  24. %REPLACE TRUE BY '1'B;
  25. %REPLACE FALSE BY '0'B;
  26.  
  27. %INCLUDE 'LL1CMN.DCL';    /* GET COMMON AREAS. */
  28.  
  29.  
  30. /****************************************************************
  31. * * * * * * * * * * * COMMON PROCUDURES * * * * * * * * * * * * *
  32. ****************************************************************/
  33.  
  34.  
  35. %INCLUDE 'LL1PRC.DCL';
  36.  
  37.  
  38. /****************************************************************
  39. * * * * * * * * * * GRAMMAR ANALYSIS PROCEDURES * * * * * * * * *
  40. ****************************************************************/
  41.  
  42.  
  43. CALC_BDW: PROC;
  44. /*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE RELATION*/
  45. /*BEGINS-DIRECTLY-WITH.  WE SAY THAT <A> BEGINS-DIRECTLY- */
  46. /*WITH B IF A SEQUENCE BEGINNING WITH B CAN BE OBTAINED   */
  47. /*FROM A BY APPLYING EXACTLY ONE PRODUCTION AND THEN OP-  */
  48. /*TIONALLY REPLACING NON-TERMINALS WITH EPSILON.  THUS, WE*/
  49. /*BUILD THE RELATIONSHIP FOR ALL NON-TERMINALS WHICH HAVE */
  50. /*A NONE NULL RIGHT-HAND-SIDE.  FIRST, THE FIRST SYMBOL ON*/
  51. /*THE RIGHT-HAND-SIDE IS PART OF THE RELATIONSHIP.  ALSO, */
  52. /*THE FOLLOWING SYMBOL IS PART OF IT AS LONG AS THE CUR-  */
  53. /*RENT ONE IS A NULLABLE NON-TERMINAL. */
  54.     DCL I BIN(15);        /* INDEXES */
  55.     DCL J BIN(15);
  56.  
  57. /* CALCULATE THE RELATION. */
  58.     DO I=1 TO NUMPRD;    /* LOOP THRU ALL PRODUCTIONS. */
  59.        IF LENGTH(RHS(I))=0 THEN /*EPSILON PRODUCTION*/
  60.           ;
  61.        ELSE
  62.           DO J=1 TO LENGTH(RHS(I));
  63.          CALL SETBIT(CHRNUM(LHS(I)),
  64.                   CHRNUM(SUBSTR(RHS(I),J,1)),ADDR(ARRAY1));
  65.              IF ISNLNT(SUBSTR(RHS(I),J,1)) THEN
  66.                 ;
  67.          ELSE
  68.             J=LENGTH(RHS(I));
  69.           END;
  70.     END;
  71.  
  72. /* RETURN TO CALLER. */
  73.     END CALC_BDW;
  74.  
  75.  
  76. CALC_BW: PROC;
  77. /*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE RELATION*/
  78. /*BEGINS-WITH.  BEGINS-WITH IS THE REFLEXIVE TRANSITIVE   */
  79. /*CLOSURE OF THE RELATION, BEGINS-DIRECTLY-WITH. */
  80.  
  81. /* CALCULATE IT. */
  82.     CALL CLOSUR(ADDR(ARRAY1));
  83.  
  84. /* RETURN TO CALLER. */
  85.     END CALC_BW;
  86.  
  87.  
  88. CALC_FIRST: PROC;
  89. /*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE RELATION*/
  90. /*FIRST FOR PROCUTIONS.  WE SAY THAT THE FIRST RELATION   */
  91. /*FOR A PRODUCTION IS THE UNION OF THE FIRST SYMBOL RELA- */
  92. /*TION INCLUDING AND UNTIL THE FIRST NON-NULLABLE NON-    */
  93. /*TERMINAL IS FOUND OR A TERMINAL IS FOUND.  THE FIRST    */
  94. /*SYMBOL RELATION IS SIMPLY THE PORTION OF THE BEGINS-WITH*/
  95. /*MATRIX FOR NON-TERMINALS HORIZONTALLY AND TERMINALS     */
  96. /*VERTICALLY. */
  97.     DCL I BIN(15);        /* INDEXES */
  98.     DCL J BIN(15);
  99.     DCL K BIN(15);
  100.  
  101. /* CALCULATE THE RELATION. */
  102.     DO I=1 TO NUMPRD;    /* LOOP THRU ALL PRODUCTIONS. */
  103.        IF LENGTH(RHS(I))=0 THEN /*EPSILON PRODUCTION*/
  104.           ;
  105.        ELSE
  106.           DO J=1 TO LENGTH(RHS(I));
  107.          IF ISTRM(SUBSTR(RHS(I),J,1)) THEN /**TERMINAL**/
  108.             DO;
  109.                CALL SETBIT(I,CHRNUM(SUBSTR(RHS(I),J,1)),
  110.                     ADDR(ARRAY2));
  111.                J=LENGTH(RHS(I)); /*FORCE END OF LOOP.*/
  112.             END;
  113.          ELSE                               /**NON-TERMINAL**/
  114.             DO;
  115.                DO K=LENGTH(NTRM)+1 TO LENGTH(NTRM)+LENGTH(TRM);
  116.               IF TSTBIT(CHRNUM(SUBSTR(RHS(I),J,1)),
  117.                           K,ADDR(ARRAY1)) THEN
  118.                  CALL SETBIT(I,K,ADDR(ARRAY2));
  119.                END;
  120.                IF ISNLNT(SUBSTR(RHS(I),J,1)) THEN /**NULLABLE**/
  121.               ;
  122.                ELSE
  123.               J=LENGTH(RHS(I)); /*FORCE END OF LOOP.*/
  124.             END;
  125.           END;
  126.     END;
  127.  
  128. /* RETURN TO CALLER. */
  129.     END CALC_FIRST;
  130.  
  131.  
  132. /****************************************************************
  133. * * * * * * * * * * * MAIN LINE PROCEDURE * * * * * * * * * * * *
  134. ****************************************************************/
  135.  
  136.  
  137. /* ANALYZE THE GRAMMAR. */
  138.     PUT SKIP LIST('BEGINNING PHASE 4 PROCESSING.');
  139.     CALL ZEROAR(ADDR(ARRAY1)); 
  140.     CALL ZEROAR(ADDR(ARRAY2)); 
  141.     PUT SKIP LIST('CALCULATING BEGINS-DIRECTLY-WITH...');
  142.     CALL CALC_BDW;        /*CALCULATE THE RELATION BEGINS-
  143.                   DIRECTLY-WITH. */
  144.     CALL PRTARY('*** BEGINS-DIRECTLY-WITH RELATION ***',TRUE,
  145.              NUMVOC,NUMVOC,ADDR(ARRAY1));
  146.     PUT SKIP LIST('CALCULATING BEGINS-WITH...');
  147.     CALL CALC_BW;        /*CALCULATE THE RELATION BEGINS-WITH.*/
  148.     CALL PRTARY('*** BEGINS-WITH RELATION ***',TRUE,
  149.              NUMVOC,NUMVOC,ADDR(ARRAY1));
  150.     PUT SKIP LIST('CALCULATING FIRST...');
  151.     CALL CALC_FIRST;    /*CALCULATE THE RELATION FIRST.*/
  152.     CALL PRTARY('*** FIRST PRODUCTION RELATION ***',FALSE, 
  153.              NUMPRD,NUMVOC,ADDR(ARRAY2));
  154.     PUT SKIP LIST('SAVING BEGINS-WITH...');
  155.     CALL SAVARY(ADDR(ARRAY1),'T01');
  156.     PUT SKIP LIST('SAVING FIRST...');
  157.     CALL SAVARY(ADDR(ARRAY2),'T02');
  158.     PUT SKIP LIST('PHASE 4 PROCESSING COMPLETE.');
  159.     END LL1P40;
  160.  
  161.