编译原理语法分析器.doc

语法分析一、实验任务 本实验的任务是编写整数算术表达式的递归下降语法分析程序，它从左至右逐个扫描输入单词，分析输入单词符号串是否合乎算术表达式语法。具体任务有：组织算术表达式的输入。拼出单词并转换成机内表示形式。在词法分析基础上分析表达式语法。发现并定位语法错误。打印错误信息。二、实验要求1 整数加减乘除四则运算表达式文法GE如下所示：E-E+T | E-T | TT-T*F | T/F | FF-(E) | i (i是整常数)文法是含回溯和左递归的上下文无关文法，实验要求首先将文法转换成等价的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)2 参照实验1、书P74和附录1的方法，实现整数算术表达式的递归下降语法分析程序四、程序代码以下的代码只支持7种节点加减乘除，标识符，数字，表达式。想要加入其他节点，在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 _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.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） ;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） 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;70） 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） 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） pGen-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） AddGen(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(char *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(PSnow-ptoken-type, gettoken-type) = GT)/PSnow未作检查，找到最左素短语尾部150） 151） while (1)/查找最左素短语头部152） 153） PStail = PSnow;154） PSnow = PSnow-pr;155） if (PSnow-ptoken-type = EXPRESSION)/未做合法性检查156） 157） PSnow = PSnow-pr;158） 159） if (PrioCmp(PSnow-ptoken-type, PStail-ptoken-type) = LS)160） /归约161） int i;162） PStackToken *pst;163） pgennow = GLhead;164） while(pgennow)165） 166） pst = PSnow-nt;167） for (i=0; isize & pst!=PStop-nt; i+)168） 169） if (pst-ptoken-type != pgennow-geni)170） break;171） pst = pst-nt;172） 173） if(i=pgennow-size & pst=PStop-nt)/找到了产生式174） 175） LexToken *pExp = (LexToken*)malloc(sizeof(LexToken);176） pst = PSnow-nt;177） pExp-strName = NULL;178） pExp-type = EXPRESSION;179） PStop = PSnow;180） PStackPush(pExp);/插入一个Expression节点181） PStop-child = pst;/为该节点建立树182） pst-pr = NULL;183） break;184） 185） pgennow = pgennow-nt;186） 187） /在这里考虑无法归约的情况188） 189） break;190） 191） / break;192） 193） if (PrioCmpRlt = LS)194） 195） PStackPush(gettoken);196） continue;197） 198） if (PrioCmpRlt = EQ)199） 200） if (PSnow-ptoken-type = JINGHAO)201） 202） /识别203）