summaryrefslogtreecommitdiff
path: root/src/closure.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/closure.c')
-rw-r--r--src/closure.c429
1 files changed, 429 insertions, 0 deletions
diff --git a/src/closure.c b/src/closure.c
new file mode 100644
index 0000000..7213443
--- /dev/null
+++ b/src/closure.c
@@ -0,0 +1,429 @@
+
+/***************************************************************
+ CLOSURE.C
+
+ This file containts CLOSURE routine of ZUBR.
+
+ PART OF : ZUBR - Parsers generator for multiple syntax
+ language compilers .
+
+ COMPILE : .
+
+ NOTE : NONE .
+
+ Copyright (C) 1995 - 2026 by Andrey V.Kosteltsev.
+ All Rights Reserved.
+ ***************************************************************/
+/*
+ This file contant RUSSIAN letters( code-page: UTF-8 )
+ ***************************************************************/
+
+#include <defs.h>
+
+#ifndef __NO_COMPILE
+
+
+int *itemset; /* use in lr0.c */
+int *itemsetend; /* use in lr0.c */
+unsigned *ruleset; /* use in lr0.c */
+
+static unsigned *first_derives;
+static unsigned *EFF;
+
+/************** Start of functions for debuging **************/
+
+#ifdef _DEBUG
+void print_closure( int n )
+/***************************************************************
+
+ Description : print closure
+
+ Concepts : print_closure() is used for debugging
+
+ Use Global Variable: int *itemset; | this file
+ int *itemsetend; | this file
+
+ Use Functions :
+
+ Parameters : int n
+
+ Return : [void]
+
+ ***************************************************************/
+{
+ register int *isp;
+
+ mpu_fprintf( mpu_stdout, MPU_UCS2( "\n\nn = %d\n\n" ), n );
+ for( isp = itemset; isp < itemsetend; isp++ )
+ mpu_fprintf( mpu_stdout, MPU_UCS2( " %d\n" ), *isp );
+
+} /******* End of print_closure( int n ) *********************/
+
+
+void print_EFF( void )
+/***************************************************************
+
+ Description : print EFF
+
+ Concepts : print_EFF() is used for debugging
+
+ Use Global Variable: int nsyms; | main.c
+ int nvars; | main.c
+ int start_symbol; | main.c
+ char **symbol_name; | main.c
+
+ Use Functions :
+
+ Parameters : [void]
+
+ Return : [void]
+
+ ***************************************************************/
+{
+ register int i, j;
+ register unsigned *rowp;
+ register unsigned word;
+ register unsigned mask;
+
+ mpu_fprintf( mpu_stdout,
+ MPU_UCS2( "\n\nEpsilon Free Firsts\n" ) );
+
+ for( i = start_symbol; i < nsyms; i++ )
+ {
+ mpu_fprintf( mpu_stdout,
+ MPU_UCS2( "\n%s" ), symbol_name[i] );
+ rowp = EFF + ((i - start_symbol) * SIZE_IN_INT( nvars ));
+ word = *rowp++;
+
+ mask = 1;
+ for( j = 0; j < nvars; j++ )
+ {
+ if( word & mask )
+ mpu_fprintf( mpu_stdout,
+ MPU_UCS2( " %s" ),
+ symbol_name[start_symbol + j] );
+
+ mask <<= 1;
+ if( mask == 0 )
+ {
+ word = *rowp++;
+ mask = 1;
+ }
+
+ } /* End of for( j = 0; j < nvars; j++ ) */
+ } /* End of for( i = start_symbol; i < nsyms; i++ ) */
+
+} /******* End of print_EFF( void ) **************************/
+
+
+void print_first_derives( void )
+/***************************************************************
+
+ Description : print first derives
+
+ Concepts : print_first_derives() is used for debugging
+
+ Use Global Variable: int nrules; | main.c
+ int nsyms; | main.c
+ int start_symbol; | main.c
+ char **symbol_name; | main.c
+ static unsigned *first_derives; | this file
+
+ Use Functions :
+
+ Parameters : [void]
+
+ Return : [void]
+
+ ***************************************************************/
+{
+ register int i;
+ register int j;
+ register unsigned *rp;
+ register unsigned cword;
+ register unsigned mask;
+
+ mpu_fprintf( mpu_stdout,
+ MPU_UCS2( "\n\n\nFirst Derives\n" ) );
+
+ for( i = start_symbol; i < nsyms; i++ )
+ {
+ mpu_fprintf( mpu_stdout,
+ MPU_UCS2( "\n%s derives\n" ), symbol_name[i] );
+ rp = first_derives + i * SIZE_IN_INT( nrules );
+ cword = *rp++;
+ mask = 1;
+ for( j = 0; j <= nrules; j++ )
+ {
+ if( cword & mask )
+ mpu_fprintf( mpu_stdout, MPU_UCS2( " %d\n" ), j );
+ mask <<= 1;
+ if( mask == 0 )
+ {
+ cword = *rp++;
+ mask = 1;
+ }
+ } /* End of for( j = 0; j <= nrules; j++ ) */
+ } /* End of for( i = start_symbol; i < nsyms; i++ ) */
+ mpu_fflush( mpu_stdout ); /* stdio.h */
+
+} /******* End of print_first_derives( void ) ****************/
+
+#endif
+
+/*************** End of functions for debuging ***************/
+
+
+void set_EFF( void )
+/***************************************************************
+
+ Description : set EFF
+
+ Concepts :
+
+ Use Global Variable: int nsyms; | main.c
+ int nvars; | main.c
+ int start_symbol; | main.c
+ int *ritem; | main.c
+ int *rrhs; | main.c
+ int **derives; | main.c
+ static unsigned *EFF; | this file
+
+ Use Functions : reflexive_transitive_closure (unsigned *, int);
+ | warshall.c
+ Parameters : [void]
+
+ Return : [void]
+
+ ***************************************************************/
+{
+ register unsigned *row;
+ register int symbol;
+ register int *sp;
+ register int rowsize, i, rule;
+
+ rowsize = SIZE_IN_INT( nvars );
+ EFF = NEW2( nvars * rowsize, unsigned );
+
+ row = EFF;
+ for( i = start_symbol; i < nsyms; i++ )
+ {
+ sp = derives[i];
+ for( rule = *sp; rule > 0; rule = *++sp )
+ {
+ symbol = ritem[rrhs[rule]];
+ if( ISVAR(symbol) )
+ {
+ symbol -= start_symbol;
+ SETBIT( row, symbol );
+ }
+ }
+ row += rowsize;
+ }
+ reflexive_transitive_closure( EFF, nvars );
+
+#ifdef _DEBUG
+ print_EFF();
+#endif
+
+} /******* End of set_EFF( void ) ****************************/
+
+
+void set_first_derives( void )
+/***************************************************************
+
+ Description : set first derives
+
+ Concepts :
+
+ Use Global Variable: int nrules; | main.c
+ int nsyms; | main.c
+ int ntokens; | main.c
+ int nvars; | main.c
+ int start_symbol; | main.c
+ int **derives; | main.c
+ static unsigned *first_derives; | this file
+
+ Use Functions : void set_EFF( void ); | this file
+
+ Parameters : [void]
+
+ Return : [void]
+
+ ***************************************************************/
+{
+ register unsigned *rrow;
+ register unsigned *vrow;
+ register int j;
+ register unsigned mask;
+ register unsigned cword;
+ register int *rp;
+
+ int rule;
+ int i;
+ int rulesetsize;
+ int varsetsize;
+
+ rulesetsize = SIZE_IN_INT( nrules );
+ varsetsize = SIZE_IN_INT( nvars );
+ first_derives = NEW2( nvars * rulesetsize, unsigned ) -
+ ntokens * rulesetsize;
+
+ set_EFF();
+
+ rrow = first_derives + ntokens * rulesetsize;
+ for( i = start_symbol; i < nsyms; i++ )
+ {
+ vrow = EFF + ((i - ntokens) * varsetsize);
+ cword = *vrow++;
+ mask = 1;
+ for( j = start_symbol; j < nsyms; j++ )
+ {
+ if( cword & mask )
+ {
+ rp = derives[j];
+ while( (rule = *rp++) >= 0 )
+ {
+ SETBIT( rrow, rule );
+ }
+ }
+
+ mask <<= 1;
+ if( mask == 0 )
+ {
+ cword = *vrow++;
+ mask = 1;
+ }
+ }
+
+ vrow += varsetsize;
+ rrow += rulesetsize;
+ }
+
+#ifdef _DEBUG
+ print_first_derives();
+#endif
+
+ FREE( EFF );
+
+} /******* End of set_first_derives( void ) ******************/
+
+
+void closure( int *nucleus, int n )
+/***************************************************************
+
+ Description : closure
+
+ Concepts :
+
+ Use Global Variable: int nrules; | main.c
+ int *ritem; | main.c
+ int *rrhs; | main.c
+ int *itemset; | this file
+ int *itemsetend; | this file
+ unsigned *ruleset; | this file
+ static unsigned *first_derives; | this file
+
+ Use Functions :
+
+ Parameters : int *nucleus, int n
+
+ Return : [void]
+
+ ***************************************************************/
+{
+ register int ruleno;
+ register unsigned word;
+ register unsigned mask;
+ register int *csp;
+ register unsigned *dsp;
+ register unsigned *rsp;
+ register int rulesetsize;
+
+ int *csend;
+ unsigned *rsend;
+ int symbol;
+ int itemno;
+
+ rulesetsize = SIZE_IN_INT( nrules );
+ rsp = ruleset;
+ rsend = ruleset + rulesetsize;
+ for( rsp = ruleset; rsp < rsend; rsp++ ) *rsp = 0;
+
+ csend = nucleus + n;
+ for( csp = nucleus; csp < csend; ++csp )
+ {
+ symbol = ritem[*csp];
+ if( ISVAR(symbol) )
+ {
+ dsp = first_derives + symbol * rulesetsize;
+ rsp = ruleset;
+ while( rsp < rsend ) *rsp++ |= *dsp++;
+ }
+ }
+
+ ruleno = 0;
+ itemsetend = itemset;
+ csp = nucleus;
+ for( rsp = ruleset; rsp < rsend; ++rsp )
+ {
+ word = *rsp;
+ if( word == 0 ) ruleno += ZUBR_BITS_PER_INT;
+ else
+ {
+ mask = 1;
+ while( mask )
+ {
+ if( word & mask )
+ {
+ itemno = rrhs[ruleno];
+ while( csp < csend && *csp < itemno )
+ *itemsetend++ = *csp++;
+ *itemsetend++ = itemno;
+ while( csp < csend && *csp == itemno ) ++csp;
+ }
+ mask <<= 1;
+ ++ruleno;
+ }
+ }
+ }
+
+ while( csp < csend ) *itemsetend++ = *csp++;
+
+#ifdef _DEBUG
+ print_closure( n );
+#endif
+
+} /******* End of closure( int *nucleus, int n ) *************/
+
+
+void finalize_closure( void )
+/***************************************************************
+
+ Description : finalize closure
+
+ Concepts :
+
+ Use Global Variable: int nrules; | main.c
+ int ntokens; | main.c
+ int *itemset; | this file
+ unsigned *ruleset; | this file
+ static unsigned *first_derives; | this file
+
+ Use Functions :
+
+ Parameters :
+
+ Return : [void]
+
+ ***************************************************************/
+{
+ FREE( itemset );
+ FREE( ruleset);
+ FREE( first_derives + ntokens * SIZE_IN_INT(nrules) );
+
+} /******* End of finalize_closure( void ) *******************/
+
+#endif /* __NO_COMPILE */
+
+/******************* END OF FILE CLOSURE.C *******************/
generated by cgit v1.2.3 (git 2.39.0) at 2026-10-03 01:07:26 +0300