#include <stdio.h>
int sub(int a, int b);
int main(void) {
  printf("%d\n", sub(3, 9)); return 0;
}

        .text
        .globl  sub
        .type   sub, @function
sub:    pushq   %rbp
        movq    %rsp, %rbp
        movl    %edi, %eax
        addl    %esi, %eax
        leave
        ret

#include <stdio.h>
int sub(int n, int a[]);
int b[] = { 5, 1, 6, 8, 2, 7, 4, 3 };
int main(void) {
  printf("%d\n", sub(8, b)); return 0;
}

        .text
        .globl  sub
        .type   sub, @function
sub:    pushq   %rbp
        movq    %rsp, %rbp
        movl    0(%rsi), %eax
.L1:    dec     %edi
        cltq
        jl      .L2
        movl    0(%rsi,%rdi,4), %edx
        cmpl    %edx, %eax
        jge      .L1
        movl    %edx, %eax
        jmp     .L1
.L2:    leave
        ret

Package samb3;

Helpers
  digit = ['0'..'9'] ;
  lcase = ['a'..'z'] ;
  ucase = ['A'..'Z'] ;
  letter = lcase | ucase ;

Tokens
  iconst = digit+ ;
  blank = (' '|13|10)+ ;
  int = 'int' ;
  if = 'if' ;
  while = 'while' ;
  semi = ';' ;
  assign = '=' ;
  add = '+' ;
  sub = '-' ;
  aster = '*' ;
  slash = '/' ;
  lt = '<' ;
  gt = '>' ;
  lbra = '{' ;
  rbra = '}' ;
  lpar = '(' ;
  rpar = ')' ;
  lsbr = '[' ;
  rsbr = ']' ;
  ident = letter (letter|digit)* ;

Ignored Tokens
  blank;

Productions
  prog = {main} int ident lpar dcls rpar stat
       ;
  dcls = {lst} dcls semi dcl
       | {one} dcl
       ;
  dcl  = {idcl} int ident
       | {adcl} int ident lsbr rsbr
       ;
  stlist = {stat} stlist stat
         | {empty}
         ;
  stat = {idcl}    int ident semi
       | {assign}  ident assign expr semi
       | {aassign} ident lsbr [idx]:expr rsbr assign expr semi
       | {if}      if lpar expr rpar stat
       | {while}   while lpar expr rpar stat
       | {block}   lbra stlist rbra
       ;
  expr = {gt}  [left]:nexp gt [right]:nexp
       | {lt}  [left]:nexp lt [right]:nexp
       | {one} nexp
       ;
  nexp = {add}  nexp add term
       | {sub}  nexp sub term
       | {one}  term
       ;
  term = {mul}  term aster fact
       | {div}  term slash fact
       | {one}  fact
       ;
  fact = {iconst} iconst
       | {ident}  ident
       | {aref}   ident lsbr expr rsbr
       | {one}    lpar expr rpar
       ;

package samb3;
import samb3.parser.*;
import samb3.lexer.*;
import samb3.node.*;
import java.io.*;
import java.util.*;

public class SamB3 {
  public static void main(String[] args) throws Exception {
    Parser p = new Parser(new Lexer(new PushbackReader(
      new InputStreamReader(new FileInputStream(args[0]), "JISAutoDetect"),
        1024)));
    Start tree = p.parse();
    Symtab st = new Symtab();
    HashMap<Node,Integer> vtbl = new HashMap<Node,Integer>();
    TypeChecker tck = new TypeChecker(st, vtbl); tree.apply(tck); st.show();
    if(Log.getError() > 0) { return; }
    Generator gen = new Generator(st, vtbl); tree.apply(gen);
  }
}
class Log {
  public static int err = 0;
  public static void pError(String s) { System.out.println(s); ++err; }
  public static int getError() { return err; }
}
class Symtab {
  public static final int ITYPE = 1, ATYPE = 2, UNDEF = -1;
  List<Ent> tbl = new ArrayList<Ent>();
  Stack<Integer> stk = new Stack<Integer>();
  int mark;

  private boolean duplCheck(String n) {
    for(int i = mark; i < tbl.size(); ++i) {
      Ent e = tbl.get(i);
      if(e.alive && e.name.equals(n)) { return true; }
    }
    return false;
  }
  public Ent addDef(String n, int t) {
    if(duplCheck(n)) {
      Log.pError("dublicate: "+n); return new Ent(n, UNDEF, 0);
    }
    Ent e = new Ent(n, t, tbl.size()); tbl.add(e); return e;
  }
  public void enterScope() { stk.push(mark); mark = tbl.size(); }
  public void exitScope() {
    for(int i = mark; i < tbl.size(); ++i) { tbl.get(i).alive = false; }
    mark = stk.pop();
  }
  public Ent lookup(String n) {
    for(int i = tbl.size()-1; i >= 0; --i) {
      Ent e = tbl.get(i);
      if(e.alive && e.name.equals(n)) { return e; }
    }
    return new Ent(n, UNDEF, 0);
  }
  public int getGsize() { return tbl.size(); }
  public void show() { for(Ent e: tbl) { System.out.println(" " + e); } }
  public static class Ent {
    public String name;
    public boolean alive = true;
    public int type, pos = 0;
    public Ent(String n, int t, int p) { name = n; type = t; pos = p; }
    public String toString() {
      return String.format("%s%s[%d %d]", name, alive?"_":"!", type, pos);
    }
  }
}

package samb3;
import samb3.analysis.*;
import samb3.node.*;
import java.io.*;
import java.util.*;

class TypeChecker extends DepthFirstAdapter {
Symtab st;
HashMap vtbl;
public TypeChecker(Symtab tb, HashMap vt) { st = tb; vtbl = vt; }
private void ckv(Node n, int t, int l, String s) {
  if(getOut(n) instanceof Integer && (Integer)getOut(n) == t) { return; }
  Log.pError(l+": "+s);
}
private int cki(String i, int t, int l) {
  Symtab.Ent e = st.lookup(i);
  if(e.type != t) { Log.pError(l+": identyfier is not of expexted type: "+i); }
  return e.pos;
}
@Override
public void inAMainProg(AMainProg node) {
  st.addDef("$dummy$", Symtab.ITYPE);
  st.addDef(node.getIdent().getText(), Symtab.ITYPE);
}
@Override
public void outAIdclDcl(AIdclDcl node) {
  Symtab.Ent e = st.addDef(node.getIdent().getText(), Symtab.ITYPE);
  vtbl.put(node, e.pos);
}
@Override
public void outAAdclDcl(AAdclDcl node) {
  Symtab.Ent e = st.addDef(node.getIdent().getText(), Symtab.ATYPE);
  vtbl.put(node, e.pos);
}
@Override
public void outAIdclStat(AIdclStat node) {
  st.addDef(node.getIdent().getText(), Symtab.ITYPE);
}
@Override
public void outAAssignStat(AAssignStat node) {
  int p = cki(node.getIdent().getText(), Symtab.ITYPE, node.getIdent().getLine());
  ckv(node.getExpr(), Symtab.ITYPE, node.getAssign().getLine(), "non-int val");
  vtbl.put(node, p);
}
@Override
public void outAAassignStat(AAassignStat node) {
  int p = cki(node.getIdent().getText(), Symtab.ATYPE, node.getIdent().getLine());
  ckv(node.getIdx(), Symtab.ITYPE, node.getLsbr().getLine(), "non-int index");
  ckv(node.getExpr(), Symtab.ITYPE, node.getAssign().getLine(), "non-int val");
  vtbl.put(node, p);
}
@Override
public void outAIfStat(AIfStat node) {
  ckv(node.getExpr(), Symtab.ITYPE, node.getLpar().getLine(), "non-int cond");
}
@Override
public void outAWhileStat(AWhileStat node) {
  ckv(node.getExpr(), Symtab.ITYPE, node.getLpar().getLine(), "non-int cond");
}
@Override
public void inABlockStat(ABlockStat node) { st.enterScope(); }
@Override
public void outABlockStat(ABlockStat node) { st.exitScope(); }
@Override
public void outAGtExpr(AGtExpr node) {
  ckv(node.getLeft(), Symtab.ITYPE, node.getGt().getLine(), "non-int val");
  ckv(node.getRight(), Symtab.ITYPE, node.getGt().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outALtExpr(ALtExpr node) {
  ckv(node.getLeft(), Symtab.ITYPE, node.getLt().getLine(), "non-int val");
  ckv(node.getRight(), Symtab.ITYPE, node.getLt().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outAOneExpr(AOneExpr node) { setOut(node, getOut(node.getNexp())); }
@Override
public void outAAddNexp(AAddNexp node) {
  ckv(node.getNexp(), Symtab.ITYPE, node.getAdd().getLine(), "non-int val");
  ckv(node.getTerm(), Symtab.ITYPE, node.getAdd().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outASubNexp(ASubNexp node) {
  ckv(node.getNexp(), Symtab.ITYPE, node.getSub().getLine(), "non-int val");
  ckv(node.getTerm(), Symtab.ITYPE, node.getSub().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outAOneNexp(AOneNexp node) { setOut(node, getOut(node.getTerm())); }
@Override
public void outAMulTerm(AMulTerm node) {
  ckv(node.getTerm(), Symtab.ITYPE, node.getAster().getLine(), "non-int val");
  ckv(node.getFact(), Symtab.ITYPE, node.getAster().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outADivTerm(ADivTerm node) {
  ckv(node.getTerm(), Symtab.ITYPE, node.getSlash().getLine(), "non-int val");
  ckv(node.getFact(), Symtab.ITYPE, node.getSlash().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outAOneTerm(AOneTerm node) { setOut(node, getOut(node.getFact())); }
@Override
public void outAIconstFact(AIconstFact node) {
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outAIdentFact(AIdentFact node) {
  Symtab.Ent e = st.lookup(node.getIdent().getText());
  setOut(node, new Integer(e.type)); vtbl.put(node, e.pos);
}
@Override
public void outAArefFact(AArefFact node) {
  int p = cki(node.getIdent().getText(), Symtab.ATYPE, node.getIdent().getLine());
  ckv(node.getExpr(), Symtab.ITYPE, node.getLsbr().getLine(), "non-int index");
  setOut(node, new Integer(Symtab.ITYPE)); vtbl.put(node, p);
}
@Override
public void outAOneFact(AOneFact node) { setOut(node, getOut(node.getExpr())); }
}

package samb3;
import samb3.analysis.*;
import samb3.node.*;
import java.io.*;
import java.util.*;

class Generator extends DepthFirstAdapter {
  HashMap<Node,Integer> pos;
  Symtab st;
  PrintStream pr;
  static String preg[] = {"%rdi", "%rsi", "%rdx", "%rcx", "%r8", "%r9"};
  int pcnt = 0, lcnt = 0;
  public Generator(Symtab s, HashMap<Node,Integer> p) throws Exception {
    st = s; pos = p; pr = new PrintStream(new File("asm.s"));
  }
  @Override
  public void inAMainProg(AMainProg node) {
    String name = node.getIdent().getText();
    pr.printf(" .text\n");
    pr.printf(" .globl %s\n", name);
    pr.printf(" .type %s, @function\n", name);
    pr.printf("%s: pushq %%rbp\n", name);
    pr.printf(" movq %%rsp, %%rbp\n");
    pr.printf(" subq $.STSIZE, %%rsp\n");
  }
  @Override
  public void outAMainProg(AMainProg node) {
    pr.printf(" movl -8(%%rbp), %%eax\n");
    pr.printf(" addq $.STSIZE, %%rsp\n");
    pr.printf(" leave\n");
    pr.printf(" ret\n");
    pr.printf(".STSIZE = %d\n", st.getGsize()*8);
  }
  @Override
  public void outAIdclDcl(AIdclDcl node) {
    pr.printf(" movq %s, -%d(%%rbp)\n", preg[pcnt++], pos.get(node)*8);
  }
  @Override
  public void outAAdclDcl(AAdclDcl node) {
    pr.printf(" movq %s, -%d(%%rbp)\n", preg[pcnt++], pos.get(node)*8);
  }
  @Override
  public void outAAssignStat(AAssignStat node) {
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getExpr()));
    pr.printf(" movl %%eax, -%d(%%rbp)\n", pos.get(node)*8);
  }
  @Override
  public void outAAassignStat(AAassignStat node) {
    pr.printf(" movq -%d(%%rbp), %%rcx\n", pos.get(node)*8);
    pr.printf(" movl -%s(%%rbp), %%edx\n", getOut(node.getIdx()));
    pr.printf(" cltq\n");
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getExpr()));
    pr.printf(" movl %%eax, 0(%%rcx,%%rdx,4)\n");
  }
  @Override
  public void caseAIfStat(AIfStat node) {
    int lbl = lcnt; lcnt += 1;
    node.getExpr().apply(this);
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getExpr()));
    pr.printf(" testl %%eax,%%eax\n");
    pr.printf(" je .L%d\n", lbl);
    node.getStat().apply(this);
    pr.printf(".L%d:\n", lbl);
  }
  @Override
  public void caseAWhileStat(AWhileStat node) {
    int lbl = lcnt; lcnt += 2;
    pr.printf(".L%d:\n", lbl);
    node.getExpr().apply(this);
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getExpr()));
    pr.printf(" testl %%eax,%%eax\n");
    pr.printf(" je .L%d\n", lbl+1);
    node.getStat().apply(this);
    pr.printf(" jmp .L%d\n", lbl);
    pr.printf(".L%d:\n", lbl+1);
  }
  @Override
  public void outAGtExpr(AGtExpr node) {
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getRight()));
    pr.printf(" cmpl -%s(%%rbp), %%eax\n", getOut(node.getLeft()));
    pr.printf(" jg .L%d\n", lcnt);
    pr.printf(" mov $1, %%eax\n");
    pr.printf(" jmp .L%d\n", lcnt+1);
    pr.printf(".L%d: movl $0, %%eax\n", lcnt++);
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    pr.printf(".L%d: movl %%eax, -%d(%%rbp)\n", lcnt++, f.pos*8);
    setOut(node, new Integer(f.pos*8));
  }
  @Override
  public void outALtExpr(ALtExpr node) {
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getRight()));
    pr.printf(" cmpl -%s(%%rbp), %%eax\n", getOut(node.getLeft()));
    pr.printf(" jl .L%d\n", lcnt);
    pr.printf(" mov $1, %%eax\n");
    pr.printf(" jmp .L%d\n", lcnt+1);
    pr.printf(".L%d: movl $0, %%eax\n", lcnt++);
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    pr.printf(".L%d: movl %%eax, -%d(%%rbp)\n", lcnt++, f.pos*8);
    setOut(node, new Integer(f.pos*8));
  }
  @Override
  public void outAOneExpr(AOneExpr node) { setOut(node, getOut(node.getNexp())); }
  @Override
  public void outAAddNexp(AAddNexp node) {
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getNexp()));
    pr.printf(" addl -%s(%%rbp), %%eax\n", getOut(node.getTerm()));
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    pr.printf(" movl %%eax, -%d(%%rbp)\n", f.pos*8);
    setOut(node, new Integer(f.pos*8));
  }
  @Override
  public void outASubNexp(ASubNexp node) {
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getNexp()));
    pr.printf(" subl -%s(%%rbp), %%eax\n", getOut(node.getTerm()));
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    pr.printf(" movl %%eax, -%d(%%rbp)\n", f.pos*8);
    setOut(node, new Integer(f.pos*8));
  }
  @Override
  public void outAOneNexp(AOneNexp node) { setOut(node, getOut(node.getTerm())); }
  @Override
  public void outAMulTerm(AMulTerm node) {
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getTerm()));
    pr.printf(" imull -%s(%%rbp), %%eax\n", getOut(node.getFact()));
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    pr.printf(" movl %%eax, -%d(%%rbp)\n", f.pos*8);
    setOut(node, new Integer(f.pos*8));
  }
  @Override
  public void outADivTerm(ADivTerm node) {
    pr.printf(" movl -%s(%%rbp), %%eax\n", getOut(node.getFact()));
    pr.printf(" cltd\n");
    pr.printf(" idivl -%s(%%rbp)\n", getOut(node.getTerm()));
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    pr.printf(" movl %%eax, -%d(%%rbp)\n", f.pos*8);
    setOut(node, new Integer(f.pos*8));
  }
  @Override
  public void outAOneTerm(AOneTerm node) { setOut(node, getOut(node.getFact())); }
  @Override
  public void outAIconstFact(AIconstFact node) {
    Symtab.Ent e = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    pr.printf(" movl $%s, %%eax\n", node.getIconst().getText());
    pr.printf(" movl %%eax, -%d(%%rbp)\n", e.pos*8);
    setOut(node, new Integer(e.pos*8));
  }
  @Override
  public void outAIdentFact(AIdentFact node) {
    setOut(node, new Integer(pos.get(node)*8));
  }
  @Override
  public void outAArefFact(AArefFact node) {
    pr.printf(" movq -%d(%%rbp), %%rdx\n", pos.get(node)*8);
    pr.printf(" movl -%s(%%rbp), %%ecx\n", getOut(node.getExpr()));
    pr.printf(" cltq\n");
    pr.printf(" movl 0(%%rdx,%%rcx,4), %%eax\n");
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    pr.printf(" movl %%eax, -%d(%%rbp)\n", f.pos*8);
    setOut(node, new Integer(f.pos*8));
  }
  @Override
  public void outAOneFact(AOneFact node) { setOut(node, getOut(node.getExpr())); }
}

int sub(int n; int a[]) {
  int remain; remain = 1;
  while(remain) {
    remain = 0; int i; i = 1;
    while(i < n) {
      if(a[i-1]>a[i]) { int z; z=a[i-1]; a[i-1]=a[i]; a[i]=z; remain=1; }
      i = i + 1; } } }

#include <stdio.h>
int sub(int n, int a[]);
int main(void) {
  int a[] = { 7, 1, 6, 3, 2, 4, 8 };
  sub(7, a);
  for(int i = 0; i < 7; ++i) { printf("%d\n", a[i]); }
}