30.cpp

四元式

/*文法

  S->if E then B else B
  B->id=id
  E->id A id
  A-> <|>

*/

#include<iostream.h>
#include<fstream.h>
#include<string.h>
#define MAX_TOKEN 256

#define IF 4
#define ELSE 5
#define THEN 6
#define ID 7

#define LESS 8
#define GREAT 9
#define ASSIGN 10

//非终结符
#define S 0
#define E 1
#define B 2
#define A 3
#define END 11
#define W -2
//定义存储符号的栈
typedef struct
{
	int type;
	char str;
}SM;
SM Stack[200]={END,' '};
//定义存储关键字的链表 
typedef struct
{
	int type;
	char ch;
}TokenNode;
TokenNode token[MAX_TOKEN];
int token_index=0;
int token_len=0;
//定义规则的结点
typedef struct
{
	int left;
	int right[20];
	int rlen;
}Formula;
//定义规则
Formula product[5]={{S,{IF,E,THEN,B,ELSE,B},6},{E,{ID,A,ID},3},{A,{LESS},1},{A,{GREAT},1},{B,{ID,ASSIGN,ID},3}};//产生式

//算符优先表
int bijiao[12][12]=
{
	{W,W,W,W,W,W,W,W,W,W,W,W},
	{W,W,W,W,W,W,0,W,W,W,W,W},
	{W,W,W,W,W,0,W,W,W,W,W,1},
	{W,W,W,W,W,W,W,0,W,W,W,W},
	{W,0,W,W,W,W,W,-1,W,W,W,W},
	{W,W,0,W,W,W,W,-1,W,W,W,W},
	{W,W,0,W,W,W,W,-1,W,W,W,W},
	{W,W,W,0,W,1,1,W,-1,-1,0,1},
	{W,W,W,W,W,W,W,1,W,W,W,W},
	{W,W,W,W,W,W,W,1,W,W,W,W},
	{W,W,W,W,W,W,W,0,W,W,W,W},
	{W,W,W,W,-1,W,W,W,W,W,W,W}
};
//
//函数声明
int label();
int JB();
int fform(int left,int right);
void GY(int can,int begin,int end);
bool statement();
void lxc(char file[125]);
void printToken();

int top=1;

int labelf[100];
int labeltop=0;
int labelindex=1;

void main()
{
	char filename[120];
	cout<<endl<<"Please input the name of file: ";
	cin>>filename;
	lxc(filename);
	cout<<endl<<"The result of CIFA analyse :\n"<<endl;
	printToken();
	cout<<endl<<"\nThe FourTable as followings:\n"<<endl;
	if(!statement())
		cout<<"ERROR"<<endl;
}

int label()
{
	return labelindex++;
}
//查看句柄出现在什么位置
int JB()
{
	int index=top-1;
	if(bijiao[Stack[index-1].type][Stack[index].type]!=1)
	{
		if(bijiao[Stack[index-1].type][Stack[index].type]==W)
			return -2;
		else
			return -1;
	}
	for(int i=index-1;i>=0;i--)
	{
		if(bijiao[Stack[i-1].type][Stack[i].type]==-1)
			return i;
		if(bijiao[Stack[i-1].type][Stack[i].type]==W)
			return -2;
	}
	return -1;
}
//判断句柄是哪个规则的右部
int fform(int left,int right)//找句柄，-1表示没找到，其他表示产生式索引
{
	for(int count=0;count<=5;count++)
	{
		for(int i=left;i<=right;i++)
		{
			if(product[count].right[i-left]!=Stack[i].type)
				break;
		}
		if(i>right)
			return count;
	}
	if(count>5)
		return -1;
	else
		return count;
}

void GY(int can,int begin,int end)//归约，符号栈中begin-end
{
	Stack[begin].type=product[can].left;
	if(can==1)
	{
		int efalse=label();
		int etrue=label();
	
		labelf[labeltop++]=efalse;
		labelf[labeltop++]=etrue;

		cout<<"      J "<<","<<Stack[begin].str<<","<<Stack[end].str<<",T"<<etrue;
		cout<<"      J ,-,-,T"<<efalse<<endl; 
	}
	else if(can==4)
	{
		cout<<"T"<<labelf[--labeltop]<<":   =,"<<Stack[end].str<<",-,"<<Stack[begin].str<<endl;
		if(Stack[begin-1].type==THEN)
		{
			cout<<"      J,-,-,T1"<<endl;
		}
	}
	else if(can==0)
	{
		cout<<"T"<<labelf[--labeltop]<<":   -,-,-,-"<<endl;
		labelf[labeltop++]=label();
	}
	for(int i=end+1,j=begin+1;i<top;i++,j++)
	{
		Stack[j]=Stack[i];
	}
	top=top-(end-begin);

}

bool statement()
{

	labelf[labeltop++]=1000;
	int pindex=0;
	int ju=-1;
	while(1)
	{
		if(Stack[top-1].type==END)
		{
			if(top>3 && ju==-1)
				return false;
		}
		if(top==3 && Stack[0].type==END && Stack[1].type==S && Stack[2].type==END)
		{
			cout<<"\nSuccessful!\n"<<endl;
			return true;
		}
		if(ju==-1)
		{
			Stack[top].str=token[pindex].ch;
			Stack[top++].type=token[pindex++].type;
		}
		else if(ju==-2)
		{
			return false;
		}
		else
		{
			int gui=fform(ju,top-2);
			if(gui==-1)
				return false;
			GY(gui,ju,top-2);
		}
		ju=JB();
	}

}

void lxc(char file[125])
{
	ifstream in;
	in.open(file);
	char si[16];
	char ch;
	while(1)
	{
		in>>ch;
	if(in.fail())
			break;
		if(ch=='I')
		{
		in>>si;
		if(strcmp(si,"F")==0)
			token[token_len++].type=IF;
	}
	else if(ch=='T')
	{
		in>>si;
		if(strcmp(si,"HEN")==0)
			token[token_len++].type=THEN;
	}
	else if(ch=='E')
	{
		in>>si;
		if(strcmp(si,"LSE")==0)
			token[token_len++].type=ELSE;
	}
	else if(ch=='<')
	{
		token[token_len].ch='<';
		token[token_len++].type=LESS;	}
	else if(ch=='>')
		{
			token[token_len].ch='>';
			token[token_len++].type=GREAT;
		}
		else if(ch=='=')
		{
			token[token_len].ch='=';
			token[token_len++].type=ASSIGN;
		}
		else if(ch=='x' || ch=='a' || ch=='b')
		{
			token[token_len].type=ID;
			token[token_len++].ch=ch;
		}
	}
	token[token_len++].type=END;
}

void printToken()
{
	for(int i=0;i<token_len;i++)
	{
		if(token[i].type==IF)
			cout<<IF<<"  IF  "<<",";
		if(token[i].type==ELSE)
			cout<<ELSE<<" ELSE  "<<",";
		if(token[i].type==THEN)
			cout<<THEN<<"  THEN  "<<",";
		if(token[i].type==ASSIGN)
			cout<<ASSIGN<<"  =  "<<",";
		if(token[i].type==LESS)
			cout<<LESS<<"  <  "<<",";
		if(token[i].type==GREAT)
			cout<<GREAT<<"  >  "<<",";
		if(token[i].type==ID)
			cout<<"    "<<ID<<"  "<<token[i].ch<<"  "<<",";
	}
}