《编译原理语法分析器》由会员分享，可在线阅读，更多相关《编译原理语法分析器（7页珍藏版）》请在金锄头文库上搜索。
1、语法分析一、实验任务 本实验的任务是编写整数算术表达式的递归下降语法分析程序，它从左至右逐个扫描输入单词，分析输入单词符号串是否合乎算术表达式语法。具体任务有：组织算术表达式的输入。拼出单词并转换成机内表示形式。在词法分析基础上分析表达式语法。发现并定位语法错误。打印错误信息。二、实验要求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 _pstacktoken *nt;15） struct _
4、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） /Parse.c/26） #include Parse.
5、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,41） LS,LS,LS,LS,LS,LS,EQ,42
6、） ;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 PStackPush(LexToken *t)55） 5
7、6） 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;70） 71） p-child = NULL;72）
8、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） void AddGen(int num, .)89
9、） 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） pGen-nt = NULL;99） for (i=0
10、; 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） AddGen(3,EXPRESSION,MINUS,E
11、XPRESSION);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(char *Source)130） 131） stat
12、ic 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(PSnow-ptoken-type, gettoken-type) = GT)/PSnow未作检查，找到最
