home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1988 / 05 / holub / holub.exm
Text File  |  1980-01-01  |  5KB  |  185 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.                 #include <ctype.h>
  9.  
  10.                 char *factor( str )
  11.                 char    *str;
  12.                 {
  13.                     char *expr();
  14.  
  15.                     if( isalpha( *str ) )       /* F -> name  */
  16.                         printf( "%c\n", *str );
  17.                     else if( *str == '(' )      /* F -> ( E ) */
  18.                         str = expr( ++str ); 
  19.                     return ++str;
  20.                 }
  21.  
  22.                 char *term( str )
  23.                 char    *str;
  24.                 {
  25.                     str = factor( str );        /* T -> FT'  */
  26.                     while( *str == '*' )        /* T'-> *FT' */
  27.                     {
  28.                         str++;
  29.                         str = factor( str );
  30.                         printf( "*\n" );
  31.                     }
  32.                     return str;                 /* T'-> eps */
  33.                 }
  34.  
  35.                 char   *expr( str )
  36.                 char   *str;
  37.                 {
  38.                     str = term( str );          /* E -> TE'  */
  39.                     while( *str == '+' )        /* E'-> +TE' */
  40.                     {
  41.                         str++;
  42.                         str = term( str );
  43.                         printf( "+\n" );
  44.                     }
  45.                     return str;                 /* E'-> eps */
  46.                 }
  47.  
  48.                 main()
  49.                 {
  50.                     char  buf[80];
  51.                     while( gets(buf) )
  52.                         expr( buf );
  53.                 }
  54.  
  55. Example 1: A postfix-output expression compiler
  56.  
  57.  
  58.               typedef struct node
  59.               {
  60.                   char        name[16];
  61.                   int         op;
  62.                   struct node *left;
  63.                   struct node *right;
  64.               }
  65.               NODE;
  66.  
  67.               NODE *new()
  68.               {
  69.                   NODE *p;
  70.                   void *calloc();
  71.  
  72.                   if( !(p = (NODE *) calloc( 1, sizeof(NODE) ) ) )
  73.                       exit(1);
  74.  
  75.                   return p;
  76.               }
  77.  
  78. Example 2: Data structure for constructing syntax trees
  79.  
  80.  
  81.  
  82.  
  83.                    NODE    *build()
  84.                    {
  85.                        char   buf[80];
  86.                        NODE   *stack[ 10 ];
  87.                        NODE   **sp = stack - 1;
  88.                        NODE   *p;
  89.  
  90.                        while( gets(buf) )
  91.                        {
  92.                            switch( *buf )
  93.                            {
  94.                            default:  p = new();
  95.                                      strcpy( p->name, buf );
  96.                                      *++sp = p;
  97.                                      break;
  98.  
  99.                            case '*':
  100.                            case '+':       
  101.                                      p          = new();
  102.                                      p->right   = *sp-- ;
  103.                                      p->left    = *sp-- ;
  104.                                      p->op      = *buf  ;
  105.                                      p->name[0] = *buf  ;
  106.                                      *++sp      = p     ;
  107.                                      break;
  108.                            }
  109.                        }
  110.                        return *sp--;
  111.                    }
  112.  
  113. Example 3: A postfix-to-syntax-tree constructor
  114.  
  115.  
  116.  
  117.         trav( root )
  118.         struct node *root;
  119.         {
  120.             static int tnum = 0;
  121.  
  122.             if( !root )
  123.                 return;
  124.  
  125.             if( !root->op )     /* leaf */
  126.             {
  127.                 printf ( "t%d = %s\n", tnum, root->name );
  128.                 sprintf( root->name , "t%d", tnum );
  129.                 ++tnum;
  130.             }
  131.             else
  132.             {
  133.                 trav( root->left  );
  134.  
  135.                 if( root->left != root->right )    /* Always true      */
  136.                     trav( root->right );           /* unless optimized */
  137.  
  138.                 printf("%s %c= %s\n", root->right->name,
  139.                                         root->op, root->left->name );
  140.                 strcpy( root->name,   root->right->name );
  141.             }
  142.         }
  143.  
  144. Example 4: A syntax-tree-traversing, code-generation pass
  145.  
  146.  
  147.  
  148.          optimize( root )
  149.          NODE    *root;
  150.          {
  151.              /* Stupid optimizer to eliminate common subexpressions */
  152.  
  153.              char sig1[ 32 ];
  154.              char sig2[ 32 ];
  155.  
  156.              if( root->right && root->left )
  157.              {
  158.                  optimize( root->right );
  159.                  optimize( root->left  );
  160.  
  161.                  *sig1 = *sig2 = '\0';
  162.                  makesig( root->right, sig1 );
  163.                  makesig( root->left , sig2 );
  164.  
  165.                  if( strcmp( sig1, sig2 ) == 0 )   /* subtrees match */
  166.                      root->right = root->left ;
  167.              }
  168.          }
  169.  
  170.          makesig( root, str )
  171.          NODE    *root;
  172.          char    *str;
  173.          {
  174.              if( !root )
  175.                  return;
  176.              
  177.              strcat( str, root->name );
  178.              makesig( root->left,  str );
  179.              makesig( root->right, str );
  180.          }
  181.  
  182. Example 5: A subroutine to do common-subexpression elimination
  183.  
  184.  
  185.