编译原理实验报告《LL(1)语法分析器构造》（推荐文档）

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\

cout<

\