Thread: produce parse tree from regular expression

i got what the program does,can anybody plz explain the control flow for this program??


write a yacc program that accepts a regular expression as input and produce its parse tree as output.

Code:

%{
   /** 
       Yacc program to recognise a regular expression
       and produce a parse tree as output
    */
   #include <stdio.h>
   #include <ctype.h>
   #include <stdlib.h>
   #include <string.h>

   /* To store the productions */
   #define MAX 100

   int getREindex ( const char* );
   
   signed char productions[MAX][MAX];
   int count = 0 , i , j;
   char temp[MAX + MAX] , temp2[MAX + MAX];
%}

%token ALPHABET

%left '|'
%left '.'
%nonassoc '*' '+'

%%
S : re '\n'    { 
   printf ( "This is the rightmost derivation--\n" );
   for ( i = count - 1 ; i >= 0 ; --i ) {
       if ( i == count - 1 ) {
            printf ( "\nre => " );
            strcpy ( temp , productions[i] );
            printf ( "%s" , productions[i] );
       }
       else {
            printf ( "\n   => " );
            j = getREindex ( temp );
            temp[j] = '\0';
            sprintf ( temp2 , "%s%s%s" , temp , 
productions[i] , (temp + j + 2) );
            printf ( "%s" , temp2 );
            strcpy ( temp , temp2 );
      }
   }
   printf ( "\n" );
   exit ( 0 ); 
}
re : ALPHABET { 
              temp[0] = yylval; temp[1] = '\0';
              strcpy ( productions[count++] , temp );
              }
   | '(' re ')' 
        { strcpy ( productions[count++] , "(re)" ); }
   | re '*'            
        { strcpy ( productions[count++] , "re*" ); }
   | re '+' 
        { strcpy ( productions[count++] , "re+" ); }
   | re '|' re         
       {strcpy ( productions[count++] , "re | re" );}
   | re '.' re         
       {strcpy ( productions[count++] , "re . re" );}
   ;
%%
int main ( int argc , char **argv ) 
{
/* 
     Parse and output the rightmost derivation,
     from which we can get the parse tree 
*/
  yyparse();

  return 0;
}

yylex() 
{
  signed char ch = getchar();
  yylval = ch;
  if ( isalpha ( ch ) )
    return ALPHABET;
  return ch;
}

yyerror() 
{
  fprintf(stderr , "Invalid Regular Expression!!\n");
  exit ( 1 );
}

int getREindex ( const char *str ) 
{ 
  int i = strlen ( str ) - 1;
  for ( ; i >= 0 ; --i ) {
    if ( str[i] == 'e' && str[i-1] == 'r' )
      return i-1;
  }
}

OUTPUT

$a.out
a+|b*|(b.c*)
This is the rightmost derivation--

re => re | re
=> re | (re)
=> re | (re . re)
=> re | (re . re*)
=> re | (re . c*)
=> re | (b . c*)
=> re | re | (b . c*)
=> re | re* | (b . c*)
=> re | b* | (b . c*)
=> re+ | b* | (b . c*)
=> a+ | b* | (b . c*)