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 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;