summaryrefslogtreecommitdiff
path: root/src/lalr.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lalr.c')
-rw-r--r--src/lalr.c956
1 files changed, 956 insertions, 0 deletions
diff --git a/src/lalr.c b/src/lalr.c
new file mode 100644
index 0000000..74bea60
--- /dev/null
+++ b/src/lalr.c
@@ -0,0 +1,956 @@
+
+/***************************************************************
+ 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 <defs.h>
+
+#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 *********************/
generated by cgit v1.2.3 (git 2.39.0) at 2026-10-02 11:34:48 +0300