parsell_1.cpp

词法分析

				if (first[Grammar[GrammarChoice][k]][EMPTY-NontmlTypeNum]==false)
					contineFrist=false;
				k++;
			}
			if (contineFrist==true)
			{           
				if (first[A][EMPTY-NontmlTypeNum]==false)
					changesAnyFrist=true;
				first[A][EMPTY-NontmlTypeNum]=true;
			//	printf("first[%d][%d]=%d 所在的%d语法，在第%d终结符 \n",A,EMPTY-NontmlTypeNum+1,first[A][EMPTY-NontmlTypeNum],GrammarChoice+2,k);	
			}	
		}
	}
	//	printf("\n");
	
}
void printFollowSet()
{ 
	int i=0,j=0;
	printf("\n");

		for (i=0;i<NontmlTypeNum;i++)
		{   	printf("%d Follow(",i);
	            printToken1(i);
	        	printf("):	");
			for(j=0;j<TmlTypeNum+1;j++)
				
					if (follow[i][j]==1)
						{
							printToken2(j);
							printf("  ");
						}
	
			
			printf("\n");
		}
	//	getchar();	
}
void getfollow()
{   
	int i=0,j=0;
	for(;i<GrammarTokenNum;i++)
		for(;j<TmlTypeNum+1;j++)
          follow[i][j]=false;

	follow[0][30]=true;//follow(start)={$}
	while(changesAnyFollow)
	{   	
		changesAnyFollow=false;
		for (int GrammarChoice=0;GrammarChoice<GrammarNum ;GrammarChoice++)
		{
			int	A=Grammar[GrammarChoice][0];//语法左部
			for (int i=1;Grammar[GrammarChoice][i]!=0;i++)/*扫描文法生成式 */
			{   int Xi=Grammar[GrammarChoice][i];
			if (Grammar[GrammarChoice][i]<=arg_list_)/*为非终结符*/
				{
				p=i+1;
				if((Grammar[GrammarChoice][p]>arg_list_)&&(Grammar[GrammarChoice][p]<=EMPTY))/*为终结符*/
					{
				
				     if(	follow[Xi][Grammar[GrammarChoice][p]-NontmlTypeNum]==false)
					 {	follow[Xi][Grammar[GrammarChoice][p]-NontmlTypeNum]=true;
					 changesAnyFollow=true;}
				/*	printf("由第%d条语法的第%d文法字符 ",GrammarChoice+2,p);
					printf("first( ");
					printToken1(Grammar[GrammarChoice][p]);
					printf(" )-> follow( ");
					printToken1(Xi);
					printf(" )添加");
					printToken1(Grammar[GrammarChoice][p]);
					printf("\n");
					printFollowSet();*/
				
					}
				else if(Grammar[GrammarChoice][p]!=0)/* 后面的一个为非终结符*/
					{		
					do 	
						{
						for (int s=0;s!=EMPTY-NontmlTypeNum;s++)//add first Xp(Xi++)-empty->follow Xi
							{  
							if(follow[Xi][s]!=(follow[Xi][s]|first[Grammar[GrammarChoice][p]][s]))
								{
								follow[Xi][s]=(follow[Xi][s]|first[Grammar[GrammarChoice][p]][s]);
						    	changesAnyFollow=true;
							/*	printf("EMPTY-NontmlTypeNum=%d %d\n",EMPTY,EMPTY-NontmlTypeNum);
								printf("由第%d条语法的第%d文法字符 ",GrammarChoice+2,p);
								printf("first( ");
								printToken1(Grammar[GrammarChoice][p]);
								printf(" )-> follow( ");
								printToken1(Xi);
								printf(" )添加");
								printToken2(s);
								printf("\n");
								printFollowSet();*/
							
							
								}  
							}	
						p++;
						if((Grammar[GrammarChoice][p]>arg_list_)&&(Grammar[GrammarChoice][p]<EMPTY))/*为终结符*/
							{
							   if(	follow[Xi][Grammar[GrammarChoice][p]-NontmlTypeNum]==false)
							   {	follow[Xi][Grammar[GrammarChoice][p]-NontmlTypeNum]=true;
								changesAnyFollow=true;}
							/*	printf("由第%d条语法的第%d文法字符 ",GrammarChoice+2,p);
								printf("first( ");
								printToken1(Grammar[GrammarChoice][p]);
								printf(" )-> follow( ");
								printToken1(Xi);
								printf(" )添加");
								printToken1(Grammar[GrammarChoice][p]);
								printf("\n");
								printFollowSet();*/
						
					}
						}	while((first[Grammar[GrammarChoice][p]][EMPTY-NontmlTypeNum]==1));//&&(Grammar[GrammarChoice][p]<=arg_list_));/*下一个为终结非终结符含有empty*/
			
					}
				if ((Grammar[GrammarChoice][p]==0)&&(Grammar[GrammarChoice][0]!=Xi))/*不断检查empty到尾部，表明empty in First(Xi+1,Xn),避免自己加自己*/
				{
					for (int s=0;s<=EMPTY-NontmlTypeNum+1;s++)//add follow Xp(A)->follow Xi
					{  
						if(follow[Xi][s]!=(follow[Xi][s]|follow[A][s]))
						{
							follow[Xi][s]=(follow[Xi][s]|follow[A][s]);
							changesAnyFollow=true;
							/*printf("%d ,%d\n",A,Xi);
							printf("由第%d条语法的左部 ",GrammarChoice+2);
							printf("follow( ");
							printToken1(Grammar[GrammarChoice][A]);
							printf(" )-> follow( ");
							printToken1(Xi);
							printf(" )添加");
							printToken2(s);
							printf("\n");
							printFollowSet();*/
						}  		
					}			
				}
			}
		}
	}	
}
}
void printfM()//打印分析表
{printf("___");
	for (int t=0;t<=TmlTypeNum;t++)
		if (t<10) printf("%d__",t);
		else printf("%d_",t);
	    printf("\n");
		//printToken2(t);//表头
    for (int m=0;m<NontmlTypeNum;m++)
	{	printf("%2d:",m);
		for(int l=0;l<=TmlTypeNum;l++)
		{
			if (M[m][l]==-1)
				printf("0  ");
				else if(M[m][l]<9)printf("%d  ",M[m][l]+1);
				else printf("%d ",M[m][l]+1);
		}
		printf("\n");
	}
	getchar();

}
void getM()
{   for (int i=0;i<NontmlTypeNum;i++)//初始化
		for (int j=0;j<=TmlTypeNum;j++)
			M[i][j]=-1;
			
		
	for (int GrammarChoice=0;GrammarChoice<GrammarNum;GrammarChoice++)
	{  	
		for (int i=0;i<TmlTypeNum;i++)
		currentGrammarFrist[i]=0;//初始化
	  int A=Grammar[GrammarChoice][0];//A左式
	  int Xi=1;//当前位置
	  
    do
	{
		for (int s=0;s!=EMPTY-NontmlTypeNum;s++)//add first Xp(Xi++)-empty->frist Grammar
	        currentGrammarFrist[s]=(currentGrammarFrist[s]|first[Grammar[GrammarChoice][Xi]][s]);
		if(first[Grammar[GrammarChoice][Xi]][EMPTY-NontmlTypeNum]==1)//含有empty在次位置的first,求下一个
		Xi++;
		else break;//否则推出循环结束


	}	while((Grammar[GrammarChoice][Xi]<=arg_list_)&&(Grammar[GrammarChoice][Xi]!=0));/*为非终结符*/
	{   //frist构造M
		for(int j=0;j<EMPTY-NontmlTypeNum;j++)
		{
			if(currentGrammarFrist[j]==true)//
			{ //if(M[A][j]!=-1)
		    //	printf("之前的M[%d][%d]=%d,已经有其他文法填入，所以非LL(1)文法\n",A,j, M[A][j]+1);
				M[A][j]=GrammarChoice;
			//  printf("frist构造M M[%d][%d]=%d\n",A,j,M[A][j]+1);
			 //printfM();
			}
		}

	}
		if((Grammar[GrammarChoice][Xi]==0)||(Grammar[GrammarChoice][Xi]==EMPTY))//到结尾了，任然有empty
		{
			//follow构造M
		for(int j=0;j<=EMPTY-NontmlTypeNum+1;j++)
		{
			if(follow[A][j]==true)//
			{  // if(M[A][j]!=-1)
		   // 	printf("之前的M[%d][%d]=%d,已经有其他文法填入，所以非LL(1)文法\n",A,j, M[A][j]+1);
				M[A][j]=GrammarChoice;
		//	 printf("follow构造M M[%d][%d]=%d\n",A,j,M[A][j]+1);
		//	 printfM();
			}
		}


		}

	}
}	

void ShowStack()
{
	int i;
	for(i = 0; i <= topAnalyse; i++)
	{
		if(ENDFILE == analyseStack[i])
			fprintf(parse,"$");
		else
		printToken3(analyseStack[i]);
		fprintf(parse,"| ");
		
		}
	fprintf(parse,"\n");

	}
void Pop()
{   StreeNode * head;
	head=new StreeNode;	
	head = str[ topAnalyse ];
	if(str[ topAnalyse ]->Nodekind!=NOTML)
		strcpy(str[ topAnalyse ]->tokenString,tokenString);
//	for (int i=0;i<linespStack[topAnalyse];i++)   //模拟栈部分显示语法树
//	printf("  ");
//	printToken4(analyseStack[topAnalyse],tokenString);
//	printf("\n");
  
	topAnalyse--;
}
int returnM(int tmltoken)//栈顶与现在得到的token返回returnM
{
  int returnChoiceGrammar; 
  char c=' ';
  fprintf(parse,"%+120cToken:",c);
  printToken3(tmltoken);
  if ((tmltoken==ID)&&(analyseStack[topAnalyse]==23))	  
  {   char ch=getNextChar();
  returnChoiceGrammar=40;//simple_expression
  char ch2;//
  int spno=0;
  while((ch==' ')||(ch=='\t')||(ch=='\n'))
  {
	  spno++;
	  ch=getNextChar();
  }
  if (ch=='=')
  { ch2=getNextChar();
  
  if (ch2!='=')
	  returnChoiceGrammar=39;//expression
		ungetNextChar();
  }
  else if  (ch=='[')
  {   ch2=getNextChar();
  while((ch2!=']'))//寻找]
  {
	  spno++;
	  ch2=getNextChar();
  }
		ch2=getNextChar();//读]右边的字符
		while((ch2==' ')||(ch2=='\t')||(ch2=='\n'))
		{
			spno++;
			ch2=getNextChar();
		}
		if (ch2=='=')//为=
		{ ch2=getNextChar();
		
		if (ch2!='=')
		{returnChoiceGrammar=39;}//expression
		ungetNextChar();
		}
		ungetNextChar();
		
		
		while (spno--)
		{
			ungetNextChar();
			
		}
		ungetNextChar();
		}
  ungetNextChar();
		
  }
  else if ((tmltoken==ID)&&(analyseStack[topAnalyse]==35))//factor
  {
	  char ch=getNextChar();
      int spno=0;
	  while((ch==' ')||(ch=='\t')||(ch=='\n'))
	  {
		  spno++;
		  ch=getNextChar();
	  }
	  if (ch=='(')
		  returnChoiceGrammar=65;//expression
	  else 	returnChoiceGrammar=64;//expression
	  while (spno--)
	  {
		  ungetNextChar();
		  
	  }
	  ungetNextChar();
	  
  }
  else
  {if (tmltoken==ENDFILE)
  returnChoiceGrammar=M[analyseStack[topAnalyse]][TmlTypeNum];
  else
	  returnChoiceGrammar=M[ analyseStack[topAnalyse]][tmltoken-NontmlTypeNum];
  }
  fprintf(parse,"  产生式%2d  ",returnChoiceGrammar+1);
  /*printToken3(Grammar[returnChoiceGrammar][0]);
  fprintf(parse," -> ");
  for(int j=1;Grammar[returnChoiceGrammar][j]!=0;j++)
	 { 
	  printToken3(Grammar[returnChoiceGrammar][j]);
	  fprintf(parse,"  ");
  }*/
  fprintf(parse,"\n");
  if(returnChoiceGrammar==-1)
  {
	  fprintf(parse,"未找到相关的文法产生式,生成错误!");
	  fprintf(parse,"语法分析错误!\n");//可以加上现在的行数
	  ParseError=TRUE;
	  //exit(-1);
  }

  return returnChoiceGrammar;
	
}
void generate(TokenType token)
{
	int choiceGrammar=returnM(token);
	int i=0;
	int GrammarLength=0;
	StreeNode *head,*child;
    head=new StreeNode ;	
	head = str[ topAnalyse ];
	Pop();

	//head->childrenno=0;
	if(EMPTY == Grammar[choiceGrammar][1]) /*若一边为空产生式时*/
	{  ShowStack();
		// linesp--;
		return;}
	while (Grammar[choiceGrammar][i+1]!=0)
		i++;//文法的长度
	GrammarLength=i;
	topAnalyse += i;
	for(i = 1; i<=GrammarLength; i++)
	{
		/*不为空产生式时*/		

        linespStack[topAnalyse- i+1]=linesp+1;	
		child = new StreeNode;
		child ->val = Grammar[choiceGrammar][i]; 
		if((child ->val==ID)||(child ->val==ID) )//ID_NUM, NOTML,TML 
			child->Nodekind=ID_NUM;
		else if(child ->val<ENDFILE)
			child->Nodekind=NOTML;
		else child->Nodekind=TML;
		child ->childrenno=0;
		child->layno=head->layno+1;
		head ->child[head->childrenno++] = child;
		analyseStack[topAnalyse - i+1] =Grammar[choiceGrammar][i];/*逆序入栈*/
		str[topAnalyse - i+1 ]=child;
	}
	linesp++;
	ShowStack();
}

void  match()
{  

	
	
	Pop();
	//linesp--;
	linesp=linespStack[topAnalyse];
	char c=' ';
    fprintf(parse,"%+120cToken:",c);
	printToken3(currToken);
	fprintf(parse,"	Match\n");
	ShowStack();
	currToken= getToken();//返回下一个getToken
	
}
	
void	 printfCreatM()//Fisrst_follow_M
	{
		
		
	//printGrammar();
	//	printFirstSet();
	//	printFollowSet();
		printfM();
	//	system("PAUSE");
	
	}

void MainCtrl(StreeNode * treeroot)//主控程序
{   getfirst();
    getfollow();
    getM();
    InitStack();
//	str[1]=treeroot;
//	StreeNode* root =new StreeNode;
	str[1]=treeroot;
	{
		str[1]->val=program;
		str[1]->childrenno=0;
		str[1]->Nodekind=NOTML;
		str[1]->layno=0;
	}//初始化语法树
	
	currToken=getToken();
	while(	analyseStack[topAnalyse] !=ENDFILE)
	{
		if ((analyseStack[topAnalyse]<EMPTY)&&(analyseStack[topAnalyse]>=ERROR))
		{if(currToken==analyseStack[topAnalyse])//为terminal
	        	match();
			else {ParseError=TRUE;
			printf("未能与栈顶的终结符匹配!\n");}}
		else if(analyseStack[topAnalyse]<=ENDFILE)
		generate(currToken);
		if(ParseError)
			return;
	}
	if((analyseStack[topAnalyse] ==ENDFILE)&&(getToken()==ENDFILE))
	{
		fprintf(parse,"\nC_MINUS PARSE COMPILATION \n");//accept
	}
	else{
		fprintf(parse,"最后未匹配完全!错误!\n");//error;
		ParseError =TRUE;
	}
	if(ParseError)
		return;//有错误词法返回
}