/* 
    Online calculator with sums and symbol tables and
    compilation to x86 assembly
*/
import java.io.*;

interface Exp   // interface for visitees
{
    public <R> R accept(Expvisitor<R> v);
}

interface Expvisitor<T> // interface for visitors that return type T
{
    public T visit(dlit d);
    public T visit(plusexp e);
    public T visit(minusexp e);
    public T visit(multexp e);
    public T visit(divexp e);
    public T visit(negexp e);
    public T visit(variable e);
    public T visit(summation s);
}


class variable implements Exp // class for simple double expressions
{
    String name;
    public variable(String x) {name=x;}
    public <R> R accept(Expvisitor<R> v) { return v.visit(this); }
}

class summation implements Exp   // [sum(i=0,n) i*i]
{
    String var;  // i
    Exp start, end;  // 0,n
    Exp body;        // i*i
    public summation(String i, Exp s, Exp e, Exp b)
    { var=i; start=s; end=e; body=b; }
    public <R> R accept(Expvisitor<R> v) { return v.visit(this); }
    
}// summation


class dlit implements Exp // class for simple double expressions
{
    double value;
    public dlit(double x) {value=x;}
    public <R> R accept(Expvisitor<R> v) { return v.visit(this); }
}

class opexp   // superclass for all binary operator expressions
{
    Exp left, right; // left and right subtrees
    public opexp(Exp l, Exp r) {left=l;  right=r;}
}

class plusexp extends opexp implements Exp
{ 
    public plusexp(Exp l, Exp r) { super(l,r); }
    public <R> R accept(Expvisitor<R> v) { return v.visit(this); }
}

class minusexp extends opexp implements Exp
{ 
    public minusexp(Exp l, Exp r) { super(l,r); }
    public <R> R accept(Expvisitor<R> v) { return v.visit(this); }
}

class multexp extends opexp implements Exp
{ 
    public multexp(Exp l, Exp r) { super(l,r); }
    public <R> R accept(Expvisitor<R> v) { return v.visit(this); }
}

class divexp extends opexp implements Exp
{ 
    public divexp(Exp l, Exp r) { super(l,r); }
    public <R> R accept(Expvisitor<R> v) { return v.visit(this); }
}

class negexp implements Exp  // negative values
{ 
    Exp sub;  // subexpression
    public negexp(Exp s) { sub=s; }
    public <R> R accept(Expvisitor<R> v) { return v.visit(this); }
}


/*
    Symbol table information: each symbol table frame consists of
    a mapping from strings to numbers indicating the original embedding
    level of the number.  Multiple frames are stacked on the table because
    names can be shadowed.  the codegeneration visitor will maintain a
    counter indicating the current embedding level.  When visiting a 
    variable expression v, it will look up the nearest frame containing
    an entry for v. The runtime stack frame where the value of v resides
    is then calculated by subtracting v's embedding level and the current
    embedding level.  In this particular example, the symbol table is
    implemented in a simple way since there's only one entry per frame.
*/

// a static frame for one summation scope
class stframe
{
    String var;  // variable name
    int level;   // embedding level
    stframe previous;     // previous frame on stack
    public stframe(String v, int l, stframe s) 
    { var=v; level=l; previous=s; }

    public int lookup(String n)
    {
	stframe i = this;
	while (i!=null && !i.var.equals(n)) i=i.previous;
	if (i!=null) return i.level;
	else throw new Error("unbound variable "+n);
    }
} // scope


class coder implements Expvisitor<Object>
{

    int clevel = 0;        // current embedding level
    stframe table = null;  // symbol table
    PrintWriter pw;

    // postorder traversal order is right-left-node

    public coder(PrintWriter p)
    { pw = p; 
      out("\t.section \t.rodata");
      out("STR1:\t.string \"the answer is %d\\n\"");
      out("\t.text\n");
      out(".global main\n\t.type main,@function");
      out("main:");
    } // constructor

    // utility for printing (encapsulates try-catch), with tab
    private void out(String s)
    { 
      try
	  {
	      pw.println(s);
	  }
      catch (Exception ie) {System.out.println(ie); System.exit(1); }
    }// out


    public Object visit(dlit d)
    {
	// push value on stack
	out("\tpush $"+(int)d.value);
	return null;
    }
    
    public Object visit(plusexp e)
    {
	// gencode for subtrees
	e.right.accept(this);
	e.left.accept(this);
	// pop two numbers, push result back on stack
	out("\tpop %eax");
	out("\tpop %ebx");
	out("\tadd %eax,%ebx");
	out("\tpush %ebx");
	return null;
    }

    public Object visit(minusexp e)
    {
	e.right.accept(this);
	e.left.accept(this);
	out("\tpop %eax");
	out("\tpop %ebx");
	out("\tsub %ebx,%eax");  // note eax is destination (eax -= ebx)
	out("\tpush %eax");
	return null;
    }

    public Object visit(multexp e)
    {
	e.right.accept(this);
	e.left.accept(this);
	out("\tpop %eax");
	out("\tpop %ebx");
	out("\timul %eax,%ebx");
	out("\tpush %ebx");
	return null;
    }

    public Object visit(divexp e)  // ???
    {
	e.right.accept(this);
	e.left.accept(this);
	out("\tpop %eax");
	out("\tpop %ebx");
	out("\tmov $0, %edx");
	out("\tidiv %ebx");
	out("\tpush %eax");
	return null;
    }

    public Object visit(negexp e)
    {
	e.sub.accept(this);
	out("\tpop %eax");
	out("\timul $-1, %eax");
	out("\tpush %eax");
	return null;
    }

    public Object visit(variable e)
    {
	//lookup variable value in table, move to top of stack
	int elevel = clevel;  // elevel is level of the var e
	if (clevel!=0) elevel=table.lookup(e.name);
	int fnum = clevel-elevel; // runtime stack frames to look under
	out("\tmov %ebp,%edx");  
	while (fnum-- > 0)        // look under stack frames
	{
	    out("\tmov 0(%edx), %edx");
	} //while
	out("\tmov 8(%edx), %eax");
	out("\tpush %eax");
	return null;
    } // variable


    int counter = 0;  // for producing unique labeles
    public Object visit(summation s)
    {
	// write code to compile start expression
	s.start.accept(this);
	s.end.accept(this);
	// create new stackframe
	clevel++; // current frame increase
	table = new stframe(s.var,clevel,table);
	out("\tpush %ebp");
	out("\tmov %esp,%ebp");  // esp,ebp both point to previous ebp
	out("\tsub $4, %esp");   // room for local var to hold running sum
	out("\tmov $0, %eax");
	out("\tmov %eax, -4(%ebp)");
	// generate code to run a loop until 8(%ebp) reaches end
	// compare counter against end
	int cl = ++counter;
	out("loop"+cl+":");          // goto label
	out("\tmov 8(%ebp), %eax"); // start
	out("\tmov 4(%ebp), %ebx"); // end
	out("\tcmp %ebx, %eax");
	out("\tjg exit"+cl);    // use level counter for new label
	// compile body of summation
	s.body.accept(this); // esp will points to result
	out("\tpop %eax");
	out("\tadd %eax, -4(%ebp)");   // update running sum
	out("\tadd $1, 8(%ebp)");      // increment counter
	out("\tjmp loop"+cl);
	out("exit"+cl+":");
	// at this point, -4(%ebp) has final result
	out("\tmov -4(%ebp), %eax");
	out("\tmov %ebp, %esp");  // restore frame pointer
	out("\tpop %ebp");
	out("\tadd $8, %esp");    // deallocate start,end
	out("\tpush %eax");
	clevel--;  // decrement static embedding level
	table = table.previous;  // pop STATIC symbol table frame
	return null;
    } // summation
} // coder visitor




//////////////////////////
// interface 

public class calcasm
{
    public static void main(String[] args) throws Exception
    {
	parser P = new parser();
	System.out.print("Enter expression: ");
	Exp E =  (Exp)P.parse().value;
	PrintWriter pw = new PrintWriter(new FileWriter("calcval.s"));
	E.accept(new coder(pw));  
	pw.println("\tpush $STR1");
	pw.println("\tcall printf");
	pw.println("\tadd $8, %esp");
	pw.println("\tpush $0\n\tcall exit");
	pw.println(".size main, .-main");
	pw.close();
	System.out.println("compile calcval.s with gcc"); 
    }
} // calcsum