ll1final.cpp

一个开发程序

#include <stdio.h>
#include "LL1.H"
#include "stack.h"

/*求first集*/
void GetFirstSet();
/*求所有生成式的first集*/
void GetExpFirstSet();
/*求某一表达式的部分文法符号串的first集*/
void getPartexpFirstSet(int*exp,Set & head);
/*求Follow集*/
void GetFollowSet();
/*初始化预测表*/
void InitiPreTable();
/*读取token*/
int GetToken();
/*查找符号表，判断表项是否为-1，若不是返回1，若是返回0*/
int Match(int vv,int tt);
/*错误信息提示*/
void error();
/*将vv,tt所对应的表达式压入栈*/
void PushStr(LinkStack*s,int vv,int tt);
/*打印产生式*/
void PrintStr(int vv ,int tt);
/*语法分析器主程序*/
void ParseLl1();
/*将宏转化成字符串*/
char* ConvertNumToString(int num);
void main()
{
	GetFirstSet();
	GetExpFirstSet();
	GetFollowSet();
	InitiPreTable();
	ParseLl1();
	
};

/*判断num是否在集head中，若存在返回1，若不存在返回0*/
int IsNumIn(Set*head,int num)
{
	int num_in_value=0;
	Set* ptr=head->next;
//	if(ptr==NULL&&num==EPS)
//	{
//		num_in_value=1;
//	}
	while (ptr!=NULL)
	{
		if(ptr->TerValue==num)
		{
			num_in_value=1;
		}
		ptr=ptr->next;
	}
	return num_in_value;
}

/*将souce中的元素无重复的加入dest中，第三个参数表示是否加入eps*/
int add(Set*dest,Set*source,bool is_eps_in)
{
	Set*ptr1;
	Set*ptr2=source->next;
	/*标识是否有新元素加入，0表示没有新元素加入*/
	int is_added_value=0;
	/*要求source中如果有eps，不加入dest中*/
	if (is_eps_in==false)
	{
		while (ptr2!=NULL)
		{
			/*如果ptr2中无EpS，并且该值不在dest中，则将其元素加入dest*/
			if (ptr2->TerValue!=EPS&& !IsNumIn(dest,ptr2->TerValue))
			{
				ptr1=new Set;
				ptr1->next=dest->next;
				dest->next=ptr1;
				ptr1->TerValue=ptr2->TerValue;
				is_added_value=1;
			}
			ptr2=ptr2->next;
		}//end of while				
	}//end of if
	else
	{
		while (ptr2!=NULL)
		{
			/*该值不在dest中，则将其元素加入dest*/
			if (!IsNumIn(dest,ptr2->TerValue))
			{
				ptr1=new Set;
				ptr1->next=dest->next;
				dest->next=ptr1;
				ptr1->TerValue=ptr2->TerValue;
				is_added_value=1;
			}
			ptr2=ptr2->next;
		}//end of while				
	}//end of if
	return is_added_value;
}
int add(Set*dest,int value)
{
	Set*ptr1;
	int is_added_value=0;
	if (!IsNumIn(dest,value))
	{
		ptr1=new Set;
		ptr1->next=dest->next;
		dest->next=ptr1;
		ptr1->TerValue=value;
		is_added_value=1;
	}
	return is_added_value;
}

void GetFirstSet()
{
	//初始化非终结符和eps的first集
	for (int t=TER_START;t<SUM_NUM+1;t++)
	{
		FirstSet[t].next=new Set;
		FirstSet[t].next->next=NULL;
		FirstSet[t].next->TerValue=t;
		
	}
	
	//初始化非终结符的first集??此处可考虑将A->eps加入即可
	for(int j=0;j<TER_START;j++)
	{
		Set*ptr=&FirstSet[j];
		for (int k=0;k<EXP_NUM;k++)
			if (express[k][0]==j&&express[k][1]>=TER_START)
			{
				ptr->next=new Set;
				ptr->next->next=NULL;
				ptr->next->TerValue=express[k][1];
				ptr=ptr->next;
			}
	}

	//递归求非终结符的first集

	int change_flag=1;/*设置标志位，1表示first集有变动，0表示first集无变动*/

	while (change_flag==1)
	{
		change_flag=0;
		for (int i=0;i<EXP_NUM;i++)
		{
			int k=1;
			bool keep_on=true;
			int destination=express[i][0]; /*非终结符*/
			while (keep_on &&express[i][k]!=-1)
			{
				int source=express[i][k];
				int if_added=add(&FirstSet[destination],&FirstSet[source],EPS_OUT);
				if (if_added==1)
				{
					change_flag=1;
				}
				if (IsNumIn(&FirstSet[source],EPS)!=1)/*若不存在eps*/
				{
					keep_on=false;
				}
				k++;
			}//end of while2
			/*如果产生式的所有文法符号均能产生eps，则将eps也加入*/
			if (keep_on)
			{
				add(&FirstSet[destination],&FirstSet[EPS],EPS_IN);
			}
		}//end of for
	}//end of while1
	
	for (int k=0;k<SUM_NUM;k++)
	{
		Set*first=&FirstSet[k];
		do 
		{
			printf("%d ",first->TerValue);
			first=first->next;	
		} while(first!=NULL);
		printf("\n");
	}
	
}
//求所有表达式的first集
void GetExpFirstSet()
{
	for (int i=0;i<EXP_NUM;i++)
	{
	//	getPartexpFirstSet(&express[i][1],ExpFirstSet[i]);
		 
		int k=1;
		int source=express[i][k];
		add(&ExpFirstSet[i],&FirstSet[source],EPS_OUT);
		k++;
		while ( source!=EXP_END&&IsNumIn(&FirstSet[source],EPS) &&source!=EPS)
		{
			add(&ExpFirstSet[i],&FirstSet[express[i][k]],EPS_OUT);
			k++;
			source=express[i][k];
		}
		/*若.......*/	
		 
		if (express[i][k]==EXP_END&&IsNumIn(&FirstSet[express[i][--k]],EPS))
		{
			add(&ExpFirstSet[i],&FirstSet[EPS],EPS_IN);
		} 
	}
	printf("串的first集\n");
	for (int k=0;k<EXP_NUM;k++)
	{
		printf("%d :",k);
		Set*first=&ExpFirstSet[k];
		do 
		{
			printf("%d ",first->TerValue);
			first=first->next;	
		} while(first!=NULL);
		printf("\n");
	}
}
void getPartexpFirstSet(int*exp,Set & head)
{
		int k=0;
		int source=exp[k];
	 	if (source==-1)
		{
			return ;
		}	 
		add(& head,&FirstSet[source],EPS_OUT);
		k++;
		/*惨痛的教训！！！！！！！！！！！！*/
		source=exp[k];
		while ( source!=EXP_END&&IsNumIn(&FirstSet[source],EPS))
		{
			add(&head,&FirstSet[exp[k]],EPS_OUT);
			k++;
			source=exp[k];
		}
		/*若.......*/	
		if (exp[k]==EXP_END&&IsNumIn(&FirstSet[exp[--k]],EPS))
		{
			add(&head,&FirstSet[EPS],EPS_IN);
		}
}
void deleteTemp()
{
	Set*ptr=Temp.next;
	delete ptr;
	Temp.next=NULL;
}			

//求follow集
void GetFollowSet()
{
	/*在开始符号的follow集中加入end符号*/
	add(&FollowSet[0],END);
	
	int change_flag=1;
	while (change_flag==1)
	{
		change_flag=0;
	/*		16 E->JK       31 20
			17 K->+JK|EPS  31 20
			18 J->MN       31 20 26
			19 N->*MN|EPS  31 20 26
			20 M->(E)|num  31 20 26 27
			E,K,J,N,M,
	*/
		/*对每一个串*/
		for (int i=0;i<EXP_NUM;i++)
		{
			/*记录生串的左部*/
			int var=express[i][0];
			int k=1;
			while (express[i][k]!=EXP_END)
			{
				if (express[i][k]>=0&&express[i][k]<TER_START)
				{
					int k_temp=k+1;
					int temp=0;
					/*截取得到的非终结符的后续串*/
					while (express[i][k_temp]!=-1)
					{
						Buffer[temp]=express[i][k_temp];
						temp++;
						k_temp++;
					}
					Buffer[temp]=-1;
					getPartexpFirstSet(Buffer,Temp);
					/**/
					if(add(&FollowSet[express[i][k]],&Temp,EPS_OUT)==1)
					{
						change_flag=1;
					}
					if (IsNumIn(&Temp,EPS)||Temp.next==NULL)
					{	
						if(add(&FollowSet[express[i][k]],&FollowSet[express[i][0]],EPS_IN)==1)
							change_flag=1;
					}
					deleteTemp();						
				}//end  of if
				k++;	
			}
		}
	}
	printf("follow集\n");	
	for (int t=0;t<VAR_NUM;t++)
	{
		Set*fir =&FollowSet[t];
		do 
		{
			printf("%d ",fir ->TerValue);
			fir =fir->next;	
		} while(fir !=NULL);
		printf("\n");
	}
}
//初始化预测表
void InitiPreTable()
{	
	//将所有表项初始化为错误
	for (int i=0;i<VAR_NUM;i++)
	{
		for (int j=0;j<TER_NUM+2;j++)
		{
			PreTable[i][j]=ERROR;
		}
	}
	for (int j=0;j<EXP_NUM;j++)
	{
		Set*ptr=ExpFirstSet[j].next;
		int var=express[j][0];
		while (ptr!=NULL)
		{
			int ter=ptr->TerValue-TER_START;
			PreTable[var][ter]=j;
			ptr=ptr->next;
		}
		
		if (IsNumIn(&ExpFirstSet[j],EPS)==1)
		{
			Set*ptr1=FollowSet[var].next;
			while (ptr1!=NULL)
			{
				int ter=ptr1->TerValue-TER_START;
				PreTable[var][ter]=j;
				ptr1=ptr1->next;
			}
		}
	}
	printf("pretable：\n");
	for (int h=0;h<VAR_NUM;h++)
	{
		for (int g=0;g<TER_NUM+2;g++)
		{
			printf("%2d ",PreTable[h][g]);	
		}
		printf("\n");
	}
}//end of InitiPreTable
char* ConvertNumToString(int num)
{ 
	char*str=new char;
	switch(num)
	{
	case START:
		str="START";
		break;
	case L:
		str="L";
		break;
	case A:
		str="L";
		break;
	case S:
		str="S";
		break;
	case D:
		str="D";
		break;
	case F:
		str="F";
		break;
	case B :
		str="B";
		break;
	case H:
		str="H";
		break;
	case G:
		str="G";
		break;
	case relop:
		str="relop";
		break;
	case I:
		str="I";
		break;
	case E :
		str="E";		
		break;
	case  J:
		str="J";
		break;
	case  K:
		str="K";
		break;
	case N:
		str="N";
		break;
	case M:
		str="M";
		break;
	case FUNC:
		str="func";
		break;
	case WHILE:
		str="while";
		break;
	case DO:
		str="do";
		break;
	case IF:
		str="if";
		break;
	case THEN:
		str="then";
		break;
	case ELSE:
		str="else";
		break;
	case INT:
		str="int ";
		break;
	case TRUE:
		str="true";
		break;
	case FALSE:
		str="false";
		break;
	case ID:
		str="id";
		break;
	case NUM:
		str="num";
		break;
	case L_BIG_BRACKET:
		str="{";
		break;
	case R_BIG_BRACKET:
		str="}";
		break;
	case EQU:
		str="=";
		break;
	case AND:
		str="&";
		break;
	case OR:
		str="|";
		break;
	case BIGGER:
		str=">";
		break;
	case SMALLER:
		str="<";
		break;
	case SEMICOLON:
		str=";";
		break;
	case DOT:
		str=",";
		break;
	case NOT :
		str="!";
		break;
	case L_MINI_BRACKET:
		str="(";		
		break;
	case R_MINI_BRACKET:
		str=")"; 
		break;
	case ADD:
		str="+";
		break;
	case MUL:
		str="*"; 
		break;
	case EPS:
		str="EPS";
	}	
	return str;
}
/************************************************************************/
/*   parse主程序                                                        */
/************************************************************************/
//从文件中读取
int GetToken()
{
	int token;
	int attr;
	fscanf(tokens,"%d %s",&token,&attr);
	return token;
}

//匹配,参数：vv非终结符 tt：终结符
//若存生成式存在则返回1，否则返回0；
int Match(int vv,int tt)
{
	if (PreTable[vv][tt]!=-1)
		return 1;
	else 
		return 0;
}
void error()
{
	fprintf(output,"ERROR!\n");
}
void PushStr(LinkStack*s,int vv,int tt)
{

	if (PreTable[vv][tt]!=-1)
	{
		int num=PreTable[vv][tt];
		int k=0;
		while (express[num][k]!=-1)
		{
			k++;
		}
		k--;
		while (k>=1)
		{
			if (express[num][k]!=EPS)
			{
				Push(s,express[num][k]);
			}
			k--;			
		}

	}

}
void PrintStr(int vv ,int tt)
{
	int num=PreTable[vv][tt];
	fprintf(output,"%s ->",ConvertNumToString(express[num][0]));
	int k=1;
	while (express[num][k]!=-1)
	{
		fprintf(output,"%s ",ConvertNumToString(express[num][k]));
		k++;
	}
	fprintf(output,"\n");
}
void ParseLl1()
{
	LinkStack *s=new LinkStack;
	Push(s,END);
	Push(s,START);
	int token=GetToken();
	int x=Top(s);
	do	{
		if (x>=TER_START||x==END)
		{
			if(x==token)
			{
				if (x!=END)
				{
					Pop(s);
					token=GetToken();
				}
			}
		else 
		{
			error();
			return ;
		}
	}
	else if(Match(x,token-TER_START)==1)
	{
		Pop(s);
		PushStr(s,x,token-TER_START);
		PrintStr(x ,token-TER_START);
	}							
	else if (Match(x,token-TER_START)==0)
	{
		error();
		return;
	}
	else
		;
	x=Top(s);
	}while(x!=END);
}