/*************************************************************** LR0.C This file containts LR0 routines of ZUBR. PART OF : ZUBR - Parsers generator for multiple syntax language compilers . COMPILE : . NOTE : Use macro _DEBUG, TRACE for out additional info into mpu_stdout, mpu_stderr. Copyright (C) 1995 - 2026 by Andrey V.Kosteltsev. All Rights Reserved. ***************************************************************/ /* This file contant RUSSIAN letters( code-page: UTF-8 ) ***************************************************************/ #include #ifndef __NO_COMPILE extern int *itemset; /* define in CLOSURE.C */ extern int *itemsetend; /* define in CLOSURE.C */ extern unsigned *ruleset; /* define in CLOSURE.C */ int nstates; core *first_state; shifts *first_shift; reductions *first_reduction; static core **state_set; static core *this_state; static core *last_state; static shifts *last_shift; static reductions *last_reduction; static int nshifts; static int *shift_symbol; static int *redset; static int *shiftset; static int **kernel_base; static int **kernel_end; static int *kernel_items; /************* Start of functions for debuging ***************/ #ifdef _DEBUG void show_cores( void ) /*************************************************************** Description : show cores Concepts : show_cores() is used for debugging Use Global Variable: char **symbol_name; | main.c int *ritem; | main.c int *rrhs; | main.c int *rlhs; | main.c core *first_state; | this file Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { core *p; int i, j, k, n; int itemno; k = 0; for( p = first_state; p; ++k, p = p->next ) { if( k ) mpu_fprintf( mpu_stdout, MPU_UCS2( "\n" ) ); mpu_fprintf( mpu_stdout, MPU_UCS2( "state %d, number = %d, accessing symbol = %s\n" ), k, p->number, symbol_name[p->accessing_symbol] ); n = p->nitems; for( i = 0; i < n; ++i ) { itemno = p->items[i]; mpu_fprintf( mpu_stdout, MPU_UCS2( "%4d " ), itemno ); j = itemno; while( ritem[j] >= 0 ) ++j; mpu_fprintf( mpu_stdout, MPU_UCS2( "%s :" ), symbol_name[rlhs[-ritem[j]]] ); j = rrhs[-ritem[j]]; while( j < itemno ) mpu_fprintf( mpu_stdout, MPU_UCS2( " %s" ), symbol_name[ritem[j++]] ); mpu_fprintf( mpu_stdout, MPU_UCS2( " ." ) ); while( ritem[j] >= 0 ) mpu_fprintf( mpu_stdout, MPU_UCS2( " %s" ), symbol_name[ritem[j++]] ); mpu_fprintf( mpu_stdout, MPU_UCS2( "\n" ) ); mpu_fflush( mpu_stdout ); /* stdio.h */ } /* End of for( i = 0; i < n; ++i ) */ } /* End of for( p = first_state; p; ++k, p = p->next ) */ } /******* End of show_cores( void ) **************************/ void show_ritems( void ) /*************************************************************** Description : show ritems Concepts : show_ritems() is used for debugging Use Global Variable: int nitems; | main.c int *ritem; | main.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { int i; for( i = 0; i < nitems; ++i ) mpu_fprintf( mpu_stdout, MPU_UCS2( "ritem[%d] = %d\n" ), i, ritem[i] ); } /******* End of show_ritems( void ) ************************/ void show_rrhs( void ) /*************************************************************** Description : show rrhs Concepts : show_rrhs() is used for debugging Use Global Variable: int nrules; | main.c int *rrhs; | main.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { int i; for( i = 0; i < nrules; ++i ) mpu_fprintf( mpu_stdout, MPU_UCS2( "rrhs[%d] = %d\n" ), i, rrhs[i] ); } /******* End of show_rrhs( void ) **************************/ void show_shifts( void ) /*************************************************************** Description : show shifts Concepts : show_shifts() is used for debugging Use Global Variable: shifts *first_shift; | this file Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { shifts *p; int i, j, k; k = 0; for( p = first_shift; p; ++k, p = p->next ) { if( k ) mpu_fprintf( mpu_stdout, MPU_UCS2( "\n" ) ); mpu_fprintf( mpu_stdout, MPU_UCS2( "shift %d, number = %d, nshifts = %d\n" ), k, p->number, p->nshifts ); j = p->nshifts; for( i = 0; i < j; ++i ) mpu_fprintf( mpu_stdout, MPU_UCS2( "\t%d\n" ), p->shift[i] ); } } /******* End of show_shifts( void ) ************************/ void print_derives( void ) /*************************************************************** Description : print derives Concepts : print_derives() is used for debugging Use Global Variable: int nsyms; | main.c int start_symbol; | main.c char **symbol_name; | main.c int **derives; | main.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int i; register int *sp; mpu_fprintf( mpu_stdout, MPU_UCS2( "\nDERIVES\n\n" ) ); for( i = start_symbol; i < nsyms; i++ ) { mpu_fprintf( mpu_stdout, MPU_UCS2( "%s derives " ), symbol_name[i] ); for( sp = derives[i]; *sp >= 0; sp++ ) { mpu_fprintf( mpu_stdout, MPU_UCS2( " %d" ), *sp ); } mpu_putc( '\n', mpu_stdout ); } mpu_putc( '\n', mpu_stdout ); } /******* End of print_derives( void ) **********************/ #endif /***************** End of functions for debuging ***************/ void allocate_itemsets( void ) /*************************************************************** Description : allocate itemsets Concepts : Use Global Variable: int nsyms; | main.c int nitems; | main.c int *ritem; | main.c static int *shift_symbol; | this file static int **kernel_base; | this file static int **kernel_end; | this file static int *kernel_items; | this file Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int *itemp; register int *item_end; register int symbol; register int i; register int count; register int max; register int *symbol_count; count = 0; symbol_count = NEW2( nsyms, int ); item_end = ritem + nitems; for( itemp = ritem; itemp < item_end; itemp++ ) { symbol = *itemp; if( symbol >= 0 ) { count++; symbol_count[symbol]++; } } kernel_base = NEW2( nsyms, int * ); kernel_items = NEW2( count, int ); count = 0; max = 0; for( i = 0; i < nsyms; i++ ) { kernel_base[i] = kernel_items + count; count += symbol_count[i]; if( max < symbol_count[i] ) max = symbol_count[i]; } shift_symbol = symbol_count; kernel_end = NEW2( nsyms, int * ); } /******* End of allocate_itemsets( void ) ******************/ void allocate_storage( void ) /*************************************************************** Description : allocate storage Concepts : Use Global Variable: int nsyms; | main.c int nitems; | main.c int nrules; | main.c static core **state_set; | this file static int *redset; | this file static int *shiftset; | this file Use Functions : void allocate_itemsets (void); | this file Parameters : [void] Return : [void] ***************************************************************/ { allocate_itemsets(); shiftset = NEW2( nsyms, int ); redset = NEW2( nrules + 1, int ); state_set = NEW2( nitems, core * ); } /******* End of allocate_storage( void ) *******************/ void free_storage( void ) /*************************************************************** Description : free storage Concepts : Use Global Variable: static core **state_set; | this file static int *redset; | this file static int *shiftset; | this file static int *shift_symbol; | this file static int **kernel_base; | this file static int **kernel_end; | this file static int *kernel_items; | this file Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { FREE( shift_symbol ); FREE( redset ); FREE( shiftset ); FREE( kernel_base ); FREE( kernel_end ); FREE( kernel_items ); FREE( state_set ); } /******* End of free_storage( void ) ***********************/ core * new_state( int symbol ) /*************************************************************** Description : new state Concepts : Use Global Variable: int nstates; | this file static core *last_state; | this file static int **kernel_base; | this file static int **kernel_end; | this file Use Functions : char *allocate (unsigned n); | main.c void fatal (char *); | error.c Parameters : int symbol Return : core *p ***************************************************************/ { register int n; register core *p; register int *isp1, *isp2; register int *iend; #ifdef TRACE mpu_fprintf( mpu_stderr, MPU_UCS2( "Entering new_state(%d)\n" ), symbol); #endif if( nstates >= MAXWORD ) fatal( (__mpu_char16_t *)MPU_UCS2( "Too many states" ) ); isp1 = kernel_base[symbol]; iend = kernel_end[symbol]; n = iend - isp1; p = (core *) allocate( (unsigned)(sizeof(core) + (n - 1) * sizeof(int)) ); p->accessing_symbol = symbol; p->number = nstates; p->nitems = n; isp2 = p->items; while( isp1 < iend ) *isp2++ = *isp1++; last_state->next = p; last_state = p; nstates++; return( p ); } /******* End of new_state( int symbol ) ********************/ int get_state( int symbol ) /*************************************************************** Description : get state Concepts : Use Global Variable: static core **state_set; | this file static int **kernel_base; | this file static int **kernel_end; | this file Use Functions : core * new_state (int symbol); | this file Parameters : int Return : int ***************************************************************/ { register int key; register int *isp1; register int *isp2; register int *iend; register core *sp; register int found; register int n; #ifdef TRACE mpu_fprintf( mpu_stderr, MPU_UCS2( "Entering get_state(%d)\n" ), symbol ); #endif isp1 = kernel_base[symbol]; iend = kernel_end[symbol]; n = iend - isp1; key = *isp1; if( 0 > key || key >= nitems ) { done( 2 ); } sp = state_set[key]; if( sp ) { found = 0; while( !found ) { if( sp->nitems == n ) { found = 1; isp1 = kernel_base[symbol]; isp2 = sp->items; while( found && isp1 < iend ) { if( *isp1++ != *isp2++ ) found = 0; } } if( !found ) { if( sp->link ) { sp = sp->link; } else { sp = sp->link = new_state( symbol ); found = 1; } } } } else { state_set[key] = sp = new_state( symbol ); } return( sp->number ); } /******* End of get_state( int symbol ) ********************/ void append_states( void ) /*************************************************************** Description : append states Concepts : Use Global Variable: static int nshifts; | this file static int *shiftset; | this file static int *shift_symbol; | this file Use Functions : int get_state (int symbol); | this file Parameters : [void] Return : [void] ***************************************************************/ { register int i; register int j; register int symbol; #ifdef TRACE mpu_fprintf( mpu_stderr, MPU_UCS2( "Entering append_states()\n" ) ); #endif for( i = 1; i < nshifts; i++ ) { symbol = shift_symbol[i]; j = i; while( j > 0 && shift_symbol[j - 1] > symbol ) { shift_symbol[j] = shift_symbol[j - 1]; j--; } shift_symbol[j] = symbol; } for( i = 0; i < nshifts; i++ ) { symbol = shift_symbol[i]; shiftset[i] = get_state (symbol); } } /******* End of append_states( void ) **********************/ void initialize_states( void ) /*************************************************************** Description : initialize states Concepts : Use Global Variable: int start_symbol; | main.c int **derives; | main.c int *rrhs; | main.c core *first_state; | this file static core *this_state; | this file static core *last_state; | this file Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int i; register int *start_derives; register core *p; start_derives = derives[start_symbol]; for( i = 0; start_derives[i] >= 0; ++i ) continue; p = (core *)MALLOC( sizeof(core) + i*sizeof(int) ); if( p == 0 ) no_space(); p->next = 0; p->link = 0; p->number = 0; p->accessing_symbol = 0; p->nitems = i; for( i = 0; start_derives[i] >= 0; ++i ) p->items[i] = rrhs[start_derives[i]]; first_state = last_state = this_state = p; nstates = 1; } /******* End of initialize_states( void ) ******************/ void new_itemsets( void ) /*************************************************************** Description : new itensets Concepts : Use Global Variable: int nsyms; | main.c int *ritem; | main.c int *itemset; | closure.c int *itemsetend; | closure.c static int nshifts; | this file static int *shift_symbol; | this file static int **kernel_base; | this file static int **kernel_end; | this file Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int i; register int shiftcount; register int *isp; register int *ksp; register int symbol; for( i = 0; i < nsyms; i++ ) kernel_end[i] = 0; shiftcount = 0; isp = itemset; while( isp < itemsetend ) { i = *isp++; symbol = ritem[i]; if( symbol > 0 ) { ksp = kernel_end[symbol]; if( !ksp ) { shift_symbol[shiftcount++] = symbol; ksp = kernel_base[symbol]; } *ksp++ = i + 1; kernel_end[symbol] = ksp; } } nshifts = shiftcount; } /******* End of new_itemsets( void ) ***********************/ void save_shifts( void ) /*************************************************************** Description : save shifts Concepts : Use Global Variable: static int nshifts; | this file static core *this_state; | this file static int *shiftset; | this file Use Functions : char * allocate (unsigned u); | main.c Parameters : [void] Return : [void] ***************************************************************/ { register shifts *p; register int *sp1; register int *sp2; register int *send; p = (shifts *)allocate( (unsigned)(sizeof (shifts) + (nshifts - 1) * sizeof(int)) ); p->number = this_state->number; p->nshifts = nshifts; sp1 = shiftset; sp2 = p->shift; send = shiftset + nshifts; while( sp1 < send ) *sp2++ = *sp1++; if( last_shift ) { last_shift->next = p; last_shift = p; } else { first_shift = p; last_shift = p; } } /******* End of save_shifts( void ) ************************/ void save_reductions( void ) /*************************************************************** Description : save reduction Concepts : Use Global Variable: int *ritem; | main.c int *itemset; | closure.c int *itemsetend; | closure.c static core *this_state; | this file reductions *first_reduction; | this file static reductions *last_reduction; | this file static int *redset; | this file Use Functions : char * allocate (unsigned u); | main.c Parameters : [void] Return : [void] ***************************************************************/ { register int *isp; register int *rp1; register int *rp2; register int item; register int count; register reductions *p; register int *rend; count = 0; for( isp = itemset; isp < itemsetend; isp++ ) { item = ritem[*isp]; if( item < 0 ) { redset[count++] = -item; } } if( count ) { p = (reductions *)allocate( (unsigned)(sizeof (reductions) + (count - 1) * sizeof(int)) ); p->number = this_state->number; p->nreds = count; rp1 = redset; rp2 = p->rules; rend = rp1 + count; while( rp1 < rend ) *rp2++ = *rp1++; if( last_reduction ) { last_reduction->next = p; last_reduction = p; } else { first_reduction = p; last_reduction = p; } } } /******* End of save_reductions( void ) ********************/ void set_derives( void ) /*************************************************************** Description : set derives Concepts : Use Global Variable: int nsyms; | main.c int nvars; | main.c int nrules; | main.c int start_symbol; | main.c int **derives; | main.c int *rlhs; | main.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int i, k; register int lhs; register int *rules; derives = NEW2( nsyms, int * ); rules = NEW2( nvars + nrules, int ); k = 0; for( lhs = start_symbol; lhs < nsyms; lhs++ ) { derives[lhs] = rules + k; for( i = 0; i < nrules; i++ ) { if( rlhs[i] == lhs ) { rules[k] = i; k++; } } rules[k] = -1; k++; } #ifdef _DEBUG print_derives(); #endif } /******* End of set_derives( void ) ************************/ void set_nullable( void ) /*************************************************************** Description : set nullable Concepts : Use Global Variable: int nsyms; | main.c int nitems; | main.c char **symbol_name; | main.c int *ritem; | main.c int *rlhs; | main.c Use Functions : void no_space (void); | error.c Parameters : [void] Return : [void] ***************************************************************/ { register int i, j; register int empty; int done; nullable = (char *)MALLOC( nsyms ); if( nullable == 0 ) no_space(); for( i = 0; i < nsyms; ++i ) nullable[i] = 0; done = 0; while( !done ) { done = 1; for( i = 1; i < nitems; i++ ) { empty = 1; while( (j = ritem[i]) >= 0 ) { if( !nullable[j] ) empty = 0; ++i; } if( empty ) { j = rlhs[-j]; if( !nullable[j] ) { nullable[j] = 1; done = 0; } } } } #ifdef _DEBUG for( i = 0; i < nsyms; i++ ) { if( nullable[i] ) mpu_fprintf( mpu_stdout, MPU_UCS2( "%s is nullable\n" ), symbol_name[i] ); else mpu_fprintf( mpu_stdout, MPU_UCS2( "%s is not nullable\n" ), symbol_name[i] ); } #endif } /******* End of set_nullable (void) ************************/ void generate_states( void ) /*************************************************************** Description : generate states Concepts : Use Global Variable: int nitems; | main.c int *itemset; | closure.c unsigned *ruleset; | closure.c static core *this_state; | this file Use Functions : void allocate_storage (void); | this file void free_storage (void); | this file void save_reductions (void); | this file void new_itemsets (void); | this file void append_states (void); | this file void save_shifts (void); | this file void initialize_states (void); | this file void set_first_derives (void); | closure.c void closure (int *, int); | closure.c void finalize_closure (void); | closure.c Parameters : [void] Return : [void] ***************************************************************/ { allocate_storage(); itemset = NEW2( nitems, int ); ruleset = NEW2( SIZE_IN_INT( nrules ), unsigned ); set_first_derives(); initialize_states(); while( this_state ) { closure( this_state->items, this_state->nitems ); save_reductions(); new_itemsets(); append_states(); if( nshifts > 0 ) save_shifts(); this_state = this_state->next; } finalize_closure(); free_storage(); } /******* Enf of generate_states( void ) ********************/ void lr0( void ) /*************************************************************** Description : lr0 Concepts : Use Global Variable: Use Functions : void set_derives (void); | this file void set_nullable (void); | this file void generate_states (void); | this file Parameters : [void] Return : [void] ***************************************************************/ { set_derives(); set_nullable(); generate_states(); } /******* End of lr0( void ) ********************************/ /********** this functions is not use of this file **********/ /********** this functions is use in main.c: done() **********/ void free_nullable( void ) /*************************************************************** Description : free nullable Concepts : Use Global Variable: char *nullable; | main.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { FREE( nullable ); } /******* End of free_nullable( void ) **********************/ void free_derives( void ) /*************************************************************** Description : free derives Concepts : Use Global Variable: int start_symbol; | main.c int **derives; | main.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { FREE( derives[start_symbol] ); FREE( derives ); } /******* Enf of free_derives( void ) ***********************/ #endif /* __NO_COMPILE */ /******************** END OF FILE LR0.C **********************/