Finding common subexpressions: implementation

• We 'choose' the uniq storage option for expr.
• We add a (boolean) attribute visited to expr, with initial value: False.
• We add a (casestring) attribute name to expr, with initial value: 0.
  (casestring is a predefined phylum to represent case-sensitive strings)
• For the reverse mapping from names to expressions
  • we define a phylum mapping, for which we
  • we 'choose' the uniq storage option, and
  • we add an (expr) attribute e to mapping, with initial value: 0.
• For the list of all mappings, we a define a list phylum mappings.

expr {uniq} :
{ boolean visited = False; /* initial value */
  casestring name = 0; /* predef case sensitive string */
};

 /* define mapping ('assoc array'): casestring -> expr */
mapping {uniq} : Mapping( casestring )
{ expr e = 0; }      /* mapping from name to expr-node */
;

mappings: list mapping;

Plus( e1, e2 ),
Times( e1, e2 )           -> [ view_visit:
  { visit($0); }       /* $0 refers to current node */
  e1
  e2
];

Const( i )                -> [ view_visit:
  { visit($0); }       /* $0 refers to current node */
];

void visit (expr n)
{
  if ( ! n->visited ) {     /* node not yet visited */
    n->visited = True;           /* mark as visited */
  } else {              /* visited this node before */
    if ( n->name == 0 ) {         /* not yet a name */
      mapping m;
      n->name = gen_name();    /* generate new name */
      m = Mapping( n->name );    /* and new mapping */
      m->e = n;            /* map from name to node */
         /* insert mapping in list of all mappings: */
      all_mappings = Consmappings( m, all_mappings );
    }
  }
}

id gen_name()
{
  static int i = 0;
  char tmp[50];
  i++;
  sprintf(tmp, "id_%d", i);
  return mkcasestring( tmp );
}

Nilidlist()               -> [: /*EMPTY*/ ];
Consmappings( h, t )      -> [: ";\n" h t ];
Mapping( s )              -> [: s " = " $0-> e ];

Plus( *, * ),
Times( *, * ),
Const( * )                 -> [ test:
  { if ($0->name != 0) }       $0->name:base_uview
  { else }                     $0:base_uview
];

Const( i )                -> [: i ];
Plus( e1, e2 )            -> [: e1:test " + " e2:test ];
Times( e1, e2 )           -> [: e1:test " * " e2:test ];

Times( e1 = Plus(*,*),
       e2 )               -> [: e1:test2 " * " e2:test ];
Plus( e1,
      e2  = Plus(*,*))    -> [: e1:test " + " e2:test2 ];
Times( e1 = Plus(*,*),
       e2 = Plus(*,*) )   -> [: e1:test2 " * " e2:test2 ];

Plus( *, * )              -> [ test2:
  { if ($0->name != 0) }       $0->name:base_uview
  { else }                     ${ "(" $0:base_uview ")" $}
];

#include "k.h"                 /* data type defs */
#include "csgiok.h"    /* structure file io defs */
#include "unpk.h"  /* unparse (view) definitions */
#include "printer.h"     /* printer function def */

void main() {
  char *io;            /* error message, or == 0 */
  expr the_expr;       /* root of the parse tree */
  all_mappings = Nilmappings();
  io = CSGIOread_expr(stdin, &the_expr);
  if (io != 0)
      fatal("Read error: %s\n", io);

  /* apply the 'visit' routine to all nodes */
  unparse_expr(the_expr, printer, view_visit);

  /* show the output: the tree, and the list of mappings. */
  unparse_expr(the_expr, printer, test);
  unparse_mappings(all_mappings, printer, base_uview);
  printer("\n", base_uview);
  
  exit(0);                           /* success! */
}

next overview up