judge.cpp

文法类型的判断 编译原理实验 C语言模拟实现 判断正规文法、上下文无关文法、上下文有关文法

#include<stdio.h>
#include<malloc.h>
const int MAX_LENGTH=10;//符号串的最大长度
#define null 0

struct VN//在此链表中存储文法的非终结符集
{
	char Vn;
	VN* next;
};

struct VT//在此链表中存储文法的终结符集
{
	char Vt;
	VT* next;
};

struct P//在此链表中存储文法的产生式
{
	char left[MAX_LENGTH];
	char right[MAX_LENGTH];
	P* next;
};

VN VNinput;//存储输入的非终结符集
VN *vn= &VNinput;

VT VTinput;//存储输入的非终结符集
VT *vt= &VTinput; 

P Pinput;
P *p1= &Pinput;

void inputVN()//获取用户输入的非终结符集，存入链表VN
{
	VNinput.next=null;//初始化链表
	char c;//临时存放输入的单个非终结符
	VN *vn0;
	printf("请输入文法的开始符号：\n");
	scanf("%c",&c);
	getchar();//过滤回车
	VNinput.Vn=c;//链表的第一个元素为文法的开始符号
	printf("请输入文法的非终结符集（除开始符号），以@结束：\n");
	while(true)
	{
		scanf("%c",&c);
		if(c=='@')break;
		vn0=(VN*)malloc(sizeof(VN));
		vn0->Vn=c;
		vn0->next=vn->next;
		vn->next=vn0;
	}
	getchar();//过滤回车
}

void inputVT()//获取用户输入的终结符集，存入链表VT
{
	VTinput.next=null;//初始化链表，链表的第一个元素为头结点，不存储终结符
	char c;//临时存放输入的单个终结符
	VT *vt0;
	printf("请输入文法的终结符集，以@结束：\n");
	while(true)
	{
		scanf("%c",&c);
		if(c=='@')break;
		vt0=(VT*)malloc(sizeof(VT));
		vt0->Vt=c;
		vt0->next=vt->next;
		vt->next=vt0;
	}
	getchar();//过滤回车
}

void inputP()//获取用户输入的产生式
{
	
	Pinput.next=null;//初始化链表，链表的第一个元素为头结点，不存储产生式
	P *p2;
	printf("输入文法的产生式,并以$结束单个产生式的输入，以@结束全部输入：\n");
	while(true)
	{
		int i,flag=0;//flag用来判断输入是否结束
		p2=(P*)malloc(sizeof(P));
		for(i=0;i<MAX_LENGTH;i++)//产生式两端的符号串长度不超过10，若超过，则做截断处理
		{
			scanf("%c",&p2->left[i]);
			if(p2->left[i]=='-')
			{
				p2->left[i]='\0';
				getchar();//过滤">"
				for(i=0;i<MAX_LENGTH;i++)//产生式两端的符号串长度不超过10，若超过，则做截断处理
				{
					scanf("%c",&p2->right[i]);
					if(p2->right[i]=='$')	//判断单个产生式是否输入结束
					{
						p2->right[i]='\0';
						getchar();//过滤回车
						break;
					}
					if(p2->right[i]=='@')break;//输入@则结束所有产生式的输入
				}
				if(p2->right[i]=='@')//所有产生式均已输入
				{
					flag=1;
					p2->right[i]='\0';
					getchar();//过滤回车
					break;
				}
				if(p2->right[i]=='\0')break;//产生式以$结束
			}
		}
		p2->next=p1->next;
		p1->next=p2;
		if(flag==1)break;
	}
}

int isVN(char c)//判断c是否是非终结符
{
	VN *v;
	v=vn;
	while(v!=null)
	{
		if(c==v->Vn)return 1;
		else v=v->next;
	}
	return 0;
}

int isVT(char c)//判断c是否是终结符
{
	VT *v;
	v=vt->next;
	while(v!=null)
	{
		if(c==v->Vt)return 1;
		else v=v->next;
	}
	return 0;
}

void judge()//文法类别的判断
{
	P *p0=p1->next;
	while(p0!=null)
	{
		if(isVN(p0->left[0])&&(p0->left[1])=='\0'&&isVT(p0->right[0]))
		{
			if(p0->right[1]=='\0'){p0=p0->next;continue;}
			else{
				if(isVN(p0->right[1])&&(p0->right[2])=='\0')p0=p0->next;
				else break;
			}
		}
		else break;
	}
	if(p0==null)
		{printf("您输入的文法是3型文法！\n");return;}
	while(p0!=null)
	{
		if(isVN(p0->left[0])&&(p0->left[1])=='\0')
			p0=p0->next;
		else break;
	}
	if(p0==null){printf("您输入的文法是2型文法！\n");return;}
	while(p0!=null)
	{
		int i,j;
		for(i=0;(p0->left[i])!='\0';i++);//while(p0->left[i])i++;
		for(j=0;(p0->right[j]!='\0');j++);
		if(i<=j)p0=p0->next;
		else {printf("您输入的文法既不是3型，又不是2型的，也不是1型的！\n");break;}
	}
	if(p0==null)
		printf("您输入的文法是1型文法！\n");
}

void main()
{
	inputVN();//输入非终结符集
	inputVT();//输入终结符集
	inputP();//输入产生式
	judge();//文法类别的判断
}