path: root/src/lalr.c

/***************************************************************
  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  *********************/