#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 NIL -1
#define LEN 256
#define SYM_TABLE_MAX 1000
#define STR_TABLE_MAX 10000
#define SPACE " \t\n\r" // 空白字元
#define ALPHA "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" // 英文字母
#define DIGIT "0123456789" // 數字字元
#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) char var[LEN];strcpy(var, token);next(tags)
#define SYMBOL(var, id) char var[LEN];strcpy(var, symbol(id))
#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;
void debug(const char *fmt, ...) {
va_list args;
va_start(args, fmt);
vprintf(fmt, args);
}
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 symFind(char *sym) {
int i;
for (i=1; i<symTop; i++) {
if (strcmp(sym, symbol(i))==0)
return i;
}
return NIL;
}
int symPut(char *sym) {
int s = symFind(sym);
if (s == NIL) {
sprintf(&strTable[strTop], "%s", sym);
s = symTop++;
symTable[s] = strTop;
strTop += strlen(sym) + 1;
}
return s;
}
void symTableDump() {
int i;
printf("======= symTable ========\n");
for (i=1; i<symTop; i++) {
printf("sym[%d]=%s\n", i, symbol(i));
}
}
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 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 { // 其他符號，都解讀為單一字元
sprintf(tag, "%c", ch);
cnext(); // 傳回單一字元
}
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) {
SYMBOL(p, s); SYMBOL(p1, s1); SYMBOL(p2, s2);
printf("pcode:%s %s %s %s\n", op, p, p1, p2);
}
int F() {
int f;
push('F');
if (isNext("(")) {
next("(");
f = E();
next(")");
} else if (isNext(NUMBER)) {
NEXT(number, NUMBER);
int n = symPut(number);
f = nextTemp();
pcode("=", f, n, 0);
} else if (isNext(ID)) {
NEXT(id, ID);
f=symPut(id);
}
pop('F');
return f;
}
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 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 A() {
push('A');
NEXT(id, "ID");
next("=");
int e = E();
next(";");
pcode("=", symPut(id), e, 0);
pop('A');
}
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();
A();
symTableDump();
strTableDump();
fclose(file);
}
int main(int argc, char * argv[]) {
printf("=== EBNF Grammar =====\n");
printf("A=ID=E;\n");
printf("E=T ([+-] T)*\n");
printf("T=F ([*/] F)*\n");
printf("F=NUMBER | ID | '(' E ')'\n");
char *fname = argv[1];
printf("==== parse file:%s ========\n", fname);
compile(fname);
}
Post preview:
Close preview