C1 語言的剖析器 -- CC1

CC1 編譯器

簡介

C1 語言

詞彙取得

語法規則

語法剖析

符號表

語意分析

中間碼

組合語言產生

訊息

相關網站

參考文獻

最新修改

簡體版

English

開放電腦計畫 — 最新版本下載

  1. ss1v0.50.zip — 包含虛擬機 VM1, 組譯器 AS1, 編譯器 CC1 (剖析器完成,符號表完成,程式碼產生修改中)

檔案:Parser.h

// 本軟體採用公共領域授權 (Public Domain License),您可以任意使用本軟體及其原始碼。 
// 但作者對於任何因本軟體所產生的損害(包含他人修改後所造成的損害),不負任何責任。
// 作者:陳鍾誠
 
// =============== C1 語言的 EBNF 語法規則  ================================== 
// PROG = (STRUCT | METHOD | DECL ; )*
// METHOD = TYPE ** ID(PARAM_LIST?) BLOCK
// STRUCT = struct ID { DECL_LIST ; }
// BLOCK = { BASE* }
// BASE = IF | FOR | WHILE | BLOCK | STMT ;
// IF = if (EXP) BASE (else BASE)?
// FOR = for (STMT ; EXP ; STMT) BASE
// WHILE = while (EXP) BASE
// STMT = return EXP | DECL | PATH (EXP_LIST) | PATH = EXP | PATH OP1
// VAR = ** ID ([ integer ])* (= EXP)?
// EXP = TERM (OP2 TERM)?
// TERM = ( EXP (OP2 EXP)? ) | CINT | CFLOAT | CSTR | PATH
// PATH = ATOM ((.|->) ATOM)*
// ATOM = ID (([ EXP ])* |( EXP_LIST? ))
// DECL = TYPE VAR_LIST
// PARAM = TYPE VAR
// VAR_LIST = VAR (, VAR)*
// EXP_LIST = EXP (, EXP)*
// DECL_LIST = DECL (; DECL)*
// PARAM_LIST = PARAM (, PARAM)*
// TYPE = (byte | char | int | float | ID) // 最後一個 ID 必須是 TYPE [STRUCT]
// ID = [A-Za-z_][0-9A-Za-z_]*
// CINT = [0-9]+
// CFLOAT = [0-9]+.[0-9]+
// CSTR = ".*"
// OP2 = +|-|/|*|%|&|&&|^|<<|>>|<|>|<=|>=|==|!=|  與 | , ||
// OP1 = ++ | --
 
#ifndef PARSER_H
#define PARSER_H
 
#include "Scanner.h"
#include "Tree.h"
#include "Lib.h"
#include "Semantic.h"
 
typedef struct {           // 剖析器的物件結構      
    Array *nodeStack;      // 剖析過程用的節點 node 堆疊 (從樹根到目前節點間的所有節點形成的堆疊)。 
    Array *blockStack;     // 符號區塊堆疊,變數 id 的區塊範圍,像是 PROG, STRUCT, METHOD, BLOCK 等。
    Var   decl;            // 在 parseType 時用來記住型態的變數。 
    Scanner *scanner;      // 詞彙掃描器 (Lexical Analysis)
    SymTable *symTable;    // 符號表 
    char  spaces[MAX_LEN]; // 用來暫存空白字串的變數。 
} Parser;                                                     
 
Tree *parse(char *text, SymTable *symTable);// 剖析器的主程式
Parser *ParserNew(Scanner *scanner, SymTable *symTable); // 剖析器的建構函數
Tree *ParserParse(Parser *p, char *text);   // 剖析器的剖析函數
void ParserFree(Parser *parser);           // 釋放記憶體
 
Tree* parseProg(Parser *p);     // PROG = (STRUCT | METHOD | DECL ; )*
Tree* parseBase(Parser *p);     // BASE = IF | FOR | WHILE | BLOCK | STMT ;
Tree* parseStruct(Parser *p);   // STRUCT = struct ID { DECL_LIST ; }
Tree* parseMethod(Parser *p);   // METHOD = TYPE ** ID(PARAM_LIST?) BLOCK
Tree* parseDecl(Parser *p);     // DECL = TYPE VAR_LIST
Tree* parseIf(Parser *p);       // IF = if (EXP) BASE (else BASE)?
Tree* parseFor(Parser *p);      // FOR = for (STMT ; EXP ; STMT) BASE
Tree* parseWhile(Parser *p);    // WHILE = while (EXP) BASE
Tree* parseStmt(Parser *p);     // STMT = return EXP | DECL | PATH (EXP_LIST) | PATH = EXP | PATH OP1
Tree* parseBlock(Parser *p);    // BLOCK = { BASE* }
Tree* parseVar(Parser *p);      // VAR = ** ID ([ integer ])* (= EXP)?
Tree* parseExp(Parser *p);      // EXP = TERM (OP2 TERM)?
Tree* parseTerm(Parser *p);     // TERM = ( EXP (OP2 EXP)? ) | CINT | CFLOAT | CSTR | PATH
Tree* parsePath(Parser *p);     // PATH = ATOM ((.|->) ATOM)*
Tree* parseAtom(Parser *p);     // ATOM = ID (([ EXP ])* |( EXP_LIST? ))
Tree* parseDecl(Parser *p);     // DECL = TYPE VAR_LIST
Tree* parseParam(Parser *p);    // PARAM = TYPE VAR
Tree* parseVarList(Parser *p);  // VAR_LIST = VAR (, VAR)*
Tree* parseExpList(Parser *p);  // EXP_LIST = EXP (, EXP)*
Tree* parseDeclList(Parser *p); // DECL_LIST = DECL (; DECL)*
Tree* parseParamList(Parser *p);// PARAM_LIST = PARAM (, PARAM)*
Tree* parseType(Parser *p);     // TYPE = (byte | char | int | float | ID)
Tree* parseId(Parser *p);       // ID = [A-Za-z_][0-9A-Za-z_]*
 
BOOL isMethod(Parser *p); // 判斷接下來是否為 METHOD 程式區塊。 
BOOL isDecl(Parser *p);  // 判斷接下來是否為 DECL 宣告語句 
// push() : 功能:建立 tag 標記的非終端節點,並建立語意結構,然後推入堆疊中 
//          範例:Tree *node = push(p, IF, SemIF);
#define push(p, tag, SemType) sem=ObjNew(SemType, 1);Tree *node=push1(p, tag);node->sem=sem; 
Tree *push1(Parser *p, char* tag);  // 建立標記為 tag 的新子樹。 
Tree *pop(Parser *p, char* tag);    // 從堆疊中取出剖析完成的子樹,並檢查標記是否為 tag。 
BOOL isNext(Parser *p, char *tags); // 檢查下一個 token 的 tag 是否屬於 tags 標記之一。 
Tree *next(Parser *p, char *tags);  // 取得下一個 token,並確認其 tag 為 tags 標記之一。 
char *token(Tree *node);            // 取得樹葉節點 node 的 token。 
 
void pushBlock(Parser *p, Symbol *sym); // 將區塊符號推入堆疊 
#define popBlock(p) ArrayPop(p->blockStack) // 從堆疊取出區塊符號 
#define peekBlock(p) ArrayPeek(p->blockStack) // 取得最上面的區塊符號 
 
// Token 的集合,用來檢查是關鍵字,運算元,基本型態,或者只是變數 ID。 
#define SET_KEYWORDS "|if|else|for|while|return|def|int|byte|char|float|struct|"
#define SET_OP1 "|++|--|"
#define SET_OP2 "|+|-|*|/|%|^|&|<<|>>|==|!=|<=|>=|<|>|&&||||"
#define SET_BTYPE "|int|byte|char|float|"
 
#endif

檔案:Parser.c

// 本軟體採用公共領域授權 (Public Domain License),您可以任意使用本軟體及其原始碼。 
// 但作者對於任何因本軟體所產生的損害(包含他人修改後所造成的損害),不負任何責任。
// 作者:陳鍾誠
 
#include "Parser.h"
 
// 功能:Parser 剖析階段的測試程式。
// 範例:ParserTest("test.c1");
void ParserTest(char *fileName) {
    debug("=======ParserTest()==========\n");
    SymTable *symTable = SymTableNew(); // 建立符號表 
    char *text = fileToStr(fileName);   // 讀入 C1 語言程式碼,成為一字串 
    Tree *tree = parse(text, symTable); // 剖析該程式碼,建立剖析樹與符號表。 
    SymTableDebug(symTable);            // 印出符號表。 
    TreeFree(tree);                     // 釋放剖析樹。 
    strFree(text);                      // 釋放程式碼字串 
    SymTableFree(symTable);             // 釋放符號表 
    memCheck();                         // 檢查記憶體
}
 
// 功能:剖析階段的主程式 
// 範例:Tree *tree = parse(text, symTable); 
Tree *parse(char *text, SymTable *symTable) {  // 剖析器的主要函數
    Scanner *scanner = ScannerNew(text);       // 建立掃描器 (詞彙分析用) 
    Parser *p=ParserNew(scanner, symTable);    // 建立剖析器 (語法剖析用)
    Tree *tree = ParserParse(p, text);         // 剖析程式為語法樹 
    ParserFree(p);                             // 釋放頗析樹 
    ScannerFree(scanner);                      // 釋放掃描器 
    return tree;                               // 傳回剖析器
}
 
// 功能:建立新的剖析器 Parser 物件 
// 範例:Parser *p = ParserNew(scanner, symTable);
Parser *ParserNew(Scanner *scanner, SymTable *symTable) {
    Parser *p = ObjNew(Parser, 1); // 分配剖析器空間 
    p->nodeStack = ArrayNew(10); // 分配 nodeStack 堆疊空間 
    p->blockStack = ArrayNew(10); // 分配 blockStack 堆疊空間 
    p->scanner = scanner; // 設定掃瞄器 
    p->symTable = symTable; // 設定符號表 
    ScannerNext(scanner); // 本剖析器總是先取得下一個 token,以便 isNext() 進行判斷。
    return p;
}
 
// 功能:釋放剖析器物件的記憶體 
// 範例:ParserFree(p); 
void ParserFree(Parser *p) {
    ArrayFree(p->blockStack, (FuncPtr1) BlockFree);  // 釋放 blockStack 堆疊空間 
    ArrayFree(p->nodeStack, NULL); // 釋放 nodeStack 堆疊空間 
    ObjFree(p); // 釋放剖析器空間
}
 
// 功能:剖析整個程式碼 (text)。 
// 範例:ParserParse(p, text); 
Tree *ParserParse(Parser *p, char *text) { // 剖析物件的主函數
    debug("======= parsing ========\n");
    Tree *tree = parseProg(p); // 開始剖析整個程式 (PROG),並建立語法樹 p->tree
    if (p->nodeStack->count != 0) { // 如果剖析完成後堆疊是空的,那就是剖析成功
        ERROR();// 否則就是剖析失敗,有語法錯誤
    }
    return tree;
}
 
// 語法:PROG = (STRUCT | METHOD | DECL ; )* 
// 功能:剖析 PROG 並建立語法樹 
// 範例:Tree *prog = parseProg(p); 
Tree *parseProg(Parser *p) { // 剖析 PROG 規則
    SemProg *sem=push(p, PROG, SemProg); // 建立 PROG 的語法樹及語意結構
    pushBlock(p, Global);  // 推入全域區塊 
    while (!isNext(p, kEND)) {     //  剖析 BASE,直到程式結束或碰到 } 為止
        if (isNext(p, "struct"))
           parseStruct(p);
        else { // 由於 METHOD 與 DECL 的開頭都是 TYPE **ID ...,因此必須判斷是哪一種情況。
           if (isMethod(p)) { // 向前偷看後發現是 TYPE **ID(,所以是 Method 
                parseMethod(p);
           } else { // 否則就必須是 DECL ; 
                parseDecl(p);
                next(p, ";");
          }
        }
    }
    popBlock(p); // 取出全域區塊
    return pop(p, PROG); // 取出 PROG 的整棵語法樹 
}
 
// 語法:METHOD = TYPE **ID (PARAM_LIST?) BLOCK
// 功能:判斷到底接下來是否為 METHOD,是的話傳回 TRUE,否則傳回 FALSE 
//       由於 METHOD 與 DECL 的開頭都是 TYPE **ID ...,因此必須判斷是哪一種情況。
//       本函數會向前偷看,如果發現是 TYPE **ID(,那就應該是 Method。 
// 範例:if (isMethod(p)) parseMethod(p);
BOOL isMethod(Parser *p) {
    BOOL rzFlag = TRUE;
    Scanner *s = p->scanner; // s=掃描器 
    ScannerStore(s); // 儲存掃描器狀態 
    if (isNext(p, "int|byte|char|float|ID")) // 偷看 TYPE
        ScannerNext(s); // 略過 TYPE
    else 
        rzFlag=FALSE;
    while (isNext(p, "*")) ScannerNext(s); // 偷看並略過星號 
    if (isNext(p, ID))  // 偷看 ID
        ScannerNext(s); // 略過 ID 
    else 
        rzFlag=FALSE;
    if (!isNext(p, "(")) rzFlag=FALSE; // 如果接下來是 (,那麼就應該是 Method。
    ScannerRestore(s); // 恢復掃描器狀態。 
    return rzFlag;
}
 
// 語法:METHOD = TYPE **ID (PARAM_LIST?) BLOCK
// 功能:剖析 METHOD 並建立語法樹
// 範例:Tree *method = parseMethod(p); 
Tree* parseMethod(Parser *p) {
    SemMethod *sem=push(p, METHOD, SemMethod); // 建立 METHOD 的語法樹及語意結構
    sem->type=parseType(p); // 剖析 TYPE
 
    // 剖析 ** (n 個星號, n>=0)
    int starCount = 0; // 星號數量的初始值 
    while (isNext(p, "*")) { // 如果下一個是星號 
        next(p, "*"); // 取得該星號 
        starCount ++; // 將星號數加一 
    }
    sem->id = next(p, ID); // 剖析 ID
 
    // 建立 ID 的符號記錄 Symbol(id, METHOD) 
    char *id = token(sem->id);    // 取得符號名稱。 
    Symbol *sym = SymNew(Global, id, SymMethod); // 建立符號記錄 
    Method *method = sym->typePtr; // 設定 method 結構。 
    method->ret.typeSym = p->decl.typeSym; // 設定傳回符號 
    method->ret.starCount = p->decl.starCount; // 設定傳回符號的星號個數。 
    SymTablePut(p->symTable, sym); // 將符號記錄放入符號表中 
 
    pushBlock(p, sym); // 將 Method 符號推入區塊堆疊
 
    sem->symMethod = sym; // 設定語意結構 sem 的 symMethod 欄位 
 
    // 剖析參數部分 (PARAM_LIST?) 
    next(p, "(");
    if (!isNext(p, ")")) // 如果接下來不是 ),那就是有 PARAM_LIST 
        sem->paramList = parseParamList(p); // 剖析 PARAM_LIST
    next(p, ")");
 
    sem->block = parseBlock(p); // 剖析 BLOCK
 
    popBlock(p);
    return pop(p, METHOD); // 取出 METHOD 的語法樹。
}
 
// 語法:STRUCT = struct ID { (DECL ;)* }
// 功能:剖析 STRUCT 並建立語法樹
// 範例:Tree *s = parseStruct(p);
Tree* parseStruct(Parser *p) {
    SemStruct *sem=push(p, STRUCT, SemStruct); // 建立 STRUCT 語法樹 
 
    next(p, "struct"); // 剖析 struct 
    sem->id = next(p, ID); // 剖析 ID
 
    // 建立 ID 的符號記錄 Symbol(id, METHOD) 
    char *id = token(sem->id);    // 取得符號名稱。 
    Symbol *sym = SymNew(Global, id, SymStruct); // 建立符號 -- 結構。 
    SymTablePut(p->symTable, sym); // 放入符號表。 
 
    sem->symStruct = sym;  // 設定語意結構 sem 的 symMethod 欄位 
 
    pushBlock(p, sym); // 將 Struct 區塊推入堆疊
 
    // 剖析 { (DECL ;)* }
    next(p, "{"); 
    while (!isNext(p, "}")) {
        parseDecl(p);
        next(p, ";");
    }
    next(p, "}");
 
    popBlock(p); // 從區塊堆疊中取出 Struct 區塊 
 
    return pop(p, STRUCT); // 取出 STRUCT 的語法樹。
}
 
// 語法:BASE = IF | FOR | WHILE | BLOCK | STMT ;
// 功能:剖析 BASE 並建立 BASE 的語法樹 
// 範例:Tree *base = parseBase(p); 
Tree* parseBase(Parser *p) { // 剖析 BASE 規則
    SemBase *sem=push(p, BASE, SemBase); // 建立 BASE 的語法樹及語意結構
    if (isNext(p, "if")) // 如果下一個詞彙是 if
        parseIf(p); // 剖析 IF 程式段 
    else if (isNext(p, "for")) // 如果下一個詞彙是 for
        parseFor(p); // 剖析 FOR 程式段
    else if (isNext(p, "while")) // 如果下一個詞彙是 for
        parseWhile(p); // 剖析 WHILE 程式段
    else if (isNext(p, "{")) // 如果下一個詞彙是 {
        parseBlock(p); // 剖析 BLOCK 程式段
    else { // 否則應該是 STMT ; 
        parseStmt(p); // 剖析 STMT 程式段
        next(p, ";"); // 取得分號 ;  
    }
    return pop(p, BASE); // 取出 BASE 的剖析樹
}
 
// 語法:BLOCK = { BASE* }
// 功能:剖析 BLOCK 並建立語法樹 
// 範例:Tree *block = parseBlock(p); 
Tree* parseBlock(Parser *p) {
    SemBlock *sem=push(p, BLOCK, SemBlock); // 建立 BLOCK 的語法樹及語意結構 
 
    Symbol *pblock = peekBlock(p); // 取得父區塊 
    Symbol *sym = SymNew(pblock, "", SymBlock); // 建立區塊符號 
    Block *block = sym->typePtr; // 設定 block 結構。 
    SymTablePut(p->symTable, sym); // 將本區塊加入到符號表中 
 
    sem->symBlock = sym; // 設定本節點的語意結構 symBlock 為本區塊
 
    pushBlock(p, sym); // 將符號推入區塊堆疊
 
    next(p, "{"); // 剖析 { BASE* } 
    while (!isNext(p, "}")) 
        parseBase(p);
    next(p, "}");
 
    popBlock(p);  // 從區塊堆疊中取出 Block 區塊
 
    return pop(p, BLOCK); // 取出 BLOCK 的語法樹。
}
 
// 語法:FOR = for (STMT ; EXP ; STMT) BASE
// 功能:剖析 FOR 並建立語法樹
// 範例:Tree *f = parseFor(p); 
Tree* parseFor(Parser *p) {                  
    SemFor *sem=push(p, FOR, SemFor); // 建立 FOR 的語法樹及語意結構
    next(p, "for");                   // 取得 for
    next(p, "(");                     // 取得 (
    sem->stmt1 = parseStmt(p);        // 剖析 STMT
    next(p, ";");                     // 取得 ;
    sem->exp = parseExp(p);           // 剖析 EXP
    next(p, ";");                     // 取得 ;
    sem->stmt2 = parseStmt(p);        // 剖析 STMT
    next(p, ")");                     // 取得 )
    parseBase(p);                     // 剖析 BASE
    return pop(p, FOR);               // 取出 FOR 的語法樹。
}
 
// 語法:IF = if (EXP) BASE (else BASE)?
// 功能:剖析 IF 並建立語法樹
// 範例:Tree *f = parseIf(p);
Tree* parseIf(Parser *p) {
    SemIf *sem=push(p, IF, SemIf);     // 建立 IF 的語法樹及語意結構
    next(p, "if");                     // 取得 if
    next(p, "(");                      // 取得 (
    sem->exp = parseExp(p);            // 剖析 EXP 
    next(p, ")");                      // 取得 )
    sem->base1 = parseBase(p);         // 剖析 BASE
    if (isNext(p, "else")) {           // 如果下一個是 else 
        next(p, "else");               // 取得 else
        sem->base2 = parseBase(p);     // 剖析下一個 BASE
    }
    return pop(p, IF);                 // 取出 IF 的語法樹。
}
 
// 語法:WHILE = while (EXP) BASE
// 功能:剖析 WHILE 並建立語法樹
// 範例:Tree *w = parseWhile(p);
Tree* parseWhile(Parser *p) {
    SemWhile *sem=push(p, WHILE, SemWhile);// 建立 WHILE 的語法樹及語意結構
    next(p, "while");                      // 取得 while
    next(p, "(");                          // 取得 (
    sem->exp = parseExp(p);                // 剖析 EXP
    next(p, ")");                          // 取得 )
    sem->base = parseBase(p);              // 剖析 BASE
    return pop(p, WHILE);                  // 取出 WHILE 的語法樹。
}
 
// 語法:STMT = return EXP | DECL | PATH (EXP_LIST) | PATH = EXP | PATH OP1
// 功能:剖析 STMT 並建立語法樹
// 範例:Tree *stmt = parseStmt(p); 
Tree* parseStmt(Parser *p) {
    SemStmt *sem=push(p, STMT, SemStmt);// 建立 STMT 的語法樹及語意結構
    if (isNext(p, "return")) { // 如果下一個是 return,就剖析 return EXP 
        next(p, "return");
        sem->exp = parseExp(p);
    } else if (isDecl(p)) { // 如果是 DECL 
        sem->decl = parseDecl(p); // 剖析 DECL 
    } else { // 否則下一個必須是 PATH 
        sem->path = parsePath(p); // 剖析 PATH 
        if (isNext(p, "(")) { // 下一個是 (,代表是 PATH (EXP_LIST) 的情況 
            next(p, "(");
            sem->expList = parseExpList(p);
            next(p, ")");
        } else if (isNext(p, "=")) { // 下一個是 =,代表是 PATH = EXP 的情況 
            next(p, "=");
            sem->exp = parseExp(p);
        } else if (isNext(p, SET_OP1)) { // 下一個是OP1,代表是 PATH OP1 的情況 
            next(p, SET_OP1);
        } else
            ERROR();
    }
    return pop(p, STMT); // 取出 STMT 的語法樹。
}
 
// 語法:PATH = ATOM ((.|->) ATOM)*
// 功能:剖析 PATH 並建立語法樹 
// 範例:Tree *path = parsePath(p);
Tree* parsePath(Parser *p) {
    SemPath *sem=push(p, PATH, SemPath);// 建立 PATH 的語法樹及語意結構
    parseAtom(p);                       // 剖析 DECL 
    while (isNext(p, ".|->")) {         // 不斷取得 (.|->) ATOM
        next(p, ".|->");
        parseAtom(p);
    }
    return pop(p, PATH);                // 取出 PATH 的語法樹。
}
 
// 語法:ATOM = ID (([ EXP ])* |( EXP_LIST? ))
// 功能:剖析 ATOM 並建立語法樹
// 範例:Tree *atom = parseAtom(p); 
Tree* parseAtom(Parser *p) {
    SemAtom *sem=push(p, ATOM, SemAtom); // 建立 ATOM 的語法樹及語意結構
    sem->id = next(p, ID); // 取得 ID
    sem->subTag = ID; // 設定子標籤 (ID, CALL 或 ARRAY_MEMBER),讓語義分析與程式產生時使用
    if (isNext(p, "(")) { // 如果接下來是 (,則應該是函數呼叫 ID ( EXP_LIST? )
       next(p, "(");
       if (!isNext(p, ")"))
           sem->expList = parseExpList(p);
       next(p, ")");
       sem->subTag = CALL;
    } else if (isNext(p, "[")) { // 如果接下來是 [,則應該是陣列宣告 ID ([ EXP ])*
        sem->subTag = ARRAY_MEMBER;
        while (isNext(p, "[")) {
            next(p, "[");
            Tree *exp = parseExp(p);
            next(p, "]");
        }
    }
    return pop(p, ATOM); // 取出 ATOM 的語法樹。
}
 
// 語法:PARAM = TYPE VAR
// 功能:剖析 PARAM 並建立語法樹
// 範例:Tree *param = parseParam(p); 
Tree* parseParam(Parser *p) {
    SemParam *sem = push(p, PARAM, SemParam);// 建立 PARAM 的語法樹及語意結構
    sem->type = parseType(p); // 剖析 TYPE
    sem->var = parseVar(p); // 剖析 VAR
    return pop(p, PARAM); // 取出 PARAM 的語法樹。
}
 
// 語法:DECL = TYPE VAR_LIST
// 功能:判斷到底接下來是否為 DECL,是的話傳回 TRUE,否則傳回 FALSE 
//       本函數會向前偷看,如果發現是 (int|byte|char|float|ID)** ID,那就是 DECL
// 範例:if (isDecl(p)) parseDecl(p);
BOOL isDecl(Parser *p) {
    BOOL rzFlag = TRUE;
    Scanner *s = p->scanner;                // s=掃描器 
    ScannerStore(s);                        // 儲存掃描器狀態 
    if (isNext(p, "int|byte|char|float|ID"))// 偷看 TYPE
        ScannerNext(s);                     // 略過 TYPE
    else 
        rzFlag=FALSE;
    while (isNext(p, "*")) ScannerNext(s);  // 偷看並略過星號 
    if (!isNext(p, ID)) rzFlag=FALSE;       // 偷看 ID
    ScannerRestore(s);                      // 恢復掃描器狀態。 
    return rzFlag;
}
 
// 語法:DECL = TYPE VAR_LIST
// 功能:剖析 PROG 並建立語法樹 
// 範例:Tree *decl = parseDecl(p);
Tree* parseDecl(Parser *p) {
    SemDecl *sem = push(p, DECL, SemDecl);// 建立 DECL 的語法樹及語意結構
    sem->type = parseType(p); // 剖析 TYPE
    sem->varList = parseVarList(p); // 剖析 VAR_LIST
    return pop(p, DECL); // 取出 DECL 的語法樹。
}
 
// 語法:TYPE = (int | byte | char | float | ID) // ID is STRUCT_TYPE
// 功能:剖析 TYPE 並建立語法樹
// 範例:Tree *type = parseType(p); 
Tree* parseType(Parser *p) {
    SemType *sem=push(p, TYPE, SemType);// 建立 TYPE 的語法樹及語意結構
    Tree *type = next(p, "int|byte|char|float|ID");  // 取得 (int | byte | char | float | ID)
    char *typeName = token(type); // 取得型態名稱 
       p->decl.typeSym = SymTableGet(p->symTable, Global, typeName); // 從符號表中查出該型態的符號
       ASSERT(p->decl.typeSym != NULL);
    return pop(p, TYPE); // 取出 TYPE 的語法樹。
}
 
// 語法:VAR = ** ID ([ CINT ])* (= EXP)?
// 功能:剖析 VAR 並建立語法樹
// 範例:Tree *var = parseVar(p); 
Tree* parseVar(Parser *p) {
    SemVar *sem = push(p, VAR, SemVar);    // 建立 VAR 的語法樹及語意結構
    int starCount = 0; // 星號數量初始值為 0 
    while (isNext(p, "*")) { // 剖析 ** 
        next(p, "*"); // 取得星號 
        starCount ++; // 計算星號數量 
    }
    sem->id = next(p, ID); // 剖析 ID
 
    // 建立 ID 的符號記錄 Symbol(id, SymVar)
    Symbol *pblock = peekBlock(p); // 取得父區塊符號 
    char *id = token(sem->id); // 取得變數名稱 
    Symbol *sym = SymNew(pblock, id, SymVar); // 建立變數符號 
    Var *var = sym->typePtr; // 取出變數結構 
    var->starCount = starCount; // 設定變數結構中的星號數量 
    var->typeSym = p->decl.typeSym; // 設定變數結構中的符號 
    var->dimCount = 0;  // 設定變數結構中的陣列維度 
    SymTablePut(p->symTable, sym); // 將變數加入符號表中 
 
    while (isNext(p, "[")) { // 剖析 ([ CINT ])*
        next(p, "[");
        Tree *cint = next(p, "CINT");
        ASSERT(var->dimCount<DIM_MAX);
        var->dim[var->dimCount++] = atoi(token(cint));
        next(p, "]");
    }
 
    if (pblock->symType == SymStruct) { // 如果父區塊是 Struct,那此 VAR 就是欄位宣告。 
        Struct *stru = pblock->typePtr;
        ArrayAdd(stru->fields, sym); // 將變數加入 Struct 的欄位 fields 中。 
    } else if (pblock->symType == SymMethod) { // 如果父區塊是 Method,那此 VAR 就是參數宣告。 
        Method *method = pblock->typePtr;
        ArrayAdd(method->params, sym); // 將變數加入 Method 的參數 params 中。 
    } else if (pblock->symType == SymBlock) { // 如果父區塊是 Block,那此 VAR 就是區域變數。
        Block *block = pblock->typePtr;
        ArrayAdd(block->vars, sym);// 將變數加入 Block 的區域變數 vars 中。 
    }
 
    if (isNext(p, "=")) { // 剖析 (= EXP)?
        next(p, "=");
        sem->exp = parseExp(p);
    }
    return pop(p, VAR);  // 取出 VAR 的語法樹。
}
 
// 語法:EXP = TERM (OP2 TERM)?
// 功能:剖析 EXP 並建立語法樹
// 範例:Tree *exp = parseExp(p); 
Tree* parseExp(Parser *p) {
    SemExp *sem = push(p, EXP, SemExp);// 建立 EXP 的語法樹及語意結構
    sem->term1 = parseTerm(p); // 剖析 TERM 
    if (isNext(p, SET_OP2)) { // 如果接下來是 OP2 ,則剖析 (OP2 TERM)?
        sem->op = next(p, SET_OP2);
        sem->term2 = parseTerm(p);
    }
    return pop(p, EXP); // 取出 EXP 的語法樹。
}
 
// 語法:TERM = ( EXP (OP2 EXP)? ) | CINT | CFLOAT | CSTR | PATH
// 功能:剖析 TERM 並建立語法樹
// 範例:Tree *term = parseTerm(p); 
Tree* parseTerm(Parser *p) {
    SemTerm *sem = push(p, TERM, SemTerm);// 建立 TERM 的語法樹及語意結構
    if (isNext(p, "(")) { // 如果下一個是 (,那就是 ( EXP (OP2 EXP)? ) 的情況 
        next(p, "(");
        sem->exp1 = parseExp(p);
        if (!isNext(p, ")")) { // 看看是否有 (OP2 EXP)
            next(p, SET_OP2);
            sem->exp2 = parseExp(p);
        }
        next(p, ")");
    } else if (isNext(p, "CINT|CFLOAT|CSTR")) { // 如果是 CINT, CFLOAT 或 CSTR 
        next(p, "CINT|CFLOAT|CSTR"); // 取得 CINT, CFLOAT 或 CSTR 
    } else
        parsePath(p); // 否則應該是 PATH,剖析之 
    return pop(p, TERM); // 取出 TERM 的語法樹。
}
 
// 語法:VAR_LIST = VAR (, VAR)*
// 功能:剖析 VarList 並建立語法樹
// 範例:Tree *varList = parseVarList(p); 
Tree* parseVarList(Parser *p) {
    SemVarList *sem = push(p, VAR_LIST, SemVarList);// 建立 VAR_LIST 的語法樹及語意結構
    parseVar(p); // 剖析 VAR 
    while (isNext(p, ",")) { // 剖析 (,VAR)* 
        next(p, ",");
        parseVar(p);
    }
    return pop(p, VAR_LIST); // 取出 VAR_LIST 的語法樹。
}
 
// 語法:EXP_LIST = EXP (, EXP)*
// 功能:剖析 EXP_LIST 並建立語法樹
// 範例:Tree *expList = parseExpList(p); 
Tree* parseExpList(Parser *p) {
    SemExpList *sem = push(p, EXP_LIST, SemExpList);// 建立 EXP_LIST 的語法樹及語意結構
    parseExp(p); // 剖析 EXP
    while (isNext(p, ",")) { // 剖析 (, EXP)*
        next(p, ",");
        parseExp(p);
    }
    return pop(p, EXP_LIST); // 取出 EXP_LIST 的語法樹。
}
 
// 語法:DECL_LIST = DECL (; DECL)*
// 功能:剖析 DECL_LIST 並建立語法樹
// 範例:Tree *declList = parseDeclList(p); 
Tree* parseDeclList(Parser *p) {
    SemDeclList *sem=push(p, DECL_LIST, SemDeclList);// 建立 DECL_LIST 的語法樹及語意結構
    parseDecl(p); // 剖析 DECL
    while (isNext(p, ";")) { // 剖析 (; DECL)*
        next(p, ";");
           parseDecl(p);
    }
    return pop(p, DECL_LIST); // 取出 DECL_LIST 的語法樹。
}
 
// 語法:PARAM_LIST = PARAM (, PARAM)*
// 功能:剖析 PARAM_LIST 並建立語法樹
// 範例:Tree *paramList = parseParamList(p); 
Tree* parseParamList(Parser *p) {
    SemParamList *sem=push(p, PARAM_LIST, SemParamList);// 建立 PARAM_LIST 的語法樹及語意結構
    parseParam(p); // 剖析 PARAM
    while (isNext(p, ";")) { // 剖析 (, PARAM)*
        next(p, ";");
           parseParam(p);
    }
    return pop(p, PARAM_LIST); // 取出 PARAM_LIST 的語法樹。
}
 
// ========================== 基本函數 ====================================
// 功能:取得 p->nodeStack->count 個空白, 以便印出剖析樹時能有階層式的排版。 
// 範例:debug("%s KEY:%s\n", level(p), s->tag);
char* level(Parser *p) {
    return strFill(p->spaces, ' ', p->nodeStack->count);
}
 
// 功能:判斷下一個 token 的標記是否為 tags 其中之一
// 範例:if (isNext(p, "struct")) parseStruct(p);
BOOL isNext(Parser *p, char *tags) { // 檢查下一個詞彙的型態
    Scanner *s = p->scanner;
    char tTags[MAX_LEN+1];
    sprintf(tTags, "|%s|", tags);
    if (strPartOf(s->tag, tTags))
        return TRUE;
    else
        return FALSE;
}
 
// 功能:取得下一個 token (標記必須為 tag 其中之一),然後掛到剖析樹上 
// 範例:Tree *node = next(p, "CINT|CFLOAT|CSTR");
Tree *next(Parser *p, char *tags) { // 檢查下一個詞彙的型態
    Scanner *s = p->scanner;
    if (isNext(p, tags)) { // 如果是pTypes型態之一
        Tree *child = TreeNew(s->tag);
        child->sem = strNew(s->token);  // 建立詞彙節點(token,type)
        Tree *parentTree = ArrayPeek(p->nodeStack); // 取得父節點,
        TreeAddChild(parentTree, child); // 加入父節點成為子樹
        if (strEqual(s->tag, s->token))
           debug("%s KEY:%s\n", level(p), s->tag);
        else
           debug("%s %s:%s\n", level(p), s->tag, s->token);
        ScannerNext(s);
        return child; // 傳回該詞彙
    } else { // 否則(下一個節點型態錯誤)
        debug("next():token=%s, tag=%s is not in tag(%s)\n", s->token, s->tag, tags); // 印出錯誤訊息
        ERROR();
        return NULL;
    }
}
 
// 功能:建立 tag 標記的非終端節點,並且推入堆疊中 
// 範例:Tree *node = push1(p, IF);
Tree* push1(Parser *p, char* tag) { // 建立 pType 型態的子樹,推入堆疊中
    debug("%s+%s\n", level(p), tag);
    Tree *node = TreeNew(tag);
    ArrayPush(p->nodeStack, node);
    return node;
}
 
// 功能:取出 tag 標記的非終端節點,然後掛到剖析樹上 
// 範例:Tree *node = pop(p, IF);
Tree* pop(Parser *p, char* tag) { // 取出 pTag 標記的子樹
    Tree *tree = ArrayPop(p->nodeStack); // 取得堆疊最上層的子樹
    debug("%s-%s\n", level(p), tree->tag); // 印出以便觀察
    if (strcmp(tree->tag, tag)!=0) {  // 如果型態不符合
        debug("pop(%s):should be %s\n",tree->tag, tag); //  印出錯誤訊息
        ERROR();
    }
    if (p->nodeStack->count > 0) { // 如果堆疊不是空的
      Tree *parentTree = ArrayPeek(p->nodeStack); //  取出上一層剖析樹
      TreeAddChild(parentTree, tree);  //  將建構完成的剖析樹掛到樹上,成為子樹
    }
    return tree;
}
 
// 功能:取得樹葉節點中的詞彙 (token) 
// 範例:char *token = token(node);
char *token(Tree *node) {
    return (char*) node->sem;
}
 
// 功能:將區塊符號 sym 推入區塊堆疊中 
// 範例:pushBlock(p, sym);
void pushBlock(Parser *p, Symbol *sym) {
    ArrayPush(p->blockStack, sym);
}

測試輸入程式:被剖析者 — test.c1

int x=1, y=2;
 
struct Date {
    int year, month, day;
}
 
struct Person {
    char *name;
    Date birthday;
}
 
int total(int* a) {
    int s = 0;
    for (int i=0; i<10; i++)
        s = s+a[i];
    return s;
}
 
char* getName(Person *p) {
    return p->name;
}
 
int main() {
    int b[10], a=3;
    int t = total(b);
    Person p;
    p.birthday.year = 1990;
    t = 3 + (5 * a);
    return t;
}

剖析器的輸出結果

======= parsing ========
+PROG
 +DECL
  +TYPE
    KEY:int
  -TYPE
  +VAR_LIST
   +VAR
     ID:x
V    x        0    003E2558 0040A340 int:*0:[0]      
     KEY:=
    +EXP
     +TERM
       CINT:1
     -TERM
    -EXP
   -VAR
    KEY:,
   +VAR
     ID:y
V    y        0    003E6590 0040A340 int:*0:[0]      
     KEY:=
    +EXP
     +TERM
       CINT:2
     -TERM
    -EXP
   -VAR
  -VAR_LIST
 -DECL
  KEY:;
 +STRUCT
   KEY:struct
   ID:Date
S    Date     0    003E6830 0040A340 
   KEY:{
  +DECL
   +TYPE
     KEY:int
   -TYPE
   +VAR_LIST
    +VAR
      ID:year
V    year     0    003E6A80 003E6830 int:*0:[0]      
    -VAR
     KEY:,
    +VAR
      ID:month
V    month    0    003E6BD8 003E6830 int:*0:[0]      
    -VAR
     KEY:,
    +VAR
      ID:day
V    day      0    003E6D18 003E6830 int:*0:[0]      
    -VAR
   -VAR_LIST
  -DECL
   KEY:;
   KEY:}
 -STRUCT
 +STRUCT
   KEY:struct
   ID:Person
S    Person   0    003E6EB8 0040A340 
   KEY:{
  +DECL
   +TYPE
     KEY:char
   -TYPE
   +VAR_LIST
    +VAR
      KEY:*
      ID:name
V    name     0    003E7148 003E6EB8 char:*1:[0]     
    -VAR
   -VAR_LIST
  -DECL
   KEY:;
  +DECL
   +TYPE
     ID:Date
   -TYPE
   +VAR_LIST
    +VAR
      ID:birthday
V    birthday 0    003E7398 003E6EB8 Date:*0:[0]     
    -VAR
   -VAR_LIST
  -DECL
   KEY:;
   KEY:}
 -STRUCT
 +METHOD
  +TYPE
    KEY:int
  -TYPE
   ID:total
M    total    0    003E75F8 0040A340 
   KEY:(
  +PARAM_LIST
   +PARAM
    +TYPE
      KEY:int
    -TYPE
    +VAR
      KEY:*
      ID:a
V    a        0    003E78A8 003E75F8 int:*1:[0]      
    -VAR
   -PARAM
  -PARAM_LIST
   KEY:)
  +BLOCK
B             0    003E79B0 003E75F8 
    KEY:{
   +BASE
    +STMT
     +DECL
      +TYPE
        KEY:int
      -TYPE
      +VAR_LIST
       +VAR
         ID:s
V    s        0    003E7C60 003E79B0 int:*0:[0]      
         KEY:=
        +EXP
         +TERM
           CINT:0
         -TERM
        -EXP
       -VAR
      -VAR_LIST
     -DECL
    -STMT
     KEY:;
   -BASE
   +BASE
    +FOR
      KEY:for
      KEY:(
     +STMT
      +DECL
       +TYPE
         KEY:int
       -TYPE
       +VAR_LIST
        +VAR
          ID:i
V    i        0    003E8128 003E79B0 int:*0:[0]      
          KEY:=
         +EXP
          +TERM
            CINT:0
          -TERM
         -EXP
        -VAR
       -VAR_LIST
      -DECL
     -STMT
      KEY:;
     +EXP
      +TERM
       +PATH
        +ATOM
          ID:i
        -ATOM
       -PATH
      -TERM
       KEY:<
      +TERM
        CINT:10
      -TERM
     -EXP
      KEY:;
     +STMT
      +PATH
       +ATOM
         ID:i
       -ATOM
      -PATH
       KEY:++
     -STMT
      KEY:)
     +BASE
      +STMT
       +PATH
        +ATOM
          ID:s
        -ATOM
       -PATH
        KEY:=
       +EXP
        +TERM
         +PATH
          +ATOM
            ID:s
          -ATOM
         -PATH
        -TERM
         KEY:+
        +TERM
         +PATH
          +ATOM
            ID:a
            KEY:[
           +EXP
            +TERM
             +PATH
              +ATOM
                ID:i
              -ATOM
             -PATH
            -TERM
           -EXP
            KEY:]
          -ATOM
         -PATH
        -TERM
       -EXP
      -STMT
       KEY:;
     -BASE
    -FOR
   -BASE
   +BASE
    +STMT
      KEY:return
     +EXP
      +TERM
       +PATH
        +ATOM
          ID:s
        -ATOM
       -PATH
      -TERM
     -EXP
    -STMT
     KEY:;
   -BASE
    KEY:}
  -BLOCK
 -METHOD
 +METHOD
  +TYPE
    KEY:char
  -TYPE
   KEY:*
   ID:getName
M    getName  0    003E9270 0040A340 
   KEY:(
  +PARAM_LIST
   +PARAM
    +TYPE
      ID:Person
    -TYPE
    +VAR
      KEY:*
      ID:p
V    p        0    003E9518 003E9270 Person:*1:[0]   
    -VAR
   -PARAM
  -PARAM_LIST
   KEY:)
  +BLOCK
B             0    003E9608 003E9270 
    KEY:{
   +BASE
    +STMT
      KEY:return
     +EXP
      +TERM
       +PATH
        +ATOM
          ID:p
        -ATOM
         KEY:->
        +ATOM
          ID:name
        -ATOM
       -PATH
      -TERM
     -EXP
    -STMT
     KEY:;
   -BASE
    KEY:}
  -BLOCK
 -METHOD
 +METHOD
  +TYPE
    KEY:int
  -TYPE
   ID:main
M    main     0    003E9B70 0040A340 
   KEY:(
   KEY:)
  +BLOCK
B             0    003E9CD8 003E9B70 
    KEY:{
   +BASE
    +STMT
     +DECL
      +TYPE
        KEY:int
      -TYPE
      +VAR_LIST
       +VAR
         ID:b
V    b        0    003E9F88 003E9CD8 int:*0:[0]      
         KEY:[
         CINT:10
         KEY:]
       -VAR
        KEY:,
       +VAR
         ID:a
V    a        0    003EA170 003E9CD8 int:*0:[0]      
         KEY:=
        +EXP
         +TERM
           CINT:3
         -TERM
        -EXP
       -VAR
      -VAR_LIST
     -DECL
    -STMT
     KEY:;
   -BASE
   +BASE
    +STMT
     +DECL
      +TYPE
        KEY:int
      -TYPE
      +VAR_LIST
       +VAR
         ID:t
V    t        0    003EA560 003E9CD8 int:*0:[0]      
         KEY:=
        +EXP
         +TERM
          +PATH
           +ATOM
             ID:total
             KEY:(
            +EXP_LIST
             +EXP
              +TERM
               +PATH
                +ATOM
                  ID:b
                -ATOM
               -PATH
              -TERM
             -EXP
            -EXP_LIST
             KEY:)
           -ATOM
          -PATH
         -TERM
        -EXP
       -VAR
      -VAR_LIST
     -DECL
    -STMT
     KEY:;
   -BASE
   +BASE
    +STMT
     +DECL
      +TYPE
        ID:Person
      -TYPE
      +VAR_LIST
       +VAR
         ID:p
V    p        0    003EAC48 003E9CD8 Person:*0:[0]   
       -VAR
      -VAR_LIST
     -DECL
    -STMT
     KEY:;
   -BASE
   +BASE
    +STMT
     +PATH
      +ATOM
        ID:p
      -ATOM
       KEY:.
      +ATOM
        ID:birthday
      -ATOM
       KEY:.
      +ATOM
        ID:year
      -ATOM
     -PATH
      KEY:=
     +EXP
      +TERM
        CINT:1990
      -TERM
     -EXP
    -STMT
     KEY:;
   -BASE
   +BASE
    +STMT
     +PATH
      +ATOM
        ID:t
      -ATOM
     -PATH
      KEY:=
     +EXP
      +TERM
        CINT:3
      -TERM
       KEY:+
      +TERM
        KEY:(
       +EXP
        +TERM
          CINT:5
        -TERM
         KEY:*
        +TERM
         +PATH
          +ATOM
            ID:a
          -ATOM
         -PATH
        -TERM
       -EXP
        KEY:)
      -TERM
     -EXP
    -STMT
     KEY:;
   -BASE
   +BASE
    +STMT
      KEY:return
     +EXP
      +TERM
       +PATH
        +ATOM
          ID:t
        -ATOM
       -PATH
      -TERM
     -EXP
    -STMT
     KEY:;
   -BASE
    KEY:}
  -BLOCK
 -METHOD
-PROG
type name     size this     scope    varType
V    i        0    003E8128 003E79B0 int:*0:[0]      
M    main     0    003E9B70 0040A340 
V    month    0    003E6BD8 003E6830 int:*0:[0]      
V    name     0    003E7148 003E6EB8 char:*1:[0]     
M    total    0    003E75F8 0040A340 
V    x        0    003E2558 0040A340 int:*0:[0]      
V    s        0    003E7C60 003E79B0 int:*0:[0]      
V    y        0    003E6590 0040A340 int:*0:[0]      
B             0    003E9CD8 003E9B70 
V    a        0    003EA170 003E9CD8 int:*0:[0]      
V    b        0    003E9F88 003E9CD8 int:*0:[1]      
S    Person   0    003E6EB8 0040A340 
T    int      4    003E5EB0 0040A340 
V    a        0    003E78A8 003E75F8 int:*1:[0]      
V    p        0    003EAC48 003E9CD8 Person:*0:[0]   
T    char     1    003E57E0 0040A340 
V    t        0    003EA560 003E9CD8 int:*0:[0]      
T    float    4    003E5778 0040A340 
B             0    003E79B0 003E75F8 
V    day      0    003E6D18 003E6830 int:*0:[0]      
M    getName  0    003E9270 0040A340 
V    birthday 0    003E7398 003E6EB8 Date:*0:[0]     
V    p        0    003E9518 003E9270 Person:*1:[0]   
V    year     0    003E6A80 003E6830 int:*0:[0]      
S    Date     0    003E6830 0040A340 
B             0    003E9608 003E9270 
Memory:newCount=2090 freeCount=2090

Facebook

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