cc0 編譯器 (1.0 版)

編譯器設計

編譯器簡介

高階語言

語法理論

剖析器

語意理論

符號表

直譯器

型態系統

中間碼

目標語言

最佳化

錯誤處理

進階議題

原始碼下載

程式實作

C 語言

案例研究

JavaScript

V8

Lua

Oberon

NeoPascal

pcc

tcc

gcc

C--

Lex

YACC

AntLR

LLVM

CLang

訊息

相關網站

參考文獻

最新修改

簡體版

English

測試檔:test.c0

int debug = 1;

int sum(int n) {
    int s=0;
    for (i=0; i<n; i++)
        s = s + i;
    return s;
}

int swap(int a, int b) {
    t = a;
    a = b;
    b = t;
}

int main() {
    int x=3, y=5, z;
    if ((x+y)>6)
        z = 0;
    else
        z = 1;

    int i=0, s=0;
    while (i<10) {
        s = s + i;
        i++;
    }

    int total=sum(10);
    =swap(x, y);
}

程式碼:cc0v0.7.c

#include <stdio.h>
#include <assert.h>
#include <stdarg.h>

// ================== 基本常數 ===================
#define FALSE   0
#define TRUE    1
#define BOOL    unsigned char
#define NIL        -1
#define LEN 256
#define MAX_ARGS 100
#define SPACE " \t\n\r"         // 空白字元
#define ALPHA "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" // 英文字母
#define DIGIT "0123456789"        // 數字字元
#define OPERATOR "+-*/%<=>!&|"        // 運算符號字元集 (用來取得 +,-,*,/, ++, ...)

char *keys[] = {"if", "else", "for", "while", "def", "return", NULL};
typedef enum Type { VOID,   BYTE,   I32,   F32,     STR,    FCALL,    OBJ ,   LABEL} Type; // 語意形態
char *types[]  =  { "void", "byte", "int", "float", "$str", "$fcall", "$obj", "$label", NULL };
typedef enum Tag { STRING, INTEGER, FLOAT, ID, OP, PROG_END } Tag; // 標記 tag 的選項 
char *tags[] = {"STRING", "INTEGER", "FLOAT", "ID", "OP", "$ENDP" };
typedef enum Kind { KEY, TYPE, FUNC, VAR, NONE } Kind; // 種類 kind 的選項 
char *kinds[] = {"KEY", "TYPE", "FUNC", "VAR", "NONE" };
typedef enum Op { NOP, SET, ADD, SUB, MUL, DIV, MOD, GOTO,   FUNCTION,   ENDF,   PARAM,   RET,   CALL,   ARG,   IF1,   IF0  , PLUS, MINUS, LAND, LOR , AND, OR,  XOR, NOT, GT,  LT,  GE,   LE,   EQ,   NE} Op;
char *ops[]   = { "",  "=", "+", "-", "*", "/", "%", "goto", "function", "endf", "param", "ret", "call", "arg", "if1", "if0", "++", "--",  "&&", "||", "&", "|", "^", "!", ">", "<", ">=", "<=", "==", "!=", NULL };

#define cmember(ch, set) (strchr(set, ch) != NULL)// 測試字元 ch 是否在 set 當中
#define NEXT(var, tag)   char var[LEN];strcpy(var, token);nextTag(tag)
#define NEXT_TOKEN(var, tokens)  char var[LEN];strcpy(var, token);next(tokens)
#define SYMBOL(var, id)  char var[LEN];strcpy(var, symName(symGet(id)))
#define OP(var, id)      char var[LEN];strcpy(var, ops[id])
#define ASSERT(cond)     if (!(cond)) { ERROR(); }  // 要求條件要成立,否則就算錯
// 錯誤報告巨集函數,會印出哪一行呼叫了 ERROR()
#define ERROR() printf("ERROR => file:%s, line: %d\n", __FILE__, __LINE__);printStack();exit(1)

FILE *file;
char ch;
int line=1, pos=0;
char token[LEN];
int  tokenIdx = 0;
Tag tag;
Kind kind;
Type type;

typedef struct Obj {
} Obj;

typedef struct Sym {
    int strIdx;
    Type type;
    union {
        float f;
        int   i;
        int   addr;
        Obj   *o;
    } val;
} Sym;

int symTop = 1;
int strTop = 0;

#define SYM_TABLE_MAX 1000
Sym symTable[SYM_TABLE_MAX];
#define TMP_TABLE_MAX 1000
Sym tmpTable[TMP_TABLE_MAX];
#define STR_TABLE_MAX 10000
char strTable[STR_TABLE_MAX];

char *nodeStack[100];
int nodeTop = 0;

void printStack() {
    int i;
    for (i=0; i<nodeTop; i++)
        printf("/%s", nodeStack[i]);
    printf("\n");
}

int push(char *name) {
    nodeStack[nodeTop] = name;
    nodeTop ++;
}

char *pop(char *name) {
    nodeTop--;
    char *nameTop = nodeStack[nodeTop];
    ASSERT(strcmp(nameTop, name)==0);
    return nameTop;
}

int strFind(char *strList[], char *key) {
    int i;
    for (i=0; strList[i] != NULL; i++) {
        if (strcmp(strList[i], key)==0)
            return i;
    }
    return NIL;
}

void debug(const char *fmt, ...) {
    va_list args;
    va_start(args, fmt);
    vprintf(fmt, args);
}

int type2id(char *typeStr) {
    int typeId = strFind(types, typeStr);
    ASSERT(typeId != NIL);
    return typeId;
}

Sym *symGet(int s) {
    if (s <= 0)
        return NULL;
    else
        return &symTable[s];
}

char *symName(Sym *sym) {
    if (sym == NULL) return "";
    return &strTable[sym->strIdx];
}

int symFind(char *name) {
    int s;
    for (s=1; s<symTop; s++) {
        Sym *sym = symGet(s);
        if (strcmp(name, symName(sym))==0)
            return s;
    }
    return NIL;
}

int symPut(char *name, Type type) {
    int s = symFind(name);
    if (s == NIL) {
        sprintf(&strTable[strTop], "%s", name);
        s = symTop++;
        symTable[s].strIdx = strTop;
        symTable[s].type = type;
        strTop += strlen(name) + 1;
    }
    return s;
}

void symPrint(Sym *sym) {
    if (sym==NULL) return;
    printf("%s(%s,", symName(sym), types[sym->type]);
    switch (sym->type) {
        case I32:printf("%d", sym->val.i); break;
        case F32:printf("%f", sym->val.f); break;
        case LABEL:printf("%d", sym->val.addr); break;
    }
    printf(")");
}

void symPrintln(Sym *sym) { symPrint(sym); printf("\n"); }

void symTableDump() {
    int i;
    printf("======= symTable ========\n");
    for (i=1; i<symTop; i++) {
        Sym *sym = &symTable[i];
        printf("%d:", i);
        symPrintln(sym);
    }
}

void strTableDump() {
    int i;
    printf("======= strTable ========\n");
    for (i=0; i<strTop; i++) {
        char c = strTable[i];
        if (c == '\0') 
            printf(".");
        else
            printf("%c", c);
    }
    printf("\n");
}

int labelIdx = 0;

int nextLabel() {
    char label[LEN];
    sprintf(label, "_L%d", labelIdx++);
    return symPut(label, LABEL);
}

int tempIdx = 1;

int nextTemp(Type type) {
    char tempName[LEN];
    sprintf(tempName, "t%d", tempIdx++);
    return symPut(tempName, type);
}

// 功能:檢查 token 是否為集合字串 set 中的元素
// 範例:strPartOf("int", "byte|int|float") 會傳回 TRUE
BOOL strPartOf(char *token, char *set) {
    ASSERT(token != NULL && set != NULL);
    ASSERT(strlen(token) < LEN);
    char ttoken[LEN+2];
    sprintf(ttoken, "|%s|", token);
    return (strstr(set, ttoken)!=NULL);
}

BOOL isNext(char *tokens) { // 檢查下一個詞彙是否為 tokens 其中之一
    char tTokens[LEN+1];
    sprintf(tTokens, "|%s|", tokens);
    if (strPartOf(token, tTokens))
        return TRUE;
    else
        return FALSE;
}

BOOL isNextTag(Tag pTag) { // 檢查下一個 tag 是否為 pTag
    return (tag == pTag);
}

BOOL isNextKind(Kind pKind) { // 檢查下一個 kind 是否為 pKind
    return (kind == pKind);
}

char cnext() {
    token[tokenIdx++]=ch;
    pos++;
    ch=fgetc(file);
    return ch;
}

void tnext() {
    while (cmember(ch, SPACE)) { // 忽略空白
        tokenIdx = 0;
        if (ch=='\n') {
            line++;
            pos = 1;
        }
        cnext();
    }
    if (feof(file)) {
        strcpy(token, "$ENDP");
        tag = PROG_END;
        return;
    }
    tokenIdx = 0;
    if (ch == '\"') { // 如果是 " 代表字串開頭
        // 字串常數 : string = ".."
        cnext(); // 跳過 "
        while (ch != '\"') cnext(); // 一直讀到下一個 " 符號為止。
        cnext(); // 跳過 "
        tag=STRING;
    } else if (cmember(ch, OPERATOR)) { // 如果是OP(+-*/<=>!等符號)
        // 運算符號 : OP = ++, --, <=, >=, ...
        while (cmember(ch, OPERATOR)) cnext(); // 一直讀到不是OP為止
        token[tokenIdx] = '\0';
        tag=OP;
    } else if (cmember(ch, DIGIT)) { // 如果是數字
        // 數字常數 : INTEGER = 312, 77568, ...
        while (cmember(ch, DIGIT)) cnext(); // 一直讀到不是數字為止
        tag=INTEGER;
        // 實數 : real = 3.14, ...
        if (ch == '.') {
            cnext(); // 取得小數點
            tag = FLOAT;
        }
        while (cmember(ch, DIGIT)) cnext(); // 取得小數部分
    } else if (cmember(ch, ALPHA)) { // 如果是英文字母
        // 基本詞彙 : token = int, sum, i, for, if, x1y2z, ....
        while (cmember(ch, ALPHA) || cmember(ch, DIGIT))
            cnext(); // 一直讀到不是英文字母 (或數字)為止
        token[tokenIdx] = '\0';
        tag=ID;
    } else { // 其他符號,都解讀為單一字元
        tag = OP;
        cnext(); // 傳回單一字元
    }
    token[tokenIdx] = '\0';
    if (strFind(keys, token)!=NIL) 
        kind = KEY;
    else if (strFind(types, token)!=NIL)
        kind = TYPE;
    else if (tag == ID)
        kind = VAR;
    else
        kind = NONE;
}

void next(char *tokens) { // 檢查下一個詞彙的型態
    if (isNext(tokens)) { // 如果是pTags型態之一
        tnext();
    } else { // 否則,印出錯誤訊息
        debug("next():line=%d pos=%d token=%s expect(%s)\n", 
            line, pos, token, tokens); 
        ERROR();
    }
}

void nextTag(Tag eTag) { // 檢查下一個 tag 的型態
    if (isNextTag(eTag)) {
        tnext();
    } else {
        debug("nextTag():line=%d pos=%d token=%s tag=%s expect(tag=%s)\n", 
            line, pos, token, tags[tag], tags[eTag]);
        ERROR();
    }
}

void nextKind(Kind eKind) { // 檢查下一個 tag 的型態
    if (isNextKind(eKind)) {
        tnext();
    } else {
        debug("nextKind():line=%d pos=%d token=%s kind=%s expect(kind=%s)\n", 
            line, pos, token, kinds[kind], kinds[eKind]); 
        ERROR();
    }
}

typedef struct PCode {
    int lab, op, s, s1, s2;
} PCode;

#define MAX_PCODE 10000
PCode pcodeList[MAX_PCODE];

#define MAX_PCODE_TEMP 1000
PCode pcodeTempList[MAX_PCODE_TEMP];

int pcodeTop = 0, pcodeTempTop = 0;

PCode *pcodeListNow = pcodeList;

void pcodePrint(PCode *pcode) {
    SYMBOL(label, pcode->lab); SYMBOL(p, pcode->s); SYMBOL(p1, pcode->s1); SYMBOL(p2, pcode->s2);
    OP(opName, pcode->op);
    printf("%-8s %-8s %-8s %-8s %-8s ; ", label, opName, p, p1, p2);
}

void pcodePrintln(PCode *pcode) { pcodePrint(pcode); printf("\n"); }

void pcode(int lab, int op, int s, int s1, int s2) {
    PCode *pcode = NULL;

    if (pcodeListNow == pcodeTempList)
        pcode = &pcodeTempList[pcodeTempTop++];
    else
        pcode = &pcodeList[pcodeTop++];

    pcode->lab = lab;
    pcode->op  = op;
    pcode->s   = s;
    pcode->s1  = s1;
    pcode->s2  = s2;

    if (pcodeListNow == pcodeTempList) {
        printf("redirect : ");
        pcodePrintln(pcode);
    } else
        pcodePrintln(pcode);
}

void pcodeDump(PCode *list, int size) {
    printf("======= pcodeDump() ========\n");
    int i;
    for (i=0; i<size; i++) {
        printf("dump %d:", i);
        pcodePrintln(&list[i]);
    }    
}

void pcodeRedirect() {
    pcodeListNow = pcodeTempList;
    pcodeTempTop = 0;
}

void pcodeRedirectEnd() {
    memcpy(&pcodeList[pcodeTop], &pcodeTempList[0], sizeof(PCode)*pcodeTempTop);
    pcodeTop += pcodeTempTop;
    pcodeDump(pcodeTempList, pcodeTempTop);
    pcodeListNow = pcodeList;
}

#define typeEqual(s1, s2) assert((s1)->type == (s2)->type)
#define varCopy(s, t) (t)->type=(s)->type; (t)->val=(s)->val

int fOp(Sym *s, Op op, Sym *s1, Sym *s2) {
    switch (op) {
        case ADD:   s->val.f = s1->val.f + s2->val.f; break;
        case SUB:   s->val.f = s1->val.f - s2->val.f; break;
        case MUL:   s->val.f = s1->val.f * s2->val.f; break;
        case DIV:   s->val.f = s1->val.f / s2->val.f; break;
//        case LAND:    s->val.f = (s1->val.f & s2->val.f); break;
//        case LOR:     s->val.f = s1->val.f | s2->val.f; break;
//        case XOR:     s->val.f = s1->val.f ^ s2->val.f; break;
        case AND:     s->val.f = s1->val.f && s2->val.f; break;
        case OR:      s->val.f = s1->val.f || s2->val.f; break;
        case GT:      s->val.f = s1->val.f > s2->val.f; break;
        case LT:      s->val.f = s1->val.f < s2->val.f; break;
        case GE:      s->val.f = s1->val.f >= s2->val.f; break;
        case LE:      s->val.f = s1->val.f <= s2->val.f; break;
        case EQ:      s->val.f = s1->val.f == s2->val.f; break;
        case NE:      s->val.f = s1->val.f != s2->val.f; break;
        case PLUS:    s->val.f++; break;
        case MINUS:    s->val.f--; break;
        case NOT:     s->val.f = !s1->val.f; break;
        default :     ERROR();
    }    
}

int iOp(Sym *s, Op op, Sym *s1, Sym *s2) {
    switch (op) {
        case ADD:     s->val.i = s1->val.i + s2->val.i; break;
        case SUB:     s->val.i = s1->val.i - s2->val.i; break;
        case MUL:     s->val.i = s1->val.i * s2->val.i; break;
        case DIV:     s->val.i = s1->val.i / s2->val.i; break;
        case MOD:     s->val.i = s1->val.i % s2->val.i; break;
        case LAND:    s->val.i = s1->val.i & s2->val.i; break;
        case LOR:     s->val.i = s1->val.i | s2->val.i; break;
        case XOR:     s->val.i = s1->val.i ^ s2->val.i; break;
        case AND:     s->val.i = s1->val.i && s2->val.i; break;
        case OR:      s->val.i = s1->val.i || s2->val.i; break;
        case GT:      s->val.i = s1->val.i > s2->val.i; break;
        case LT:      s->val.i = s1->val.i < s2->val.i; break;
        case GE:      s->val.i = s1->val.i >= s2->val.i; break;
        case LE:      s->val.i = s1->val.i <= s2->val.i; break;
        case EQ:      s->val.i = s1->val.i == s2->val.i; break;
        case NE:      s->val.i = s1->val.i != s2->val.i; break;
        case PLUS:    s->val.i = s->val.i+1; break;
        case MINUS:    s->val.i = s->val.i-1; break;
        case NOT:     s->val.i = !s1->val.i; break;
        default :     ERROR();
    }
}

int varOp(Sym *s, Op op, Sym *s1, Sym *s2) {
    assert(s1 ==NULL || s->type == s1->type);
    assert(s2 ==NULL || s->type == s2->type);
    switch (s->type) {
        case F32: fOp(s, op, s1, s2);
        case I32: iOp(s, op, s1, s2);
    }
}

int argList[MAX_ARGS];
int argTop = 0;

int argPush(int a)     { argList[argTop++] = a; }
int argPop()         { 
    assert(argTop > 0);
    return argList[--argTop]; 
}

int varPush(int a) { 
    Sym *pushArg = symGet(a);
//    printf("varPush : ");
//    symPrintln(pushArg);
    argList[argTop++] = a; 
}

int varPop(int a)     { 
    assert(argTop > 0);
    Sym *popArg = symGet(argList[--argTop]);
    Sym *arg = symGet(a);
//    printf("varPop : ");
//    symPrint(popArg);
    varCopy(popArg, arg); 
//    printf(" => ");
//    symPrintln(arg);
}

int pc=0, /*lr=-1, */ ret=-1, rzcall = -1;

typedef struct Call {
    int backto;
} Call;

#define CALL_STACK_MAX 100
Call callStack[CALL_STACK_MAX];
int callStackTop = 0;

int callPush(int backto) {
    callStack[callStackTop++].backto = backto; 
//    printf("callPush(%d) top=%d\n", backto, callStackTop);
}

Call *callPop() {
    assert(callStackTop > 0);
    Call *call = &callStack[--callStackTop];
//    printf("callPop(%d) top=%d\n", call->backto, callStackTop);
    return call; 
}

int pcodeExec(PCode *pcode) {
    int op = pcode->op;
    int lab = pcode->lab;
    Sym *s = symGet(pcode->s);
    Sym *s1 = symGet(pcode->s1);
    Sym *s2 = symGet(pcode->s2);
    BOOL isJmp = FALSE;

    switch (op) {
        case NOP: break;
        case SET: varCopy(s1, s); break;
        case ADD: varOp(s, ADD, s1, s2); break;
        case SUB: varOp(s, SUB, s1, s2); break;
        case MUL: varOp(s, MUL, s1, s2); break;
        case DIV: varOp(s, DIV, s1, s2); break;
        case MOD: varOp(s, MOD, s1, s2); break;
        case LAND:varOp(s, LAND, s1, s2); break;
        case LOR: varOp(s, LOR, s1, s2); break;
        case AND: varOp(s, AND, s1, s2); break;
        case OR:  varOp(s, OR, s1, s2); break;
        case XOR: varOp(s, XOR, s1, s2); break;
        case GT:  varOp(s, GT, s1, s2); break;
        case LT:  varOp(s, LT, s1, s2); break;
        case GE:  varOp(s, GE, s1, s2); break;  
        case LE:  varOp(s, LE, s1, s2); break;
        case EQ:  varOp(s, EQ, s1, s2); break;
        case NE:  varOp(s, NE, s1, s2); break;
        case PLUS:varOp(s, PLUS, s1, s2); break;
        case MINUS:varOp(s,MINUS, s1, s2); break;
        case NOT: varOp(s, NOT, s1, s2); break;
        case FUNCTION: break;
        case PARAM: varPop(pcode->s); break;
        case RET: 
            argTop = 0; 
            Sym *ret = symGet(pcode->s);
            Sym *result = symGet(rzcall);
            varCopy(ret, result);
            pc = callPop()->backto;
            isJmp = TRUE;
            break;
        case ENDF: 
            if (callStackTop <=0) return FALSE;
            pc = callPop()->backto; 
            isJmp = TRUE;
            break;
        case CALL: callPush(pc+1); pc = s->val.addr; rzcall = pcode->s1; break;
        case ARG:  varPush(pcode->s); break;
        case GOTO: pc = s->val.addr; isJmp = TRUE; break;
        case IF1: if (s->val.i!=0) { pc = s1->val.addr; isJmp = TRUE; } break;
        case IF0: if (s->val.i==0) { pc = s1->val.addr; isJmp = TRUE; } break;
        default: ERROR();
    }
    pcodePrint(pcode);
    symPrintln(s);
    if (!isJmp) pc++;
    return TRUE;
}

void pcodeInit() {
    printf("======== pcodeInit() ========\n");
    int s;
    for (s=1; s<symTop; s++) {
        SYMBOL(name, s);
        Sym *sym = symGet(s);
        if (isdigit(name[0])) {
            if (strchr(name, '.')!=NULL) {
                sym->type = F32;
                sym->val.i = atoi(name);
                assert(FALSE);
            } else {
                sym->type = I32;
                sym->val.i = atoi(name);
            }
        }
    }
    int addr;
    for (addr=0; addr<pcodeTop; addr++) {
        PCode *pcode = &pcodeList[addr];
        printf("%-3d:", addr);
        pcodePrint(pcode);
        if (pcode->lab > 0) {
            Sym *symLabel = symGet(pcode->lab);
            symLabel->val.addr = addr;
            symPrint(symLabel);
        }
        printf("\n");
    }
}

int pcodeRun() {
    printf("======== pcodeRun() ========\n");
    pc=0; argTop = 0;
    int idMain = symFind("main");
    Sym *symMain = symGet(idMain);
    pc = symMain->val.addr;
    while (TRUE) {
        printf("%-3d:", pc);
        if (!pcodeExec(&pcodeList[pc]))
            break;
    }
}

// ARGS = {} | E {, ARGS}?
// 用在 ID(ARGS) 中,follow 為 )
int ARGS() {
    push("ARGS");
    if (!isNext(")")) {
        argPush(E());
        if (isNext(",")) {
            next(",");
            ARGS();
        }
    }
    pop("ARGS");
}

// F=STRING | INTEGER | FLOAT | '(' E ')' | ID ('('ARGS')')?
int F() {
    int f;
    push("F");
    if (isNext("(")) {
        next("(");
        f = E();
        next(")");
    } else if (isNextTag(INTEGER)) {
        NEXT(iStr, INTEGER);
        f = symPut(iStr, I32);
    } else if (isNextTag(FLOAT)) {
        NEXT(fStr, FLOAT);
        f = symPut(fStr, F32);
    } else if (isNextTag(STRING)) {
        NEXT(str, STRING);
        f=symPut(str, STR);
    } else { // if (isNextTag(ID))
        NEXT(id, ID);
        f=symPut(id, FCALL);
        if (isNext("(")) { // function call
            next("(");
            argTop = 0;
            ARGS();
            next(")");
            int i;
            for (i=0; i<argTop; i++) {
                pcode(0, ARG, argList[i], 0, 0);
            }
            int t = nextTemp(VOID); // 需修改
            pcode(0, CALL, f, t, 0);
            f = t;
        }
    }
    pop("F");
    return f; 
}

#define E_OP "+|-|*|/|%|&|^|||&&||||>>|<<|==|<=|>=|<|>"
// E=F (E_OP F)?
int E() {
    push("E");
    int f1 = F();
    if (isNext(E_OP)) {
        NEXT_TOKEN(op, E_OP);
        int f2 = F();
        int e = nextTemp(symGet(f1)->type);
        int iop = strFind(ops, op);
        pcode(0, iop, e, f1, f2);
        f1 = e;
    }
    pop("E");
    return f1;
}

// ASSIGN = (ID[++|--]?)?(=E)?
int ASSIGN() {
    push("ASSIGN");
    int var = NIL;
    if (isNextTag(ID)) {
        NEXT(id, ID);
        var = symPut(id, type);
        if (isNext("++|--")) {
            NEXT_TOKEN(op1, "++|--");
            int iop1 = strFind(ops, op1);
            pcode(0, iop1, var, 0, 0);
        }
    }
    if (isNext("=")) {
        next("=");
        int e = E();
        if (var != NIL)
            pcode(0, SET, var, e, 0);
    }
    pop("ASSIGN");
}

// DECLS = TYPE? ASSIGN_LIST 
int DECLS() {
    push("DECLS");
    if (isNextKind(TYPE)) {
        type = type2id(token);
        nextKind(TYPE);
    }
    ASSIGN_LIST();
    pop("DECLS");
}

// ASSIGN_LIST = {} | ASSIGN {, ASSIGN_LIST}?
int ASSIGN_LIST() {
    push("ASSIGN_LIST");
    if (!isNext(";")) {
        ASSIGN();
        if (isNext(",")) {
            next(",");
            ASSIGN_LIST();
        }
    }
    pop("ASSIGN_LIST");
}

// STMT=return E | DECLS
int STMT() {
    push("STMT");
    if (isNext("return")) { 
        next("return");
        int e = E();
        pcode(0, RET, e, 0, 0);
    } else {
        DECLS();
    }
    pop("STMT");
}

// BASE=STMT;|IF|WHILE|FOR|BLOCK
int BASE() {
    push("BASE");
    if (isNext("{"))
        BLOCK();
    else if (isNext("if"))
        IF();
    else if (isNext("while"))
        WHILE();
    else if (isNext("for"))
        FOR();
    else {
        STMT();
        next(";");
    }
    pop("BASE");
}

// BASE_LIST = {} | BASE BASE_LIST?
int BASE_LIST() {
    push("BASE_LIST");
    if (!isNext("}|$ENDP")) {
        BASE();
        BASE_LIST();
    }
    pop("BASE_LIST");
}

// BLOCK={ BASE_LIST }
int BLOCK() {
    push("BLOCK");
    next("{");
    BASE_LIST();
    next("}");
    pop("BLOCK");
}

// IF=if (E) BASE else BASE
int IF() {
    push("IF");
    next("if");
    next("(");
    int e = E();
    next(")");
    int elseLabel = nextLabel();
    pcode(0, IF0, e, elseLabel, 0);
    BASE();
    if (isNext("else")) {
        next("else");
        pcode(elseLabel, NOP, 0, 0, 0);
        BASE();
    }
    pop("IF");
}

// WHILE=while (E) BASE
int WHILE() {
    push("WHILE");
    int startLabel = nextLabel();
    int exitLabel = nextLabel();
    pcode(startLabel, NOP, 0, 0, 0);
    next("while");
    next("(");
    int e = E();
    next(")");
    pcode(0, IF0, e, exitLabel, 0);
    BASE();
    pcode(0, GOTO, startLabel, 0, 0);
    pcode(exitLabel, NOP, 0, 0, 0);
    pop("WHILE");
}

// FOR=for (STMT;E;STMT) BASE
int FOR() {
    push("FOR");
    int startLabel = nextLabel();
    int exitLabel = nextLabel();
    next("for");
    next("(");
    STMT();
    next(";");
    pcode(startLabel, NOP, 0, 0, 0);
    int e = E();
    pcode(0, IF0, e, exitLabel, 0);
    next(";");
    pcodeRedirect();     // 先將 pcode 輸出轉向
    STMT();             // 這個不能邊比對邊編譯,所以才用 pcode 轉向。
    next(")");
    pcodeRedirectEnd(); // 然後在將 pcode 輸出結果補在這裏。
    BASE();
    pcode(0, GOTO, startLabel, 0, 0);
    pcode(exitLabel, NOP, 0, 0, 0);
    pop("FOR");
}

// PARAMS = {} | TYPE ID {, PARAMS}?
int PARAMS() {
    push("PARAMS");
    if (isNextKind(TYPE)) {
        type = type2id(token);
        nextKind(TYPE);
        NEXT(p1, ID);
        pcode(0, PARAM, symPut(p1, type), 0, 0);
        if (isNext(",")) {
            next(",");
            PARAMS();
        }
    }
    pop("PARAMS");
}

// DEF=TYPE ID ( (=E)? ; | ('(' PARAMS ')' BLOCK) )
// 宣告 int x = 1; 或函數 int f(x) {...}
int DEF() {
    push("DEF");
    type = type2id(token);
    nextKind(TYPE);
    NEXT(id, ID);
    if (isNext("(")) {
        next("(");
        int exitLabel = nextLabel();
        int f = symPut(id, FCALL);
        pcode(f, FUNCTION, 0, 0, 0);
        PARAMS();
        next(")");    
        BLOCK();
        pcode(0, ENDF, 0, 0 , 0);
    } else {
        if (isNext("=")) {
            next("=");
            int var = symPut(id, type);
            int e = E();
            pcode(0, SET, var, e, 0);
        }
        next(";");
    }
    pop("DEF");
}

// DEF_LIST = {} | DEF DEF_LIST?
int DEF_LIST() {
    push("DEF_LIST");
    if (!isNext("$ENDP")) {
        DEF();
        DEF_LIST();
    }    
    pop("DEF_LIST");
}

// PROG=DEF_LIST
int PROG() {
    push("PROG");
    DEF_LIST();
    pop("PROG");
}

int init() {
    fseek(file, 0, SEEK_SET);
    tokenIdx = 0;
    tnext();
}

int scan() {
    init();
    while (TRUE) {
        tnext();
        if (tag == PROG_END)
            break;
        printf("token=%-8s tag=%-8s kind=%d,%-8s\n", token, tags[tag], kind, kinds[kind]);
    }
}

int compile(char *fname) {
    printf("==== compile file:%s ========\n", fname);
    file = fopen(fname, "r");
//  init(); scan();
    init();
    PROG();
    symTableDump();
    strTableDump();
    fclose(file);
}

int main(int argc, char * argv[]) {
    char *fname = argv[1];
    compile(fname);
    pcodeDump(pcodeList, pcodeTop);
    pcodeInit();
    pcodeRun();
}

執行結果

==== compile file:test.c0 ========
         =        debug    1                 ; 
sum      function                            ; 
         param    n                          ; 
         =        s        0                 ; 
         =        i        0                 ; 
_L1                                          ; 
         <        t1       i        n        ; 
         if0      t1       _L2               ; 
redirect :          ++       i                          ; 
======= pcodeDump() ========
dump 0:         ++       i                          ; 
         +        t2       s        i        ; 
         =        s        t2                ; 
         goto     _L1                        ; 
_L2                                          ; 
         ret      s                          ; 
         endf                                ; 
swap     function                            ; 
         param    a                          ; 
         param    b                          ; 
         =        t        a                 ; 
         =        a        b                 ; 
         =        b        t                 ; 
         endf                                ; 
main     function                            ; 
         =        x        3                 ; 
         =        y        5                 ; 
         +        t3       x        y        ; 
         >        t4       t3       6        ; 
         if0      t4       _L5               ; 
         =        z        0                 ; 
_L5                                          ; 
         =        z        1                 ; 
         =        i        0                 ; 
         =        s        0                 ; 
_L6                                          ; 
         <        t5       i        10       ; 
         if0      t5       _L7               ; 
         +        t6       s        i        ; 
         =        s        t6                ; 
         ++       i                          ; 
         goto     _L6                        ; 
_L7                                          ; 
         arg      10                         ; 
         call     sum      t7                ; 
         =        total    t7                ; 
         arg      x                          ; 
         arg      y                          ; 
         call     swap     t8                ; 
         endf                                ; 
======= symTable ========
1:debug(int,0)
2:1(int,0)
3:_L0($label,0)
4:sum($fcall,)
5:n(int,0)
6:s(int,0)
7:0(int,0)
8:_L1($label,0)
9:_L2($label,0)
10:i(int,0)
11:t1(int,0)
12:t2(int,0)
13:_L3($label,0)
14:swap($fcall,)
15:a(int,0)
16:b(int,0)
17:t(int,0)
18:_L4($label,0)
19:main($fcall,)
20:x(int,0)
21:3(int,0)
22:y(int,0)
23:5(int,0)
24:z(int,0)
25:t3(int,0)
26:6(int,0)
27:t4(int,0)
28:_L5($label,0)
29:_L6($label,0)
30:_L7($label,0)
31:10(int,0)
32:t5(int,0)
33:t6(int,0)
34:total(int,0)
35:t7(void,)
36:t8(void,)
======= strTable ========
debug.1._L0.sum.n.s.0._L1._L2.i.t1.t2._L3.swap.a.b.t._L4.main.x.3.y.5.z.t3.6.t4._L5._L6._L7.10.t5.t6.total.t7.t8.
======= pcodeDump() ========
dump 0:         =        debug    1                 ; 
dump 1:sum      function                            ; 
dump 2:         param    n                          ; 
dump 3:         =        s        0                 ; 
dump 4:         =        i        0                 ; 
dump 5:_L1                                          ; 
dump 6:         <        t1       i        n        ; 
dump 7:         if0      t1       _L2               ; 
dump 8:         ++       i                          ; 
dump 9:         +        t2       s        i        ; 
dump 10:         =        s        t2                ; 
dump 11:         goto     _L1                        ; 
dump 12:_L2                                          ; 
dump 13:         ret      s                          ; 
dump 14:         endf                                ; 
dump 15:swap     function                            ; 
dump 16:         param    a                          ; 
dump 17:         param    b                          ; 
dump 18:         =        t        a                 ; 
dump 19:         =        a        b                 ; 
dump 20:         =        b        t                 ; 
dump 21:         endf                                ; 
dump 22:main     function                            ; 
dump 23:         =        x        3                 ; 
dump 24:         =        y        5                 ; 
dump 25:         +        t3       x        y        ; 
dump 26:         >        t4       t3       6        ; 
dump 27:         if0      t4       _L5               ; 
dump 28:         =        z        0                 ; 
dump 29:_L5                                          ; 
dump 30:         =        z        1                 ; 
dump 31:         =        i        0                 ; 
dump 32:         =        s        0                 ; 
dump 33:_L6                                          ; 
dump 34:         <        t5       i        10       ; 
dump 35:         if0      t5       _L7               ; 
dump 36:         +        t6       s        i        ; 
dump 37:         =        s        t6                ; 
dump 38:         ++       i                          ; 
dump 39:         goto     _L6                        ; 
dump 40:_L7                                          ; 
dump 41:         arg      10                         ; 
dump 42:         call     sum      t7                ; 
dump 43:         =        total    t7                ; 
dump 44:         arg      x                          ; 
dump 45:         arg      y                          ; 
dump 46:         call     swap     t8                ; 
dump 47:         endf                                ; 
======== pcodeInit() ========
0  :         =        debug    1                 ; 
1  :sum      function                            ; sum($fcall,)
2  :         param    n                          ; 
3  :         =        s        0                 ; 
4  :         =        i        0                 ; 
5  :_L1                                          ; _L1($label,5)
6  :         <        t1       i        n        ; 
7  :         if0      t1       _L2               ; 
8  :         ++       i                          ; 
9  :         +        t2       s        i        ; 
10 :         =        s        t2                ; 
11 :         goto     _L1                        ; 
12 :_L2                                          ; _L2($label,12)
13 :         ret      s                          ; 
14 :         endf                                ; 
15 :swap     function                            ; swap($fcall,)
16 :         param    a                          ; 
17 :         param    b                          ; 
18 :         =        t        a                 ; 
19 :         =        a        b                 ; 
20 :         =        b        t                 ; 
21 :         endf                                ; 
22 :main     function                            ; main($fcall,)
23 :         =        x        3                 ; 
24 :         =        y        5                 ; 
25 :         +        t3       x        y        ; 
26 :         >        t4       t3       6        ; 
27 :         if0      t4       _L5               ; 
28 :         =        z        0                 ; 
29 :_L5                                          ; _L5($label,29)
30 :         =        z        1                 ; 
31 :         =        i        0                 ; 
32 :         =        s        0                 ; 
33 :_L6                                          ; _L6($label,33)
34 :         <        t5       i        10       ; 
35 :         if0      t5       _L7               ; 
36 :         +        t6       s        i        ; 
37 :         =        s        t6                ; 
38 :         ++       i                          ; 
39 :         goto     _L6                        ; 
40 :_L7                                          ; _L7($label,40)
41 :         arg      10                         ; 
42 :         call     sum      t7                ; 
43 :         =        total    t7                ; 
44 :         arg      x                          ; 
45 :         arg      y                          ; 
46 :         call     swap     t8                ; 
47 :         endf                                ; 
======== pcodeRun() ========
22 :main     function                            ; 
23 :         =        x        3                 ; x(int,3)
24 :         =        y        5                 ; y(int,5)
25 :         +        t3       x        y        ; t3(int,8)
26 :         >        t4       t3       6        ; t4(int,1)
27 :         if0      t4       _L5               ; t4(int,1)
28 :         =        z        0                 ; z(int,0)
29 :_L5                                          ; 
30 :         =        z        1                 ; z(int,1)
31 :         =        i        0                 ; i(int,0)
32 :         =        s        0                 ; s(int,0)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,0)
37 :         =        s        t6                ; s(int,0)
38 :         ++       i                          ; i(int,1)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,1)
37 :         =        s        t6                ; s(int,1)
38 :         ++       i                          ; i(int,2)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,3)
37 :         =        s        t6                ; s(int,3)
38 :         ++       i                          ; i(int,3)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,6)
37 :         =        s        t6                ; s(int,6)
38 :         ++       i                          ; i(int,4)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,10)
37 :         =        s        t6                ; s(int,10)
38 :         ++       i                          ; i(int,5)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,15)
37 :         =        s        t6                ; s(int,15)
38 :         ++       i                          ; i(int,6)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,21)
37 :         =        s        t6                ; s(int,21)
38 :         ++       i                          ; i(int,7)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,28)
37 :         =        s        t6                ; s(int,28)
38 :         ++       i                          ; i(int,8)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,36)
37 :         =        s        t6                ; s(int,36)
38 :         ++       i                          ; i(int,9)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,1)
35 :         if0      t5       _L7               ; t5(int,1)
36 :         +        t6       s        i        ; t6(int,45)
37 :         =        s        t6                ; s(int,45)
38 :         ++       i                          ; i(int,10)
39 :         goto     _L6                        ; _L6($label,33)
33 :_L6                                          ; 
34 :         <        t5       i        10       ; t5(int,0)
35 :         if0      t5       _L7               ; t5(int,0)
40 :_L7                                          ; 
41 :         arg      10                         ; 10(int,10)
42 :         call     sum      t7                ; sum($fcall,)
2  :         param    n                          ; n(int,10)
3  :         =        s        0                 ; s(int,0)
4  :         =        i        0                 ; i(int,0)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,1)
9  :         +        t2       s        i        ; t2(int,1)
10 :         =        s        t2                ; s(int,1)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,2)
9  :         +        t2       s        i        ; t2(int,3)
10 :         =        s        t2                ; s(int,3)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,3)
9  :         +        t2       s        i        ; t2(int,6)
10 :         =        s        t2                ; s(int,6)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,4)
9  :         +        t2       s        i        ; t2(int,10)
10 :         =        s        t2                ; s(int,10)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,5)
9  :         +        t2       s        i        ; t2(int,15)
10 :         =        s        t2                ; s(int,15)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,6)
9  :         +        t2       s        i        ; t2(int,21)
10 :         =        s        t2                ; s(int,21)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,7)
9  :         +        t2       s        i        ; t2(int,28)
10 :         =        s        t2                ; s(int,28)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,8)
9  :         +        t2       s        i        ; t2(int,36)
10 :         =        s        t2                ; s(int,36)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,9)
9  :         +        t2       s        i        ; t2(int,45)
10 :         =        s        t2                ; s(int,45)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,1)
7  :         if0      t1       _L2               ; t1(int,1)
8  :         ++       i                          ; i(int,10)
9  :         +        t2       s        i        ; t2(int,55)
10 :         =        s        t2                ; s(int,55)
11 :         goto     _L1                        ; _L1($label,5)
5  :_L1                                          ; 
6  :         <        t1       i        n        ; t1(int,0)
7  :         if0      t1       _L2               ; t1(int,0)
12 :_L2                                          ; 
13 :         ret      s                          ; s(int,55)
43 :         =        total    t7                ; total(int,55)
44 :         arg      x                          ; x(int,3)
45 :         arg      y                          ; y(int,5)
46 :         call     swap     t8                ; swap($fcall,)
16 :         param    a                          ; a(int,5)
17 :         param    b                          ; b(int,3)
18 :         =        t        a                 ; t(int,5)
19 :         =        a        b                 ; a(int,3)
20 :         =        b        t                 ; b(int,5)
21 :         endf                                ; 
47 :

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License