LL(1)预测分析表
一．测试文法：（放在文件chanshengshi.txt中）
E->TA
A->+TA
A->~
T->FB
B->*FB
B->~
F->(E)
F->i
二．输出（在analysis_table.txt中）
产生式：
0:E->TA
1:A->+TA
2:A->~
3:T->FB
4:B->*FB
5:B->~
6:F->(E)
7:F->i
--------------------------------------------
first follow
E (i #)
A ~+ #)
T (i +#)
B ~* +#)
F (i *+#)
--------------------------------------------
预测分析表如下：
+ * ( ) i #
E ERROR ERROR 0 ERROR 0 ERROR
A 1 ERROR ERROR 2 ERROR 2
T ERROR ERROR 3 ERROR 3 ERROR
B 5 4 ERROR 5 ERROR 5
F ERROR ERROR 6 ERROR 7 ERROR
三．源码
/*
LL(1)预测分析表的构造，空字用符号~表示
This procedure is written by fanxiangchao.
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<malloc.h>
#define FALSE 0
#define TRUE 1
#define MAX 100
#define NULL 0
#define ERROR -1
/***********************定义结构体*********************************/
//1.定义非终结符的结构体
struct no_terminal_sign
{
char no_ter; //非终结符
char first[MAX]; //非终结符的first集合
char follow[MAX]; //非终结符的follow集合
};
//2.定义候选式的结构体
struct candidate_formular
{
char candidate[MAX]; //候选式串
char first[MAX]; //候选式的first集合
};
//3.定义产生式的结构体
typedef struct produce
{
char left; //产生式左部
char right[MAX]; //产生式右部
}chanshengshi;
//4.定义终结符的结构体
struct terminal_sign
{
char ter; //终结符
char first[MAX]; //终结符的first集合
};
/******************************************************************/
//函数定义
int is_include(char * a,char b)//一个终结符属于某个集合
{
int i;
for(i=0;a[i]!='\0';i++)
if(b==a[i])
return TRUE;
return FALSE;
}
void add_ter(char * a,char sign)//向一个集合中添加一个终结符
{
int length;
if(!is_include(a,sign)){
length=strlen(a);
a[length]=sign;
a[length+1]='\0';
}
}
void add_ter_to_first(struct no_terminal_sign * a,char sign)//向一个终结符的first集合中添加一个终结符
{
int length;
if(!is_include(a->first,sign)){
length=strlen(a->first);
a->first[length]=sign;
a->first[length+1]='\0';
}
}
void add_ter_to_candidate_first(struct candidate_formular * a,char sign)//向一个候选式的first集合中添加一个终结符
{
int length;
if(!is_include(a->first,sign)){
length=strlen(a->first);
a->first[length]=sign;
a->first[length+1]='\0';
}
}
void add_ter_to_follow(struct no_terminal_sign * a,char sign)//向一个终结符的follow集合中添加一个终结符
{
int length;
if(!is_include(a->follow,sign)){
length=strlen(a->follow);
a->follow[length]=sign;
a->follow[length+1]='\0';
}
}
int is_terminal(char sign,struct terminal_sign *a)//判断一个符号是终结符还是非终结符
{
struct terminal_sign * p;
if(sign=='~') return -1;
for(p=a;p->ter!=NULL;p++)
if(p->ter==sign)
return TRUE;
return FALSE;
}
int is_include_null(struct no_terminal_sign *a)//判断一个非终结符的first集合中包含空字
{
int i;
for(i=0;a->first[i]!='\0';i++)
if(a->first[i]=='~')
return TRUE;
return FALSE;
}
void subtract_null(char *a)//将一个集合减去空字
{
int i,mark;
for(i=0;a[i]!='\0';i++)
if(a[i]=='~')
break;
mark=i;
for(i=mark;i<(signed)strlen(a);i++)
a[i]=a[i+1];
}
void merge_to_first(struct no_terminal_sign * a,char *b)//将集合b添加到非终结符的first集合a中
{
int i,n;
n=strlen(a->first);
for(i=0;b[i]!='\0';i++)
if(!is_include(a->first,b[i]))
a->first[n++]=b[i];
a->first[n]='\0';
}
void merge_to_candidate_first(struct candidate_formular * a,char *b)//将集合b添加到候选式的first集合a中
{
int i,n;
n=strlen(a->first);
for(i=0;b[i]!='\0';i++)
if(!is_include(a->first,b[i]))
a->first[n++]=b[i];
a->first[n]='\0';
}
void merge_to_follow(struct no_terminal_sign * a,char *b)//将集合b添加到非终结符的first集合a中
{
int i,n;
n=strlen(a->follow);
for(i=0;b[i]!='\0';i++)
if(!is_include(a->follow,b[i]))
a->follow[n++]=b[i];
a->follow[n]='\0';
}
struct no_terminal_sign * search_by_sign(char sign,struct no_terminal_sign *a)//根据一个非终结符找到对应的结构体
{
struct no_terminal_sign *p;
for(p=a;p->no_ter!=NULL;p++)
if(p->no_ter==sign)
return p;
return NULL;
}
int sum_first(struct no_terminal_sign * a)//所有first集合元素的和
{
int sum=0;
struct no_terminal_sign * p;
for(p=a;p->no_ter!=NULL;p++)
sum+=strlen(p->first);
return sum;
}
int sum_follow(struct no_terminal_sign * a)//所有follow集合元素的和
{
int sum=0;
struct no_terminal_sign * p;
for(p=a;p->no_ter!=NULL;p++)
sum+=strlen(p->follow);
return sum;
}
struct candidate_formular * search_by_string(char * a,struct candidate_formular *b)//根据产生式右部找到候选式的结构体
{
struct candidate_formular *p;
for(p=b;p->candidate!=NULL;p++)
if(strcmp(p->candidate,a)==0)
return p;
return NULL;
}
int total_ter(struct terminal_sign *a)//终结符的个数
{
struct terminal_sign *p;
int n=0;
for(p=a;p->ter!=NULL;p++)
n++;
return n;
}
int total_no_ter(struct no_terminal_sign *a)//非终结符的个数
{
struct no_terminal_sign *p;
int n=0;
for(p=a;p->no_ter!=NULL;p++)
n++;
return n;
}
//1.非终结符first集合的构造
void no_ter_first_create(chanshengshi *formular,struct no_terminal_sign * no_terminal,struct terminal_sign * terminal)
{
chanshengshi * p;
int n,i;
struct no_terminal_sign *q;
char temp[MAX]=""; //临时数组变量
for(p=formular;p->left!=NULL;p++)
{
n=0;
q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体
if(strcmp(p->right,"~")==0)//如果产生式右部为空字
continue;
struct no_terminal_sign *r;
for(i=0;p->right[i]!='\0';i++)
{
if(!is_terminal(p->right[i],terminal))
{
r=search_by_sign(p->right[i],no_terminal);//根据非终结符找到对应的非终结符结构体
if(is_include_null(r))
n++;
else break;
}
else break;
}
for(i=0;i<n;i++)
{
r=search_by_sign(p->right[i],no_terminal);//根据非终结符找到对应的非终结符结构体
strcpy(temp,""); //临时数组变量赋空串
strcpy(temp,r->first);
subtract_null(temp); //减空字
merge_to_first(q,temp);//将所有非空元素加入左部非终结符的first
}
if(n>=(signed)strlen(p->right))
{
add_ter_to_first(q,'~');
}
else
{
if(is_terminal(p->right[n],terminal))
add_ter_to_first(q,p->right[n]);
else{
r=search_by_sign(p->right[n],no_terminal);//根据非终结符找到对应的非终结符结构体
merge_to_first(q,r->first);//将所有元素加入左部非终结符的first(已确定不含空字)
}
}
}
}
//2.候选式first集合的构造
void candidate_first_create(chanshengshi *formular,struct no_terminal_sign * no_terminal,struct terminal_sign * terminal,struct candidate_formular *candi)
{
int n=0,i;
char temp[MAX]; //临时数组变量
chanshengshi *p;
struct candidate_formular *q;
struct no_terminal_sign *r;
for(p=formular;p->left!=NULL;p++){
q=search_by_string(p->right,candi);
for(i=0;i<p->right[i]!='\0';i++){
if(!is_terminal(p->right[i],terminal)){
r=search_by_sign(p->right[i],no_terminal);
if(is_include_null(r))
n++;
else
break;
}else
break;
}
for(i=0;i<n;i++){
r=search_by_sign(p->right[i],no_terminal);//根据非终结符找到对应的非终结符结构体
strcpy(temp,""); //临时数组变量
strcpy(temp,r->first);
subtract_null(temp); //减空字
merge_to_candidate_first(q,temp);//将所有非空元素加入到候选式的first
}
if(n>=(signed)strlen(p->right)){
add_ter_to_candidate_first(q,'~');
}else{
if(is_terminal(p->right[n],terminal))
add_ter_to_candidate_first(q,p->right[n]);
else{
r=search_by_sign(p->right[i],no_terminal);//根据非终结符找到对应的非终结符结构体
merge_to_candidate_first(q,r->first);//将所有非空元素加入左部非终结符的first
}
}
}
}
//3.非终结符follow集合的构造
void no_ter_follow_create(chanshengshi *formular,struct no_terminal_sign * no_terminal,struct terminal_sign * terminal,struct candidate_formular *candi)
{
struct no_terminal_sign *q,*r,*s;
chanshengshi *p;
int i;
char temp[MAX];
for(p=formular;p->left!=NULL;p++)
{
q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体
for(i=0;i<(signed)strlen(p->right)-1;i++)
{
if(!is_terminal(p->right[i],terminal))
{
//根据非终结符找到对应的非终结符结构体r，即当前需要求follow集合的非终结符
r=search_by_sign(p->right[i],no_terminal);
int n=i+1;//记录当前非终结符的标号
for(int j=i+1;j<(signed)strlen(p->right);j++){
if(!is_terminal(p->right[j],terminal)){
s=search_by_sign(p->right[j],no_terminal);
if(is_include_null(s))
n++;
else
break;
}else
break;
}
for(j=i+1;j<n;j++){
s=search_by_sign(p->right[j],no_terminal);//根据非终结符找到对应的非终结符结构体
strcpy(temp,""); //临时数组变量
strcpy(temp,s->first);
subtract_null(temp); //减空字
merge_to_follow(r,temp);//将所有非空元素加入当前非终结符的follow集合
}
//如果当前非终结符后面的符号都含空字，则将左部非终结符的follow加入到该终结符的follow集合
if(n>=(signed)strlen(p->right))
{
merge_to_follow(r,q->follow);
}else
{
if(is_terminal(p->right[n],terminal))
add_ter_to_follow(r,p->right[n]);
else{
s=search_by_sign(p->right[n],no_terminal);//根据非终结符找到对应的非终结符结构体
merge_to_follow(r,s->first);//将所有元素加入当前非终结符的follow
}
}
}
}
//如果右部的最后一个字符是非终结符，则将左部的follow加到该非终结符的follow
if(!is_terminal(p->right[i],terminal)){
r=search_by_sign(p->right[i],no_terminal);
merge_to_follow(r,q->follow);
}
}
}
/******************************************************************/
//主函数
void main()
{
//构造一个预测分析表，一个二维数组，行代表非终结符序号，列代表非结符序号
int analysis[MAX][MAX];
//定义非终结符集
struct no_terminal_sign no_terminal[MAX];
//定义终结符集
struct terminal_sign terminal[MAX];
//定义开始符号
char start_sign;
//定义产生式集合
chanshengshi formular[MAX];
struct candidate_formular candi[MAX];
chanshengshi *p;
int t1,t2,i,j;
/**********************************************************************/
//读取存放产生式的文件
FILE *in;
if((in=fopen("chanshengshi.txt","r"))==NULL){
printf("cannot open file!\n");
return;
}
char sign;
int no_ter_num=0,ter_num=0,chanshengshi_num=0,candidate_num=0;
char temp[MAX];
sign=fgetc(in);
start_sign=sign;//读取的第一个符号为开始符号
rewind(in); //文件指针重新回到文件头部
//产生式添加并赋初值
while (fscanf(in,"%s",temp)!=-1)
{
formular[chanshengshi_num].left=temp[0];
strcpy(formular[chanshengshi_num].right,temp+3);
chanshengshi_num++;
}
formular[chanshengshi_num].left=NULL;
strcpy(formular[chanshengshi_num].right,"");
//非终结符和终结符添加并赋初值
for(p=formular;p->left!=NULL;p++)
{
//1.将非终结符加入非终结符集并赋初值
for(i=0;i<no_ter_num;i++)
if(p->left==no_terminal[i].no_ter)
break;
if(i>=no_ter_num)
{
no_terminal[no_ter_num].no_ter=p->left;
strcpy(no_terminal[no_ter_num].first,"");
strcpy(no_terminal[no_ter_num].follow,"");
no_ter_num++;
}
//2.将终结符加入非终结符集
for(i=0;p->right[i]!='\0';i++)
if(!((p->right[i]<='Z' && p->right[i]>='A') || (p->right[i]=='~')))
{
for(j=0;j<ter_num;j++)
if(p->right[i]==terminal[j].ter)
break;
if(j>=ter_num){
terminal[ter_num].ter=p->right[i];
strcpy(terminal[ter_num].first,"");
//add_ter(terminal[ter_num].first,temp[i]);
ter_num++;
}
}
//3.将候选式加入候选式集并赋初值
for(i=0;i<candidate_num;i++)
if(strcmp(p->right,candi[i].candidate)==0)
break;
if(i>=candidate_num)
{
strcpy(candi[candidate_num].candidate,p->right);
strcpy(candi[candidate_num].first,"");
candidate_num++;
}
}
//各集合终结标志添加
no_terminal[no_ter_num].no_ter=NULL;
strcpy(no_terminal[no_ter_num].first,"");
strcpy(no_terminal[no_ter_num].follow,"");
formular[chanshengshi_num].left=NULL;
strcpy(formular[chanshengshi_num].right,"");
strcpy(candi[candidate_num].candidate,"");
strcpy(candi[candidate_num].first,"");
terminal[ter_num].ter='#';
strcpy(terminal[ter_num].first,"");
ter_num++;
terminal[ter_num].ter=NULL;
strcpy(terminal[ter_num].first,"");
fclose(in);
/**********************************************************************/
//first集合的构造
//1和2是处理空字问题，即先把空字写入每个所属first集合
//1
for(p=formular;p->left!=NULL;p++)
{
struct no_terminal_sign *q;
q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体
if(strcmp(p->right,"~")==0)//如果产生式右部为空字
add_ter_to_first(q,'~');//则将空字加入到左部非终结符的first
}
//2
for(p=formular;p->left!=NULL;p++)
{
struct no_terminal_sign *q,*r;
q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体
if(!is_terminal(p->right[0],terminal))
{
r=search_by_sign(p->right[0],no_terminal);
if(is_include_null(r))
add_ter_to_first(q,'~');
}
}
//3构造first集合，直至不在增加为止
while(1)
{
t1=sum_first(no_terminal);
no_ter_first_create(formular,no_terminal,terminal);
t2=sum_first(no_terminal);
if(t1>=t2) break;//first集合不再增大
}
//打印first集合
for(i=0;no_terminal[i].no_ter!=NULL;i++)
printf("%s\n",no_terminal[i].first);
printf("\n");
/********************************************************************/
//产生式候选式的first集合的构造
candidate_first_create(formular, no_terminal,terminal,candi);
//打印候选式的first集合
for(i=0;strcmp(candi[i].candidate,"")!=0;i++)
printf("%s\n",candi[i].first);
printf("\n");
/***********************************************************************/
//非终结符follow集合的构造
struct no_terminal_sign *a;
a=search_by_sign(start_sign,no_terminal);//开始符号的结构体
add_ter_to_follow(a,'#'); //把#添加到开始符号的follow集合中
while(1){
t1=sum_follow(no_terminal);
no_ter_follow_create(formular,no_terminal,terminal,candi);
t2=sum_follow(no_terminal);
if(t1>=t2)
break;
}
//打印终结符的follow集合
for(i=0;no_terminal[i].no_ter!=NULL;i++)
printf("%s\n",no_terminal[i].follow);
printf("\n");
/***************************************************************************/
//构造分析表
t1=total_ter(terminal); //终结符个数
t2=total_no_ter(no_terminal); //非终结符个数
printf("%d,%d\n",t1,t2);
//初始化预测分析表
for(i=0;i<t2;i++)
for(j=0;j<t1;j++)
analysis[i][j]=ERROR;
//构造
for(i=0;i<t2;i++){
struct no_terminal_sign *q;
struct candidate_formular *r;
int mark;
for(mark=0;formular[mark].left!=NULL;mark++){ //对每个产生式
q=search_by_sign(formular[mark].left,no_terminal); //由左部找到非终结符结构体
r=search_by_string(formular[mark].right,candi); //由右部找到候选式结构体
if(formular[mark].left==no_terminal[i].no_ter){
for(j=0;j<t1;j++){
if(is_include(r->first,terminal[j].ter)){
analysis[i][j]=mark;
}
}
if(is_include_null(q)){
for(j=0;j<t1;j++){
if(is_include(q->follow,terminal[j].ter)){
analysis[i][j]=mark;
}
}
}
}
}
}
//打印预测分析表
for(i=0;i<t2;i++)
{
for(j=0;j<t1;j++)
printf("%d\t",analysis[i][j]);
printf("\n");
}
/************************************************************************/
//将预测分析表保存到文件中
FILE *fp;
if((fp=fopen("analysis_table.txt","w"))==NULL){
printf("cannot open the file of analysis_table.txt !\n");
return;
}
fprintf(fp,"%s\n","产生式：");
for(i=0,p=formular;p->left!=NULL;p++,i++)
fprintf(fp,"%d%s%c%s%s\n",i,":",p->left,"->",p->right);
fprintf(fp,"%s\n","--------------------------------------------");
fprintf(fp,"%-10s\t%-10s\t%-10s\n","","first","follow");
for(i=0;no_terminal[i].no_ter!=NULL;i++){
fprintf(fp,"%-10c\t%-10s\t%-10s\n",no_terminal[i].no_ter,no_terminal[i].first,no_terminal[i].follow);
}
fprintf(fp,"%s\n","--------------------------------------------");
fprintf(fp,"%s\n","预测分析表如下：");
fprintf(fp,"%-10s","");
for(i=0;terminal[i].ter!=NULL;i++)
fprintf(fp,"%-10c",terminal[i].ter);
fprintf(fp,"\n");
for(i=0;i<t2;i++){
fprintf(fp,"%-10c",no_terminal[i]);
for(j=0;j<t1;j++){
if(analysis[i][j]==ERROR)
fprintf(fp,"%-10s","ERROR");
else
fprintf(fp,"%-10d",analysis[i][j]);
}
fprintf(fp,"\n");
}
fclose(fp);
}
