Like Tree1Likes
  • 1 Post By dollyve

produce parse tree from regular expression

This is a discussion on produce parse tree from regular expression within the Linux Programming forums, part of the Platform Specific Boards category; i got what the program does,can anybody plz explain the control flow for this program?? write a yacc program that ...

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    1

    Post 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*)
    sonic987 likes this.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    I'd like to learn yacc, but I still haven't, so I can't help, and I have xmas honey to jar -- but just to make certain: you do know what lex and yacc are? I notice there are some tutorials available online, maybe one of those would clear things up if nobody has any further light to shed.

    Putting "YACC" in the title or a tag would have been a good idea. Maybe one of the nice mods will do that for you
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Regular Expression
    By stevesmithx in forum C Programming
    Replies: 0
    Last Post: 02-18-2008, 10:00 AM
  2. regular expression
    By jackel7777 in forum C Programming
    Replies: 4
    Last Post: 08-16-2007, 03:02 AM
  3. about regular expression
    By asert in forum C Programming
    Replies: 1
    Last Post: 11-07-2006, 10:53 AM
  4. Regular Expression
    By tintifaxe in forum C++ Programming
    Replies: 3
    Last Post: 06-14-2006, 07:16 AM
  5. Regular Expression..
    By vasanth in forum Tech Board
    Replies: 3
    Last Post: 08-03-2004, 07:56 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21