/*************************************************************** LALR.C This file containts LALR routines 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 #ifndef __NO_COMPILE typedef struct ints { struct ints *next; int value;/*short*/ } ints; int tokensetsize; int *lookaheads; int *LAruleno; unsigned *LA; int *accessing_symbol; core **state_table; shifts **shift_table; reductions **reduction_table; int *goto_map; int *from_state; int *to_state; static int infinity; static int maxrhs; static int ngotos; static unsigned *F; static int **includes; static ints **lookback; static int **R; static int *INDEX; static int *VERTICES; static int top; void traverse( int i ) /*************************************************************** Description : traverse Concepts : Use Global Variable: int tokensetsize; | this file static int infinity; | this file static unsigned *F; | this file static int **R; | this file static int *INDEX; | this file static int *VERTICES; | this file static int top; | this file Use Functions : void traverse( int ); | this file Parameters : int i Return : [void] ***************************************************************/ { register unsigned *fp1, *fp2, *fp3; register int j; register int *rp; int height; unsigned *base; VERTICES[++top] = i; INDEX[i] = height = top; base = F + i * tokensetsize; fp3 = base + tokensetsize; rp = R[i]; if( rp ) { while( (j = *rp++) >= 0 ) { if( INDEX[j] == 0 ) traverse( j ); /* recursive call */ if( INDEX[i] > INDEX[j] ) INDEX[i] = INDEX[j]; fp1 = base; fp2 = F + j * tokensetsize; while( fp1 < fp3 ) *fp1++ |= *fp2++; } } if( INDEX[i] == height ) { for( ;; ) { j = VERTICES[top--]; INDEX[j] = infinity; if( i == j ) break; fp1 = base; fp2 = F + j * tokensetsize; while( fp1 < fp3 ) *fp2++ = *fp1++; } } } /******* End of traverse( int i ) **************************/ void digraph( int **relation ) /*************************************************************** Description : digraph Concepts : Use Global Variable: static int infinity; | this file static int ngotos; | this file static int **R; | this file static int *INDEX; | this file static int *VERTICES; | this file static int top; | this file Use Functions : void traverse( int ); | this file Parameters : int **relation Return : [void] ***************************************************************/ { register int i; infinity = ngotos + 2; INDEX = NEW2 (ngotos + 1, int ); VERTICES = NEW2 (ngotos + 1, int ); top = 0; R = relation; for( i = 0; i < ngotos; i++ ) INDEX[i] = 0; for( i = 0; i < ngotos; i++ ) { if( INDEX[i] == 0 && R[i] ) traverse( i ); } FREE( INDEX ); FREE( VERTICES ); } /******* End of digraph( int **relation ) ******************/ int ** transpose( int **R, int n ) /*************************************************************** Description : transpose Concepts : Use Global Variable: Use Functions : Parameters : int **R, int n Return : int ** ***************************************************************/ { register int **new_R; register int **temp_R; register int *nedges; register int *sp; register int i; register int k; nedges = NEW2( n, int ); for( i = 0; i < n; i++ ) { sp = R[i]; if( sp ) { while( *sp >= 0 ) nedges[*sp++]++; } } new_R = NEW2 (n, int *); temp_R = NEW2 (n, int *); for( i = 0; i < n; i++ ) { k = nedges[i]; if( k > 0 ) { sp = NEW2( k + 1, int ); new_R[i] = sp; temp_R[i] = sp; sp[k] = -1; } } FREE( nedges ); for( i = 0; i < n; i++ ) { sp = R[i]; if( sp ) { while( *sp >= 0 ) *temp_R[*sp++]++ = i; } } FREE( temp_R ); return( new_R ); } /******* End of transpose( int **R, int n ) ****************/ int map_goto( int state, int symbol ) /*************************************************************** Description : map_goto Concepts : Map_goto maps a state/symbol pair into its numeric representation. Use Global Variable: int *goto_map; | this file int *from_state; | this file Use Functions : Parameters : int state, int symbol Return : int ***************************************************************/ { register int high, low, middle; register int s; low = goto_map[symbol]; high = goto_map[symbol+1]; for( ;; ) { if( low > high ) { done( 2 ); } middle = ( low + high ) >> 1; s = from_state[middle]; if( s == state ) return( middle ); else if( s < state ) low = middle + 1; else high = middle - 1; } } /******* End of map_goto( int state, int symbol ) **********/ void add_lookback_edge( int stateno, int ruleno, int gotono ) /*************************************************************** Description : add_lookback_edge Concepts : Use Global Variable: int *lookaheads; | this file int *LAruleno; | this file static ints **lookback; | this file Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int i, k; register int found = 0; register ints *sp; i = lookaheads[stateno]; k = lookaheads[stateno + 1]; found = 0; while( !found && i < k ) { if( LAruleno[i] == ruleno ) found = 1; else ++i; } if( found == 0 ) { done( 2 ); } sp = NEW( ints ); sp->next = lookback[i]; sp->value = gotono; lookback[i] = sp; } /******* End of add_lookback_edge( int, int, int ) *********/ void compute_lookaheads( void ) /*************************************************************** Description : compute_lookaheads Concepts : Use Global Variable: int tokensetsize; | this file int *lookaheads; | this file unsigned *LA; | this file static unsigned *F; | this file static ints **lookback; | this file Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int i, n; register unsigned *fp1, *fp2, *fp3; register ints *sp, *next; register unsigned *rowp; rowp = LA; n = lookaheads[nstates]; for( i = 0; i < n; i++ ) { fp3 = rowp + tokensetsize; for( sp = lookback[i]; sp; sp = sp->next ) { fp1 = rowp; fp2 = F + tokensetsize * sp->value; while( fp1 < fp3 ) *fp1++ |= *fp2++; } rowp = fp3; } for( i = 0; i < n; i++ ) for( sp = lookback[i]; sp; sp = next ) { next = sp->next; FREE( sp ); } FREE( lookback ); FREE( F ); } /******* End of compute_lookaheads( void ) *****************/ void compute_FOLLOWS( void ) /*************************************************************** Description : compute_FOLLOWS Concepts : Use Global Variable: static short **includes; | this file Use Functions : void digraph( int ** ); | this file Parameters : [void] Return : [void] ***************************************************************/ { digraph( includes ); } /******* End of compute_FOLLOWS( void ) ********************/ void build_relations( void ) /*************************************************************** Description : build_relations Concepts : Use Global Variable: int *accessing_symbol; | this file shifts **shift_table; | this file int *from_state; | this file int *to_state; | this file static int maxrhs; | this file static int ngotos; | this file static int **includes; | this file char *nullable; | main.c int **derives; | main.c int *ritem; | main.c int *rrhs; | main.c Use Functions : void add_lookback_edge( int, int, int ); int map_goto( int, int ); | this file int ** transpose( int **, int ); | this file Parameters : [void] Return : [void] ***************************************************************/ { register int i; register int j; register int k; register int *rulep; register int *rp; register shifts *sp; register int length; register int nedges; register int done; register int state1; register int stateno; register int symbol1; register int symbol2; register int *intp; register int *edge; register int *states; register int **new_includes; includes = NEW2( ngotos, int * ); edge = NEW2( ngotos + 1, int ); states = NEW2( maxrhs + 1, int ); for( i = 0; i < ngotos; i++ ) { nedges = 0; state1 = from_state[i]; symbol1 = accessing_symbol[to_state[i]]; for( rulep = derives[symbol1]; *rulep >= 0; rulep++ ) { length = 1; states[0] = state1; stateno = state1; for( rp = ritem + rrhs[*rulep]; *rp >= 0; rp++ ) { symbol2 = *rp; sp = shift_table[stateno]; k = sp->nshifts; for( j = 0; j < k; j++ ) { stateno = sp->shift[j]; if( accessing_symbol[stateno] == symbol2 ) break; } states[length++] = stateno; } /* End of for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++) */ add_lookback_edge( stateno, *rulep, i ); length--; done = 0; while( !done ) { done = 1; rp--; if( ISVAR( *rp ) ) { stateno = states[--length]; edge[nedges++] = map_goto( stateno, *rp ); if( nullable[*rp] && length > 0 ) done = 0; } } /* End of while (!done) */ } /* End of for( rulep = derives[symbol1]; *rulep >= 0; rulep++ ) */ if( nedges ) { includes[i] = intp = NEW2( nedges + 1, int ); for( j = 0; j < nedges; j++ ) intp[j] = edge[j]; intp[nedges] = -1; } } /* End of for( i = 0; i < ngotos; i++ ) */ new_includes = transpose( includes, ngotos ); for( i = 0; i < ngotos; i++ ) if( includes[i] ) FREE( includes[i] ); FREE( includes ); includes = new_includes; FREE( edge ); FREE( states ); } /******* End of build_relations( void ) ********************/ void initialize_F( void ) /*************************************************************** Description : initialize_F Concepts : Use Global Variable: int tokensetsize; | this file int *accessing_symbol; | this file shifts **shift_table; | this file int *to_state; | this file static int ngotos; | this file static unsigned *F; | this file char *nullable; | main.c Use Functions : int map_goto( int, int ); | this file void digraph( int ** ); | this file Parameters : [void] Return : [void] ***************************************************************/ { register int i; register int j; register int k; register shifts *sp; register int *edge; register unsigned *rowp; register int *rp; register int **reads; register int nedges; register int stateno; register int symbol; register int nwords; nwords = ngotos * tokensetsize; F = NEW2( nwords, unsigned ); reads = NEW2( ngotos, int * ); edge = NEW2( ngotos + 1, int ); nedges = 0; rowp = F; for( i = 0; i < ngotos; i++ ) { stateno = to_state[i]; sp = shift_table[stateno]; if( sp ) { k = sp->nshifts; for( j = 0; j < k; j++ ) { symbol = accessing_symbol[sp->shift[j]]; if( ISVAR(symbol) ) break; SETBIT( rowp, symbol ); } for( ; j < k; j++ ) { symbol = accessing_symbol[sp->shift[j]]; if( nullable[symbol] ) edge[nedges++] = map_goto( stateno, symbol ); } if( nedges ) { reads[i] = rp = NEW2( nedges + 1, int ); for( j = 0; j < nedges; j++ ) rp[j] = edge[j]; rp[nedges] = -1; nedges = 0; } } rowp += tokensetsize; } /* End of for( i = 0; i < ngotos; i++ ) */ SETBIT( F, 0 ); digraph( reads ); for( i = 0; i < ngotos; i++ ) { if( reads[i] ) FREE( reads[i] ); } FREE( reads ); FREE( edge ); } /******* End of initialize_F( void ) ***********************/ void set_goto_map( void ) /*************************************************************** Description : set_goto_map Concepts : Use Global Variable: int *goto_map; | this file int *accessing_symbol; | this file static int ngotos; | this file int *from_state; | this file int *to_state; | this file shifts *first_shift; | lr0.c int nsyms; | main.c int nvars; | main.c int ntokens; | main.c Use Functions : void fatal( char * ); | error.c Parameters : [void] Return : [void] ***************************************************************/ { register shifts *sp; register int i; register int symbol; register int k; register int *temp_map; register int state2; register int state1; goto_map = NEW2( nvars + 1, int ) - ntokens; temp_map = NEW2( nvars + 1, int ) - ntokens; ngotos = 0; for( sp = first_shift; sp; sp = sp->next ) { for( i = sp->nshifts - 1; i >= 0; i-- ) { symbol = accessing_symbol[sp->shift[i]]; if( ISTOKEN(symbol) ) break; if( ngotos == MAXWORD ) fatal( (__mpu_char16_t *)MPU_UCS2( "Too many gotos" ) ); ngotos++; goto_map[symbol]++; } } k = 0; for( i = ntokens; i < nsyms; i++ ) { temp_map[i] = k; k += goto_map[i]; } for( i = ntokens; i < nsyms; i++ ) goto_map[i] = temp_map[i]; goto_map[nsyms] = ngotos; temp_map[nsyms] = ngotos; from_state = NEW2( ngotos, int ); to_state = NEW2( ngotos, int ); for( sp = first_shift; sp; sp = sp->next ) { state1 = sp->number; for( i = sp->nshifts - 1; i >= 0; i-- ) { state2 = sp->shift[i]; symbol = accessing_symbol[state2]; if( ISTOKEN(symbol) ) break; k = temp_map[symbol]++; from_state[k] = state1; to_state[k] = state2; } } FREE( temp_map + ntokens ); } /******* End of set_goto_map( void ) ***********************/ void initialize_LA( void ) /*************************************************************** Description : initialize_LA Concepts : Use Global Variable: int tokensetsize; | this file int *lookaheads; | this file reductions **reduction_table; | this file int *LAruleno; | this file unsigned *LA; | this file static ints **lookback; | this file int nstates; | lr0.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int i, j, k; register reductions *rp; lookaheads = NEW2( nstates + 1, int ); k = 0; for( i = 0; i < nstates; i++ ) { lookaheads[i] = k; rp = reduction_table[i]; if( rp ) k += rp->nreds; } lookaheads[nstates] = k; LA = NEW2 (k * tokensetsize, unsigned); LAruleno = NEW2 (k, int); lookback = NEW2 (k, ints *); k = 0; for( i = 0; i < nstates; i++ ) { rp = reduction_table[i]; if( rp ) { for( j = 0; j < rp->nreds; j++ ) { LAruleno[k] = rp->rules[j]; k++; } } } } /******* End of initialize_LA( void ) **********************/ void set_maxrhs( void ) /*************************************************************** Description : set_maxrhs Concepts : Use Global Variable: static int maxrhs; | this file int nitems; | main.c int *ritem; | main.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register int *itemp; register int *item_end; register int length; register int max; length = 0; max = 0; item_end = ritem + nitems; for( itemp = ritem; itemp < item_end; itemp++ ) { if( *itemp >= 0 ) { length++; } else { if( length > max ) max = length; length = 0; } } maxrhs = max; } /******* End of set_maxrhs( void ) *************************/ void set_reduction_table( void ) /*************************************************************** Description : set_reduction_table Concepts : Use Global Variable: reductions **reduction_table; | this file int nstates; | lr0.c reductions *first_reduction; | lr0.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register reductions *rp; reduction_table = NEW2( nstates, reductions * ); for( rp = first_reduction; rp; rp = rp->next ) reduction_table[rp->number] = rp; } /******* End of set_reduction_table( void ) ****************/ void set_shift_table( void ) /*************************************************************** Description : set_shift_table Concepts : Use Global Variable: shifts **shift_table; | this file int nstates; | lr0.c shifts *first_shift; | lr0.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register shifts *sp; shift_table = NEW2( nstates, shifts * ); for( sp = first_shift; sp; sp = sp->next ) shift_table[sp->number] = sp; } /******* End of set_shift_table( void ) ********************/ void set_accessing_symbol( void ) /*************************************************************** Description : set_accessing_symbol Concepts : Use Global Variable: short *accessing_symbol; | this file int nstates; | lr0.c core *first_state; | lr0.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register core *sp; accessing_symbol = NEW2( nstates, int ); for( sp = first_state; sp; sp = sp->next ) accessing_symbol[sp->number] = sp->accessing_symbol; } /******* End of set_accessing_symbol( void ) ***************/ void set_state_table( void ) /*************************************************************** Description : set_state_table Concepts : Use Global Variable: core **state_table; | this file int nstates; | lr0.c core *first_state; | lr0.c Use Functions : Parameters : [void] Return : [void] ***************************************************************/ { register core *sp; state_table = NEW2( nstates, core * ); for( sp = first_state; sp; sp = sp->next ) state_table[sp->number] = sp; } /******* End of set_state_table( void ) ********************/ void lalr( void ) /*************************************************************** Description : lalr Concepts : use in main.c Use Global Variable: int tokensetsize; | this file int ntokens; | main.c Use Functions : void set_state_table (void); | this file void set_accessing_symbol (void); | this file void set_shift_table (void); | this file void set_reduction_table (void); | this file void set_maxrhs (void); | this file void initialize_LA (void); | this file void set_goto_map (void); | this file void initialize_F (void); | this file void build_relations (void); | this file void compute_FOLLOWS (void); | this file void compute_lookaheads (void); | this file Parameters : [void] Return : [void] ***************************************************************/ { tokensetsize = SIZE_IN_INT( ntokens ); set_state_table(); set_accessing_symbol(); set_shift_table(); set_reduction_table(); set_maxrhs(); initialize_LA(); set_goto_map(); initialize_F(); build_relations(); compute_FOLLOWS(); compute_lookaheads(); } /******* End of lalr( void ) *******************************/ #endif /* __NO_COMPILE */ /******************** ENF OF FILE LALR.C *********************/