搜索
自底向上语法分析器实验报告一．问题描述编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。E-E+T|E-T|TT-T*F|T/F|FF-id|(E)|num实验要求：在对输入表达式进行分析的过程中，输出所采用的产生式。编写语法分析程序实现自底向上的分析，要求如下：（1）构造识别所有活前缀的DFA。（2）构造LR分析表。（3）编程实现算法4.3，构造LR分析程序。二．算法思想1.大体步骤：（1）根据题目所给出的文法构造相应的拓广文法，并求出该文法各非终结符的FIRST、FOLLOW集合；（2）.构造拓广文法的项目集规范族，并构造出识别所有前缀的DFA；（3）构造文法的LR分析表；（4）由此构造LR分析程序。2.数据结构：1.输入缓冲区为一个字符型数组，读入输入的算术表达式并保存在此，以’$’结束；2.构建一个相对应的整型数组，将输入缓冲区中的字符转换为相应的代号并保存；3.构造一个结构体，以保存文法的某个产生式，该结构包括三个元素：整形变量，保存产生式左部非终结符代号。整型数组，保存产生式右部字符串的代号。整型变量，保存产生式右部长度；4.定义该结构的数组，保存文法的所有产生式；5.定义两个二维整形数组，goto和action，其值大于零代表移进操作，小于零代表规约操作，引进的状态或规约用到的产生式又绝对值表示。等于零代表出现错误。等于特殊值999代表acc.状态。3.计算过程：文法对应的拓广文法为：1S-E2E-E+T3E-E-T4E-T5T-T*F6T-T/F7T-F8F-(E)9F-id10F-num求的各个非终结符的FIRST、FOLLOW集合为：FIRST(S)={id,num,(}FOLLOW(S)={$}FIRST(E)={id,num,(}FOLLOW(E)={$,+,-,)}FIRST(T)={id,num,(}FOLLOW(T)={$,+,-,*,/,)}FIRST(F)={id,num,(}FOLLOW(F)={$,+,-,*,/,)}构造项目集规范族：I0=closure({S-·E})={S-·E,E-·E+T,E-·E-T,E-·T,T-·T*F,T-·T/F,T-·F,F-·id,F-·(E),F-·num};从I0出发：I1=go(I0,E)=closure({S-E·,E-E·+T,E-E·-T})={S-E·,E-E·+T,E-E·-T};I2=go(I0,T)=closure({E-T·,T-T·*F,T-T·/F})={E-T·,T-T·*F,T-T·/F};I3=go(I0,F)=closure({T-F·})={T-F·};I4=go(I0,id)=closure({F-id·})={F-id·};I5=go(I0,()=closure({F-(·E)})={F-(·E),E-·E+T,E-·E-T,E-·T,T-·T*F,T-·T/F,T-·F,F-·id,F-·(E),F-·num};I6=go(I0,num)=closure({F-num·})={F-num·};从I1出发：I7=go(I1,+)=closure({E-E+·T})={E-E+·T,T-·T*F,T-·T/F,T-·F,F-·id,F-·(E),F-·num};I8=go(I1,-)=closure({E-E-·T})={E-E-·T,T-·T*F,T-·T/F,T-·F,F-·id,F-·(E),F-·num};从I2出发：I9=go(I2,*)=closure({T-T*·F})={T-T*·F,F-·id,F-·(E),F-·num};I10=go(I2,/)=closure({T-T/·F})={T-T/·F,F-·id,F-(E),F-·num};从I5出发：I11=go(I5,E)=closure({F-(E·),E-E·+T,E-E·-T})={F-(E·),E-E·+T,E-E·-T};从I7出发：I12=go(I7,T)=closure({E-E+T·,T-T·*F,T-T·/F})={E-E+T·,T-T·*F,T-T·/F};从I8出发：I13=go(I8,T)=closure({E-E-T·,T-T·*F,T-T·/F})={E-E-T·,T-T·*F,T-T·/F};从I9出发：I14=go(I9,F)=closure({T-T*F·})={T-T*F·};从I10出发：I15=go(I10,F)=closure({T-T/F·})={T-T/F·};从I11出发：I16=go(I11,))=closure({F-(E)·})={F-(E)·};下面构造文法的LR分析表：goto[0,E]=1;goto[0,T]=2;goto[0,F]=3;action[0,id]=S4;action[0,(]=S5;action[0,num]=S6;action[1,$]=ACC.;action[1,+]=S7;action[1,-]=S8;;action[2,)]=action[2,+]=action[2,-]=action[2,$]=R4;action[2,*]=S9;action[2,/]=S10;action[3,)]=action[3,+]=action[3,-]=action[3,*]=action[3,/]=action[3,$]=R7;action[4,)]=action[4,+]=action[4,-]=action[4,*]=action[4,/]=action[4,$]=R8;goto[5,E]=11;goto[5,T]=2;goto[5,F]=3;action[5,id]=S4;action[5,(]=S5;action[5,num]=S6;action[6,)]=action[6,+]=action[6,-]=action[6,*]=action[6,/]=action[6,$]=R10;goto[7,T]=12;goto[7,F]=3;action[7,id]=S4;action[7,(]=S5;action[7,num]=S6;goto[8,T]=13;goto[8,F]=3;action[8,id]=S4;action[8,(]=S5;action[8,num]=S6;goto[9,F]=14;action[9,id]=S4;action[9,(]=S5;action[9,num]=S6;goto[10,F]=15;action[10,id]=S4;action[10,(]=S5;action[10,num]=S6;action[11,)]=S16;action[11,+]=S7;action[11,-]=S8;action[12,)]=action[12,+]=action[12,-]=action[12,$]=R2;action[12,*]=S9;action[12,/]=S10;action[13,)]=action[13,+]=action[13,-]=action[13,$]=R3;action[13,*]=S9;action[13,/]=S10;action[14,)]=action[14,+]=action[14,-]=action[14,*]=action[14,/]=action[14,$]=R5;action[15,)]=action[15,+]=action[15,-]=action[15,*]=action[15,/]=action[15,$]=R6;action[16,)]=action[16,+]=action[16,-]=action[16,*]=action[16,/]=action[16,$]=R9;4.SLR(1)分析表为：E1:缺少运算对象。认为加入一个Id入栈并转移至相应状态E2:括号不匹配删掉右括号，则删去右括号并转移至相应状态E3:缺少运算符，添加运算符并转移至相应状态actiongoto()+-*/idnum$ETF0s5E2E1E1E1E1s4s6E11231E3E2s7s8E3E3Acc.2E3r4r4r4s9s10E3E3r43r7r7r7r7r7r74r8r8r8r8r8r85s5E2E1E1E1E1s4s611236E3r10r10r10r10r10r107s5E2E1E1E1E1s4s61238s5E2E1E1E1E1s4s61339s5E2E1E1E1E1s4s61410s5E2E1E1E1E1s4s61511E3s16s7s8E3E312E3r2r2r2s2s2E3E3r213E3r3r3r3s9s10E3E3r314r5r5r5r5r5r515r6r6r6r6r6r616r9r9r9r9r9r9三、实验程序设计说明1.主要函数说明voidTRANS();/*将读入的buffer数组内容按字符转换为相应代号存入code数组*/voidGetFromCode();/*取得当前输入符号串的元素*/voidPUSH(intA,intS);/*入栈操作*/voidPOP();/*出栈操作*/voidSHITF();/*移入操作*/voidREDUCE();/*规约操作*/voidACC();/*接受操作*/voidERROR();/*错误处理*/voidE1();/*错误处理*/voidE2();voidE3();2.源程序代码#includestdlib.h#includestdio.h#includestring.hintsymbol,status;/*移入或规约时压入分析栈的符号、移入或规约操作后转而进入的状态*/intanalysis_stack[50];/*定义分析栈*/intip=-1;/*ip为栈顶元素下标*/charbuffer[30];/*将输入符号串w保存于数组中*/intcode[30];/*将读入的字符串转换为代号形式*/intposition=0;/*position为code数组的下标*/intX;/*X为当前获取的输入符号的代号*/intflag=1;/*循环标志*/typedefstruct{/*定义文法产生式的结构*/intVn;/*文法产生式的左部非终结符的代码*/intStr[4];/*文法产生式右部的代码串*/intsize;/*文法产生式右部的长度*/}G;Gproduction[11]={/*该文法的所有产生式*/{0},{101,{0,102},1},/*S-E*/{102,{0,102,3,103},3},/*E-E+T*/{102,{0,102,4,103},3},/*E-E-T*/{102,{0,103},1},/*E-T*/{103,{0,103,5,104},3},/*T-T*F*/{103,{0,103,6,104},3},/*T-T/F*/{103,{0,104},1},/*T-F*/{104,{0,7},1},/*F-id*/{104,{0,1,101,2},3},/*F-(E)*/{104,{0,8},1},/*F-num*/};intGOTO[17][5]={/*LR分析表goto*/{0,0,1,2,3},/*0*/{0,0,0,0,0},/*1*/{0,0,0,0,0},/*2*/{0,0,0,0,0},/*3*/{0,0,0,0,0},/*4*/{0,0,11,2,3},/*5*/{0,0,0,0,0},/*6*/{0,0,0,12,3},/*7*/{0,0,0,13,3},/*8*/{0,0,0,0,14},/*9*/{0,0,0,0,15},/*10*/{0,0,0,0,0},/*11*/{0,0,0,0,0},/*12*/{0,0,0,0,0},/*13*