发布时间 : 星期六 文章编译原理实验报告《LL(1)语法分析器构造》（推荐文档）更新完毕开始阅读4f0191bb53d380eb6294dd88d0d233d4b04e3f44
int* empty=new int [n];//指示非终结符能否推导到空串 int i,j,r;
for(r=0;r int step=100;//假设一条规则最大推导步数为100步 while(step--) { for(i=0;i r=U.find(P[i][0]); if(P[i][4]=='^') empty[r]=1;//直接推导到空 else { for(j=4;P[i][j]!=' ';j++) { if(U.find(P[i][j])!=string::npos) { if(empty[U.find(P[i][j])]==0) break; } else break; } if(P[i][j]==' ') empty[r]=1;//多步推导到空 else flag=0; } } } return empty; } string* FIRST_X(string* P,string U,string u,int* empty,int k,int n) { int i,j,r,s,tmp; string* first=new string[n]; char a; int step=100;//最大推导步数 while(step--){ // cout<<\ for(i=0;i //cout< 5 if(P[i][4]=='^'&&first[r].find('^')==string::npos) first[r].append(1,'^');//规则右部首符号为空 else { for(j=4;P[i][j]!=' ';j++) { a=P[i][j]; if(u.find(a)!=string::npos&&first[r].find(a)==string::npos)//规则右部首符号是终结符 { first[r].append(1,a); break;//添加并结束 } if(U.find(P[i][j])!=string::npos)//规则右部首符号是非终结符,形如X：：=Y1Y2...Yk { s=U.find(P[i][j]); //cout< for(tmp=0;first[s][tmp]!='\\0';tmp++) { a=first[s][tmp]; if(a!='^'&&first[r].find(a)==string::npos)//将FIRST[Y1]中的非空符加入 first[r].append(1,a); } } if(!empty[s]) break;//若Y1不能推导到空，结束 } if(P[i][j]==' ') if(first[r].find('^')==string::npos) first[r].append(1,'^');//若Y1、Y2...Yk都能推导到空，则加入空符号 } } } return first; } string FIRST(string U,string u,string* first,string s)//求符号串s=X1X2...Xn的FIRST集 { int i,j,r; char a; string fir; for(i=0;i if(s[i]=='^') fir.append(1,'^'); if(u.find(s[i])!=string::npos&&fir.find(s[i])==string::npos){ fir.append(1,s[i]);break;}//X1是终结符，添 6 加并结束循环 if(U.find(s[i])!=string::npos)//X1是非终结符 { r=U.find(s[i]); for(j=0;first[r][j]!='\\0';j++) { a=first[r][j]; if(a!='^'&&fir.find(a)==string::npos)//将FIRST(X1)中的非空符号加入 fir.append(1,a); } if(first[r].find('^')==string::npos) break;//若X1不可推导到空，循环停止 } if(i==s.length())//若X1-Xk都可推导到空 if(fir.find(s[i])==string::npos) //fir中还未加入空符号 fir.append(1,'^'); } return fir; } string** create_table(string *P,string U,string u,int n,int t,int k,string* first)//构造分析表，P为文法G的产生式构成的集合 { int i,j,p,q; string arfa;//记录规则右部 string fir,follow; string FOLLOW[5]={\ string **table=new string*[n]; for(i=0;i table[i][j]=\ \存储分析表的元素，“ ”表示error for(i=0;i arfa=P[i]; arfa.erase(0,4);//删除前4个字符，如：E::=E+T,则arfa=\ fir=FIRST(U,u,first,arfa); for(j=0;j p=U.find(P[i][0]); if(fir.find(u[j])!=string::npos) { q=j; table[p][q]=P[i]; }//对first（）中的每一终结符置相应的规则 7 } if(fir.find('^')!=string::npos) { follow=FOLLOW[p];//对规则左部求follow() for(j=0;j if((q=follow.find(u[j]))!=string::npos) { q=j; table[p][q]=P[i]; }//对follow（）中的每一终结符置相应的规则 } table[p][t]=P[i];//对#所在元素置相应规则 } } return table; } void analyse(string **table,string U,string u,int t,string s)//分析符号串s { string stack;//分析栈 string ss=s;//记录原符号串 char x;//栈顶符号 char a;//下一个要输入的字符 int flag=0;//匹配成功标志 int i=0,j=0,step=1;//符号栈计数、输入串计数、步骤数 int p,q,r; string temp; for(i=0;!s[i];i++) { if(u.find(s[i])==string::npos)//出现非法的符号 cout< s.append(1,'#'); stack.append(1,'#');//’#’进入分析栈 stack.append(1,U[0]);i++;//文法开始符进入分析栈 a=s[0]; //cout< cout<<\步骤 分析栈 余留输入串 所用产生式\\n\ while(!flag) { // cout<<\步骤 分析栈 余留输入串 所用产生式\\n\