《编译原理语法分析器.doc》由会员分享,可在线阅读,更多相关《编译原理语法分析器.doc(7页珍藏版)》请在金锄头文库上搜索。
1、计算机科学与工程学院 计算机033班 曾志强 22号语法分析一、实验任务 本实验的任务是编写整数算术表达式的递归下降语法分析程序,它从左至右逐个扫描输入单词,分析输入单词符号串是否合乎算术表达式语法。具体任务有:组织算术表达式的输入。拼出单词并转换成机内表示形式。在词法分析基础上分析表达式语法。发现并定位语法错误。打印错误信息。二、实验要求1 整数加减乘除四则运算表达式文法GE如下所示:E-E+T | E-T | TT-T*F | T/F | FF-(E) | i (i是整常数)文法是含回溯和左递归的上下文无关文法,实验要求首先将文法转换成等价的LL(1)文法,再从转换后的LL(1)文法构造出
2、整数四则运算表达式的递归下降分析器。2能检查并处理某些语法错误,一旦发现错误,输出错误位置及错误类型,可停止分析或进行错误恢复处理(同学们自行选择处理方式)。错误类型:(同学们自行定义,如)1:非法字符。2:三、实验内容1 将文法GE转化为LL(1)文法1) 提取公共左因子如E-E+T | E-T | T 提取公共左因子得到E-E E1 | T (1)E1-+T | -T (2)2) 消除左递归,如上(1) 消除左递归得到E-T E2 (1)E2-E1 E2 | e(空串) (3)2 参照实验1、书P74和附录1的方法,实现整数算术表达式的递归下降语法分析程序四、程序代码以下的代码只支持7种节
3、点加减乘除,标识符,数字,表达式。想要加入其他节点,在opprio数组中加入优先级。1) /Parse.h/2)3) #ifndef _PARSE_H_4) #define _PARSE_H_5) #include lexical.h6)7) /算法优先文法中优先级关系枚举8) typedef enum LS, GT, EQ,UN Priority;9) /移进归约算法中使用到的栈节点结构(双向链表)10) typedef struct _pstacktoken11) 12) LexToken *ptoken;13) struct _pstacktoken *pr;14) struct _ps
4、tacktoken *nt;15) struct _pstacktoken *child;16) PStackToken;17) void PStackPush(LexToken *t);18) LexToken* PStackPop();19)20) /产生式链表节点结构(单向链表)21) typedef struct _generator LexTokenType *gen; int size; struct _generator *nt; Generator;22) PStackToken* Parse(char *Source);23)24) #endif/_PARSE_H25) /P
5、arse.c/26) #include Parse.h27) #include 28) #include 29) #include 30) #include 31)32) /各个运算符之间的优先级定义33) #define OPNUM 734) Priority opprioOPNUMOPNUM=35) GT,GT,LS,LS,LS,LS,GT,36) GT,GT,LS,LS,LS,LS,GT,37) GT,GT,GT,GT,LS,LS,GT,38) GT,GT,GT,GT,LS,LS,GT,39) GT,GT,GT,GT,UN,UN,GT,40) GT,GT,GT,GT,UN,UN,GT,4
6、1) LS,LS,LS,LS,LS,LS,EQ,42) ;43) Priority PrioCmp(LexTokenType first, LexTokenType second)/这段函数被优化代码替代44) 45) if (first=OPNUM | second=OPNUM)46) return UN;47) return oppriofirstsecond;48) 49)50)51) PStackToken *PSbot = NULL;/栈底指针52) PStackToken *PStop = NULL;/栈顶指针53) /int PSnum = 0;/栈元素个数54) void PS
7、tackPush(LexToken *t)55) 56) static int size = sizeof(PStackToken);57) PStackToken *p = (PStackToken*)malloc(size);/不检查合法性58) p-ptoken = t;/不对t的合法性检查59) if (!PSbot)/第一个节点60) 61) PSbot = PStop = p;62) p-pr = p-nt = NULL;63) 64) else65) 66) PStop-nt = p;67) p-pr = PStop;68) p-nt = NULL;69) PStop = p;7
8、0) 71) p-child = NULL;72) 73) LexToken* PStackPop()74) 75) LexToken *p = PStop-ptoken;76) PStackToken *last = PStop;77) if (PStop=NULL)/如果已无元素可弹出78) return NULL;79) PStop = PStop-pr;80) PStop-nt = NULL;81) free(last);82) return p;83) 84)85)86) Generator *GLhead = NULL;87) Generator *GLend = NULL;88)
9、 void AddGen(int num, .)89) 90) static int sizegen = sizeof(Generator);91) static int sizetype = sizeof(LexTokenType);92) Generator *pGen = (Generator*)malloc(sizegen);93) int i;94) va_list pArgList;95) va_start (pArgList, num);96) pGen-size = num;97) pGen-gen = (LexTokenType*)malloc(sizetype);98) p
10、Gen-nt = NULL;99) for (i=0; igeni = va_arg(pArgList, LexTokenType);102) 103) va_end (pArgList);104) if (!GLhead)105) 106) GLhead = pGen;107) GLend = pGen;108) 109) else110) 111) GLend-nt = pGen;112) GLend = pGen;113) 114) 115) void InitGenerator()116) 117) AddGen(3,EXPRESSION,PLUS,EXPRESSION);118) A
11、ddGen(3,EXPRESSION,MINUS,EXPRESSION);119) AddGen(3,EXPRESSION,MULTI,EXPRESSION);120) AddGen(3,EXPRESSION,DIVIDE,EXPRESSION);121) AddGen(1,IDENTI);122) AddGen(1,NUMBER);123) 124)125)126) PStackToken *PSnow = NULL;127) LexToken *gettoken = NULL;128) PStackToken *PStail = NULL;129) PStackToken* Parse(c
12、har *Source)130) 131) static int sizeLexToken = sizeof(LexToken);132) Generator *pgennow = NULL;/查找产生式时使用133) LexToken *pstart = (LexToken*)malloc(sizeLexToken);/不检查合法性134) Priority PrioCmpRlt = UN;135) InitGenerator();136) pstart-strName = NULL;137) pstart-type = JINGHAO;138) PStackPush(pstart);139) while (gettoken = GetNextToken(Source)140) 141) if (PStop-ptoken-type = EXPRESSION)142) 143) PSnow = PStop-pr;144) 145) else146) 147) PSnow = PStop;148) 149) while (PrioCmpRlt = PrioCmp(