parse.h
#ifndef PARSE_H
#define PARSE_H

#define MAXCHILDNUM    3
#define INDENTADD    4
/**
 * 語法樹具有如下結構
 * 具體節點可以分為：語句節點STMT，表達式節點EXPR
 * 語句節點可以分為：賦值語句ASSIGNSTMT，條件語句IFSTMT，循環語句WHILESTMT，
 *             復合語句COMPOUNDSTMT
 * 表達式節點可以分為：操作符類型OPEXP，常數類型CONSTEXP，標識符類型IDEXP,
 *                關系操作符REALEXP
 */
enum NodeKind {
    STMT,
    EXP,
};
enum StmtKind {
    ASSIGNSTMT,
    IFSTMT,
    WHILESTMT,
}; 
enum ExpKind { 
    OPEXP,
    CONSTEXP, 
    IDEXP,
    REALEXP,
}; 
struct TreeNode {
    struct TreeNode    *child[MAXCHILDNUM];
    struct TreeNode    *sib;
    /**
     * kind用于指明該節點是語句節點STMT
     * 或是表達式節點EXP
     */
    enum NodeKind    kind;
    union {
        enum StmtKind stmt;
        enum ExpKind exp;
    } subKind;
    union {
        int    val;    /* 值 */
        LexType    op;    /* 操作符 */
        char    idname[256]; /*標識符 */
    } attr;
    int    lineno;        /* 所在行號 */
}; 
/**
 * 源程序中的聲明部分的語法樹
 */
#define PARSE_VAR  -1
struct DecNode {
    struct DecNode    *next;
    /* 標識符 */
    char    idname[256];
    /* 如果該值是PARSE_VAR則表示這個聲明是變量聲明 */
    /* 否則該值是標識符對應的常量 */
    int    icval;
    int    lineno;
};
/**
 * 程序語法樹結構
 */
struct SyntaxTree {
    /* 指向程序常量聲明部分 */
    struct DecNode    *pconstDec;
    /* 指向程序變量聲明部分 */
    struct DecNode    *pvarDec;
    /* 指向程序語句部分 */
    struct TreeNode    *pstmt;
};
/*
 * 以上所定義的節點處了語法分析要用外，語義分析
 * 用到這些節點，它會根據節點的情況去遍歷語法樹
 * 去完成相應的任務。
 */
#endif

parse.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "lib.h"

#include "lex.h"
#include "parse.h"

extern int gerrLine;    // define in main.cpp
// 本地程序的聲明
static struct TreeNode *PARSE_newTreeNode(void);
static struct TokenType *PARSE_getToken(void);
static void PARSE_ungetToken(struct TokenType *ptoken);
static struct TreeNode *PARSE_expr(void);
static struct TreeNode *PARSE_factor(void);
static struct TreeNode *PARSE_term(void);
static struct TreeNode *PARSE_relationExpr(void);
static void PARSE_printExpr(struct TreeNode *phead);
static struct DecNode *PARSE_constDec(void);
static struct DecNode *PARSE_varDec(void);
static struct DecNode *PARSE_insert(struct DecNode *phead, const char *id, int icval, int lineno);
static struct TreeNode *PARSE_stmt(void);
static struct TreeNode *PARSE_assign(void);
static struct TreeNode *PARSE_if(void);
static struct TreeNode *PARSE_while(void);
static struct TreeNode *PARSE_compound(void);
static void PARSE_empty(int indent);

// 本地變量的聲明ptokenSeq指向記號流
static struct TokenSeq *ptokenSeq;
static char    buf[256];

/*
 * 語法分析主程序，它先分析程序的常量節點，然后分析程序的變量部分
 * 最后分析程序的語句部分，如果程序分析的過程中出現錯誤，就不再分
 * 析下去，而是直接返回，并做相應標記，錯誤信息寫在全局變量errMsg中。
 */
struct SyntaxTree *PARSE_parser(struct TokenSeq *phead)
{
    struct SyntaxTree    *ptree;
    struct TokenType    *ptoken;
    int    flag;

    ptokenSeq = phead;
    ptree = (struct SyntaxTree *)malloc(sizeof(struct SyntaxTree));
    if (ptree == NULL)
    {
        // TODO 內存分配錯誤
        exit(1);
    }
    ptree->pvarDec = NULL;
    ptree->pstmt = NULL;
    ptree->pconstDec = PARSE_constDec();
    if (gerrLine == -1)
    {
        // 如果常量分析沒有錯誤，就進行變量分析
        // 否則程序就返回，不再分析下去。
        ptree->pvarDec = PARSE_varDec();
        if (gerrLine == -1)
        {
            // 如果對程序變量分析沒有錯誤，就分析程序的
            // 語句，否則程序就返回，不再分析下去。
            ptree->pstmt = PARSE_stmt();
            if (gerrLine == -1)
            {
                flag = 0;
                while (ptoken = PARSE_getToken())
                {
                    if (!flag) {
                        flag = ptoken->lineno;
                        sprintf(buf, "行 %d：多于的記號 %s\n", ptoken->lineno, ptoken->lexval);
                    }
                    free(ptoken);
                }
                if (flag) 
                {
                    msgOutPut(buf);
                    gerrLine = flag;
                }
            }
        }
    }
    return ptree;
}
// 分配一個新的樹節點，并將節點中的區域初始化。
static struct TreeNode *PARSE_newTreeNode(void)
{
    struct TreeNode *ptmp;
    
    ptmp = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    if (ptmp == NULL)
    {
        printf("%s: %d\n", __FILE__, __LINE__);
        exit(1);
    }
    memset(ptmp->child, 0, sizeof(ptmp->child));
    ptmp->sib = NULL;
    return ptmp;
}
/**
* 從記號流中獲取一個記號，并將他的地址返回
* 如果記號流中已經沒有則返回NULL代表沒有
* 記號流中已經沒有記號了。
*/
static struct TokenType *PARSE_getToken(void)
{
    struct TokenType    *ptoken;
    struct TokenSeq        *ptmp;
    
    if (ptokenSeq) 
    {
        ptoken = (struct TokenType *)malloc(sizeof(struct TokenType));
        if (ptoken == NULL)
        {
            printf("%s: %d\n", __FILE__, __LINE__);
            exit(1);
        }
        /**
        * v
        */
        *ptoken = ptokenSeq->token;
        ptmp = ptokenSeq;
        ptokenSeq = ptokenSeq->next;
        free(ptmp);
        return ptoken;
    }
    return NULL;
}
/**
* 將參數所指的記號回退到記號流中去，如果參數為空
* 直接返回
*/
static void PARSE_ungetToken(struct TokenType *ptoken)
{
    struct TokenSeq        *ptmp;
    
    if (!ptoken) return;    
    ptmp = (struct TokenSeq *)malloc(sizeof(struct TokenSeq));
    if (ptmp == NULL)
    {
        printf("%s: %d\n", __FILE__, __LINE__);
        exit(1);
    }
    ptmp->token = *ptoken;
    ptmp->next = ptokenSeq;
    ptokenSeq = ptmp;
}
/**
* 分析表達式
*    expr -> term {+term}
*    term -> factor {*factor}
*    factor -> (expr) | number
*/
static struct TreeNode *PARSE_expr(void)
{
    struct TreeNode *phead, *ptmp;
    struct TokenType *ptoken;
    
    phead = PARSE_term();
    ptoken = PARSE_getToken();
    if (!ptoken || gerrLine != -1) 
    {
        return phead;
    }
    while (ptoken && (ptoken->lextype == ADD || ptoken->lextype == SUB)) 
    {
        ptmp = PARSE_newTreeNode();
        ptmp->lineno = ptoken->lineno;
        ptmp->kind = EXP;
        ptmp->subKind.exp = OPEXP;
        ptmp->attr.op = ptoken->lextype;
        ptmp->child[0] = phead;
        ptmp->child[1] = PARSE_term();
        phead = ptmp;
        if (gerrLine != -1) return phead;
        ptoken = PARSE_getToken();
    }
    if (ptoken)
    {
        PARSE_ungetToken(ptoken);
    }
    return phead;
}
/*
*    term -> factor {*factor}
*    factor -> (expr) | number
*/
static struct TreeNode *PARSE_term(void)
{
    struct TreeNode *phead, *ptmp;
    struct TokenType *ptoken;
    
    phead = NULL;
    phead = PARSE_factor();
    ptoken = PARSE_getToken();
    if (!ptoken || gerrLine != -1) return phead;
    while (ptoken && (ptoken->lextype == MUL || ptoken->lextype == DIV))
    {
        ptmp = PARSE_newTreeNode();
        ptmp->lineno = ptoken->lineno;
        ptmp->kind = EXP;
        ptmp->subKind.exp = OPEXP;
        ptmp->attr.op = ptoken->lextype;
        ptmp->child[0] = phead;
        ptmp->child[1] = PARSE_factor();
        phead = ptmp;
        if (gerrLine != -1) return phead;
        ptoken = PARSE_getToken();
    }
    if (ptoken)
        PARSE_ungetToken(ptoken);
    return phead;
}
//factor -> (expr) | number
static struct TreeNode *PARSE_factor(void)
{
    struct TreeNode *phead;
    struct TokenType *ptoken;
    int        lineno;
    
    phead = NULL;
    ptoken = PARSE_getToken();
    if (!ptoken) return NULL;
    lineno = ptoken->lineno;
    if (ptoken->lextype == LBR) 
    {
        free(ptoken);
        phead = PARSE_expr();
        if (gerrLine != -1) return phead;
        ptoken = PARSE_getToken();
        if (ptoken && ptoken->lextype != RBR) 
        {
            sprintf(buf, "行 %d，括號不匹配\n", lineno);
            msgOutPut(buf);
            gerrLine = ptoken->lineno;
            return phead;
        }
        if (ptoken) free(ptoken);
    } 
    else 
    {
        if (ptoken->lextype != NUM 
            && ptoken->lextype != ID)
        {
            sprintf(buf, "行 %d，因子不是數字或標識符\n", lineno);
            msgOutPut(buf);
            gerrLine = ptoken->lineno;
            free(ptoken);
            return phead;
        }
        phead = PARSE_newTreeNode();
        phead->kind = EXP;
        lineno = phead->lineno = ptoken->lineno;
        if (ptoken->lextype == NUM) 
        {
            phead->subKind.exp = CONSTEXP;
            sscanf(ptoken->lexval, "%d", &phead->attr.val);
        } 
        else 
        {
            phead->subKind.exp = IDEXP;
            if (ptoken->lextype == ID)
            {
                strcpy(phead->attr.idname, ptoken->lexval);
                free(ptoken);
            }
            else
            {
                sprintf(buf, "行 %d，因子不是標識符\n", lineno);
                msgOutPut(buf);
                gerrLine = lineno;    
                return phead;
            }
        }
    }
    return phead;
}
/**
* 關系表達式節點，他的左邊和右邊都是表達式
* 中間是關系運算符
*/
static struct TreeNode *PARSE_relationExpr(void)
{
    struct TreeNode    *phead;
    struct TokenType *ptmp;
    
    phead = PARSE_newTreeNode();
    phead->child[0] = PARSE_expr();
    if (gerrLine != -1) return phead;
    ptmp = PARSE_getToken();
    phead->lineno = ptmp->lineno;
    switch (ptmp->lextype)
    {
    case EQ:
        phead->kind = EXP;
        phead->subKind.exp = REALEXP;
        phead->attr.op = ptmp->lextype;
        break;
    case NE:
        phead->kind = EXP;
        phead->subKind.exp = REALEXP;
        phead->attr.op = ptmp->lextype;
        break;
    case LT:
        phead->kind = EXP;
        phead->subKind.exp = REALEXP;
        phead->attr.op = ptmp->lextype;
        break;
    case LE:
        phead->kind = EXP;
        phead->subKind.exp = REALEXP;
        phead->attr.op = ptmp->lextype;
        break;
    case GT:
        phead->kind = EXP;
        phead->subKind.exp = REALEXP;
        phead->attr.op = ptmp->lextype;
        break;
    case GE:
        phead->kind = EXP;
        phead->subKind.exp = REALEXP;
        phead->attr.op = ptmp->lextype;
        break;
    default:
        // 程序中沒有關系運算符，程序中盡量少用exit(1)
        // 免得誤用是程序異常退出。
        gerrLine = ptmp->lineno;
        phead->child[1] = NULL;
        sprintf(buf, "行 %d: 缺少關系運算符\n", ptmp->lineno);
        msgOutPut(buf);
        return phead;
    }
    phead->child[1] = PARSE_expr();
    return phead;
}
/**
* 匹配記號程序，如果記號流中有一個記號和
* 要匹配的記號不同，就簡單的忽略這個記號
* 并返回NULL
*/
static struct TokenType *PARSE_match(enum LexType lextype)
{
    struct TokenType *ptoken;
    
    ptoken = PARSE_getToken(); 
    if (ptoken && ptoken->lextype == lextype)
        return ptoken;
    if (ptoken)
    {
        /* 如果不匹配就將這個記號回退到記號流中去 */
        PARSE_ungetToken(ptoken);
        free(ptoken);
        return NULL;
    }
    else
    {
        return NULL;
    }
}
/**
* 處理有關常量聲明或變量聲明的程序部分
* 它將建立一個鏈表，指向程序中的常量序列
*/
static struct DecNode *PARSE_constDec(void)
{
    struct DecNode         *phead;
    struct TokenType    *ptoken, *ptokenid, *ptokennum;
    char    idname[256];
    int        icval, lineno;
    
    phead = NULL;
    if (ptoken = PARSE_match(CONST))
    {
        lineno = ptoken->lineno;
        /* 處理常量聲明部分，并將聲明部分節點插入到鏈表中去 */
        while (ptokenid = PARSE_match(ID))
        {
            lineno = ptokenid->lineno;
            ptoken = PARSE_match(ASSIGN);
            ptokennum = PARSE_match(NUM);
            if (ptokenid && ptoken && ptokennum)
            {
                /* 將一個常量定義放到鏈表中去 */
                strcpy(idname, ptokenid->lexval);
                sscanf(ptokennum->lexval, "%d", &icval);
                phead = PARSE_insert(phead, idname, icval, ptokennum->lineno);
                free(ptokenid);
                free(ptoken);
                free(ptokennum);
                if (ptoken = PARSE_match(COMMA)) 
                {
                    free(ptoken);
                    continue;
                }
                else if (ptoken = PARSE_match(COLON))
                {
                    free(ptoken);
                    return phead;
                }
                else 
                {
                    sprintf(buf, "行 %d: 缺少逗號或分號\n", lineno);
                    msgOutPut(buf);
                    gerrLine = lineno;
                    return phead;
                }
            }