%{
#include <stream.h>
#include <fstream.h>
#include <strstream.h>
#include <string.h>
#include "external.h"
#include "basic.h"

static _IO_ostream_withassign cout_stream;

bool put_gen_lines = true;

ofstream fout;
ofstream fstring;

static bool file_IO = false;

static char buffer[1000];

static int lineno = 1;

static bool in_rule = false;

static list<String>* all_strings = new list<String>;

const Expr _variable = variable("variable");
const Expr _EMPTY_NAME_ = variable("");
const Expr _function = variable("function");
const Expr _Cons = variable("Cons");
const Expr _Nil = variable("Nil");
const Expr _integer = variable("integer");
const Expr _estring = variable("estring");


class continuation: public gc {
  list<String>* value;
public:
  continuation () { value = (new list<String>)->cons(new string("")); };
  remember ( const char* str ) { string s = string(str) + *value->hd; value->hd = new string(s); };
  remember () { remember("}"); };
  close () { String s = value->hd; value = value->tl; cout << s; };
  open () { value = value->cons(new string("")); };
};

static continuation* cont = new continuation;


yyerror (char*);


class stop_symbols: public gc {
  list<list<int>*>* stack;
public:
  stop_symbols() { stack = new list<list<int>*>; }
  push() { stack = stack->cons(new list<int>); };
  push(char c) { stack = stack->cons((new list<int>)->cons(c)); };
  push(int i) { stack = stack->cons((new list<int>)->cons(i)); };
  push(char c, int n) { stack = stack->cons((new list<int>)->cons(c)->cons(n)); };
  pop() { if (stack->consp()) stack = stack->tl;
          else yyerror("Unbalanced parentheses"); };
  list<int>* top() { if (stack->consp()) return stack->hd;
                     else yyerror("Unbalanced parentheses"); };
  print() { for(list<list<int>*>* r = stack; r->consp(); r=r->tl) cout << r->hd << endl; };
};

static stop_symbols* stopsyms = new stop_symbols;

int fsyms ( int sym ) {
  if (stopsyms->top()->nullp()) return sym;
  switch (sym)
  { case '(' : stopsyms->push(')'); break;
    case '{' : stopsyms->push('}'); break;
    case '[' : stopsyms->push(']'); break;
    case ')' : stopsyms->pop(); break;
    case '}' : stopsyms->pop(); break;
    case ']' : stopsyms->pop(); break;
    default: for(list<int>* r = stopsyms->top(); r->consp(); r=r->tl) 
               if (sym == r->hd) return sym;
  };
  return SPECIAL;
};

#include "optgen.yy.c"

yyerror (char *s) {
   cerr << s << " (line: " << lineno << ")" << " Token: " << yytext << endl;
   exit(-1);
};

static int rule_number;
static Expr rule_pattern;
static list<String>* inherited = new list<String>;
static list<String>* synthesized = new list<String>;
static logical_module_size = 0;
list<int>* logical_modules = new list<int>;


Expr reify ( Expr e ) {
  if (e->functionp())
  { list<Expr> *params = e->info.Function.Parameters;
    if (e->info.Function.Name->eq(variable("VAR")) && (params->consp()))
       if (params->hd->variablep()) return variable(params->hd->info.Variable);
    Expr ps = _Nil;
    for(list<Expr>* r = params->reverse(); r->consp(); r=r->tl)
       ps = function(_Cons,Nil->cons(ps)->cons(reify(r->hd)));
    return function(_function,Nil->cons(ps)->cons(reify(e->info.Function.Name)));
  } else if (e->variablep())
         return function(_variable,Nil->cons(estring(e->info.Variable)));
    else if (e->integerp())
         return function(_integer,Nil->cons(integer(e->info.Integer)));
    else if (e->stringp())
         return function(_estring,Nil->cons(estring(e->info.Estring)));
  return variable("error");
};


compile_pattern (expr *pattern, String exp, bool casep ) {
   if (pattern->variablep())
      if (file_IO)
      cout << form(" if (%s->variablep())\n if (%s->eq(_%s_))\n",
                   exp->value(),exp->value(),pattern->info.Variable->value());
      else cout << form(" if (%s->variablep())\n if (%s->info.Variable->eq(\"%s\"))\n",
                        exp->value(),exp->value(),pattern->info.Variable->value());
   else if (pattern->integerp())
      cout << form(" if (%s->integerp())\n if (%s->info.Integer == %i)\n",
                   exp->value(),exp->value(),pattern->info.Integer);
   else if (pattern->stringp())
      cout << form(" if (%s->stringp())\n if (%s->info.Estring->eq(\"%s\"))\n",
                   exp->value(),exp->value(),pattern->info.Estring->value());
   else if (pattern->functionp())
      { list<Expr>* params = pattern->info.Function.Parameters;
        if (pattern->info.Function.Name->eq(variable("VAR")) && (params->consp()))
        {  if (params->hd->variablep())
              { cout << form(" { %s = %s;\n",params->hd->info.Variable->value(),exp->value());
		cont->remember();
              }
	}
        else if (!casep && pattern->info.Function.Name->eq(variable("RVAR")) && (params->consp()))
        {  if (params->tl->hd->variablep())
              { cout << form(" { %s = %s;\n",params->tl->hd->info.Variable->value(),exp->value());
		cont->remember();
              }
	}
        else if (casep && pattern->info.Function.Name->eq(variable("RVAR")) && (params->consp()))
        { if (params->tl->hd->variablep())
         { String nm = params->tl->hd->info.Variable;
	   String nv = new_name();
	   String rv = new_name();
           cout << form(" { %s = %s; ",nm->value(),exp->value())
		<< form(" String %s = new_name();\n Expr %s;\n list<Expr>* stack_%s = Cons(%s,Nil);\n",
			rv->value(),nv->value(),nv->value(),nm->value())
		<< form(" loop_%s: if (stack_%s->nullp()) goto exit_%s;\n",
			nv->value(),nv->value(),nv->value())
		<< form(" %s = stack_%s->hd;\n stack_%s = stack_%s->tl;\n",
			nv->value(),nv->value(),nv->value(),nv->value());
	   cont->open();
	   compile_pattern(pattern->arguments()->hd,nv,casep);
	   cout	<< form("{ FOUND = true; %s = function(variable(\"bind\"),Cons(variable(%s),Cons(subst_expr(",
			nm->value(), rv->value() )
		<< reify(params->hd)
		<< form(",variable(%s),%s),Nil)));\n", rv->value(), nm->value() );
	   cont->close();
	   cout << "}; if (FOUND) {\n";
	   cont->remember(form("}};\n if (%s->functionp()) stack_%s = %s->arguments()->append(stack_%s);\n goto loop_%s;\n exit_%s: ;\n",
		         nv->value(),nv->value(),nv->value(),nv->value(),nv->value(),nv->value()));
	 }
        }
	else {
	if (pattern->info.Function.Name->functionp()
           && pattern->info.Function.Name->info.Function.Name->eq(variable("VAR"))
	   && pattern->info.Function.Name->info.Function.Parameters->consp())
        { cout << form(" if (%s->functionp())\n",exp->value())
	       << form(" { %s = %s->info.Function.Name;\n",
		       pattern->info.Function.Name->info.Function.Parameters->hd->info.Variable->value(),exp->value());
	  cont->remember();
	}
        else cout << form(" if (%s->functionp())\n",exp->value())
		  << form(" if (%s->info.Function.Name->eq(_",exp->value())
		  << pattern->info.Function.Name
		  << "_))\n";
        String cexp = new string(form("%s->info.Function.Parameters",exp->value()));
        list<Expr> *r = params;
        for( ; r->consp(); r=r->tl )
           { if (r->hd->functionp())
		if (r->hd->info.Function.Name->eq(variable("VARN"))
                    && (r->hd->info.Function.Parameters->consp()))
                   if (r->hd->info.Function.Parameters->tl->nullp())
		   { String nm = new_name();
		     String vm = r->hd->info.Function.Parameters->hd->info.Variable;
		     if (r->tl->nullp())
		     { cout << form(" { %s = %s;\n",vm->value(),cexp->value());
		       cont->remember();
		       break;
                     };
		     cout << form(" { %s = Nil;\n for(list<Expr>* %s = %s; %s%s->consp(); %s=%s->append(Cons(%s->hd,Nil)), %s=%s->tl)\n",
				  vm->value(),nm->value(),cexp->value(),
				  (in_rule?"":"!FOUND && "),nm->value(),vm->value(),vm->value(),
				  nm->value(),nm->value(),nm->value());
		     cont->remember();
		     cexp = nm;
		     continue;
		   };
             cout << form(" if ((%s)->consp())\n",cexp->value());
             compile_pattern(r->hd,new string(form("%s->hd",cexp->value())),casep);
	     string s = *cexp + "->tl";
             cexp = new string(s);
          };
        if (r->nullp()) cout << form(" if (%s->nullp())\n",cexp->value());
      }
    }
};


var_decl ( Expr e, const char* type_name ) {
  if (e->functionp())
  { list<Expr>* params = e->info.Function.Parameters;
    if (e->info.Function.Name->functionp()
	&& e->info.Function.Name->info.Function.Name->eq(variable("VAR"))
	&& e->info.Function.Name->info.Function.Parameters->consp())
       { if (e->info.Function.Name->info.Function.Parameters->hd->variablep())
            cout << form("%s %s;\n",type_name,
		e->info.Function.Name->info.Function.Parameters->hd->info.Variable->value());
       };
    if (e->info.Function.Name->eq(variable("VAR")) && (params->consp()))
       { if (params->hd->variablep())
            cout << form("%s %s;\n",type_name,params->hd->info.Variable->value());
       }
    else if (e->info.Function.Name->eq(variable("RVAR")) && (params->consp()))
       { if (params->tl->hd->variablep())
            cout << form("%s %s;\n",type_name,params->tl->hd->info.Variable->value());
	 var_decl(params->hd,type_name);
       }
    else if (e->info.Function.Name->eq(variable("VARN")) && (params->consp()))
       { if (params->hd->variablep() && (params->tl->nullp()))
            cout << form("list<%s>* %s;\n",type_name,params->hd->info.Variable->value());
       }
    else for( list<Expr>* r = params; r->consp(); r=r->tl ) var_decl(r->hd,type_name);
  };
};


rewrite_vars ( Expr e, String rname) {
  if (e->functionp())
  { list<Expr> *params = e->info.Function.Parameters;
    if (e->info.Function.Name->eq(variable("VAR")) && (params->consp()))
       { if (params->hd->variablep())
         { String nm = params->hd->info.Variable;
           cout << form(" for(list<plan*>* _%s = %s_REWRITE(%s,",nm->value(),rname->value(),nm->value());
	   if (params->tl->nullp()) cout << "ATRBS";
           else if (params->tl->hd->functionp())
		{ cout << "inherit(";
		  for(list<Expr>* r = params->tl->hd->info.Function.Parameters; r->consp(); r=r->tl)
		  {  if (r->hd->functionp())
			if (r->hd->info.Function.Name->eq(variable("#")))
			   cout << r->hd->info.Function.Parameters->hd;
			else cout << "ATRBS." << r->hd;
		     else cout << "ATRBS." << r->hd;
		     if (r->tl->consp()) cout << ",";
		  };
		  cout << ")";
		} else cout << "ATRBS";
           cout << form(",LEVEL+1); _%s->consp(); _%s=_%s->tl) {\n",nm->value(),nm->value(),nm->value())
		<< form(" Expr %s = _%s->hd->expression;\n",nm->value(),nm->value());
	   cont->remember();
	 }
       }
    else if (e->info.Function.Name->eq(variable("RVAR")) && (params->consp()))
       { if (params->tl->hd->variablep())
         { String nm = params->tl->hd->info.Variable;
           cout << form(" for(list<plan*>* _%s = %s_REWRITE(%s,",nm->value(),rname->value(),nm->value());
	   if (params->tl->tl->nullp()) cout << "ATRBS";
           else if (params->tl->tl->hd->functionp())
		{ cout << "inherit(";
		  for(list<Expr>* r = params->tl->tl->hd->info.Function.Parameters; r->consp(); r=r->tl)
		  {  if (r->hd->functionp())
			if (r->hd->info.Function.Name->eq(variable("#")))
			   cout << r->hd->info.Function.Parameters->hd;
			else cout << "ATRBS." << r->hd;
		     else cout << "ATRBS." << r->hd;
		     if (r->tl->consp()) cout << ",";
		  };
		  cout << ")";
		} else cout << "ATRBS";
	   String nv = new_name();
	   String rv = new_name();
           cout << form(",LEVEL+1); _%s->consp(); _%s=_%s->tl) {\n",nm->value(),nm->value(),nm->value())
		<< form(" bool RFOUND = false; String %s = new_name();\n Expr %s;\n",
			rv->value(),nv->value())
		<< form(" list<Expr>* stack_%s = Cons(_%s->hd->expression,Nil);\n",
			nv->value(),nm->value())
		<< form(" loop_%s: if (stack_%s->nullp()) goto exit_%s;\n",
			nv->value(),nv->value(),nv->value())
		<< form(" %s = stack_%s->hd;\n stack_%s = stack_%s->tl;\n",
			nv->value(),nv->value(),nv->value(),nv->value());
	   cont->open();
	   compile_pattern(e->arguments()->hd,nv,false);
	   cout	<< form("{ RFOUND = true; %s = function(variable(\"bind\"),Cons(variable(%s),Cons(subst_expr(",
			nm->value(), rv->value() )
		<< reify(params->hd)
		<< form(",variable(%s),_%s->hd->expression),Nil)));\n", rv->value(), nm->value() );
	   cont->close();
	   cout << "}; if (RFOUND) {\n";
	   cont->remember(form("}};\n if (%s->functionp()) stack_%s = %s->arguments()->append(stack_%s);\n goto loop_%s;\n exit_%s: ;\n",
		         nv->value(),nv->value(),nv->value(),nv->value(),nv->value(),nv->value()));
	 }
       }
    else if (e->info.Function.Name->eq(variable("VARN")) && (params->consp()))
       { if (params->hd->variablep())
         { String nm = params->hd->info.Variable;
	   cout << form(" for(list<plan*>* _%s = default_rewrite(function(_EMPTY_NAME_,%s),",
			nm->value(),nm->value())
		<< form("ATRBS,LEVEL+1,%s_REWRITE); _%s->consp(); _%s=_%s->tl) {\n",
			rname->value(),nm->value(),nm->value(),nm->value())
		<< form(" list<Expr>* %s = _%s->hd->expression->info.Function.Parameters;\n",
			nm->value(),nm->value());
	   cont->remember();
	 }
       }
    else for( list<Expr> *r = params; r->consp(); r=r->tl )
	    rewrite_vars(r->hd,rname);
  };
};


Expr change_attributes ( binding<Expr>* bl ) {
  list<Expr>* params = Nil;
  for(list<String>* r = inherited; r->consp(); r = r->tl)
  { params = params->cons(variable(r->hd));
    for(binding<Expr>* s = bl; s->more(); s = s->next())
       if (s->current()->first->eq(r->hd))
          params = params->tl->cons(function(variable("#"),Nil->cons(s->current()->second)));
  };
  return function(variable("ATRBS"),params->reverse());
};


prelude (String name) {
  cout << "list<plan*>* " << name << "_REWRITE ( Expr EXPR, inherited ATRBS, int LEVEL ) {\n"
       << form("memo* MEMO = memoized(%s_hash_table,EXPR,ATRBS);\n",name->value())
       << "if (MEMO != 0) {\n"
       << "   /* if (trace_rules) trace_output(LEVEL,0,MEMO->plans); */\n"
       << "   return MEMO->plans;\n"
       << "};\n"
       << "list<plan*>* PLANS = EMPTY_PLANS;\n"
       << "list<plan*>* NEW_PLANS = EMPTY_PLANS;\n"
       << form("MEMO = memoize_empty(%s_hash_table,EXPR,ATRBS);\n",name->value())
       << "if (trace_rules && EXPR->functionp()) trace_input(LEVEL,0,EXPR,ATRBS);";
};

%}
%union {
   String				Tstring;
   list<String>*			Tstrings;
   int					Tint;
   bool					Tbool;
   Expr					Texpression;
   list<Expr>*				Tparameters;
   pair<String,Expr>*			Tbinding;
   binding<Expr>*			Tbindings;
}
%type <Tstring> name rname
%type <Texpression> pattern exp rest variable patvar prelude cprelude
%type <Tparameters> patterns exps
%type <Tint> condition patrbs
%type <Tbool> becomes pcases pcase pbinds
%type <Tbinding> atrbpat atrbexp
%type <Tbindings> atrbpats attributes atrbexps
%type <Tstrings> names synths
%token ID NUM CSTRING SPECIAL META CASE END IMPLIES DOTS IS LOGICAL PHYSICAL PERMUTATION INHERITED SYNTHESIZED COMPUTE LET IN DO FORALL TRACE FAIL
%%
main:	  ccode			{ stopsyms->push(); }
	  optgen
	;
ccode:    ctoken
	| ccode ctoken
	;
ctoken:	  name			{ cout << $1; }
	| NUM			{ cout << yytext; }
	| CSTRING		{ cout << yytext; }
	| '^' name		{ cout << "_" << $2 << "->hd->attributes"; }
	| SPECIAL		{ cout << yytext; }
	| '#' name		{ cout << "#" << $2; }
	| META 			{ stopsyms->push(); }
	  exp '>' 		{ cout << $3; stopsyms->pop(); }
	| CASE			{ stopsyms->push('|');
				  cout << "{ bool FOUND = false;\n Expr EXPR = "; }
	  ccode			{ cout << ";\n";
				  stopsyms->pop();
				  stopsyms->push(); }
          cases			{ stopsyms->pop(); }
	  END			{ cout << "\n}";
				  if (put_gen_lines) cout << "\n#line " << lineno << endl; }
	;
case:	  '|'			{ cont->open();
				  cout << "if (!FOUND) {\n";
				  cont->remember(); }
	  cprelude condition IMPLIES
				{ stopsyms->pop();
				  stopsyms->push('|',END); }
	  ccode			{ cout << "\n FOUND = true;";
				  cont->close();
				  if ($4) cout << " } };";
				  stopsyms->pop();
				  stopsyms->push(); }
	;
cases:	  case
	| cases case
	;
prelude:  pattern		{ cout << "{ ";
				  cont->remember();
				  var_decl($1,"Expr");
				  compile_pattern($1,new string("EXPR"),false);
				  cout << " {\n";
				  cont->remember();
				  $$ = $1; }
	| LET blist IN prelude	{ cout << "{ ";
				  cont->remember();
				  var_decl($4,"Expr");
				  compile_pattern($4,new string("EXPR"),false);
				  cout << " {\n";
				  cont->remember();
				  $$ = $4; }
	;
cprelude:  pattern		{ cout << "{ ";
				  cont->remember();
				  var_decl($1,"Expr");
				  compile_pattern($1,new string("EXPR"),true);
				  cout << " {\n";
				  cont->remember();
				  $$ = $1; }
	;
name:	  ID			{ $$ = new string(yytext); }
	;
variable: name			{ if (!member(variable($1),all_strings))
				     all_strings = all_strings->cons($1);
				  if (file_IO)
				     { $$ = variable(new string(form("_%s_",$1->value()))); }
				  else $$ = function(_variable,Nil->cons(estring($1))); }
	| '`' name		{ $$ = variable($2); }
	| '`' '('		{ buffer[0] = '\0';
				  ostrstream so(buffer,1000,ios::out);
				  cout_stream = cout;
				  cout = so;
				  stopsyms->push(')'); }
	  ccode			{ cout << '\0';
				  cout = cout_stream;
				  buffer[strlen(buffer)-1] = '\0';
				  $$ = function(_EMPTY_NAME_,Nil->cons(variable(new string(buffer)))); }
	| '_'			{ $$ = function(_variable,Nil->cons(estring("_"))); }
	;
exp:	  NUM			{ $$ = function(_integer,Nil->cons(integer(atoi(yytext)))); }
	| CSTRING		{ yytext[strlen(yytext)-1] = '\0';
				  $$ = function(_estring,Nil->cons(estring(new string(yytext+1)))); }
	| variable		{ $$ = $1; }
	| variable '(' ')'	{ $$ = function(_function,Nil->cons(_Nil)->cons($1)); }
	| variable '(' exps ')'
			{ Expr params = _Nil;
			  for(list<Expr>* r = $3; r->consp(); r=r->tl)
			     if (r->hd->functionp() && r->hd->info.Function.Name->eq(variable("*")))
				if (r != $3)
				   params = function(variable("Append"),
						Nil->cons(params)->cons(r->hd->info.Function.Parameters->hd));
				else params = r->hd->info.Function.Parameters->hd;
			     else params = function(_Cons,Nil->cons(params)->cons(r->hd));
			  $$ = function(_function,Nil->cons(params)->cons($1)); }
	| '`' name '[' exp ']'
			{ $$ = function(variable("substitute"),Cons(variable($2),Cons($4,Nil))); }
	| '(' exp ')'		{ $$ = $2; }
	;
exps:	  exp			{ $$ = Nil->cons($1); }
	| rest			{ $$ = Nil->cons(function(variable("*"),Nil->cons($1))); }
	| exps ',' rest		{ $$ = $1->cons(function(variable("*"),Nil->cons($3))); }
	| exps ',' exp		{ $$ = $1->cons($3); }
	;
rest:	  /* empty */		{ $$ = _Nil; }
	| DOTS name		{ $$ = variable($2); }
	| DOTS '('		{ for(short i = 100; i>=0; i--) buffer[i] = '\0';
				  ostrstream so(buffer,100,ios::out);
				  cout_stream = cout;
				  cout = so;
				  stopsyms->push(')'); }
	  ccode			{ cout = cout_stream;
				  buffer[strlen(buffer)-1] = '\0';
				  $$ = variable(new string(buffer)); }
	| DOTS			{ $$ = variable("_"); }
	;
patvar:   name			{ if (!member(variable($1),all_strings))
				     all_strings = all_strings->cons($1);
				  $$ = variable($1); }
	| '`' name		{ $$ = function(variable("VAR"),Nil->cons(variable($2))); }
	| '`' name IS '{' atrbexps '}'
		{ $$ = function(variable("VAR"),Nil->cons(change_attributes($5))->cons(variable($2))); }
	| '`' name '[' pattern ']'
			{ $$ = function(variable("RVAR"),Nil->cons(variable($2))->cons($4)); }
	| '`' name '[' pattern ']' IS '{' atrbexps '}'
			{ $$ = function(variable("RVAR"),Nil->cons(change_attributes($8))->cons(variable($2))->cons($4)); }
	| '_'			{ $$ = function(variable("VAR"),Nil->cons(new_variable())); }
	;
pattern:  NUM			{ $$ = integer(atoi(yytext)); }
	| CSTRING		{ yytext[strlen(yytext)-1] = '\0';
				  $$ = estring(yytext+1); }
	| patvar		{ $$ = $1; }
	| patvar '(' patterns ')'
			{ $$ = function($1,$3->reverse()); }
	| patvar '(' ')'
			{ $$ = function($1,Nil); }
	| '(' pattern ')'	{ $$ = $2; }
	;
patterns: pattern		{ $$ = Nil->cons($1); }
	| DOTS name		{ $$ = Nil->cons(function(variable("VARN"),Nil->cons(variable($2)))); }
	| patterns ',' DOTS name { $$ = $1->cons(function(variable("VARN"),Nil->cons(variable($4)))); }
	| patterns ',' pattern	{ $$ = $1->cons($3); }
	;
optgen:   /* empty */
	| '%' '{'	{ stopsyms->push('%'); }
	  ccode		{ stopsyms->pop();
			  cout << "#ifndef trace_rules\n#define trace_rules false\n#endif\n"
			       << "#ifndef trace_stages\n#define trace_stages false\n#endif\n"
			       << "#ifndef hash_size\n#define hash_size 1000\n#endif\n"; }
	  '%' TRACE	{ cout << "#define rules_to_trace "; stopsyms->push('%'); }
	  ccode		{ cout << endl; stopsyms->pop(); }
	  '%' INHERITED		{ cout << "struct inherited {"; }
	  names			{ for(list<String>* r = $14; r->consp(); r = r->tl)
				     inherited = inherited->cons(r->hd);
				  for(list<String>* r = inherited; r->consp(); r = r->tl)
				     cout << " Expr " << r->hd << ";";
				  cout << "\n};\n\ninherited inherit( Expr _" << inherited->hd;
				  for(list<String>* r = inherited->tl; r->consp(); r = r->tl)
				     cout << ", Expr _" << r->hd;
				  cout << " ) { inherited atrb; ";
				  for(list<String>* r = inherited; r->consp(); r = r->tl)
				     cout << "atrb." << r->hd << "=_" << r->hd << "; ";
				  cout << "return atrb; };\n\n"
				       << "ostream& operator<< ( ostream& s, inherited x ) { return s";
				  for(list<String>* r = inherited; r->consp(); r = r->tl)
				     cout << " << \"" << r->hd << ": \" << x." << r->hd << " << \",\"";
				  cout << "; };\n\n"; }
	  '%' SYNTHESIZED	{ cout << "struct synthesized {\n"; }
	  '{' synths '}' '='	{ stopsyms->push('%');
				  cout << "\n};\n\nsynthesized default_synthesized = "; }
	  ccode	 { cout << ";\n\n"
			<< "class plan: public gc {\npublic:\n  Expr expression;\n  synthesized attributes;\n"
			<< "  plan ( Expr e, synthesized s ) { expression = e; attributes = s; };\n};\n\n"
			<< "list<plan*>* EMPTY_PLANS = new list<plan*>;\n\n"
			<< "class memo: public gc {\npublic:\n  Expr expression;\n  inherited attributes;\n"
			<< "  list<plan*>* plans;\n"
			<< "  memo ( Expr e, inherited s, list<plan*>* p )\n"
			<< "       { expression = e; attributes = s; plans = p; };\n};"
			<< "\n\nshort eqatrb ( inherited X, inherited Y ) { return ";
		   for(list<String>* r = inherited; r->consp(); r = r->tl)
		      cout << "X." << r->hd << "->eq(Y." << r->hd << ") && ";
		   cout << "true; };\n\n#include \"common.h\"\n\n";
		   stopsyms->pop();
		   synthesized = $20; }
	  logrules '%' PHYSICAL
				{ cout << "\n\nlist<plan*>* all_plans_ (list<plan*>* x) { return x; };\n"
				       << "static list<plan*>* (*best_plans) (list<plan*>*) = &all_plans_;\n\n";
				  prelude(new string("PHYSICAL")); }
	  prules
				{ cout << "  if (PLANS->nullp())\n"
				       << "     PLANS = default_rewrite(EXPR,ATRBS,LEVEL,PHYSICAL_REWRITE);\n"
				       << "  PLANS = (*best_plans)(PLANS);\n"
				       << "if (trace_rules && EXPR->functionp()) trace_output(LEVEL,0,PLANS);\n"
				       << "MEMO->plans = PLANS; return PLANS;\n};\n";
				  if (put_gen_lines) cout << "#line " << lineno << endl; }
	  '%' '}'		{ stopsyms->pop();
				  cout << "\noptimizer_init () {\n"
				       << "  int x[100] = rules_to_trace;\n"
				       << "  for(short i = 0; i<100; i++) rules2trace[i] = x[i];\n"
				       << "  if (trace_rules) { cout << \"Tracing the rules: \";\n  for(short i = 0; x[i]; i++) cout << x[i] << \",\";\n  cout << endl; };\n";
				  for(int i = 1; i<=logical_module_size; i++)
				     cout << form("  hash_table_init(LOGICAL%i_hash_table);\n",i);
				  cout << "  hash_table_init(PHYSICAL_hash_table);\n};\n\n";
				  cout << "list<plan*>* rewrite ( Expr EXPR, inherited ATRBS, bool generate_plans ) {\n"
				       << "  list<plan*>* res = EMPTY_PLANS;\n";
				  for(int i = 1; i<=logical_module_size; i++)
				     cout << form("  for(list<plan*>* p%i = LOGICAL%i_REWRITE(%s,ATRBS,0);",
						  i,i,(i==1)?"EXPR":form("p%i->hd->expression",i-1))
					  << form(" p%i->consp(); p%i=p%i->tl)\n",
						  i,i,i)
					  << form("  { if (trace_stages)\n    { cout << \"\\nStage %i: \"; p%i->hd->expression->pretty_print(9); cout << endl; };\n",i,i);
				  cout << "     if (generate_plans)\n"
				       << form("         res = (*best_plans)(res->append(PHYSICAL_REWRITE(p%i->hd->expression",
					       logical_module_size)
				       << form(",ATRBS,0)));\n else res = res->cons(p%i->hd);\n",
					       logical_module_size);
				  for(int i = 1; i<=logical_module_size; i++) cout << " };";
				  cout << "   return res;\n};\n";
				  if (put_gen_lines) cout << "#line " << lineno << endl;
				}
	  ccode
	;
logrule:  '%' LOGICAL		{ logical_modules = logical_modules->cons(logical_module_size++);
				  String name = new string(form("LOGICAL%i",logical_module_size));
				  cout << form("static list<memo*>* %s_hash_table[hash_size];\n\n",name->value());
				  prelude(name); }
	  lrules		{ /* cout << " PLANS = merge_plans(PLANS,default_rewrite(EXPR,"
				       << form("ATRBS,LEVEL,LOGICAL%i_REWRITE));\n",
					       logical_module_size); */
				  cout << " if (PLANS->nullp()) PLANS = default_rewrite(EXPR,"
				       << form("ATRBS,LEVEL,LOGICAL%i_REWRITE);\n",
					       logical_module_size);
				  cout << "if (trace_rules && EXPR->functionp()) trace_output(LEVEL,0,PLANS);\n"
				       << "MEMO->plans = PLANS; return PLANS;\n};\n";
				  if (put_gen_lines) cout << "#line " << lineno << endl; }
	;
logrules: logrule
	| logrules logrule
	;
names:	  name			{ $$ = (new list<String>)->cons($1); }
	| names ',' name	{ $$ = $1->cons($3); }
	;
synths:	  name name ';'		{ cout << $1 << " " << $2 << ";";
				  $$ = (new list<String>)->cons($2); }
	| synths name name ';'	{ cout << $2 << " " << $3 << ";";
				  $$ = $1->cons($3); }
	;
lrule:				{ cont->open(); }
	  patrbs prelude	{ cout << form(" if (trace_rules && EXPR->functionp()) trace_input(LEVEL,%i,EXPR,ATRBS);\n",
					       rule_number);
				  in_rule = false;
				  rewrite_vars($3,new string(form("LOGICAL%i",logical_module_size)));
				  if (put_gen_lines) cout << "#line " << lineno << endl;
				  cout << "{ \nNEW_PLANS = EMPTY_PLANS;\n";
				  rule_pattern = $3; }
	  condition becomes binds ';'
				{ cout << form(" if (trace_rules && EXPR->functionp()) trace_output(LEVEL,%i,NEW_PLANS);\n",
					       rule_number);
				  if ($6) cout << " MEMO->plans = NEW_PLANS;\n return NEW_PLANS;";
				     else cout << " PLANS = merge_plans(PLANS,NEW_PLANS);";
				  if ($5) cout << form("\n } else if (trace_rules && EXPR->functionp()) trace(LEVEL,%i,\"condition failed\"); };",
						       rule_number);
				  cont->close();
				  cout << form("} }; exit_%i:;\n",rule_number);
				}
	;
becomes:  '='			{ $$ = false; }
	| IMPLIES		{ $$ = true; }
	;
lrules:	  lrule			{}
	| lrules lrule		{}
	;
binds:	  exp			{ if (put_gen_lines) cout << "\n#line " << lineno << endl;
				  cout << " NEW_PLANS = merge_plans(NEW_PLANS,"
				       << form("LOGICAL%i",logical_module_size)
				       << "_REWRITE(" << $1 << ",ATRBS,LEVEL+1));\n"; }
	| FAIL			{ cout << form(" FOUND = false; goto exit_%i; ",rule_number); }
	| CASE			{ stopsyms->push('|');
				  cout << "{ bool FOUND = false;\n Expr EXPR = "; }
	  ccode			{ cout << ";\n";
				  stopsyms->pop();
				  stopsyms->push(); }
          lcases		{ stopsyms->pop(); }
	  END			{ cout << form("\n if (!FOUND || NEW_PLANS->nullp()) goto exit_%i; }\n",
					       rule_number);
				  if (put_gen_lines) cout << "#line " << lineno << endl; }
	| FORALL name IN	{ stopsyms->push(DO);
				  cout << form("for(list<Expr>* _%s = ",$2->value()); }
	  ccode			{ cout << form("; _%s->consp(); _%s=_%s->tl) { Expr %s = _%s->hd;\n",
					       $2->value(),$2->value(),$2->value(),$2->value(),$2->value());
				  stopsyms->pop();
				  stopsyms->push(); }
          DO binds ';'		{ stopsyms->pop(); }
	  END			{ cout << " };\n";
				  if (put_gen_lines) cout << "#line " << lineno << endl; }
	| LET blist IN binds	{}
	;
bind:	  			{ stopsyms->push(',',IN); }
	  ccode			{ cout << "; "; stopsyms->pop(); }
	;
blist:	  bind			{}
	| blist ',' bind	{}
	;
lcase:	  '|'			{ cont->open();
				  cout << "if (!FOUND) {\n"; }
	  cprelude condition IMPLIES binds ';'
				{ cout << "\n FOUND = true;";
				  if ($4) cout << " } else FOUND = false;";
				  cont->close();
				  if ($4) cout << " }";
				  cout << " };\n"; }
	;
lcases:	  lcase
	| lcases lcase
	;
prule:				{ cont->open(); }
	  patrbs prelude	{ cout << form(" if (trace_rules && EXPR->functionp()) trace_input(LEVEL,%i,EXPR,ATRBS);\n",
					       rule_number);
				  in_rule = false;
				  rewrite_vars($3,new string("PHYSICAL"));
				  if (put_gen_lines) cout << "#line " << lineno << endl;
				  cout << "{ \nNEW_PLANS = EMPTY_PLANS;\n";
				  rule_pattern = $3; }
	  condition becomes pbinds ';'
			{ cout << form("if (trace_rules && EXPR->functionp()) trace_output(LEVEL,%i,NEW_PLANS);\n",
				       rule_number);
			  cout << " PLANS = merge_plans(PLANS,NEW_PLANS);";
			  if ($5) cout << form("\n } else if (trace_rules && EXPR->functionp()) trace(LEVEL,%i,\"condition failed\"); };",
					       rule_number);
			  cont->close();
			  cout << form("} }; exit_%i:;\n",rule_number);
			}
	;
pbinds:	  exp ':' '{'		{ if (put_gen_lines) cout << "\n#line " << lineno << endl;
				  cout << "synthesized _S = default_synthesized; "; }
	  synths '}'		{ cout << "\nNEW_PLANS = NEW_PLANS->cons(new plan(" << $1 << ",_S));\n";
				  $$=true; }
	| FAIL			{ cout << form(" FOUND = false; goto exit_%i; ",rule_number); }
	| CASE			{ stopsyms->push('|');
				  cout << "{ bool FOUND = false;\n Expr EXPR = "; }
	  ccode			{ cout << ";\n";
				  stopsyms->pop();
				  stopsyms->push(); }
          pcases		{ stopsyms->pop(); }
	  END			{ cout << form("\n if (!FOUND) goto exit_%i; }\n",rule_number);
				  if (put_gen_lines) cout << "#line " << lineno << endl;
				  $$=$5; }
	| FORALL name IN	{ stopsyms->push(DO);
				  cout << form("for(list<Expr>* _%s = ",$2->value()); }
	  ccode			{ cout << form("; _%s->consp(); _%s=_%s->tl) { Expr %s = _%s->hd;\n",
					       $2->value(),$2->value(),$2->value(),$2->value(),$2->value());
				  stopsyms->pop();
				  stopsyms->push(); }
          DO pbinds ';'		{ stopsyms->pop(); }
	  END			{ cout << "\n}"; if (put_gen_lines) cout << "\n#line " << lineno << endl;
				  $$=$8; }
	| LET blist IN pbinds	{ $$=$4; }
	;
synth:	  name '='		{ cout << "_S." << $1 << " = ";
				  stopsyms->push(';');  }
	  ccode	';'		{ stopsyms->pop(); }
	;
synths:	  synth			{ cout << "; "; }
	| synths synth		{ cout << "; "; }
	;
pcase:	  '|'			{ cont->open();
				  cout << "if (!FOUND) {\n"; }
	  cprelude condition IMPLIES pbinds ';'
				{ cout << "\n FOUND = true;";
				  if ($4) cout << " } else FOUND = false;";
				  cont->close();
				  if ($4) cout << " }";
				  cout << " };\n";
				  $$=$6; }
	;
pcases:	  pcase			{ $$=$1; }
	| pcases pcase		{ if ($1!=$2) yyerror("incompatible cases"); $$=$2; }
	;
patrbs:   rname attributes	{ int lv = 0;
				  in_rule = true;
				  rule_number++;
				  if ($1) cout << "#define " << $1 << " " << rule_number << endl;
				  cout << "{ ";
				  binding<Expr>* atrbs = new binding<Expr>($2->env->reverse());
				  for(binding<Expr>* r = atrbs; r->more(); r=r->next())
				     { cout << "{ ";
				       var_decl(r->current()->second,"Expr");
				       cont->remember();
				       compile_pattern(r->current()->second,
					   new string(form("ATRBS.%s",r->current()->first->value())),false);
				     };
				  $$ = lv; }
	;
prules:	  prule
	| prules prule
	;
atrbexp:  name '=' exp ';'	{ $$ = new pair<String,Expr>($1,$3); }
	;
atrbexps: atrbexp		{ $$ = (new binding<Expr>)->extend($1); }
	| atrbexps atrbexp	{ $$ = $1->extend($2); }
	;
attributes:  /* empty */	{ $$ = new binding<Expr>; }
	| '{' atrbpats '}'	{ $$ = $2; }
	;
atrbpat:  name '=' pattern ';'	{ $$ = new pair<String,Expr>($1,$3); }
	;
atrbpats: atrbpat		{ $$ = (new binding<Expr>)->extend($1); }
	| atrbpats atrbpat	{ $$ = $1->extend($2); }
	;
condition: /* empty */		{ $$ = 0; }
	| ':'			{ stopsyms->push('=',IMPLIES);
				  cout << " { if ("; }
	  ccode			{ stopsyms->pop();
				  cout << ") { "; $$ = 1; }
	;
rname:	  /* empty */		{ $$ = NULL; }
	| '[' name ']'		{ $$ = $2; }
	;
%%
int main (int argc,char* arg[]) {
  lineno = 1;
  stopsyms->push('#');
  char* ifile = new char[40];
  String Ifile = new string("");;
  char* strfile = new char[40];
  strcpy(ifile," ");
  if (argc>1)
  { int len = strlen(arg[1]);
    file_IO = true;
    if (len>4 && arg[1][len-4] == '.' && arg[1][len-3] == 'g'
        && arg[1][len-2] == 'e' && arg[1][len-1] == 'n')
    { strcpy(ifile,arg[1]);
      Ifile = new string(arg[1]);
      yyin = fopen(ifile,"r");
      char* ofile = new char[len+4];
      strcpy(ofile,arg[1]);
      strcpy(ofile+len-4,"_out.cc");
      fout.open(ofile);
      cout = fout;
      strfile = new char[len+3];
      strcpy(strfile,arg[1]);
      strcpy(strfile+len-4,"_str.h");
      fstring.open(strfile);
    } else {
      ifile = new char[len+4];
      strcpy(ifile,arg[1]);
      strcat(ifile,".gen");
      Ifile = new string(ifile);
      yyin = fopen(ifile,"r");
      char* ofile = new char[len+7];
      strcpy(ofile,arg[1]);
      strcat(ofile,"_out.cc");
      fout.open(ofile);
      cout = fout;
      strfile = new char[len+3];
      strcpy(strfile,arg[1]);
      strcat(strfile,"_str.h");
      fstring.open(strfile);
    };
  };
  cout << "/***** NOTE: This file was generated automatically by the OPTGEN program ******/\n#include \"external.h\"\n#include \""
       << strfile << "\"\n";
  if (put_gen_lines) cout << "#line 1 \"" << Ifile << "\"\n";
  yyparse();
  if (file_IO)
  for(list<String>* r = all_strings; r->consp(); r=r->tl)
     fstring << "const Expr _" << r->hd << "_ = variable(\"" << r->hd <<"\");\n";
};
