home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / simtel / sigm / vols000 / vol039 / ll1p30.pli < prev    next >
Encoding:
Text File  |  1984-04-29  |  9.6 KB  |  318 lines
  1. LL1P30: PROC;
  2. /****************************************************************
  3. *               LL(1) GRAMMAR ANALYZER - PHASE 3        *
  4. *PURPOSE:                                                       *
  5. *    THIS PROGRAM ANALYZES A LL(1) GRAMMAR GIVEN IN MODIFIED    *
  6. *    BNF FORMAT AND FINDS THE NULLABLE NON-TERMINALS AND NUL-   *
  7. *    LABLE PRODUCTIONS.                                         *
  8. *INPUT:                                                         *
  9. *OUTPUT:                                                        *
  10. *OUTLINE:                                                       *
  11. *REMARKS:                                                       *
  12. ****************************************************************/
  13.  
  14. /****************************************************************
  15. * * * * * * * * * * * COMMON DATA DEFINITIONS * * * * * * * * * *
  16. ****************************************************************/
  17.  
  18. /*    * * *  COMMON REPLACEMENTS  * * *    */
  19. %REPLACE TRUE BY '1'B;
  20. %REPLACE FALSE BY '0'B;
  21.  
  22. %INCLUDE 'LL1CMN.DCL';    /* GET COMMON AREAS. */
  23.  
  24.  
  25. /****************************************************************
  26. * * * * * * * * * * * COMMON PROCUDURES * * * * * * * * * * * * *
  27. ****************************************************************/
  28.  
  29.  
  30. %INCLUDE 'LL1PRC.DCL';
  31.  
  32.  
  33. COMPUTE_ALIVE: PROC (PRDSET_NUM,PRDSET_PTR) RETURNS(CHAR(254) VARYING);
  34. /* THIS ROUTINE COMPUTES THE SET OF ALIVE NON-TERMINALS. */
  35. /* A NONTERMINAL IS ALIVE IF IT CAN DERIVE ONE OR MORE
  36.    TERMINAL STRINGS; OTHERWISE, IT IS DEAD. */
  37.  
  38.     DCL PRDSET_NUM BIN(15); /* NUMBER OF PRODUCTIONS IN SET */
  39.     DCL PRDSET_PTR PTR;    /* PTR TO PRODUCTION SET */
  40.     DCL PRDSET(MAX_PROD) BIN(15) BASED(PRDSET_PTR);
  41.     DCL ALIVE_SET CHAR(254) VARYING;
  42.     DCL ALIVE_FLAG BIT(1);    /* FLAG USED DURING CHECKING */
  43.     DCL ALIVE_LOOP BIT(1); /* FLAG USED TO CONTROL LOOPING */
  44.     DCL I FIXED;        /* INTERNAL INDEX */
  45.     DCL J FIXED;        /* INTERNAL INDEX */
  46.  
  47. /* DETERMINE ALL NONTERMINALS WHICH APPEAR ON THE LEFT-HAND
  48.    SIDE OF AT LEAST ONE PRODUCTION WHICH HAS NO NON-TERMINALS
  49.    ON THE RIGHT-HAND SIDE. */
  50.     ALIVE_SET='';
  51.     DO I=1 TO PRDSET_NUM;
  52.        IF LENGTH(RHS(PRDSET(I)))=0 THEN
  53.           ALIVE_FLAG=TRUE;
  54.        ELSE
  55.           DO;
  56.              ALIVE_FLAG=TRUE;
  57.              DO J=1 TO LENGTH(RHS(PRDSET(I)));
  58.                 IF ISNTRM(SUBSTR(RHS(PRDSET(I)),J,1)) THEN
  59.                DO;
  60.                       ALIVE_FLAG=FALSE;
  61.               J=LENGTH(RHS(PRDSET(I)));
  62.                END;
  63.              END;
  64.           END;
  65.        IF ALIVE_FLAG THEN
  66.           DO;
  67.          IF LENGTH(ALIVE_SET)=0 THEN /*INSURE NO DUPLICATES*/
  68.             ;
  69.          ELSE
  70.             DO J=1 TO LENGTH(ALIVE_SET);
  71.                IF LHS(PRDSET(I))=SUBSTR(ALIVE_SET,J,1) THEN
  72.               DO;
  73.                  ALIVE_FLAG=FALSE;
  74.                  J=LENGTH(ALIVE_SET);
  75.               END;
  76.             END;
  77.          IF ALIVE_FLAG THEN
  78.                 ALIVE_SET=ALIVE_SET||LHS(PRDSET(I));
  79.           END;
  80.     END; /* DO */
  81.  
  82. /* ALSO, DETERMINE ALL NON-TERMINALS WHICH APPEAR ON THE 
  83.    LEFT-HAND SIDE OF AT LEAST ONE PRODUCTION FOR WHICH ALL
  84.    NON-TERMINALS ON THE RIGHT-HAND SIDE ALREADY ARE ALIVE.
  85.     ALIVE_LOOP=TRUE;    /* SET FOR FIRST TIME. */
  86.     DO WHILE(ALIVE_LOOP);   /* LOOP AS LONG AS WE FOUND
  87.                    AN ALIVE NON-TERMINAL ON
  88.                    THE LAST PASS. */
  89.        ALIVE_LOOP=FALSE;    /* DEFAULT TO NOT FOUND ONE */
  90.        DO I=1 TO PRDSET_NUM;
  91.           ALIVE_FLAG=TRUE;
  92.           IF LENGTH(RHS(PRDSET(I)))~=0 THEN
  93.              DO J=1 TO LENGTH(RHS(PRDSET(I)));
  94.                 IF IS_ALIVE(SUBSTR(RHS(PRDSET(I)),J,1),
  95.                 ALIVE_SET)=FALSE THEN
  96.                    ALIVE_FLAG=FALSE;
  97.              END;
  98.           IF ALIVE_FLAG=TRUE THEN
  99.              DO;
  100.             IF LENGTH(ALIVE_SET)=0 THEN
  101.                DO;
  102.                END;
  103.             ELSE
  104.                DO J=1 TO LENGTH(ALIVE_SET); /*INSURE NO DUPLICATES*/
  105.               IF LHS(PRDSET(I))=SUBSTR(ALIVE_SET,J,1) THEN
  106.                  DO;
  107.                     ALIVE_FLAG=FALSE;
  108.                     J=LENGTH(ALIVE_SET);
  109.                  END;
  110.                END;
  111.             IF ALIVE_FLAG=TRUE THEN
  112.                DO;
  113.                       ALIVE_SET=ALIVE_SET||LHS(PRDSET(I));
  114.                       ALIVE_LOOP=TRUE; /* INDICATE WE FOUND ONE. */
  115.                END;
  116.              END;
  117.        END;
  118.     END; /* WHILE */
  119.  
  120. /* RETURN TO CALLER. */
  121.     RETURN(ALIVE_SET);
  122.     END COMPUTE_ALIVE;
  123.     
  124.  
  125. IS_ALIVE: PROC (X,SET) RETURNS(BIT(1));
  126. /* THIS ROUTINE INDICATES IF A NON-TERMINAL IS ALIVE. */
  127.     DCL X CHAR;        /* INPUT INDEX */
  128.     DCL SET CHAR(254) VARYING; /* SET OF ALIVE NON-TERMINALS */
  129.     DCL I FIXED;        /* INTERNAL INDEX */
  130.  
  131.     IF LENGTH(SET)=0 THEN
  132.        RETURN(FALSE);
  133.  
  134.     DO I=1 TO LENGTH(SET);
  135.        IF X=SUBSTR(SET,I,1) THEN
  136.           RETURN(TRUE);
  137.     END;
  138.  
  139.     RETURN(FALSE);
  140.     END IS_ALIVE;
  141.     
  142.  
  143. PRINT_NPRD: PROC;
  144. /*THIS ROUTINE IS RESPONSIBLE FOR PRINTING THE NULLABLE */
  145. /*PRODUCTIONS. */
  146.     DCL I BIN(15);        /* INDEXES */
  147.     DCL J BIN(15);
  148.     DCL LHS_ENT CHAR(10) VARYING;
  149.     DCL RHS_ENT(5) CHAR(10) VARYING;
  150.  
  151. /* OUTPUT THE HEADING. */
  152.     ON ENDPAGE(LSTFIL)
  153.        BEGIN;
  154.           PUT FILE(LSTFIL) PAGE;
  155.           PUT FILE(LSTFIL) SKIP(3) 
  156.           EDIT('*** NULLABLE PRODUCTION LISTING ***','PAGE',
  157.             PAGENO(LSTFIL)-1)
  158.           (X(15),A(35),X(10),A(4),F(4));
  159.           PUT FILE(LSTFIL) SKIP(1);
  160.        END;
  161.     SIGNAL ENDPAGE(LSTFIL);
  162.  
  163. /* PRINT THE REPORT LINES. */
  164.     DO I=1 TO NNLPRD;
  165.        LHS_ENT=VOC(CHRNUM(LHS(NULPRD(I))));
  166.        DO J=1 TO 5;
  167.           IF J>LENGTH(RHS(NULPRD(I))) THEN
  168.              RHS_ENT(J)='';
  169.           ELSE
  170.              RHS_ENT(J)=VOC(CHRNUM(SUBSTR(RHS(NULPRD(I)),J,1)));
  171.        END;
  172.        PUT FILE(LSTFIL) SKIP(1)
  173.            EDIT(NULPRD(I),LHS_ENT,' -> ',(RHS_ENT(J) DO J=1 TO 5),';')
  174.           (F(4),X(01),A,A(04),5(A,X(01)),A(1));
  175.     END;
  176.  
  177.         END  PRINT_NPRD;
  178.  
  179.  
  180. PRINT_NNT: PROC;
  181. /*THIS ROUTINE IS RESPONSIBLE FOR PRINTING THE NULLABLE */
  182. /*NON-TERMINALS.*/
  183.     DCL I BIN(15);        /* INDEXES */
  184.     DCL J BIN(15);
  185.     DCL LHS_ENT CHAR(10) VARYING;
  186.     DCL RHS_ENT(5) CHAR(10) VARYING;
  187.  
  188. /* OUTPUT THE HEADING. */
  189.     ON ENDPAGE(LSTFIL)
  190.        BEGIN;
  191.           PUT FILE(LSTFIL) PAGE;
  192.           PUT FILE(LSTFIL) SKIP(3) 
  193.           EDIT('*** NULLABLE NON-TERMINAL LISTING ***','PAGE',
  194.             PAGENO(LSTFIL)-1)
  195.           (X(25),A(35),X(10),A(4),F(4));
  196.           PUT FILE(LSTFIL) SKIP(1);
  197.        END;
  198.     SIGNAL ENDPAGE(LSTFIL);
  199.  
  200. /* PRINT THE REPORT LINES. */
  201.     DO I=1 TO LENGTH(NLNTRM);
  202.        LHS_ENT=VOC(CHRNUM(SUBSTR(NLNTRM,I,1)));
  203.        PUT FILE(LSTFIL) SKIP(1)
  204.            EDIT(I,LHS_ENT)
  205.           (X(20),F(4),X(01),A);
  206.     END;
  207.  
  208.         END  PRINT_NNT;
  209.  
  210.  
  211. /****************************************************************
  212. * * * * * * * * * * GRAMMAR ANALYSIS PROCEDURES * * * * * * * * *
  213. ****************************************************************/
  214.  
  215.  
  216. CALC_NULPRD: PROC;
  217. /*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE SET OF  */
  218. /*NULLABLE PRODUCTIONS.  THE NULLABLE PRODUCTIONS ARE     */
  219. /*THOSE FOR WHICH THE SYMBOLS ON THE RIGTH-HAND SIDE ARE  */
  220. /*ALL NULLABLE.  THAT IS, ALL RIGHT-HAND SIDE SYMBOLS     */
  221. /*MUST BE NULLABLE NON-TERMINALS. */
  222.     DCL I BIN(15);        /* INDEXES */
  223.     DCL J BIN(15);
  224.     DCL NNL_FND BIT(1);    /* TERMINAL FOUND INDICATOR */
  225.  
  226. /* CALCULATE PRODUCTION SET. */
  227.     NNLPRD=0;        /* ZERO NUL PRD COUNT. */
  228.     DO I=1 TO NUMPRD;    /* LOOP THRU ALL PRODUCTIONS. */
  229.        IF LENGTH(RHS(I))=0 THEN /*EPSILON PRODUCTION*/
  230.           DO;
  231.              NNL_FND=TRUE;        /*ADD PRODUCTION TO SET.*/
  232.           END;
  233.        ELSE
  234.           DO J=1 TO LENGTH(RHS(I));
  235.              NNL_FND=ISNLNT(SUBSTR(RHS(I),J,1));
  236.              IF NNL_FND=FALSE THEN
  237.                 J=LENGTH(RHS(I));    /*FORCE END OF SEARCH.*/
  238.           END;
  239.        IF NNL_FND=TRUE THEN
  240.           DO;
  241.              NNLPRD=NNLPRD+1;    /*ADD PRODUCTION TO SET.*/
  242.              NULPRD(NNLPRD)=I;
  243.        END;
  244.     END;
  245.  
  246. /* RETURN TO CALLER. */
  247.     END CALC_NULPRD;
  248.  
  249.  
  250. CALC_NULTRM: PROC;
  251. /*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE SET OF  */
  252. /*NULLABLE NON-TERMINALS GIVEN THE GRAMMAR CALCULATED IN  */
  253. /*THE PREVIOUS STEP.  THE NULLABLE NON-TERMINALS ARE THOSE*/
  254. /*FOUND TO BE ALIVE IN THE NEW GRAMMAR. */
  255.  
  256. /* CALCULATE THE NULLABLE NON-TERMINALS. */
  257.     NLNTRM=COMPUTE_ALIVE(NNLPRD,ADDR(NULPRD));
  258.  
  259. /* RETURN TO CALLER. */
  260.     END CALC_NULTRM;
  261.  
  262.  
  263. CALC_PRDSET: PROC;
  264. /*THIS ROUTINE IS RESPONSIBLE FOR CALCULATING THE INITIAL */
  265. /*SET OF POSSIBLE NULLABLE PRODUCTIONS.  TO DO THIS, IT   */
  266. /*TAKES THE SET OF ALL PRODUCTIONS IN THE GIVEN GRAMMAR   */
  267. /*AND DELETES ALL PRODUCTIONS WHICH CONTAIN A TERMINAL IN */
  268. /*ITS RIGHT-HAND SIDE.  SINCE EPSILON IS NOT A TERMINAL   */
  269. /*SYMBOL, THIS STEP DOES NOT DELETE ANY EPSILON PRODUC-      */
  270. /*TIONS. */
  271.     DCL I BIN(15);        /* INDEXES */
  272.     DCL J BIN(15);
  273.     DCL TRM_FND BIT(1);    /* TERMINAL FOUND INDICATOR */
  274.  
  275. /* CALCULATE PRODUCTION SET. */
  276.     NNLPRD=0;        /* ZERO NUL PRD COUNT. */
  277.     DO I=1 TO NUMPRD;    /* LOOP THRU ALL PRODUCTIONS. */
  278.        IF LENGTH(RHS(I))=0 THEN /*EPSILON PRODUCTION*/
  279.           DO;
  280.              TRM_FND=FALSE;
  281.           END;
  282.        ELSE
  283.           DO J=1 TO LENGTH(RHS(I));
  284.              TRM_FND=ISTRM(SUBSTR(RHS(I),J,1));
  285.              IF TRM_FND=TRUE THEN
  286.                 J=LENGTH(RHS(I));    /*FORCE END OF SEARCH.*/
  287.           END;
  288.        IF TRM_FND=FALSE THEN
  289.           DO;
  290.              NNLPRD=NNLPRD+1;    /*ADD PRODUCTION TO SET.*/
  291.              NULPRD(NNLPRD)=I;
  292.        END;
  293.     END;
  294.  
  295. /* RETURN TO CALLER. */
  296.     END CALC_PRDSET;
  297.  
  298.  
  299. /****************************************************************
  300. * * * * * * * * * * * MAIN LINE PROCEDURE * * * * * * * * * * * *
  301. ****************************************************************/
  302.  
  303.  
  304. /* ANALYZE THE GRAMMAR. */
  305.     PUT SKIP LIST('BEGINNING PHASE 3 PROCESSING.');
  306.     CALL CALC_PRDSET;    /*CALCULATE INITIAL SET OF POSSIBLE
  307.                   NULLABLE PRODUCTIONS. */
  308.     CALL CALC_NULTRM;    /*CALCULATE NULLABLE NON-TERMINALS
  309.                   FROM THE ABOVE SET. */
  310.     CALL CALC_NULPRD;    /*CALCULATE THE NULLABEL PRODUCTIONS.*/
  311.  
  312. /* PRINT THE RESULTS. */
  313.     CALL PRINT_NNT;        /*PRINT NULLABLE NON-TERMINALS.*/
  314.     CALL PRINT_NPRD;    /*PRINT NULLABLE PRODUCTIONS.*/
  315.     PUT SKIP LIST('PHASE 3 PROCESSING COMPLETE.');
  316.     END LL1P30;
  317.  
  318.