语法.cpp

用预测分析法实现的语法分析

#include <fstream.h>
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#define max_id	256		//标识符最大长度；
#define stack_size	90	//栈的大小；
#define max_in  90    //输入存放数组的大小；
struct token{
char id;
char val[max_id];
};		//符号表表项的结构体定义;
char row[]={"PMSXKLRQEATBFC"};       //预测分析表的行标号;
char collumn[]={"i(){}e;5401uv=+-*/n>y<xzw$"};  //预测分析表的列标号;
int M[14][26]={ {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,2,1,-1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
				{7,-1,-1,-1,-1,3,-1,4,5,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
				{9,-1,-1,-1,9,9,-1,9,9,9,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
				{10,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10,10,-1,-1,10,-1,-1,-1,-1,-1,-1,-1},
				{-1,-1,12,-1,-1,-1,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,11,11,11,11,11,11,-1},
				{13,-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,14,15,16,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
				{17,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,17,17,-1,-1,17,-1,-1,-1,-1,-1,-1,-1},
				{-1,-1,20,-1,-1,-1,20,-1,-1,-1,-1,-1,-1,-1,18,19,-1,-1,-1,20,20,20,20,20,20,-1},
				{21,21,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,21,21,-1,-1,21,-1,-1,-1,-1,-1,-1,-1},
				{-1,-1,24,-1,-1,-1,24,-1,-1,-1,-1,-1,-1,-1,24,24,22,23,-1,24,24,24,24,24,24,-1},
				{28,25,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,27,26,-1,-1,29,-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,30,31,32,33,34,35,-1}};
//const char *p[]={"AT","AT+","\0","BF","BF*","\0",")E(","i"}; //产生式右端集合;
const char *q[]={"P→i(){M}","M→SM","M→ε","S→for(R;K;R){M}","S→while(K){M}","S→do{M}while(K)"
				,"S→if(K){M}X","S→R;","X→else{M}","X→ε","K→EL","L→CE","L→ε","R→iQ;","Q→u"
				,"Q→v","Q→=E","E→TA","A→+TA","A→-TA","A→ε","T→FB","B→*FB","B→/FB","B→ε"
				,"F→(E)","F→-F","F→+F","F→i","F→n","C→>","C→>=","C→<","C→<=","C→==","C→!="};

//const char *q[]={"P→i(){M}","M→SM","M→ε","S→e(R;K;R){M}","S→5(K){M}","S→4{M}5(K)"
//				,"S→0(K){M}X","S→R;","X→1{M}","X→ε","K→EL","L→CE","L→ε","R→iQ;","Q→u"
//				,"Q→v","Q→=E","E→TA","A→+TA","A→-TA","A→ε","T→FB","B→*FB","B→/FB","B→ε"
//				,"F→(E)","F→-F","F→+F","F→i","F→n","C→>","C→y","C→<","C→x","C→z","C→w"};
const char *p[]={"}M{)(i","MS","\0","}M{)R;K;R(e","}M{)K(5",")K(5}M{4","X}M{)K(0",";R","}M{1","\0",
                "LE","EC","\0","Qi","u","v","E=","AT","AT+","AT-","\0","BF","BF*","BF/","\0",")E(",
				"F-","F+","i","n",">","y","<","c","z","w"};
//关键字与界符的编码如下：for-e,while-5,do-4,if-0,else-1,++-u,---v,>=-y,<=-x,==-z,!=-w
/*定义预测分析表;
0.P→i(){M}
1.M→SM
2.M→ε
3.S→for(R;K;R){M}
4.S→while(K){M}
5.S→do{M}while(K)
6.S→if(K){M}X
7.S→R;
8.X→else{M}
9.X→ε
10.K→EL
11.L→CE
12.L→ε
13.R→iQ;
14.Q→u
15.Q→v
16.Q→=E
17.E→TA
18.A→+TA
19.A→-TA
20.A→ε
21.T→FB
22.B→*FB
23.B→/FB
24.B→ε
25.F→(E)
26.F→-F
27.F→+F
28.F→i
29.F→n
30.C→>
31.C→>=
32.C→<
33.C→<=
34.C→==
35.C→!=*/
int link(char c)	//关联函数，将输入的字符转换为对应的行(列)号；
{	int i;
	int a=strlen(row);
	for(i=0;i<a;i++)
		if(row[i]==c)	return i;
	a=strlen(collumn);
	for(i=0;i<a;i++)
		if(collumn[i]==c)	return i;
		return -1;
}
int ifterminal(char c)	
//判断函数，判断输入的字符是否为终结符，是终结符则返回1，是非终结符则返回0，出错则返回-1；
{	int i;
	int a=strlen(row);
	for(i=0;i<a;i++)
		if(row[i]==c) return 0;
	a=strlen(collumn);
	for(i=0;i<a;i++)
		if(collumn[i]==c)	return 1;
	return -1;
}
void main()
{	token temp[max_in];
	char filename[40];
	cout<<"请输入语法分析源文件的文件名及路径：";
	cin>>filename;
	ifstream infile(filename,ios::in);
	cout<<"请输入语法分析过程描述文件的文件名及路径：";
	cin>>filename;
	ofstream outfile(filename,ios::out);
//	infile>>temp.id>>temp.val;
	char stack[stack_size]={'$','P'};
	//定义并初始化栈，栈底置$,栈顶为开始状态；
	int  top_ptr=1;
	char inbuff[max_in]={'\0'};
	int in_ptr=0;
	outfile<<"栈"<<'\t'<<'\t'<<'\t'<<'\t'<<"输入"<<'\t'<<'\t'<<'\t'<<'\t'<<'\t'<<"输出"<<endl;
	//输出表头； 
	int i=0;
//	char ch;
	do{	infile>>temp[i].id>>temp[i].val;
		if(temp[i].id=='#') break;
		inbuff[i]=temp[i].id;
		i++;
	}while(1);
	//从源文件中读入token字；
	inbuff[i]='$';
	outfile<<stack<<'\t'<<'\t'<<'\t'<<inbuff<<'\t'<<'\t'<<'\t'<<endl;
	cout<<inbuff<<endl;
	while(top_ptr!=0)
	{	//outfile<<stack<<'\t'<<inbuff<<'\t';
		int b=-1;
		int a=ifterminal(stack[top_ptr]);
		if(a==1)	//栈顶是终结符或$；
		{	
			if(stack[top_ptr]==inbuff[in_ptr])
			//若栈顶字符与输入字符串的当前字符匹配，则栈顶字符出栈，并且输入指针向前移动一位；　
			{	stack[top_ptr]='\0';
				top_ptr--;
				inbuff[in_ptr]=' ';
				in_ptr++;
			}
			else
			{	cout<<"出错！栈顶符号与输入符号不匹配!"<<endl;
				break;
			}
		}
		else
			//栈顶为非终结符则调用产生式替换栈顶的非终结符，栈顶指针随之移动，输入指针不动；
		{	int m=link(stack[top_ptr]);
			int n=link(inbuff[in_ptr]);
		    b=M[m][n];
			if(b!=-1)
			{	//char temp=stack[top_ptr];
		//		outfile<<stack[top_ptr]<<"->"<<q[b]<<endl;
				stack[top_ptr]='\0';
				top_ptr--;
				strcat(stack,p[b]);
				top_ptr+=strlen(p[b]);
			}
			else
			{	cout<<"出错！预测分析表中无匹配的产生式!"<<endl;
			break;}
		}
		if(b!=-1)
			outfile<<stack<<'\t'<<'\t'<<'\t'<<inbuff<<'\t'<<'\t'<<q[b]<<endl;
		else
			outfile<<stack<<'\t'<<'\t'<<'\t'<<inbuff<<'\t'<<'\t'<<endl;
	}	//进行语法分析并输出分析的过程到指定文件；

}