ll1.c

输入已经消除左递归的以及提取公共左因子的LL(1)文法

	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或为空*/
			    //	若X ∈VN，且  X→a…..|ε， a ∈VT，则    FIRST(X)={a,ε}
				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;
						}
					}
					
					
					//若X ∈VN 且X→Y1 Y2 …YK，则按如下顺序计算FIRST(X) ，将FIRST(Y1) –{ε} 加入FIRST(X) 
					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);
						}
					}
					
					//若ε∈FIRST(Yk-1)  则将FIRST(Yk)-{ε}加入FIRST(X)

					else
					{
						for (l=0;l<k;l++)
						{
							length=strlen(infoVn[inVN(ll1[i].array[l])].firstSet);//获得右部产生式FIRST集长度
							for (m=0;m<length; m++)
							{
								if (infoVn[inVN(ll1[i].array[l])].firstSet[m] != '^')//右部产生式FIRST集不能为空
								{
									addIn1(infoVn[inVN(ll1[i].origin)].firstSet,infoVn[inVN(ll1[i].array[l])].firstSet[m],&flag1);
								}
							}
						}
						  //若ε∈FIRST(Y1) ～ FIRST(YK)，则将ε加入FIRST(X) 

						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);//将#加入FOLLOW(S)， S为文法的开始符号

	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;
							}
						}
						
						
						//若有产生式A→αB ，或A→αBβ,β→ ε(即ε∈FIRST(β))，则把 FOLLOW(A)加入 FOLLOW(B)
						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//若有产生式A→αBβ，则把FIRST(β)–{ε}加入FOLLOW(B)中
						{
							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*/
			//若a∈FIRST(α)，则将A→α==> M[A,a]  
			else
				addIn1(select[i],ll1[i].array[0],&flag);
		}
		else//若ε∈FIRST(α),则对任何b∈FOLLOW(A)， 则将A→α==>M[A,b]
		{
			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);
						}
					}
                    //把所有无定义的M[A,a]都标上error
					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);
}