CC0 編譯器

計算語言學

簡介

詞彙

語法

語意

理解

問題領域

語言生成

語法剖析

語意分析

處理方法

正規表達式

BNF 語法

掃描

剖析器

符號表

解譯

編譯

翻譯

各種語言

組合語言

程式語言

標記語言

維基語言

自然語言

中文

英文

程式實作

JavaScript

C

Python

相關書籍

自然語言處理

編譯器設計

系統程式

訊息

相關網站

參考文獻

最新修改

簡體版

English

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

// ================== 基本常數 ===================
#define FALSE   0
#define TRUE    1
#define BYTE    unsigned char
#define BOOL    unsigned char
#define INT32   long
#define INT16   short
#define INT8    char
#define UINT32  unsigned long
#define UINT16  unsigned short
#define UINT8   unsigned char

#define LEN 256

#define SYM_TABLE_MAX 1000
#define STR_TABLE_MAX 10000
#define SYM_NULL 0

#define SPACE " \t\n\r"     // 空白字元
#define ALPHA "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" // 英文字母
#define DIGIT "0123456789"    // 數字字元
#define SYMBOL "~!@#$%^&*()_+{}:<>?-=[]|\"\\;',./" // 符號字元
#define OP "+-*/%<=>!&|"        // 運算符號字元集 (用來取得 +,-,*,/, ++, ...)
#define STRING "STRING"
#define NUMBER "NUMBER"
#define FLOAT  "FLOAT"
#define ID     "ID"
#define END    "$END$"

#define cmember(ch, set) (strchr(set, ch) != NULL)// 測試字元 ch 是否在 set 當中
#define NEXT(var, tags) next(tags);char var[LEN];strcpy(var, token)
#define ASSERT(cond)     if (!(cond)) ERROR()  // 要求條件要成立,否則就算錯

// 錯誤報告巨集函數,會印出哪一行呼叫了 ERROR()
#define ERROR()    do { \
                  printf("ERROR => file:%s, line: %d\n", __FILE__, __LINE__);\
                  system("pause"); exit(1); \
                } while (1)

FILE *file;
char ch;
int line=1, pos=0;
char token[LEN], tag[LEN];
int  tokenIdx = 0;

int symTop = 1;
int symTable[SYM_TABLE_MAX];

char strTable[STR_TABLE_MAX];
int  strTop = 0;

// char *keywords[100] = {"+",   "-", "*", "/", "%",     ">>", "<<", "&", "|", "^", "&&", "||", "?", ".", "=", "<", ">", "==", "!=", "<=", ">=", "++", "--", "+=", "-=", "*=", "/=", "!", ",",  ";", "[", "]", "{", "}", "(", ")", "if", "else", "for", "while", "return", "int", "char", "void"};
// enum KEY              {ADD=0, SUB, MUL, DIV, PERCENT, SHR,  SHL,  AND, OR,  XOR, LAND, LOR,  QU,  DOT, SET, LT,  GT,  EQ,   NE,   LE,   GE,   ADD1, SUB1, ADDE, SUBE, MULE, DIVE, EX,  COMMA,SE,  OB,  CB,  OC,  CC,  OP,  CP,  IF,   ELSE,   FOR,   WHILE,   RETURN,   INT,   CHAR,   VOID};

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

int symPut(char *sym) {
    sprintf(&strTable[strTop], "%s", sym);
    symTable[symTop] = strTop;
    strTop += strlen(sym) + 1;
    return symTop++;
}

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

char symTemp[LEN];

char *symbol(int s) {
    if (s == 0)
        return "";
    else if (s > 0)
        return &strTable[symTable[s]];
    else { // s < 0; temp variable
        sprintf(symTemp, "t%d", -1*s);
        return symTemp;
    }
}
int tempIdx = -1;

int nextTemp() {
    return tempIdx--;
}

char stack[100];
int top = 0;

void printStack() {
    int i;
    for (i=0; i<top; i++)
        printf("%c", stack[i]);
    printf("\n");
}

int push(char c) {
    stack[top++] = c;
    printStack();
}

char pop(char c) {
    char ctop = stack[--top];
    printStack();
    ASSERT(ctop==c);
    return ctop;
}

// 功能:檢查 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 *tags) { // 檢查下一個詞彙的型態
    char tTags[LEN+1];
    sprintf(tTags, "|%s|", tags);
    if (strPartOf(tag, tTags))
        return TRUE;
    else
        return FALSE;
}

char cnext() {
    token[tokenIdx++]=ch;
    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, END);
        strcpy(tag, END);
        return;
    }
    tokenIdx = 0;
    if (ch == '\"') { // 如果是 " 代表字串開頭
        // 字串常數 : string = ".."
        cnext(); // 跳過 "
        while (ch != '\"') cnext(); // 一直讀到下一個 " 符號為止。
        cnext(); // 跳過 "
        strcpy(tag, STRING);
    } else if (cmember(ch, OP)) { // 如果是OP(+-*/<=>!等符號)
          // 運算符號 : OP = ++, --, <=, >=, ...
        while (cmember(ch, OP)) cnext(); // 一直讀到不是OP為止
        token[tokenIdx] = '\0';
        strcpy(tag, token);
    } else if (cmember(ch, DIGIT)) { // 如果是數字
           // 數字常數 : number = 312, 77568, ...
        while (cmember(ch, DIGIT)) cnext(); // 一直讀到不是數字為止
        strcpy(tag, NUMBER);
        // 浮點常數 : float = 3.14, ...
        if (ch == '.') {
            cnext(); // 取得小數點
            strcpy(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(); // 一直讀到不是英文字母 (或數字)為止
        strcpy(tag, ID);
    } else { // 其他符號,都解讀為單一字元
        cnext(); // 傳回單一字元
        sprintf(tag, "%c", ch);
    }
    token[tokenIdx] = '\0';
    printf("token=%s tag=%s\n", token, tag);
}

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

void pcode(char *op, int s, int s1, int s2) {
    printf("pcode:%s %s %s %s\n", op, symbol(s), symbol(s1), symbol(s2));
}

int E() {
    push('E');
    int t1 = T();
    while (isNext("+|-")) {
        NEXT(op, "+|-");
        int t2 = T();
        int t = nextTemp();
        pcode(op, t, t1, t2);
        t1 = t;
    }
    pop('E');
    return t1;
}

int T() {
    push('T');
    int f1 = F();
    while (isNext("*|/")) {
        NEXT(op, "*|/");
        int f2 = F();
        int f = nextTemp();
        pcode(op, f, f1, f2);
        f1 = f;
    }
    pop('T');
    return f1;
}

int F() {
    int f;
    push('F');
    if (isNext("(")) {
        next("(");
        f = E();
        next(")");
    } else {
        NEXT(number, NUMBER);
        int n = symPut(number);
        f = nextTemp();
        pcode("=", f, n, SYM_NULL);
    }
    pop('F');
    return f; 
}

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

int scan() {
    init();
    while (TRUE) {
        tnext();
        if (strcmp(token, END)==0)
            break;
        printf("%s\n", token);
    }
}

int compile(char *fname) {
    file = fopen(fname, "r");
    init();
//    scan();
    E();
    strTableDump();
    fclose(file);
}

int main(int argc, char * argv[]) {
    printf("=== EBNF Grammar =====\n");
    printf("E=T ([+-] T)*\n");
    printf("T=F ([*/] F)*\n");
    printf("F=N | '(' E ')'\n");
    char *fname = argv[1];
    printf("==== parse file:%s ========\n", fname);
    compile(fname);
}

Facebook

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