实验二：自底向上语法分析算法程序设计实验内容：根据课堂讲授的自底向上语法分析方法，可以根据简单优先语法分析算法、算符优先语法分析算法或LR语法分析算法设计语法分析程序，针对文法：G[E]E→E+T | TT→T*F | FF→( E ) | i1.设计过程:自底向上语法分析含义：自底向上分析过程是从所给输入串出发，对其进行最左归约的过程。
自底向上归约的过程也是自底向上构建语法树的过程●设计主要思想:–从输入串出发;–尽可能地找到可归约子串并将其归约成一个非终极符;–直到归约成文法的开始符或发现语法错误;●分析动作:移入(shift),归约(reduce)●包含以下方法:–LR 类的方法; 简单优先法; 算符优先法●关键问题:–什么时候进行归约，按照哪条产生式进行归约;2.设计内容:程序流程图：3. 程序关键代码:#include <stdio.h>int flag;//初始化变量char m[20]={'+','*','^','i','(',')','#'};chart[20][20]={{'>','<','<','<','<','>','>'},{'>','>','<', '<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>',' >','n','n','>','>'},{'<','<','<','<','<','=','n'},{'>','>' ,'>','n','n','>','>'},{'<','<','<','<','<','n','='}};int termin(char arr[20],char c); //函数：判断是否终结符char compare(char xarr[20][20],char c1,char c2); //函数：比较两个终结符之间的优先关系void error();main (){printf("请输入字符串并以#结束\n:");char str[50];char a,q;char s[50];int k,j,n;scanf("%s",str);s[0]='n';flag=0;n=0;k=1;s[k]='#';do //读取输入的字符串到#号结束{a=str[n];if (termin(m,a)>=0)n++;else{error();return(0);}if (termin(m,s[k])>=0)j=k;elsej=k-1;while (compare(t,s[j],a)=='>'){do{q=s[j];if ((j-1)<=0){error();return(0);}if (termin(m,s[j-1])>=0){j=j-1;}elsej=j-2;}while (compare(t,s[j],q)!='<');k=j+1;s[k]='N';}if((compare(t,s[j],a)=='<')||(compare(t,s[j],a)= ='=')){k=k+1;s[k]=a;}elseerror();}while (a!='#');if (!flag)printf("The sentence is legal!\n");}int termin(char arr[20],char c){int i=0;int l=0;while (arr[i]!='\0'){if (arr[i]==c){l=1;break;}i=i+1;}if (l==1)return(i);elsereturn(-1);}char compare(char xarr[20][20],char c1,char c2)//比较两个终结符之间的优先关系{int i,j;char r;i=termin(m,c1);j=termin(m,c2);r=xarr[i][j];return(r);}void error() //通过flag来判断字符串是否非法{flag=1;printf("The sentence is not legal\n!");}4.实验结果:上图输入的字符串虽符合要求,但是进行运行分析是发现不能进行规约,结果错误非法.5.实验总结：通过实验知道了采用自底向上分析方法对输入的字符串进行语法分析，进一步掌握最左归约的过程.。
