编译原理LR(0)分析器(C语言)

数学与软件科学学院实验报告学期：2015至2016第2学期2016年5月2日课程名称：编译原理专业：信息与计算科学2013级5班实验编号：4实验名称：LR(0)分析器指导教师：王开端学生姓名：李丹学号：2013060510实验成绩：实验四LR(0)分析器实验目的：根据书本知识和查阅相关资料，设计一个LR(0)语法分析器。实验内容：设计一个LR(0)语法分析器，并判断语句i+i*i是否为文法G[E]的句子。文法G[E]如下：G[E]：iFEFFTFTTTETEE)(*实验步骤：1LR分析法LR分析法是一种自底向上进行的规范规约的语法分析方法，LR指“自左向右扫描和自底向上进行归约”。LR分析法的一个主要缺点是，若用手工构造分析器则工作量相当大，因此必须求助于自动产生LR分析器的产生器。2LR分析器LR分析器是一个DFA，应具有一个称为GOTO表的状态转换矩阵，GOTP[s,x]规定了状态栈栈顶s在在输入符号为x时所应转换的下一状态是什么；其次LR分析器还必须完成“移进—归约”操作，因此还应有一个称为ACTION表的操作动作表，且每一项ACTION[s,a]所规定的动作是以下四种情况之一：（1）移进：使栈顶状态s与当前扫描的输入符号a（终结符）的下一状态s’=ACTION[s,a]和输入符号a进栈，而下一个输入符号则变成当前扫描的输入符号。（2）归约：如果符号栈栈顶的符号串为α（自栈顶向下则为α的逆序）且文法中存在A，则将栈顶的符号串α用非终结符A替换，即实现将α归约为A。对状态栈来说，假定α中有个符号（即α的长度为），则状态栈栈顶的个状态序列恰好能识别符号串α，此时用产生式A进行归约。归约的动作是去掉栈顶的个状态项，然后使ms（ms为栈顶状态）与所归约的非终结符A的下一状态s’=GOTO[ms,A]和A分别进入状态栈和符号栈。（3）接受：分析工作成功，表明所分析的句子为文法所识别，此时分析器停止工作。（4）报错：发现所分析的句子不是文法所允许的句子，调用出错处理程序进行处理。LR分析器由分析栈、分析表和总控程序三部分组成，结构示意图如图1：图1LR(0)分析器结构图3文法G[E]的LR分析表本实现直接手工构造LR表，编写总控程序，文法G[E]的LR分析表如表1：表1文法G[E]的LR分析表状态ACTIONGOTOi+*()#ETF05s4s12316sacc22r7s2r2r34r4r4r4r45s4s82356r6r6r6r65s4s9375s4s1086s11s91r7s1r1r103r3r3r3r115r5r5r5r其中，js指把下一状态j和现行输入符号a移进栈；jr指按文法的第j个产生式进行归约；acc表示分析成功；空白格为出错。4i+i*i的LR分析过程表2i+i*i的LR分析过程表步骤状态栈符号栈输入串说明10#i+i*i#ACTION[0,i]，移进205#i+i*i#ACTION[5,+]，归约且GOTO[0,F]303#F+i*i#ACTION[3,+]，归约且GOTO[0,T]402#T+i*i#ACTION[2,+]，归约且GOTO[0,]501#E+i*i#ACTION[1,+]，移进6016#E+i*i#ACTION[6,i]，移进70165#E+i*i#ACTION[5,*]，归约且GOTO[6,F]80163#E+F*i#ACTION[3,*]，归约且GOTO[6,T]90169#E+T*i#ACTION[9,*]，移进1001697#E+T*i#ACTION[7,i]，移进11016975#E+T*i#ACTION[5,#]，归约且GOTO[7,F]120169710#E+T*F#ACTION[10,#]，归约且GOTO[6,T]130169#E+T#ACTION[9,#]，归约且GOTO[0,E]1401#E#ACTION[1,#]，acc：分析成功5流程图图2LR(0)分析器流程图6程序设计总控程序涉及到分析表和文法以及栈的输出等，本实验做了以下定义：二维数组sym[12][6]：用于存放分析表ACTION所代表的状态（s,r,acc或空白）二维数组snum[12][6]：用于存放分析表ACTION状态的下标，表示下一步执行情况二维数组go[12][3]：用于存放分析表GOTO中内容一维数组state[]：状态栈一位数组ch[]：符号栈一位数组str[]：输入串length：str数组大小l：数组state和ch的大小how：判断状态代码：#includestdio.h#includestring.hcharsym[12][6]={{'s','e','e','s','e','e'},{'e','s','e','e','e','a'},{'e','r','s','e','r','r'},{'e','r','r','e','r','r'},{'s','e','e','s','e','e'},{'e','r','r','e','r','r'},{'s','e','e','s','e','e'},{'s','e','e','s','e','e'},{'e','s','e','e','s','e'},{'e','r','s','e','r','r'},{'e','r','r','e','r','r'},{'e','r','r','e','r','r'}};/*createactiontable'sstate&'a'standforacc*/intsnum[12][6]={{5,0,0,4,0,0},{0,6,0,0,0,0},{0,2,7,0,2,2},{0,4,4,0,4,4},{5,0,0,4,0,0},{0,6,6,0,6,6},{5,0,0,4,0,0},{5,0,0,4,0,0},{0,6,0,0,11,0},{0,1,7,0,1,1},{0,3,3,0,3,3},{0,5,5,0,5,5}};/*createactiontable'sstatenumber*/intgo[12][3]={{1,2,3},{0,0,0},{0,0,0},{0,0,0},{8,2,3},{0,0,0},{0,9,3},{0,0,10},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};/*creategototable'sstate*/voidmain(){intstep=1;/*numberofanalysisstep*/intlength=0;/*lengthofstring*/inti,j,m,n;intl=0;/*lengthofstate&ch*/intk=0;intnum;intstate[6]={0};/*initialstatestack*/charch[6]={'#'};/*initialcharacterstack*/charstr[10];/*definearrayofstring*/charcha;charhow;/*howinclude's','r','a'andnull*/charA;clrscr();printf(Pleaseinputastring:);do{scanf(%c,&cha);str[length]=cha;length++;}while(cha!='#');/*inputastringandcalculateit'slength*/printf(\n-------------------------------------------------------------------------------\n);printf(Step\tState\t\tCharacter\tString\t\tAction\n);printf(-------------------------------------------------------------------------------\n);do{switch(str[k])/*judgestr[k]*/{case'i':j=0;break;case'+':j=1;break;case'*':j=2;break;case'(':j=3;break;case')':j=4;break;case'#':j=5;break;default:j=-1;break;}if(j!=-1){how=sym[state[l]][j];/*judgehow*/num=snum[state[l]][j];/*state'snumber*/if(how=='s'){printf(%d\t,step);/*outputstep*/for(i=0;i=l;i++)printf(%d,state[i]);/*outputstatestack*/if(l=3)printf(\t);elseprintf(\t\t);for(i=0;i=l;i++)printf(%c,ch[i]);/*outputcharacterstack*/printf(\t\t);for(i=0;ik;i++){str[i]='';printf(%c,str[i]);}for(i=k;ilength;i++)printf(%c,str[i]);/*outputstringstack*/printf(\t\t);printf(Pushstate%d!\n,num);/*outputaction*/l=l+1;state[l]=num;ch[l]=str[l-1];step=step+1;k=k+1;/*nextrotatevalue*/}/*ifhow=='s'*/elseif(how=='r'){printf(%d\t,step);for(i=0;i=l;i++)printf(%d,state[i]);if(l=3)printf(\t);elseprintf(\t\t);for(i=0;i=l;i++)printf(%c,ch[i]);printf(\t\t);for(i=0;ik;i++){str[i]='';printf(%c,str[i]);}for(i=k;ilength;i++)printf(%c,str[i]);printf(\t\t);switch(num)/*judgenum*/{case1:A='E',m=3;l=l-m;printf(E-E+T);break;case2:A='E',m=1;l=l-m;printf(E-T);break;case3:A='T',m=3;l=l-m;printf(T-T*F);break;case4:A='T',m=1;l=l-m;printf(T-F);break;case5:A='F',m=3;l=l-m;printf(F-(E));break;case6:A='F',m=1;l=l-m;printf(F-i);break;}switch(A)/*judgeA*/{case'E':n=0;break;case'T':n=1;break;case'F':n=2;break;}num=go[state[l]][n];printf(,push%d!\n,num);l=l+1;state[l]=num;ch[l]=A;step=step+1;k=k;}/*ifhow=='r'*/elseif(how=='a'){printf(%d\t,step);for(i=0;i=l;i++)printf(%d,state[i]);if(l=3)printf(\t);elseprintf(\t\t);for(i=0;i=l;i++)printf(%c,ch[i]);printf(\t\t);for(i=0;ik;i++){str[i]='';printf(%c,str[i]);}for(i=k;ilength;i++)printf(%c,str[i]);printf(\t\t);printf(acc!\n);exit(1)