编译原理_语法分析部分

        接着昨天的词法分析器，语法分析主要是将从词法分析那里得来的记号构成一棵语法树。这次我将作案的词法分析部分的代码稍作了修改，让他更适合语法分析器。我使用的是自下而上的分析法，针对算符优先文法的产生式构造语法树。
        以下的代码只支持7种节点——加减乘除，标识符，数字，表达式。想要加入其他节点，在opprio数组中加入优先级。
////////////////////////////////Parse.h//////////////////////////////////
#ifndef _PARSE_H_
#define _PARSE_H_
#include "lexical.h"

//算法优先文法中优先级关系枚举
typedef enum {LS, GT, EQ,UN} Priority;
//移进归约算法中使用到的栈节点结构（双向链表）
typedef struct _pstacktoken
{
    LexToken *ptoken;
    struct _pstacktoken *pr;
    struct _pstacktoken *nt;
    struct _pstacktoken *child;
}PStackToken;
void PStackPush(LexToken *t);
LexToken* PStackPop();

//产生式链表节点结构（单向链表）
typedef struct _generator {LexTokenType *gen; int size; struct _generator *nt;} Generator;
PStackToken* Parse(char *Source);

#endif//_PARSE_H
////////////////////////////////////////Parse.c/////////////////////////////
#include "Parse.h"
#include <malloc.h>
#include <string.h>
#include <stdarg.h>
#include <stdio.h>

//各个运算符之间的优先级定义
#define OPNUM 7
Priority opprio[OPNUM][OPNUM]={
    {GT,GT,LS,LS,LS,LS,GT,},
    {GT,GT,LS,LS,LS,LS,GT,},
    {GT,GT,GT,GT,LS,LS,GT,},
    {GT,GT,GT,GT,LS,LS,GT,},
    {GT,GT,GT,GT,UN,UN,GT,},
    {GT,GT,GT,GT,UN,UN,GT,},
    {LS,LS,LS,LS,LS,LS,EQ,},
};
Priority PrioCmp(LexTokenType first, LexTokenType second)//这段函数被优化代码替代
{
    if (first>=OPNUM || second>=OPNUM)
        return UN;
    return opprio[first][second];
}


PStackToken *PSbot = NULL;//栈底指针
PStackToken *PStop = NULL;//栈顶指针
//int PSnum = 0;//栈元素个数
void PStackPush(LexToken *t)
{
    static int size = sizeof(PStackToken);
    PStackToken *p = (PStackToken*)malloc(size);//不检查合法性
    p->ptoken = t;//不对t的合法性检查
    if (!PSbot)//第一个节点
    {
        PSbot = PStop = p;
        p->pr = p->nt = NULL;
    }
    else
    {
        PStop->nt = p;
        p->pr = PStop;
        p->nt = NULL;
        PStop = p;
    }
    p->child = NULL;
}
LexToken* PStackPop()
{
    LexToken *p = PStop->ptoken;
    PStackToken *last = PStop;
    if (PStop==NULL)//如果已无元素可弹出
        return NULL;
    PStop = PStop->pr;
    PStop->nt = NULL;
    free(last);
    return p;
}


Generator *GLhead = NULL;
Generator *GLend = NULL;
void AddGen(int num, ...)
{
    static int sizegen = sizeof(Generator);
    static int sizetype = sizeof(LexTokenType);
    Generator *pGen = (Generator*)malloc(sizegen);
    int i;
    va_list pArgList;
    va_start (pArgList, num);
    pGen->size = num;
    pGen->gen = (LexTokenType*)malloc(sizetype);
    pGen->nt = NULL;
    for (i=0; i<num; i++)
    {
        pGen->gen[i] = va_arg(pArgList, LexTokenType);
    }
    va_end (pArgList);
    if (!GLhead)
    {
        GLhead = pGen;
        GLend = pGen;
    }
    else
    {
        GLend->nt = pGen;
        GLend = pGen;
    }
}
void InitGenerator()
{
    AddGen(3,EXPRESSION,PLUS,EXPRESSION);
    AddGen(3,EXPRESSION,MINUS,EXPRESSION);
    AddGen(3,EXPRESSION,MULTI,EXPRESSION);
    AddGen(3,EXPRESSION,DIVIDE,EXPRESSION);
    AddGen(1,IDENTI);
    AddGen(1,NUMBER);
}


PStackToken *PSnow = NULL;
LexToken *gettoken = NULL;
PStackToken *PStail = NULL;
PStackToken* Parse(char *Source)
{
    static int sizeLexToken = sizeof(LexToken);
    Generator *pgennow = NULL;//查找产生式时使用
    LexToken *pstart = (LexToken*)malloc(sizeLexToken);//不检查合法性
    Priority PrioCmpRlt = UN;
    InitGenerator();
    pstart->strName = NULL;
    pstart->type = JINGHAO;
    PStackPush(pstart);
    while (gettoken = GetNextToken(Source))
    {
        if (PStop->ptoken->type == EXPRESSION)
        {
            PSnow = PStop->pr;
        }
        else
        {
            PSnow = PStop;
        }
        while ((PrioCmpRlt = PrioCmp(PSnow->ptoken->type, gettoken->type)) == GT)//PSnow未作检查，找到最左素短语尾部
        {
            while (1)//查找最左素短语头部
            {
                PStail = PSnow;
                PSnow = PSnow->pr;
                if (PSnow->ptoken->type == EXPRESSION)//未做合法性检查
                {
                    PSnow = PSnow->pr;
                }
                if (PrioCmp(PSnow->ptoken->type, PStail->ptoken->type) == LS)
                {//归约
                    int i;
                    PStackToken *pst;
                    pgennow = GLhead;
                    while(pgennow)
                    {
                        pst = PSnow->nt;
                        for (i=0; i<pgennow->size && pst!=PStop->nt; i++)
                        {
                            if (pst->ptoken->type != pgennow->gen[i])
                                break;
                            pst = pst->nt;
                        }
                        if(i==pgennow->size && pst==PStop->nt)//找到了产生式
                        {
                            LexToken *pExp = (LexToken*)malloc(sizeof(LexToken));
                            pst = PSnow->nt;
                            pExp->strName = NULL;
                            pExp->type = EXPRESSION;
                            PStop = PSnow;
                            PStackPush(pExp);//插入一个Expression节点
                            PStop->child = pst;//为该节点建立树
                            pst->pr = NULL;
                            break;
                        }
                        pgennow = pgennow->nt;
                    }
                    //在这里考虑无法归约的情况
                }
                break;
            }
//            break;
        }
        if (PrioCmpRlt == LS)
        {
            PStackPush(gettoken);
            continue;
        }
        if (PrioCmpRlt == EQ)
        {
            if (PSnow->ptoken->type == JINGHAO)
            {
                //识别
                break;
            }
            else
            {
                PStackPush(gettoken);
                continue;
            }
        }
    }
    return PStop;
}

本文地址：http://com.8s8s.com/it/it22565.htm