接着昨天的词法分析器，语法分析主要是将从词法分析那里得来的记号构成一棵语法树。这次我将作案的词法分析部分的代码稍作了修改，让他更适合语法分析器。我使用的是自下而上的分析法，针对算符优先文法的产生式构造语法树。
以下的代码只支持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;
}
