/*
 * TinierC 再帰的下降構文解析プログラム
 * 対象の BNF は以下の通りである
 *
 * ※ Bison で使ったものと微妙に異なり、
 *    再帰下降法で簡単に構文解析できるように、
 *        S から 
 *            E ;
 *        E から、
 *            print ( E )
 *            println ( E )
 *            ID =  E
 *        を外し、
 *        その代わり S に、
 *            print ( E ) ; 
 *            println ( E ) ; 
 *            ID =  E ;
 *        を追加している
 *
 *     (Statement List)
 *     X -> S X
 *        | ε
 *     (Statement)
 *     S -> if ( E ) S else S
 *        | while ( E ) S
 *        | do S while ( E ) ;
 *        | for ( id = E ; E ; id = E ) S
 *        | { X }
 *        | print ( E ) ;
 *        | println ( E ) ;
 *        | id = E ;
 *     (Expression)
 *     E -> C
 *        | E || C
 *     (Logical And Expression)
 *     C -> Q
 *        | C && Q
 *     (Eqaulity Expression)
 *     Q -> R
 *        | Q == R
 *        | Q != R
 *     (Relational Expression)
 *     R -> A
 *        | R < A
 *        | R > A
 *        | R >= A
 *        | R <= A
 *     (Additive Expression)
 *     A -> M
 *        | A + M
 *        | A - M
 *     (Multiplicative Expression)
 *     M -> P
 *        | M * P
 *        | M / P
 *        | M % P
 *     (Primary Expression)
 *     P -> ID
 *        | NUM
 *        | ( E )
 *
 * （BNF 終わり）
 *
 * 例えば M から左再帰を除去すると
 *     M  -> P M1
 *     M1 -> * P M1
 *         | / P M1
 *         | % P M1
 *         | ε
 * となる、A, R, Q, C, E についても同様である
 */

/*
 *  TODO: ほんとうは不要になったメモリーの解放が全体的に必要である
 */

#include <stdio.h>
#include <stdlib.h>   // exit, malloc, ...
#include <ctype.h>    // isdigit, isalpha, ... 
#include <string.h>   // strcmp, strcpy, strchr, ...
#include <stdarg.h>   // 可変引数を使うため

/*
 * 構造体の宣言 --- 
 *     左再帰を除去したときの補助的な非終端記号に対応する関数が
 *     一旦結果を返すためのリストを定義する
 * 
 * ほんとうは、このプログラムの場合は中間的な構造体を使わず、
 * 直接ターゲットコードを出力することも可能だが、一般的には
 * 中間的なデータ構造が必要になる。 
 */

struct _list {
    int token;
    char* yylval;
    struct _list* next;
};

typedef struct _list* list;

/* 大域変数の宣言 */
int token;      /* 入力の先頭のトークンを表す */
char* yylval;   /* token の属性 */

int column = 0; /* デバッグ用 */
int line = 1;

/* 終端記号に対応するマクロの定義 */
#define ID      256
#define NUM     257
#define IF      258
#define ELSE    259
#define WHILE   260
#define DO      261
#define FOR     262
#define LE      263 // <=
#define GE      264 // >= 
#define EQ      265 // ==
#define NE      266 // !=
#define AND     267 // &&
#define OR      268 // ||
#define PRINT   269
#define PRINTLN 270

char* newlabel(void) {      /* 新しいラベル名を生成する関数 */
    static int counter = 0; /* 静的変数: 次に呼ばれた時に以前の値を保持している */ 
    char* ret = (char*)malloc(5 * sizeof(char));
    sprintf(ret, "l%03d", counter++);
    return ret;
}

/*
 *   文字列のフォーマットを行なう関数: mysprintf
 *
 *   printf と似ているが、出力する代わりに戻り値として返す。
 *
 *   アクション中で、printf を使って Oolong の命令を出力すると、
 *   思い通りの順番にするのが難しいので、属性値として計算し、
 *   最後にまとめて出力する。
 *
 *   警告: この関数は、メモリを大量にムダ使いするので、
 *         実用に供するプログラムには使ってはダメ
 */

char* mysprintf(char* format, ...) {
    va_list arg; 
    int len;
    char* ret;
    va_start(arg, format);
    len = vsnprintf(NULL, 0, format, arg);
    va_end(arg);
    ret = (char*)malloc((len + 1) * sizeof(char));
    va_start(arg, format);
    vsprintf(ret, format, arg) ;
    va_end(arg);
    return ret;
}

/*
 *    ==, !=, >, >=, <=, < に直接対応する命令は JVM にないので、
 *    いくつかの命令を組み合わせて定義する。
 */

/* == */
char ieq[] = "isub\n"
             "invokestatic java/lang/Math/abs(I)I\n"
             "iconst_1\n"
             "invokestatic java/lang/Math/min(II)I\n"
             "iconst_1\n"
             "swap\n"
             "isub\n";

/* != */
char ine[] = "isub\n"
             "invokestatic java/lang/Math/abs(I)I\n"
             "iconst_1\n"  
             "invokestatic java/lang/Math/min(II)I\n";

/* > */
char igt[] = "isub\n"
             "iconst_0\n"
             "invokestatic java/lang/Math/max(II)I\n"
             "iconst_1\n"
             "invokestatic java/lang/Math/min(II)I\n";

/* < */
char ilt[] = "swap\n"
             "isub\n"     
             "iconst_0\n"
             "invokestatic java/lang/Math/max(II)I\n"
             "iconst_1\n"
             "invokestatic java/lang/Math/min(II)I\n";

/* >= */
char ige[] = "isub\n"
             "iconst_1\n" 
             "iadd\n"
             "iconst_0\n"
             "invokestatic java/lang/Math/max(II)I\n"
             "iconst_1\n"
             "invokestatic java/lang/Math/min(II)I\n";

/* <= */
char ile[] = "swap\n"
             "isub\n"
             "iconst_1\n" 
             "iadd\n"
             "iconst_0\n"
             "invokestatic java/lang/Math/max(II)I\n"
             "iconst_1\n"
             "invokestatic java/lang/Math/min(II)I\n";

/* PRINT */
char iprint[] = "dup\n"
                "getstatic java/lang/System/out Ljava/io/PrintStream;\n"
                "swap\n"
                "invokevirtual java/io/PrintStream/print(I)V\n";

/* PRINTLN （= PRINT + 改行）*/
char iprintln[] = "dup\n"
                  "getstatic java/lang/System/out Ljava/io/PrintStream;\n"
                  "swap\n"
                  "invokevirtual java/io/PrintStream/println(I)V\n";

/* 簡易字句解析ルーチン */
int yylex(void) {
    int c;

    do {
        c = getchar();
        column++;
        if (c == '\n') {
            column = 0;
            line++;
        }
            
    } while (c == ' ' || c == '\t' || c == '\n'); /* 空白は読み飛ばす */

    if (isalpha(c)) { 
        char buf[8];        // 変数名は最大 7 文字とする
        ungetc(c, stdin);
        scanf("%7[_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789]", buf);
        int len = strlen(buf);
        column += len - 1;
        if (strcmp(buf, "if") == 0) {
            return IF;
        }
        if (strcmp(buf, "else") == 0) {
            return ELSE;
        }
        if (strcmp(buf, "while") == 0) {
            return WHILE;
        }
        if (strcmp(buf, "do") == 0) {
            return DO;
        }
        if (strcmp(buf, "for") == 0) {
            return FOR;
        }
        if (strcmp(buf, "print") == 0) {
            return PRINT;
        }
        if (strcmp(buf, "println") == 0) {
            return PRINTLN;
        }

        char* ret = (char*)malloc(len + 1);
        strcpy(ret, buf);
        yylval = ret;
        return ID;
    }

    if (isdigit(c)) {
        char buf[16];       // 数値定数は最大 15 文字とする
        ungetc(c, stdin);
        scanf("%15[0123456789]", &buf);
        int len = strlen(buf);
        column += len - 1;
        char* ret = (char*)malloc(len + 1);
        strcpy(ret, buf);   
        yylval = ret;       // 数値に変換する必要はないので、文字列を返す 
        return NUM;
    }

    if (strchr("<>=!&|+-*/%^", c) != NULL) {
        char buf[4];   // 演算子は最大 3 文字のはず
        ungetc(c, stdin);
        scanf("%3[<>=!&|+-*/%^]", &buf);
        int len = strlen(buf);
        column += len - 1;
        if (len == 1) {
            return c;
        }
        if (strcmp(buf, "<=") == 0) {
            return LE;
        }
        if (strcmp(buf, ">=") == 0) {
            return GE;
        }
        if (strcmp(buf, "==") == 0) {
            return EQ;
        }
        if (strcmp(buf, "!=") == 0) {
            return NE;
        }
        if (strcmp(buf, "&&") == 0) {
            return AND;
        }
        if (strcmp(buf, "||") == 0) {
            return OR;
        }
        fprintf(stderr, "unknown operator (%s) at line %d column %d", buf, line, column - len);
        exit(1);
    }
    
    if (c == EOF) { /* ファイルの終 */
        return EOF;
    }
    /* 上のどの条件にも合わなければ、文字をそのまま返す。*/
    return c;   /* '{', '}', '(', ')', '[', ']' など */
}

/* デバッグ用 */
char* tokenName(int t) {
    switch(t) {
      case 256:  return "ID";
      case 257:  return "NUM";
      case 258:  return "IF";    
      case 259:  return "ELSE";
      case 260:  return "WHILE"; 
      case 261:  return "DO";
      case 262:  return "FOR";   
      case 263:  return "LE";
      case 264:  return "GE";    
      case 265:  return "EQ";    
      case 266:  return "NE";    
      case 267:  return "AND";   
      case 268:  return "OR";
      case 269:  return "PRINT"; 
      case 270:  return "PRINTLN"; 
      case '+':  return "+";
      case '-':  return "-";
      case '*':  return "*";
      case '/':  return "/";
      case '%':  return "%";
      case '>':  return ">";
      case '<':  return "<";
      case '=':  return "=";
      case '(':  return "(";
      case ')':  return ")";
      case '{':  return "{";
      case '}':  return "}";
      case '[':  return "[";
      case ']':  return "]";
      case ';':  return ";";
      case ',':  return ",";
      case EOF:  return "EOF";
      default:   return "(Unknown)";
    }
}

/* id と番号の対応 a -> 1, b -> 2, ..., e -> 5 */
int idNum(char* id) {
    if (strcmp(id, "a") == 0) return 1;
    if (strcmp(id, "b") == 0) return 2;
    if (strcmp(id, "c") == 0) return 3;
    if (strcmp(id, "d") == 0) return 4;
    if (strcmp(id, "e") == 0) return 5;

    fprintf(stderr, "Variable (%s) is not available.\n", id);
    exit(1);
}

/* token（終端記号）を消費して、次の token を読む */
void eat(int t) {
    //    fprintf(stderr, "eating %s.\n", tokenName(t));
    if (token == t) {
        token = yylex();
        return;
    } else {
        if (isprint(t)) {
            fprintf(stderr, "eat: Character '%c' is expected at line %d column %d ",
                    t, line, column);
        } else {
            fprintf(stderr, "eat: Token %s is expected here at line %d column %d ",
                    tokenName(t), line, column);
        }
        if (isprint(token)) {
            fprintf(stderr, "instead of '%c'.\n", token);
        } else {
            fprintf(stderr, "instead of %s.\n", tokenName(token));
        }
        exit(1);
    }
}

/* 関数プロトタイプ宣言 */
char* E(void);
char* X(void);

/*
 * 再帰的構文解析関数群
 * 文法の各非終端記号に対応する関数
 */

char* P(void) {
    switch (token) {
      case '(': {
          eat('(');
          char* s1 = E();
          eat(')');
          return s1;
      }
      case ID: {
          char* id = yylval;
          int num = idNum(id);
          eat(ID);
          return mysprintf("iload %d\n", num);
      }
      case NUM: {
          char* num = yylval;
          char* ret = mysprintf("ldc %s\n", num);
          eat(NUM);
          return ret;
      }
      default:    
        fprintf(stderr, "unknown token %s.\n", tokenName(token));
        exit(1);
    }
}


list M1(void) {
    // TODO: 末尾再帰を繰り返しに書き換える
    switch (token)  {
      case '+':
      case '-':
      case ')':
      case '<':
      case '>':
      case GE:
      case LE:
      case EQ:
      case NE:
      case AND:
      case OR:
      case ';':
        return NULL;
      case '*': case '/': case '%': {
        list ret = (list)malloc(sizeof(struct _list));
        ret->token = token;
        eat(token);
        ret->yylval = P();
        ret->next   = M1();
        return ret;
      }
      default:
        fprintf(stderr, "unknown token %s.\n", tokenName(token));
        exit(1);
    }
}

char* M(void) {
    char *ret = P();
    list ss   = M1();
    // 左結合になるようにリストを処理する
    for (; ss != NULL; ss = ss->next) {
        char* op;
        switch (ss->token) {
          case '*':
              op = "imul\n"; break;
          case '/':
              op = "idiv\n"; break;
          case '%':
              op = "irem\n"; break;
          default:
              fprintf(stderr, "unknown token %s.\n", tokenName(ss->token));
              exit(1);
        }
        ret = mysprintf("%s%s%s",
                        ret,
                        ss->yylval,
                        op);
    }
    return ret;
}

list A1(void) {
    // TODO: 末尾再帰を繰り返しに書き換える
    switch (token)  {
      case ')':
      case '<':
      case '>':
      case GE:
      case LE:
      case EQ:
      case NE:
      case AND:
      case OR:
      case ';':
        return NULL;
      case '+': case '-': {
        list ret = (list)malloc(sizeof(struct _list));
        ret->token = token;
        eat(token);
        ret->yylval = M();
        ret->next   = A1(); 
        return ret;
      }
      default:
        fprintf(stderr, "unknown token %s.\n", tokenName(token));
        exit(1);
    }
}

char* A(void) {
    char *ret = M();
    list ss   = A1();
    // 左結合になるようにリストを処理する
    for (; ss != NULL; ss = ss->next) {
        char* op;
        switch (ss->token) {
          case '+':
              op = "iadd\n"; break;
          case '-':
              op = "isub\n"; break;
          default:
              fprintf(stderr, "unknown token %s.\n", tokenName(ss->token));
              exit(1);
        }
        ret = mysprintf("%s%s%s",
                        ret,
                        ss->yylval,
                        op);
    }
    return ret;
}

list R1(void) {
    // TODO: 末尾再帰を繰り返しに書き換える
    switch (token)  {
      case ')':
      case EQ:
      case NE:
      case AND:
      case OR:
      case ';':
        return NULL;
      case '<': case '>': case LE: case GE: {
        list ret = (list)malloc(sizeof(struct _list));
        ret->token = token;
        eat(token);
        ret->yylval = A();
        ret->next   = R1();
        return ret;
      }
      default:
        fprintf(stderr, "unknown token %s.\n", tokenName(token));
        exit(1);
    }
}

char* R(void) {
    char *ret = A();
    list ss   = R1();
    // 左結合になるようにリストを処理する
    for (; ss != NULL; ss = ss->next) {
        char* op;
        switch (ss->token) {
          case '<':
              op = ilt; break;
          case '>':
              op = igt; break;
          case LE:
              op = ile; break;
          case GE:
              op = ige; break;
          default:
              fprintf(stderr, "unknown token %s.\n", tokenName(ss->token));
              exit(1);
        }
        ret = mysprintf("%s%s%s",
                        ret,
                        ss->yylval,
                        op);
    }
    return ret;
}

list Q1(void) {
    // TODO: 末尾再帰を繰り返しに書き換える
    switch (token)  {
      case AND:
      case OR:
      case ')':
      case ';':
        return NULL;
      case EQ: case NE: {
        list ret = (list)malloc(sizeof(struct _list));
        ret->token = token;
        eat(token);
        ret->yylval = R();
        ret->next   = Q1();
        return ret;
      }
      default:
        fprintf(stderr, "unknown token %s.\n", tokenName(token));
        exit(1);
    }
}

char* Q(void) {
    char *ret = R();
    list ss   = Q1();
    // 左結合になるようにリストを処理する
    for (; ss != NULL; ss = ss->next) {
        char* op;
        switch (ss->token) {
          case EQ:
              op = ieq; break;
          case NE:
              op = ine; break;
          default:
              fprintf(stderr, "unexpected token %s.\n", tokenName(ss->token));
              exit(1);
        }
        ret = mysprintf("%s%s%s",
                        ret,
                        ss->yylval,
                        op);
    }
    return ret;
}

char* C(void) {
    // TODO: Logical-And (&&) 演算子の実装
    return Q();
}

char* E(void) {
    // TODO: Logical-Or (||) 演算子の実装
    return C();
}

char* S(void) {
    switch (token) {
      case IF: {
        eat(IF);
        eat('(');
        char* s1 = E();
        eat(')');
        char* s2 = S();
        eat(ELSE);
        char* s3 = S();
        char* label1 = newlabel();
        char* label2 = newlabel();
        return mysprintf("%s%s%s%s%s%s%s",
                         s1,
                         mysprintf("ifeq %s\n", label1),
                         s2,
                         mysprintf("goto %s\n", label2),
                         mysprintf("%s:\n", label1),
                         s3,
                         mysprintf("%s:\n", label2));
      }
      case WHILE: {
        eat(WHILE);
        eat('(');
        char* s1 = E();
        eat(')');
        char* s2 = S();
        char* label1 = newlabel();
        char* label2 = newlabel();
        return mysprintf("%s%s%s%s%s%s",
                         mysprintf("%s:\n", label1),
                         s1,
                         mysprintf("ifeq %s\n", label2),
                         s2,
                         mysprintf("goto %s\n", label1),
                         mysprintf("%s:\n", label2));
      }
      case DO: {
        // TODO: do 文の実装  
        fprintf(stderr, "do statement is not implemented yet.\n");
        exit(1);
      }
      case FOR: {
        // TODO:for 文の実装  
        fprintf(stderr, "for statement is not implemented yet.\n");
        exit(1);
      } 
      case '{': {
        eat('{');
        char* s1 = X();
        eat('}');
        return s1;
      }
      case ID: {
        char* id = yylval;
        int num = idNum(id);
        eat(ID);
        eat('=');
        char* s1 = E();
        eat(';');
        return mysprintf("%s%s",
                         s1,
                         mysprintf("istore %d\n", num));
      }
      case PRINT: {
        eat(PRINT);
        eat('(');
        char* s1 = E();
        eat(')');
        eat(';');
        return mysprintf("%s%s%s", s1, iprint, mysprintf("pop\n"));
      }
      case PRINTLN: {
        eat(PRINTLN);
        eat('(');
        char* s1 = E();
        eat(')');
        eat(';');
        return mysprintf("%s%s%s", s1, iprintln, mysprintf("pop\n"));
      }
      default: {
        fprintf(stderr, "unexpected token %s.\n", tokenName(token));
        exit(1);
      }
    }
}

char* X(void) {
    // TODO: 末尾再帰を繰り返しに書き換える
    switch (token) {
      case '}': case EOF: {
        char* ret = (char*)malloc(1);
        *ret = '\0';
        return ret;       // 空文字列を返す
      }
      case '*': case '/': case '%': case '+': case '-':
      case '<': case '>': case GE: case LE: case EQ: case NE:
      case AND: case OR: case '=':
          fprintf(stderr, "unexpected token %s.\n", tokenName(token));
          exit(1);
      default: {
        char* s1 = S();
        char* s2 = X();
        return mysprintf("%s%s", s1, s2);
      }
    }
}

/* Oolong のテンプレートを生成する */
void mae(void) { 
    int i, n = 5;          /* n は用意する変数の個数 */

    printf(".super java/lang/Object\n");
    printf("\n");
    printf(".method public static main([Ljava/lang/String;)V\n");
    /*
        スタックの最大の大きさを指定する。
        クラス実行時に Stack size too large というエラーメッセージが出る時は、
        下の``16''をより大きな数に変更すること。 
     */
    printf(".limit stack 16\n");  
    printf(".catch java/lang/ArrayIndexOutOfBoundsException from begin to end using handler\n");
    /*
        JVM の変数 1〜5 を 0 に初期化する。
     */
    for (i = 1; i <= n; i++) {
        printf("iconst_0\n");
        printf("istore %d\n", i);
    }
    /*
        1〜5 番目のコマンドライン引数を整数に変換して、
        JVM の変数 1〜5 に代入する。
     */
    printf("begin:\n");
    for (i = 1; i <= n; i++) {  
        printf("aload_0\n");
        printf("ldc %d\n", i - 1);
        printf("aaload\n");
        printf("invokestatic java/lang/Integer/parseInt(Ljava/lang/String;)I\n");
        printf("istore %d\n", i);
    }
    printf("end: \n");
    printf("goto exit\n");
    printf("handler:\n");
    printf("pop\n");
    printf("exit:\n");
    printf("\n");
}

/* Oolong のテンプレートを生成する */
void ato(void) { 
    printf("\n");
    printf("return\n");
    printf(".end method\n");
}

/* main関数 */
int main(void) {
    token = yylex(); /* 最初のトークンを読む */
    char* ret = X();
    if (token != EOF) {
        fprintf(stderr, "premature end of file\n");
        exit(1);
    }
    mae();
    printf("   ; ↑↑↑の部分は、1〜5 番目のコマンドライン引数を変数 1〜5 に順に格納する。\n");    
    printf("   ; ↓↓↓ この部分が再帰的関数が出力するコード ↓↓↓\n");
    printf("%s", ret);
    printf("   ; ↑↑↑ この部分が再帰的関数が出力するコード ↑↑↑\n");  
    ato();
    return 0;
}