编译原理上机三

学号成绩编译原理上机报告上机题目编写语法分析分析器上机时间11月18日学院信息与控制工程学院专业计算机科学与技术班级计算机1301班姓名周砚豪一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。1、选择最有代表性的语法分析方法，如LL(1)语法分析程序、算符优先分析程序和LR分析分析程序，并至少完成两个题目。2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。二、实验过程（一）根据分析法总控制流程图，编写一个分析对象的语法分析程序。可根据自己的能力选择以下三项（由易到难）之一作为分析算法中的输入：1.直接输入根据已知文法人工构造的分析表M。2.输入已知文法的集合FIRST（x）和FOLLOW（U），由程序自动生成该文法的分析表M。3.输入已知文法，由程序自动生成该文法分析表M。??（二）程序具有通用性，即所编制的LL（1）语法分析程序能够适用于不同文法以及各种?输入单词串，并能判断该文法是否为算符文法和算符优先文法。??（三）有运行实例。对于输入的一个文法和一个单词串，所编制的语法分析程序应能正确地判断，此单词串是否为该文法的句子，并要求输出分析过程。??三、实验结果四、讨论与分析LL（1）文法的判定：对于文法G的每一个非终结符U的产生式：U→α1|α2|…|αn。如果文法G是一个LL(1)文法，则有SELECT(U→αi)∩SELECT(U→αj)=Ф(i≠j，i，j=1，2，…，n)。SELECT集的构造：SELECT(U→α)=?FIRST(α)，当α不空FIRST(α)∪FOLLOW(U)，否则LL（1）分析表构造算法：?对于每个产生式U→α，执行下一步骤：1、对于每个终结符号：a∈FIRST(α)，M[U，a]=?→α?;?2、如果e∈FIRST(α?)，对于每个终结符号：b∈FOLLOW(U)，M[U，b]=?→α?;?3、将其它未定义的分析元素置为ERROR。五、附录：关键代码/*LL(1)分析法源程序，只能在VC++中运行*/#include#include#include#includecharA[20];/*分析栈*/charB[20];/*剩余串*/charv1[20]={'i','+','*','(',')','#'};/*终结符*/charv2[20]={'E','G','T','S','F'};/*非终结符*/intj=0,b=0,top=0,l;/*L为输入串长度*/typedefstructtype/*产生式类型定义*/{charorigin;/*大写字符*/chararray[5];/*产生式右边字符*/intlength;/*字符个数*/}type;typee,t,g,g1,s,s1,f,f1;/*结构体变量*/typeC[10][10];/*预测分析表*/voidprint()/*输出分析栈*/{inta;/*指针*/for(a=0;a=top+1;a++)printf(%c,A[a]);printf(\t\t);}/*print*/voidprint1()/*输出剩余串*/{intj;for(j=0;jb;j++)/*输出对齐符*/printf();for(j=b;j=l;j++)printf(%c,B[j]);printf(\t\t\t);}/*print1*/voidmain(){intm,n,k=0,flag=0,finish=0;charch,x;typecha;/*用来接受C[m][n]*//*把文法产生式赋值结构体*/='E';strcpy,TG);=2;='T';strcpy,FS);=2;='G';strcpy,+TG);=3;='G';[0]='^';=1;='S';strcpy,*FS);=3;='S';[0]='^';=1;='F';strcpy,(E));=3;='F';[0]='i';=1;for(m=0;m=4;m++)/*初始化分析表*/for(n=0;n=5;n++)C[m][n].origin='N';/*全部赋为空*//*填充分析表*/C[0][0]=e;C[0][3]=e;C[1][1]=g;C[1][4]=g1;C[1][5]=g1;C[2][0]=t;C[2][3]=t;C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;C[4][0]=f1;C[4][3]=f;printf(提示:本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析,\n);printf(请输入要分析的字符串:);do/*读入分析串*/{scanf(%c,&ch);if((ch!='i')&&(ch!='+')&&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')){printf(输入串中有非法字符\n);exit(1);}B[j]=ch;j++;}while(ch!='#');l=j;/*分析串长度*/ch=B[0];/*当前分析字符*/A[top]='#';A[++top]='E';/*'#','E'进栈*/printf(步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n);do{x=A[top--];/*x为当前栈顶字符*/printf(%d,k++);printf(\t\t);for(j=0;j=5;j++)/*判断是否为终结符*/if(x==v1[j]){flag=1;break;}if(flag==1)/*如果是终结符*/{if(x=='#'){finish=1;/*结束标记*/printf(acc!\n);/*接受*/getchar();getchar();exit(1);}/*if*/if(x==ch){print();print1();printf(%c匹配\n,ch);ch=B[++b];/*下一个输入字符*/flag=0;/*恢复标记*/}/*if*/else/*出错处理*/{print();print1();printf(%c出错\n,ch);/*输出出错终结符*/exit(1);}/*else*/}/*if*/else/*非终结符处理*/{for(j=0;j=4;j++)if(x==v2[j]){m=j;/*行号*/break;}for(j=0;j=5;j++)if(ch==v1[j]){n=j;/*列号*/break;}cha=C[m][n];if!='N')/*判断是否为空*/{print();print1();printf(%c-,;/*输出产生式*/for(j=0;j;j++)printf(%c,[j]);printf(\n);for(j=;j=0;j--)/*产生式逆序入栈*/A[++top]=[j];if(A[top]=='^')/*为空则不进栈*/top--;}/*if*/else/*出错处理*/{print();print1();printf(%c出错\n,x);/*输出出错非终结符*/exit(1);}/*else*/}/*else*/}while(finish==0);}/*main*/六、实验者自评在LL（1）分析器的编写中我只达到了最低要求，就是自己手动输入的select集，first集，follow集然后通过程序将预测分析表构造出来了，并且没有做出对输入串的分析。通过本次试验，我能够设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。并且有能力选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。