grammaranalysis.cpp

语法及语义分析程序

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;
                }
            }