语法fx.rar_ LR-BP_lr 0 分析_lr(1)_slr 1_编译原理

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