parse.c

根据tiny实现的C-词法语法分析器 编译原理课程

"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e",
"e"
};

char *nt[]={"ID",";","[","]","NUM","int","void","{","}","if","(",")",
"else","while","return","<=","<",">",">=","==","!=","+","-","*","/",",","=","$"};

int table[45][28]={
-1,-1,-1,-1,-1, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1, 1, 1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1, 2, 2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 3,
-1,-1,-1,-1,-1, 4, 4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1, 5, 7,-1,-1,-1,-1,-1,-1,-1, 6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1, 8,80,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,//params
81,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,82,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1, 9, 9,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10,-1,-1,
-1,-1,-1,-1,-1,12,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
13,-1,-1,-1,13,-1,-1,-1,-1,-1,13,14,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
15,-1,-1,-1,15,-1,-1,-1,-1,-1,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,16,-1,-1,
18,18,-1,-1,18,-1,-1,18,18,18,18,-1,-1,18,18,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
19,19,-1,-1,19,-1,-1,19,20,19,19,-1,-1,19,19,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
21,21,-1,-1,21,-1,-1,22,-1,23,21,-1,-1,24,25,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,26,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
27,27,27,-1,-1,27,27,27,-1,27,27,-1,-1,27,27,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
29,29,-1,-1,29,28,28,29,-1,29,29,-1,-1,29,29,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,30,30,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
31,32,-1,-1,31,-1,-1,-1,-1,-1,31,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,33,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
35,35,-1,-1,35,-1,-1,35,35,35,35,-1,34,35,35,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,36,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,37,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
39,38,-1,-1,39,-1,-1,-1,-1,-1,39,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
40,-1,-1,-1,42,-1,-1,-1,-1,-1,41,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,43,-1,43,-1,-1,-1,-1,-1,-1,-1,43,-1,-1,-1,43,43,43,43,43,43,43,43,43,43,43,-1,-1,
-1,44,44,44,-1,-1,-1,-1,-1,-1,45,44,-1,-1,-1,44,44,44,44,44,44,44,44,44,44,44,44,-1,
-1,47,-1,47,-1,-1,-1,-1,-1,-1,-1,47,-1,-1,-1,47,47,47,47,47,47,47,47,47,47,47,46,-1,
48,-1,-1,-1,48,-1,-1,-1,-1,-1,48,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,50,-1,50,-1,-1,-1,-1,-1,-1,-1,50,-1,-1,-1,49,49,49,49,49,49,-1,-1,-1,-1,50,-1,-1,
51,-1,-1,-1,51,-1,-1,-1,-1,-1,51,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,53,-1,53,-1,-1,-1,-1,-1,-1,-1,53,-1,-1,-1,53,53,53,53,53,53,52,52,-1,-1,53,-1,-1,
54,-1,-1,-1,54,-1,-1,-1,-1,-1,54,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,56,-1,56,-1,-1,-1,-1,-1,-1,-1,56,-1,-1,-1,56,56,56,56,56,56,56,56,55,55,56,-1,-1,
-1,-1,57,-1,-1,-1,-1,-1,-1,-1,58,57,-1,-1,-1,-1,-1,-1,-1,-1,-1,57,57,57,57,-1,-1,-1,
-1,59,60,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,61,62,61,-1,-1,-1,-1,-1,-1,-1,61,-1,-1,-1,61,61,61,61,61,61,61,61,61,61,61,61,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,63,64,65,66,67,68,-1,-1,-1,-1,-1,-1,-1,
-1,-1,70,-1,-1,-1,-1,-1,-1,-1,-1,69,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,69,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,71,72,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,73,74,-1,-1,-1,
76,-1,-1,-1,77,-1,-1,-1,-1,-1,75,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,78,79,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
};



//
void printtree(tnode *t)
{int i,j;
	if(t->str=="")
		return; 

	for(i=0;i<t->n;i++)
	{
		for(j=0;j<t->lineno+1;j++)
			fputs("-",fp);
			//printf("-");
		//printf("%s:\n",t->child[i]->str);
			fputs(t->child[i]->str,fp);
        fputs("\r\n",fp);
		printtree(t->child[i]);
	}

}

//创建节点
tnode *newtreenode(void)
{
	int i=0;
	tnode *t=(tnode *) malloc(sizeof(tnode));
	for(;i<6;i++)
	{
		t->child[i]=NULL;
	}
	t->str="";
	t->lineno=0;
	t->n=0;
	return t;
}

//添加节点
tnode *addtreenode(tnode *t,int i,char *s)
{

	t->child[i]=NULL;
	t->str=s;
	return t;
}

//判断是否是终结符号
int isinnt(char *q)
{
	int j=0;
	int i;
	for(i=0;i<num;i++)
	{
		if(strcmp(nt[i],q)==0)
		j=1;
	}
	return j;
}

//判断一个串在某个字符数组的位置
int findstring(char *string,char *p[],int n)
{
	int j;
	for(j=0;j<n;j++)
	{
		if(strcmp(p[j],string)==0)
		{
			return j;
		}
	}
	return -1;
}


initiate()
{
	td=newtreenode();
	addtreenode(td,0,"program");
	td->n=1;
}


int errorcheck(char *p)
{
	int h,l;//table表的行列号
	int n=0;//generate表达式的压栈的个数
	while(1)
	{		
		if(isinnt(stack[sp]))//如果分析栈顶部为终结符
		{
			if(strcmp(stack[sp],p)==0)
			{
				sp--;
				return 1;
			}
			else
				return 0;
		}
		
		else
		{
			h=findstring(stack[sp],t,number);
			l=findstring(p,nt,num);

			if(l==-1||table[h][l]==-1)
				return 0;
		


			else
			{
				if(strcmp(q1[table[h][l]],"e")==0)
					n=0;
				else if(strcmp(q2[table[h][l]],"e")==0)
					n=1;
				else if(strcmp(q3[table[h][l]],"e")==0)
					n=2;
				else if(strcmp(q4[table[h][l]],"e")==0)
					n=3;
				else if(strcmp(q5[table[h][l]],"e")==0)
					n=4;
				else if(strcmp(q6[table[h][l]],"e")==0)
					n=5;
				else
					n=6;
				
				sp--;

				if(n==0) continue;
				//表达式压栈
				for(;n>=1;n--)
				{
					sp++;
					if(n==1)
					{
						stack[sp]=q1[table[h][l]];
					//	printf("%s	",q1[table[h][l]]);
					}
					if(n==2)
					{
						stack[sp]=q2[table[h][l]];
					//	printf("%s	",q2[table[h][l]]);
					}
					if(n==3)
					{
						stack[sp]=q3[table[h][l]];
					//	printf("%s	",q3[table[h][l]]);
					}
					if(n==4)
					{
						stack[sp]=q4[table[h][l]];
					//	printf("%s	",q4[table[h][l]]);
					}
					if(n==5)
					{
						stack[sp]=q5[table[h][l]];
					//	printf("%s	",q5[table[h][l]]);
					}
					if(n==6)
					{
						stack[sp]=q6[table[h][l]];
					//	printf("%s	",q6[table[h][l]]);
					}
				}
				n=0;
					
			}
		}
	}

}

tnode *parsetr(tnode* tt)
{
	int i=0,j=0,c=0;
	int h,l;//table表的行列号
	int n=0;//generate表达式的压栈的个数
	
	if(get==1)
	{
		if(tk==ENDFILE)	return tt;
	if(sp==0 ||getToken()==ENDFILE)
	{
		tk=getToken();
		get=0;
		return tt;
	}
	if(flag==1)p="ID";
		else if(flag==3)
			p="NUM";
		else
			p=&tokenString;
		flag=0;
	}
	get=0;
	
	//	if(flag==1 ||flag==2 ) flag=0;//id=1,res=2,other=0,num=3
	if(isinnt(stack[sp]))//如果分析栈顶部为终结符
		{
			if(strcmp(stack[sp],p)==0)
			{
				sp--;
				get=1;
				return tt;
			}
			
			else
			{
				sp--;
				parsetr(tt);
			}
		}
	else
		{
			h=findstring(stack[sp],t,number);
			l=findstring(p,nt,num);
			if(l==-1||table[h][l]==-1)
			{
				if(ENDFILE==tk)
				return tt;

				for(i=0;i<=num-1;i++)
				{
					if(1==errorcheck(nt[i]))
					{
						break;
					}
				}
			}

			else
			{
				if(strcmp(q1[table[h][l]],"e")==0)
					n=0;
				else if(strcmp(q2[table[h][l]],"e")==0)
					n=1;
				else if(strcmp(q3[table[h][l]],"e")==0)
					n=2;
				else if(strcmp(q4[table[h][l]],"e")==0)
					n=3;
				else if(strcmp(q5[table[h][l]],"e")==0)
					n=4;
				else if(strcmp(q6[table[h][l]],"e")==0)
					n=5;
				else
					n=6;
				
				sp--;
				j=n;
				//if(n==0) return tt;
				//表达式压栈
				for(;n>=1;n--)
				{
					sp++;
					if(n==1)
					{
						stack[sp]=q1[table[h][l]];
					//	printf("%s	",q1[table[h][l]]);
					}
					if(n==2)
					{
						stack[sp]=q2[table[h][l]];
					//	printf("%s	",q2[table[h][l]]);
					}
					if(n==3)
					{
						stack[sp]=q3[table[h][l]];
					//	printf("%s	",q3[table[h][l]]);
					}
					if(n==4)
					{
						stack[sp]=q4[table[h][l]];
					//	printf("%s	",q4[table[h][l]]);
					}
					if(n==5)
					{
						stack[sp]=q5[table[h][l]];
					//	printf("%s	",q5[table[h][l]]);
					}
					if(n==6)
					{
						stack[sp]=q6[table[h][l]];
					//	printf("%s	",q6[table[h][l]]);
					}
				}
			}
	}
		
		tt->n=j;
		j=sp;
		if(tt->n==0)
		{
			if(ENDFILE==tk)
				return tt;
			c=0;
			tt->child[c]=newtreenode();
			addtreenode(tt->child[c],c,nt[i]);
			return tt;
		}
	

		for(c=0;c<tt->n;c++)
		{
			tt->child[c]=newtreenode();
			addtreenode(tt->child[c],c,stack[j--]);//t->child[i]=NULL;t->str=s;	return t;
		//	printf("%s\n",tt->child[c]->str);
		}
	//	printf("%d\n",tt->n);

		tt->lineno=tab++;
		for(c=0;c<tt->n;c++)
		{
			parsetr(tt->child[c]);
		}	
		
		return tt;

}



void parse()
{
	int i=0,j=0;
	int h,l;//table表的行列号
	int n=0;//generate表达式的压栈的个数

	while(getToken()!=ENDFILE && sp!=0)
	{

	//	if(flag==1 ||flag==2 ) flag=0;//id=1,res=2,other=0,num=3
		if(flag==1)p="ID";
		else if(flag==3)
			p="NUM";
		else
			p=&tokenString;
		flag=0;
loop:	while(1)
		{		
			if(isinnt(stack[sp]))//如果分析栈顶部为终结符
		{
			if(strcmp(stack[sp],p)==0)
			{
				sp--;
				break;
			}
			else
			{

			printf(">>> lose char1 at line %d:  -> %s\n\n",lineno,stack[sp]);
			sp--;
		
			goto loop;
			break;
			
			}

		}

		else
		{
			h=findstring(stack[sp],t,number);
			l=findstring(p,nt,num);
			if(l==-1||table[h][l]==-1)
			{
				//buf=p;
				printf(">>> Syntax error2 at line %d: unexpected token -> %s\n\n",lineno,p);
				for(i=0;i<=num-1;i++)
				{
					if(1==errorcheck(nt[i]))
					{
						printf(">>> lose char2 at line %d:  -> %s\n\n",lineno,nt[i]);
						break;
						
					}

				}
				break;

			}

			else
			{
				if(strcmp(q1[table[h][l]],"e")==0)
					n=0;
				else if(strcmp(q2[table[h][l]],"e")==0)
					n=1;
				else if(strcmp(q3[table[h][l]],"e")==0)
					n=2;
				else if(strcmp(q4[table[h][l]],"e")==0)
					n=3;
				else if(strcmp(q5[table[h][l]],"e")==0)
					n=4;
				else if(strcmp(q6[table[h][l]],"e")==0)
					n=5;
				else
					n=6;
				
				sp--;

				if(n==0) continue;
				//表达式压栈
				
			for(;n>=1;n--)
				{
					sp++;
					if(n==1)
					{
						stack[sp]=q1[table[h][l]];
					//	printf("%s	",q1[table[h][l]]);
					}
					if(n==2)
					{
						stack[sp]=q2[table[h][l]];
					//	printf("%s	",q2[table[h][l]]);
					}
					if(n==3)
					{
						stack[sp]=q3[table[h][l]];
					//	printf("%s	",q3[table[h][l]]);
					}
					if(n==4)
					{
						stack[sp]=q4[table[h][l]];
					//	printf("%s	",q4[table[h][l]]);
					}
					if(n==5)
					{
						stack[sp]=q5[table[h][l]];
					//	printf("%s	",q5[table[h][l]]);
					}
					if(n==6)
					{
						stack[sp]=q6[table[h][l]];
					//	printf("%s	",q6[table[h][l]]);
					}
					
				}
				n=0;
					
			}

		
		}
		}
	}
	

}