📄 ll1.c
字号:
/**
20031401008 褚超
实验三 LL(1)语法分析
编写为某一任意上下文无关文法构造的LL(1)语法分析程序，并对任给的一个输入串进行语法分析检查。
程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已
知的语法规则，如果不符合（编译出错），则输出错误信息。
注意:本程序不具备判断输入的文法是否为LL1文法的功能,所以在进行测试时请确保输入的文法是LL1文法
在输入文法过程中请按提示进行操作
程序测试示例文法:
E->aH
H->aMd
H->d
M->Ab
M->^
A->aM
A->e
程序测试数据:aaebd
(可以选用任何LL1文法以及符合该文法的输入串进行测试)
**/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
/*产生式类型定义*/
typedef struct type
{
char origin; /*大写字符*/
char array[5]; /*产生式右边字符*/
int length; /*字符个数*/
}type;
/*各个非终结符的信息*/
typedef struct info
{
int isNull; /*能否推出"空"? 1是 0否*/
char firstSet[10];
char followSet[10];
}info;
int n1; /*文法中产生式的个数*/
int numOfVn,numOfVt; /*记录VN和VT的个数*/
char VN[10],VT[10]; /*非终结符和终结符表*/
char select[10][10]; /*各个产生试的SELECT集*/
type table[10][10]; /*预测分析表*/
int j=0,b=0,top=0,l; /*L为输入串长度*/
char A[20]; /*分析栈*/
char B[20]; /*剩余串*/
/* 获取由用户输入的文法的产生式,保存到所定义的数据结构中,在此过程中可以顺便搜集非终结符列表 */
void getLL1(type ll1[]);
void print() /*输出分析栈*/
{
int a; /*指针*/
for(a=0;a<=top+1;a++)
printf("%c",A[a]);
printf("\t\t");
} /*print*/
void print1() /*输出剩余串*/
{
int j;
for(j=0;j<b;j++) /*输出对齐符*/
printf(" ");
for(j=b;j<=l;j++)
printf("%c",B[j]);
printf("\t\t\t");
}/*print1*/
/*返回某一非终结符在表中的序号*/
int inVN(char c)
{
int i;
for (i=0;i<numOfVn;i++)
{
if (c==VN[i])
{
return i;
}
}
return -1;
}
/*返回某一终结符在表中的序号*/
int inVT(char c)
{
int i;
for (i=0;i<numOfVt;i++)
{
if (c==VT[i])
{
return i;
}
}
return -1;
}
/*辅助函数:若字符c不在s中，则将c加入s*/
void addIn1(char s[],char c,int *flag)
{
int i,len,tag=1;
len=strlen(s);
for (i=0;i<len;i++)
{
if (s[i]==c)
{
tag=0;
break;
}
}
if (tag)
{
s[len]=c;
s[len+1]='\0';
*flag=1;
}
}
/*辅助函数:将s2中不存在与s1中的字符加入到s1中*/
void addIn2(char s1[],char s2[],int *flag)
{
int i,len;
len=strlen(s2);
for (i=0;i<len;i++)
{
addIn1(s1,s2[i],flag);
}
}
/* 扫描每条产生式,求出能推出"空的" VN ,在此过程中可以顺便搜集终结符列表 */
void getNULL(type ll1[],info infoVn[]);
/* 计算各非终结符的First集 */
void getFirst(type ll1[],info infoVn[]);
/* 计算各非终结符的Follow集 */
void getFollow(type ll1[],info infoVn[]);
/* 根据计算出来的First,Follow集求解各个产生式的SELECT
构造LL1的预测分析表
*/
void setTable(type ll1[],info infoVn[]);
/* 对输入的文法串进行分析扫描的主控程序 */
void doScan();
void main()
{
int i,m,n;
type ll1[15];
info infoVn[10];
getLL1(ll1);
getNULL(ll1,infoVn);
getFirst(ll1,infoVn);
getFollow(ll1,infoVn);
for(m=0;m<numOfVn;m++) /*初始化分析表*/
for(n=0;n<numOfVt;n++)
table[m][n].origin='N'; /*全部赋为空*/
setTable(ll1,infoVn);
printf("能推出空的非终结符有:");
for (i=0;i<numOfVn;i++)
{
if (infoVn[i].isNull==1)
{
printf("%3c",VN[i]);
}
}
printf("\n");
for (i=0;i<numOfVn;i++)
{
printf("FIRST(%c)=%s\n",VN[i],infoVn[i].firstSet);
}
printf("\n");
for (i=0;i<numOfVn;i++)
{
printf("FOLLOW(%c)=%s\n",VN[i],infoVn[i].followSet);
}
printf("\n");
doScan();
}
/* 获取由用户输入的文法的产生式,保存到所定义的数据结构中 */
void getLL1(type ll1[])
{
int n,i,k=0,flag=0;
char l,r[10];
printf("请输入文法的产生式个数:\n");
scanf("%d",&n);
getchar();
n1=n;
for (i=0;i<n;i++)
{
flag=0;
printf("输入第%d条产生式的左部:\n",i+1);
scanf("%c",&l);
getchar();
ll1[i].origin=l;
printf("输入第%d条产生式的右部(默认不超过10个字符):\n",i+1);
scanf("%s",r);
getchar();
strcpy(ll1[i].array,r);
ll1[i].length=strlen(ll1[i].array);
addIn1(VN,l,&flag);
}
numOfVn=strlen(VN);
printf("您所输入的文法为:\n");
for (i=0;i<n;i++)
{
printf("%c->%s\n",ll1[i].origin,ll1[i].array);
}
}
/* 扫描每条产生式,求出能推出"空的" VN ,在此过程中可以顺便搜集终结符列表 */
void getNULL(type ll1[],info infoVn[])
{
int i,j,m,flag[10],flag1=0,flag2=1,flag3=1,k=0,len;
int isModified[10];
for (i=0;i<10;i++)
{
flag[i]=1;
}
/*将每一非终结符能否推出"空"的标记置为未定*/
for (i=0;i<numOfVn;i++)
{
infoVn[i].isNull=-1;
}
/*第一遍扫描，删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的产生式都被删除，则该非终结符不能推出空*/
/*在此过程中可以搜集终结符表*/
for (i=0;i<n1;i++)
{
/*产生式右部为空的非终结符当然可以推出空*/
if( ll1[i].array[0]=='^' )
{
infoVn[inVN(ll1[i].origin)].isNull=1;
/*删除该非终结符的所有产生式*/
for (m=0;m<n1;m++)
{
if (ll1[i].origin == ll1[m].origin)
{
flag[m]=0;
}
}
}
for(j=0;j<ll1[i].length;j++)
{
flag1=0;
if ( (!isupper(ll1[i].array[j])) && ll1[i].array[j]!='^' )
{
flag[i]=0; /*删除所有右部含有终结符的产生式,将对应的标志置0*/
infoVn[inVN(ll1[i].origin)].isNull=0;
/*搜集终结符*/
addIn1(VT,ll1[i].array[j],&flag1);
}
}
}
addIn1(VT,'#',&flag1);
numOfVt=strlen(VT);
for (i=0;i<numOfVn;i++)
{
isModified[i]=infoVn[i].isNull;
}
/*flag3用来标记是否停止扫描(到非终结符对应的特征没有变化为止)*/
while(flag3)
{
/*扫描产生式右部的每一符号*/
flag3=0;
for (i=0;i<n1;i++)
{
len=ll1[i].length;
for (j=0;j<ll1[i].length;j++)
{
if (isupper(ll1[i].array[j]))
{
if (infoVn[inVN(ll1[i].array[j])].isNull==1)
{
len--;
}
else if (infoVn[inVN(ll1[i].array[j])].isNull==0)
{
flag[i]=0;
for (k=0;k<n1;k++)
{
/*某一VN的产生式在扫描过程中是否都被删除?*/
if ( inVN(ll1[i].array[j]) == inVN(ll1[k].origin) )
{
if(flag[k]==1)
flag2=0;
}
}
if (flag2)
{
infoVn[inVN(ll1[i].array[j])].isNull=0;
}
}
}
}
/*某项产生式长度能减为0?*/
if (len==0)
{
infoVn[inVN(ll1[i].origin)].isNull=1;
/*删除该非终结符的所有产生式*/
for (m=0;m<n1;m++)
{
if (ll1[i].origin == ll1[m].origin)
{
flag[m]=0;
}
}
}
}
for (i=0;i<numOfVn;i++)
{
if ( isModified[i]!=infoVn[i].isNull )
{
flag3=1;
isModified[i]=infoVn[i].isNull;
//break;
}
}
}
}
/* 计算各非终结符的First集 */
void getFirst(type ll1[],info infoVn[])
{
int i,j,k,l,m,length,flag1=1;
/*将各非终结符的FIRST集合初始化为空串*/
for (i=0;i<numOfVn;i++)
{
infoVn[i].firstSet[0]='\0';
}
while (flag1)
{
flag1=0;
for (i=0;i<n1;i++)
{
for (j=0;j<ll1[i].length;j++)
{
if ( !isupper(ll1[i].array[j]) )
{
break;
}
}
/*某条产生式的第一个字符是非VT或为空*/
if (j==0)
{
addIn1(infoVn[inVN(ll1[i].origin)].firstSet,ll1[i].array[0],&flag1);
}
/*如果产生式右部以VN开头,则定位到不能推出空的VN*/
else
{
for (k=0;k<j;k++)
{
if (infoVn[inVN(ll1[i].array[k])].isNull != 1)
{
break;
}
}
/*处理书中算法所列的情况⑤*/
if (k==ll1[i].length)
{
for (l=0;l<k;l++)
{
addIn2(infoVn[inVN(ll1[i].origin)].firstSet,infoVn[inVN(ll1[i].array[l])].firstSet,&flag1);
}
}
/*处理书中算法所列的情况④*/
else
{
for (l=0;l<k;l++)
{
length=strlen(infoVn[inVN(ll1[i].array[l])].firstSet);
for (m=0;m<length; m++)
{
if (infoVn[inVN(ll1[i].array[l])].firstSet[m] != '^')
{
addIn1(infoVn[inVN(ll1[i].origin)].firstSet,infoVn[inVN(ll1[i].array[l])].firstSet[m],&flag1);
}
}
}
addIn2(infoVn[inVN(ll1[i].origin)].firstSet,infoVn[inVN(ll1[i].array[k])].firstSet,&flag1);
}
}
}
}
}
/* 计算各非终结符的Follow集 */
void getFollow(type ll1[],info infoVn[])
{
int i,j,k,l,m,n,length,flag;
char ch;
/*将各非终结符的FOLLOW集合初始化为空串*/
for (i=0;i<numOfVn;i++)
{
infoVn[i].followSet[0]='\0';
}
addIn1(infoVn[0].followSet,'#',&flag);
while (flag)
{
flag=0;
for (i=0;i<n1;i++)
/*扫描每条产生式*/
{
for (j=0;j<ll1[i].length;j++)
{
/*找到该VN后第一个不能推出空的字符*/
if (isupper(ll1[i].array[j]))
{
for (k=j+1;k<ll1[i].length;k++)
{
if ( !isupper(ll1[i].array[k]) )
{
break;
}
}
/*紧跟某VN后的是一个VT*/
if (k==j+1 && k<ll1[i].length)
{
addIn1(infoVn[inVN(ll1[i].array[j])].followSet,ll1[i].array[k],&flag);
//continue;
}
else
{
for (l=j+1;l<k;l++)
{
if (infoVn[inVN(ll1[i].array[l])].isNull!=1)
{
break;
}
}
/*P82 算法的②中第2点*/
if (l == ll1[i].length)
{
addIn2(infoVn[inVN(ll1[i].array[j])].followSet,infoVn[inVN(ll1[i].origin)].followSet,&flag);
for (m=j+1;m<l;m++)
{
length=strlen(infoVn[inVN(ll1[i].array[m])].firstSet);
for (n=0;n<length;n++)
{
if ( (ch=infoVn[inVN(ll1[i].array[m])].firstSet[n])!='^' )
{
addIn1(infoVn[inVN(ll1[i].array[j])].followSet,ch,&flag);
}
}
}
}
else
{
for (m=j+1;m<=l;m++)
{
length=strlen(infoVn[inVN(ll1[i].array[m])].firstSet);
for (n=0;n<length;n++)
{
if ( (ch=infoVn[inVN(ll1[i].array[m])].firstSet[n])!='^' )
{
addIn1(infoVn[inVN(ll1[i].array[j])].followSet,ch,&flag);
}
}
}
}
}
}
}
}
}
}
/*
根据计算出来的First,Follow集求解各个产生式的SELECT
构造LL1的预测分析表
*/
void setTable(type ll1[],info infoVn[])
{
int i,j,k,l,m,n,flag,flag1=0,flag2=0,length;
char ch;
for (i=0;i<n1;i++)
{
/*扫描各产生式,计算SELECT集*/
if (!isupper(ll1[i].array[0]))
{
/*对 A->^ 类型的产生式的处理*/
if (ll1[i].array[0]=='^')
{
addIn2(select[i],infoVn[inVN(ll1[i].origin)].followSet,&flag);
}
/*产生式第一个字符是VT*/
else
addIn1(select[i],ll1[i].array[0],&flag);
}
else
{
for (j=0;j<ll1[i].length;j++)
{
if (isupper(ll1[i].array[j]))
{
length=strlen(infoVn[inVN(ll1[i].array[j])].firstSet);
for (k=0;k<length;k++)
{
if ( (ch=infoVn[inVN(ll1[i].array[j])].firstSet[k])!='^' )
{
addIn1(select[i],ch,&flag);
}
}
if (infoVn[inVN(ll1[i].array[j])].isNull != 1)
{
flag1=1;
break;
}
}
else
{
flag2=1;
break;
}
}
/*处理像E->ABaβ的产生式的情况,游标j扫描到a时停止*/
if ((!flag1) && flag2)
{
addIn1(select[i],ll1[i].array[j],&flag);
}
/*处理像E->β的产生式的情况,其中β可以推出空*/
if (j==ll1[i].length)
{
addIn2(select[i],infoVn[inVN(ll1[i].origin)].followSet,&flag);
}
}
}
for (i=0;i<n1;i++)
{
length=strlen(select[i]);
for (j=0;j<length;j++)
{
table[inVN(ll1[i].origin)][inVT(select[i][j])]=ll1[i];
}
}
}
/* 对输入的文法串进行分析扫描的主控程序 */
void doScan()
{
char ch,x;
int m,n,k=0,flag=0,finish=0;
type cha;
printf("\n请输入要分析的字符串(以'#'结束):");
do/*读入分析串*/
{
scanf("%c",&ch);
if (inVT(ch)==-1)
{
printf("输入串中有非法字符\n");
exit(1);
}
B[j]=ch;
j++;
}while(ch!='#');
l=j; /*分析串长度*/
ch=B[0]; /*当前分析字符*/
//printf("\n%c\n",ch);
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<numOfVt;j++) /*判断是否为终结符*/
{
if(x==VT[j])
{
flag=1;
break;
}
}
if(flag==1) /*如果是终结符*/
{
if(x=='#')
{
finish=1; /*结束标记*/
printf("acc!\n"); /*接受*/
getchar();
getchar();
exit(1);
}/*if*/
else 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<numOfVn;j++)
{
if(x==VN[j])
{
m=j; /*行号*/
break;
}
}
for(j=0;j<numOfVt;j++)
{
if(ch==VT[j])
{
n=j; /*列号*/
break;
}
}
cha=table[m][n];
if(cha.origin!='N') /*判断是否为空*/
{
print();
print1();
printf("%c->",cha.origin);/*输出产生式*/
for(j=0;j<cha.length;j++)
printf("%c",cha.array[j]);
printf("\n");
for(j=(cha.length-1);j>=0;j--) /*产生式逆序入栈*/
A[++top]=cha.array[j];
if(A[top]=='^') /*为空则不进栈*/
top--;
}/*if*/
else /*出错处理*/
{
print();
print1();
printf("%c出错\n",x); /*输出出错非终结符*/
exit(1);
}/*else*/
}/*else*/
}while(finish!=1);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -