实验要求如下:
实验 LL(1)型语法分析器
1.存放文法、产生规则 （二维数组）
2。由规则产生LL(1)预测表
3。建立堆栈、队列
4。形成分析程序
5。以下面的文法为例：
E->TM
M->+TM
M->ε
T->FN
N->*FN
N->ε
F->(E)
F->id
程序如下:(附件为该程序的代码)
#include<iostream.h>
#include<iomanip.h>
#include<string.h>
int M_first[6][13],M_follow[6][13];//定义求解first&follow的数组
char MR[6][13]={" EMTNFi+*()$","E","M","T","N","F"};
char sheet[6][70];
int lenG[8];//求解文法每个产生式长度的变量
/**********************first函数****************************/
void first(char G1[8][5])
{
int i,j,m,n;
char MS[6][13]={" EMTNFi+*()#","E","M","T","N","F"};
int M_first1[6][13]={0};
//求M_first初值，如果一个字符属于first（A）中，则A与该字符在数组矩阵中对应关系为1
for(i=0;i<=7;i++)
for(m=1;m<=5;m++)
if(MS[m][0]==G1[i][0])
for(n=1;n<=11;n++)
if(MS[0][n]==G1[i][1])
M_first1[m][n]=1;
//求整理后的M_first值（即：若有E->TM,则将first（T）加入first（E）中
for(i=5;i>=1;i--)
for(j=1;j<=5;j++)
if(M_first1[i][j]==1)
for(m=1;m<=11;m++)
M_first1[i][m]=M_first1[i][m]||M_first1[j][m];
//将M_first1的值赋给M_first
for(i=0;i<=5;i++)
for(j=0;j<=12;j++)
M_first[i][j]=M_first1[i][j];
//输出first的值：
cout<<"求得first值如下："<<endl;
for(i=1;i<=5;i++)
{
cout<<"first("<<MS[i][0]<<")={";
for(j=6;j<=11;j++)
if(M_first1[i][j]==1)cout<<MS[0][j]<<",";
cout<<"\b}"<<endl;
}
}
/************************follow函数*************************/
void follow(char G2[8][5],int M_first2[6][13])
{
int i,j,m,n;
int M_follow1[6][13]={0};
M_follow1[1][11]=1;//若A是开始符号，则$属于follow（A）
//求初始条件下的follow值（如果有A=>*…BC…，则B与C的对应关系为1，即C属于follow（B））
for(i=0;i<=7;i++)
for(j=1;j<=lenG[i];j++)
for(m=1;m<=5;m++)
if(MR[m][0]==G2[i][j])
for(n=1;n<=11;n++)
{
if(MR[0][n]==G2[i][j+1])
M_follow1[m][n]=1;
if(G2[i][lenG[i]-1]==MR[m][0])
M_follow1[m][11]=1;
}
//E->TM情况下将first（M）加入到follow（T）中:
for(i=5;i>=1;i--)
for(j=1;j<=5;j++)
if(M_follow1[i][j]==1)
for(m=1;m<=11;m++)
M_follow1[i][m]=M_follow1[i][m]||M_first2[j][m];
//E->TM,M->#下将follow（E）都加入到follow（T）的情况:
for(i=0;i<=7;i++)
for(j=1;j<=lenG[i];j++)
if(G2[i][j]>='A'&&G2[i][j]<='Z'&&G2[i][j+1]>='A'&&G2[i][j+1]<='Z')
for(m=1;m<=5;m++)
for(n=1;n<=5;n++)
if(MR[m][0]==G2[i][j]&&MR[0][n]==G2[i][j+1]&&M_first2[n][11]==1)
for(int k=1;k<=5;k++)
if(MR[k][0]==G2[i][0])
for(int l=6;l<=11;l++)
M_follow1[m][l]=M_follow1[m][l]||M_follow1[k][l];
//E->TM，将follow（E）都加入到follow（M）的情况:
for(i=0;i<=7;i++)
for(m=1;m<=5;m++)
if(MR[m][0]==G2[i][0])
for(n=1;n<=5;n++)
if(MR[n][0]==G2[i][lenG[i]-1])
for(j=6;j<=12;j++)
M_follow1[n][j]=M_follow1[n][j]||M_follow1[m][j];
for(i=0;i<=5;i++)
for(j=0;j<=12;j++)
M_follow[i][j]=M_follow1[i][j];
//输出所求folow的值
cout<<"求得follow值如下："<<endl;
for(i=1;i<=5;i++)
{
cout<<"follow("<<MR[i][0]<<")={";
for(j=6;j<=11;j++)
if(M_follow1[i][j]==1)cout<<MR[0][j]<<",";
cout<<"\b}"<<endl;
}
}
/*****************************构造分析表*******************************/
void analysis_sheet(char G1[8][5],int M_first3[6][13],int M_follow2[6][13])
{
int i,j,m,n=0;
char sheet[6][70]={""};
for(i=6;i<=11;i++)
sheet[0][n=n+10]=MR[0][i];
for(i=1;i<=5;i++)
sheet[i][0]=MR[i][0];
//分析表求解
for(i=1;i<=5;i++)
{
//first中不含空集的情况
for(int j1,j=1;j<=5;j++)
if(M_first3[i][j+5]==1)
for(m=0;m<=7;m++)
{
if(G1[m][0]==MR[i][0]&&G1[m][1]!='#')
{
if(G1[m][0]==G1[m+1][0]&&G1[m][1]!=MR[0][j+5])
continue;
j1=j*10;
sheet[i][j1]=G1[m][0];
sheet[i][j1+1]='-';
sheet[i][j1+2]='>';
for(n=1;n<lenG[m];n++)
sheet[i][j1+n+2]=G1[m][n];
break;
}
}
//first中包含空集的情况
if(M_first3[i][11]==1)
for(m=1;m<=6;m++)
if(M_follow2[i][m+5]==1)
{
sheet[i][10*m]=sheet[i][0];
sheet[i][10*m+1]='-';
sheet[i][10*m+2]='>';
sheet[i][10*m+3]='#';
}
}
//输出分析表
cout<<setw(45)<<"文法（3.8）的分析表如下："<<endl;
cout<<"________________________________________________________________"<<endl;
cout<<setw(8)<<"非终结符"<<setw(30)<<"输入符号"<<endl;
cout<<setw(64)<<"________________________________________________________"<<endl;
for(j=0;j<=5;j++)
{
for(i=0;i<70;i++)
cout<<sheet[j][i];
cout<<endl;
cout<<"________________________________________________________________"<<endl;
}
}
/*************************main函数**************************/
void main()
{
char G[8][5]={"ETM","M+TM","M#","TFN","N*FN","N#","F(E)","Fi"};
int i,j;
for(i=0;i<=7;i++)
lenG[i]=strlen(G[i]); //求文法中每个产生式的长度
cout<<"声明：该程序中，M，N，i，#分别代表文法3.8中的E'，T'，id，ε"<<endl;
cout<<"****************************************************************"<<endl;
cout<<"输入文法如下："<<endl;
for(i=0;i<=7;i++)
{
cout<<G[i][0]<<"→";
for(j=1;j<=lenG[i];j++)
cout<<G[i][j];
cout<<endl;
}
cout<<"****************************************************************"<<endl;
first(G);//调用first函数求first
cout<<"****************************************************************"<<endl;
follow(G,M_first);//调用follow函数求follow
cout<<"****************************************************************"<<endl;
analysis_sheet(G,M_first,M_follow);//调用求分析表数组函数
cout<<"****************************************************************"<<endl;
}

[此贴子已经被作者于2007-11-20 11:52:38编辑过]