《编译原理语法分析器》由会员分享，可在线阅读，更多相关《编译原理语法分析器（7页珍藏版）》请在金锄头文库上搜索。
1、计算机科学与工程学院 计算机 033 班 曾志强 22 号1 / 7语法分析语法分析一、实验任务一、实验任务本实验的任务是编写整数算术表达式的递归下降语法分析程序，它从左至右逐个扫描输 入单词，分析输入单词符号串是否合乎算术表达式语法。 具体任务有： 组织算术表达式的输入。 拼出单词并转换成机内表示形式。 在词法分析基础上分析表达式语法。 发现并定位语法错误。 打印错误信息。二、实验要求二、实验要求1 整数加减乘除四则运算表达式文法 GE如下所示：E-E+T | E-T | T T-T*F | T/F | F F-(E) | i (i 是整常数) 文法是含回溯和左递归的上下文无关文法，实验要求
2、首先将文法转换成等价的 LL(1)文法，再从转换后的 LL(1)文法构造出整数四则运算表达式的递归下降分析 器。 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
3、) 2 参照实验 1、书 P74 和附录 1 的方法，实现整数算术表达式的递归下降语法分析程序四、程序代码四、程序代码以下的代码只支持 7 种节点加减乘除，标识符，数字，表达式。想要加入其 他节点，在 opprio 数组中加入优先级。1） /Parse.h/ /计算机科学与工程学院 计算机 033 班 曾志强 22 号2 / 72） 3） #ifndef _PARSE_H_ 4） #define _PARSE_H_ 5） #include “lexical.h“ 6） 7） /算法优先文法中优先级关系枚举8） typedef enum LS, GT, EQ,UN Priority; 9） /移
4、进归约算法中使用到的栈节点结构（双向链表）10）typedef struct _pstacktoken 11） 12） LexToken *ptoken; 13） struct _pstacktoken *pr; 14） struct _pstacktoken *nt; 15） struct _pstacktoken *child; 16）PStackToken; 17）void PStackPush(LexToken *t); 18）LexToken* PStackPop(); 19） 20）/产生式链表节点结构（单向链表）21）typedef struct _generator LexTo
5、kenType *gen; int size; struct _generator *nt; Generator; 22）PStackToken* Parse(char *Source); 23） 24）#endif/_PARSE_H 25）/Parse.c/ / 26）#include “Parse.h“ 27）#include 28）#include 29）#include 30）#include 31） 32）/各个运算符之间的优先级定义33）#define OPNUM 7 34）Priority opprioOPNUMOPNUM= 35） GT,GT,LS,LS,LS,LS,GT, 3
6、6） 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）; 43）Priority PrioCmp(LexTokenType first, LexTokenType second)/这段函数计算机科学与工程学院 计算机 033 班 曾志强 22 号3 / 7被优化代码替代44） 45） if (first=OPNUM | second=O
7、PNUM) 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） 56） static int size = sizeof(PStackToken); 57） PStackToken *p = (PStackToken*)malloc(size);/不检查合法性 58） p-pt
8、oken = t;/不对 t 的合法性检查 59） if (!PSbot)/第一个节点60） 61） PSbot = PStop = p; 62） p-pr = p-nt = NULL; 63） 64） else 65） 66） PStop-nt = p; 67） p-pr = PStop; 68） p-nt = NULL; 69） PStop = p; 70） 71） p-child = NULL; 72） 73）LexToken* PStackPop() 74） 75） LexToken *p = PStop-ptoken; 76） PStackToken *last = PStop; 7
9、7） 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;计算机科学与工程学院 计算机 033 班 曾志强 22 号4 / 787）Generator *GLend = NULL; 88）void AddGen(int num, .) 89） 90） static int sizegen = sizeof(Generator); 91） s
10、tatic 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; igeni = va_arg(pArgList, LexTokenType);
11、102） 103） va_end (pArgList); 104） if (!GLhead) 105） 106） GLhead = pGen; 107） GLend = pGen; 108） 109） else 110） 111） GLend-nt = pGen; 112） GLend = pGen; 113） 114） 115）void InitGenerator() 116） 117） AddGen(3,EXPRESSION,PLUS,EXPRESSION); 118） AddGen(3,EXPRESSION,MINUS,EXPRESSION); 119） AddGen(3,EXPRESS
12、ION,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）计算机科学与工程学院 计算机 033 班 曾志强 22 号5 / 713
13、1） 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） else 146） 147） PSnow = PStop; 148） 149） while (PrioCmpRlt = PrioCmp(PSnow-ptoken-type, gettoken- type) = GT)/PSnow 未作检查，找到最左素短语尾部150） 151） while (
