11.txt

该程序能够对if-else进行语法指导的翻译

#include<iostream>
#include<cstdio>   //包含gets();
#include<cstring>  //包含strcmp();
#include<cctype>   //包含isdigit(),isalpha()
using namespace std;

#define symbolSize 28
#define generateSize 21
#define NULL 0
//----------------------------词法分析---------------------------------------------------
typedef struct Node{
	int type;//单词类型
	char data[10];
	struct Node*next;
}TNode;

char *key[]={"main","int","double","void","char","if","else",
             "for","while","switch","case","return","cout","cin","endl"};
char *suanfu4[]={"+","-","*","/","<",">",">=","<=","=","==","!=","++","--","&","&&","|","||","!"};
char *jiefu5[]={"{","}",";","(",")","<<",">>"};
char token[10];
char str[256];
static int k=0;

void initlize(){
	cout<<"Enter a string:";
	gets(str);
	cout<<"The string you put is:"<<endl;
	cout<<str;
	cout<<endl;
}

char getcch(){
	char ch;
	ch=str[k];
	while(ch==' '&&k<256){
		ch=str[k+1];
		k++;
	}
	return ch;
}

char getkch(){
	char ch=str[k+1];
	k++;
	return ch;
}

int letter(char ch){
	return isalpha((int)ch);
}

int digit(char ch){
	return isdigit((int)ch);
}

int suanfu(char ch){
	if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%'||ch=='<'||ch=='>'
		||ch=='='||ch=='!'||ch=='&'||ch=='|')
		return 1;
	return 0;
}

int jiefu(char ch){
	if(ch=='('||ch==')'||ch=='{'||ch=='}'||ch==';'||ch=='<'||ch=='>'
		||ch==',')
		return 1;
	return 0;
}

int reserve(){
	int i;
	for(i=0;i<20;i++){
		if(!(strcmp(key[i],token))) 
			return 3;
	}
	return 1;
}

void keysym(char ch){
	int i=0;
	int r;
	while(letter(ch)||digit(ch)||ch=='_'){
			token[i]=ch;
			token[i+1]='\0';
			ch=getkch();
			i++;
	}
	r=reserve();
}

void digitsym(char ch){
	int i=0;
	while(digit(ch)||ch=='.'||ch=='E'||ch=='e'){
			token[i]=ch;
			token[i+1]='\0';
			ch=getkch();
			i++;
		}
}

int suanfusym(char ch){
	if(suanfu(ch)){
		token[0]=ch;
		token[1]='\0';
		ch=getkch();
		if(!suanfu(ch))
			return 1;
		else{
			token[1]=ch;
			token[2]='\0';
			if(token[0]=='+'&&token[1]=='+'){
				k++;
				return 1;
			}
			if(token[0]=='-'&&token[1]=='-'){
				k++;
				return 1;
			} 
			if(token[0]=='!'&&token[1]=='='){
				k++;
				return 1;
			} 
			if(token[0]=='='&&token[1]=='='){
				k++;
				return 1;
			}
			if(token[0]=='>'&&token[1]=='='){
				k++;
				return 1;
			} 
			if(token[0]=='<'&&token[1]=='='){
				k++;
				return 1;
			}
			if(token[0]=='|'&&token[1]=='|'){
				k++;
				return 1;
			} 
			if(token[0]=='&'&&token[1]=='&'){
				k++;
				return 1;
			} 
			if(token[0]=='<'&&token[1]=='<'){
				k++;
				return 0;
			} 
			if(token[0]=='>'&&token[1]=='>'){ 
			k++;
			return 0;
			}
		}
	}	
	return 1;
}

int jiefusym(char ch){
	int i=0;
	if(jiefu(ch)){
		token[i]=ch;
		token[i+1]='\0';
		ch=getkch();	
		if(!jiefu(ch))		
	    	return 0;
	}
	return 1;
}

void print(TNode *head){
	TNode *r;
	r=head->next;
	while(r->next){
		cout<<r->type<<"  "<<r->data<<endl;
		r=r->next;
	}
	cout<<"0  "<<r->data<<endl;
}

TNode* word_analysis(TNode *head){
	cout<<"单词种别：标识符－－1，常数－－2，关键字－－3，运算符－－4，界符－－5"<<endl;
	initlize();
	char ch;
	int j;	
	head=new TNode;
	head->next=NULL;
	TNode *p,*s;
	p=head;
	cout<<"The words after being analyzed are:"<<endl;
	do{
		for(j=0;j<10;j++)
			token[j]=NULL;
  		ch=getcch();
		if(letter(ch)||ch=='_'){
			keysym(ch);
			s=new TNode;
			s->type=reserve();
			strcpy(s->data,token);
			s->next=NULL;
			if(head->next==NULL){
				head->next=s;
				p=s;
			}
			else{
				p->next=s;
				p=s;
			}
		}
		else if(digit(ch)){
			digitsym(ch);
			s=new TNode;
			s->type=2;
			strcpy(s->data,token);
			s->next=NULL;
			if(head->next==NULL){
				head->next=s;
				p=s;
			}
			else{
				p->next=s;
				p=s;
			}
		}
		else if(suanfu(ch)){
         	s=new TNode;
			if(suanfusym(ch)==1)
		        s->type=4;
            else if(suanfusym(ch)==0)
		        s->type=5;
			strcpy(s->data,token);
			s->next=NULL;
			if(head->next==NULL){
				head->next=s;
				p=s;
			}
			else{
				p->next=s;
				p=s;
			}
		}
		else if(jiefu(ch)){
			jiefusym(ch);
			s=new TNode;
			s->type=5;
			strcpy(s->data,token);
			s->next=NULL;
			if(head->next==NULL){
				head->next=s;
				p=s;
			}
			else{
				p->next=s;
				p=s;
			}
		}
	}while(ch!='#');
	TNode *rear=new TNode;
	strcpy(rear->data,"#");
	rear->next=NULL;
	s->next=rear;	
	print(head);
	return head;
}

//-----------------------------------语法分析及语义处理-------------------------------------------

typedef struct Ge{//表示产生式
	char head[2];//左部
	char *gen[5];//右部
}Generate;
Generate gene[generateSize];

void show_G(){
	cout<<"--------------------文法G[C]--------------------"<<endl;
	cout<<"(0) C -> if S then A"<<endl;
	cout<<"(1) E--> E&&T"<<endl;
	cout<<"(2) E--> T"<<endl;	
	cout<<"(3) T--> T||F"<<endl;
	cout<<"(4) T--> F"<<endl;	
	cout<<"(5) F--> (E)"<<endl;
	cout<<"(6) F-->!E"<<endl;
	cout<<"(7) F--> i rop i"<<endl;
	cout<<"(8) rop--> > | >= | < | <= |=="<<endl;
	cout<<"(9) A-->i=R"<<endl;
	cout<<"(10) R-->M"<<endl;
	cout<<"(11) M-->M+N"<<endl;
	cout<<"(12) M-->N"<<endl;
	cout<<"(13) N-->N*P"<<endl;
	cout<<"(14) N-->P"<<endl;
	cout<<"(15) P-->(M)"<<endl;
	cout<<"(16) P-->i"<<endl;
}

void init_gene(){
	strcpy(gene[0].head,"C");
	gene[0].gen[0]="if";gene[0].gen[1]="S";gene[0].gen[2]="then";gene[0].gen[3]="A";
    strcpy(gene[1].head,"E");
	gene[1].gen[0]="E";gene[1].gen[1]="&&";gene[1].gen[2]="T";
	strcpy(gene[2].head,"T");
	gene[2].gen[0]="T";gene[2].gen[1]="||";gene[2].gen[2]="F";
	strcpy(gene[3].head,"T");gene[3].gen[0]="F";
	strcpy(gene[4].head,"E");gene[4].gen[0]="T";
	strcpy(gene[5].head,"F");gene[5].gen[0]="(E)";
	strcpy(gene[6].head,"F");
	gene[6].gen[0]="i";gene[6].gen[1]=">=";gene[6].gen[2]="i";
	strcpy(gene[7].head,"F");
	gene[7].gen[0]="i";gene[7].gen[1]="<=";gene[7].gen[2]="i";
	strcpy(gene[8].head,"F");
	gene[8].gen[0]="i";gene[8].gen[1]=">";gene[8].gen[2]="i";
	strcpy(gene[9].head,"F");
	gene[9].gen[0]="i";gene[9].gen[1]="<";gene[9].gen[2]="i";
	strcpy(gene[10].head,"F");
	gene[10].gen[0]="i";gene[10].gen[1]="==";gene[10].gen[2]="i";
    strcpy(gene[11].head,"F");
	gene[11].gen[0]="!";gene[11].gen[1]="E";
	strcpy(gene[12].head,"A");
	gene[12].gen[0]="i";gene[12].gen[1]="=";gene[12].gen[2]="R";
    strcpy(gene[13].head,"M");
	gene[13].gen[0]="M";gene[13].gen[1]="+";gene[13].gen[2]="N";
	strcpy(gene[14].head,"N");
	gene[14].gen[0]="N";gene[14].gen[1]="*";gene[14].gen[2]="P";
    strcpy(gene[15].head,"N");gene[15].gen[0]="P";
	strcpy(gene[16].head,"M");gene[16].gen[0]="N";
	strcpy(gene[17].head,"P");gene[17].gen[0]="M)";
	strcpy(gene[18].head,"P");gene[18].gen[0]="i";
    strcpy(gene[19].head,"S");gene[19].gen[0]="E";
	strcpy(gene[20].head,"R");gene[20].gen[0]="M";
}

char Matrix[symbolSize][symbolSize];
void init_Matrix(){
	Matrix[0][27]='>';
	Matrix[1][2]='=';Matrix[1][3]=Matrix[1][8]=Matrix[1][9]=Matrix[1][10]=Matrix[1][15]=Matrix[1][26]='<';
    Matrix[2][4]='=';
	Matrix[3][4]='>';Matrix[3][6]=Matrix[3][16]='=';
	Matrix[4][5]='=';Matrix[4][8]='<';
	Matrix[5][27]='>';
	Matrix[6][9]='=';Matrix[6][8]=Matrix[6][10]='<';
	Matrix[7][8]='<';Matrix[7][10]='=';
    Matrix[8][4]=Matrix[8][6]=Matrix[8][7]=Matrix[8][13]=Matrix[8][14]=Matrix[8][27]='>';
	Matrix[8][11]=Matrix[8][21]=Matrix[8][22]=Matrix[8][23]=Matrix[8][24]=Matrix[8][25]='=';
    Matrix[9][4]=Matrix[9][6]=Matrix[9][15]='>';Matrix[9][7]='=';
	Matrix[10][4]=Matrix[10][6]=Matrix[10][7]=Matrix[10][15]='>';
	Matrix[11][8]=Matrix[11][12]=Matrix[11][18]=Matrix[11][19]='<';Matrix[11][20]='=';
    Matrix[12][13]='=';Matrix[12][27]='>';
	Matrix[13][8]=Matrix[13][19]='<';Matrix[13][18]='=';
	Matrix[14][8]='<';Matrix[14][19]='=';
    Matrix[15][8]=Matrix[15][9]=Matrix[15][10]='<';Matrix[15][3]='=';
	Matrix[16][4]='>';
	//
	Matrix[18][14]='=';Matrix[18][13]=Matrix[18][27]='>';
	Matrix[19][13]=Matrix[19][14]=Matrix[18][27]='>';
	Matrix[20][27]='>';
	Matrix[21][8]='=';Matrix[22][8]='=';Matrix[23][8]='=';Matrix[24][8]='=';Matrix[25][8]='=';
	Matrix[26][8]=Matrix[26][9]=Matrix[26][10]='<';Matrix[26][3]='=';
	Matrix[27][1]='<';
}

char *array[symbolSize]={"C","if","S","E","then","A","&&","||","i","T","F","=", "M","+","*",
                "(",")","-","N","P","R",">","<",">=","<=","==","!","#"};

int get_Index(char *ch){
	int i;
	for(i=0;i<symbolSize;i++){
		if(!strcmp(ch,array[i]))
			return i;
	}
	return 0;
}

struct intertable{
	char *op;
	char *arg1;
	char *arg2;
	int result;
};
intertable s_yuan_s[10];

int nextstat=1;
void gencode(char *ope,char *a1,char *a2,int res){//生成新的四元式
	s_yuan_s[nextstat].op=ope;
	s_yuan_s[nextstat].arg1=a1;
    s_yuan_s[nextstat].arg2=a2;
	s_yuan_s[nextstat].result=res;
	nextstat++;
}

int count=0;
int count_E=0;
struct E_value{
	int TC;
	int FC;
	int codebegin;
};
E_value E_val[10];

char *symbol[symbolSize];
int s_Index=0;
char *attribute[symbolSize];
char *gene_rear[5];
int length;

int merge(int i,int j){
	s_yuan_s[j].result=i;
	return j;
}

void backpatch(int i,int j){
	int temp=s_yuan_s[i].result;
	if(temp==0)
		s_yuan_s[i].result=j;
	else{
		while(s_yuan_s[temp].result)
			temp=s_yuan_s[temp].result;
		s_yuan_s[temp].result=j;
	}
}

char *str_dec[20]={"0","1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19"};

int flag;
int count_F=0;

int find_S(int &Index){
	memset(gene_rear,0,sizeof(gene_rear));
	int i,j;
	length=1;
	i=get_Index(symbol[Index-1]);
	j=get_Index(symbol[Index]);
	while(Matrix[i][j]=='='){
		Index--;
        i=get_Index(symbol[Index-1]);
		j=get_Index(symbol[Index]);
		length++;
	}
	for(i=0;i<length;i++){
		gene_rear[i]=symbol[Index];
		Index++;
	}
		//-----------语义处理-------------
	Index=Index-length;
			if((count==0)&&((Index+1)!=s_Index)){
				if((!strcmp(attribute[Index+1],">"))||(!strcmp(attribute[Index+1],"<"))||(!strcmp(attribute[Index+1],"<="))
					||(!strcmp(attribute[Index+1],">="))||(!strcmp(attribute[Index+1],"=="))){
					flag=0;
					E_val[count_E].TC=nextstat;
					E_val[count_E].codebegin=nextstat;
					E_val[count_E].FC=nextstat+1;
					count_E++;
					gencode(attribute[Index+1],attribute[Index],attribute[Index+2],0);
					gencode("-","-","-",0);
				}
				if(!strcmp(attribute[Index+1],"&&")){
					flag=1;
					backpatch(E_val[count_E-2].TC,E_val[count_E-1].codebegin);
					E_val[count_E].codebegin=E_val[count_E-2].codebegin;
                    E_val[count_E].TC=E_val[count_E-1].TC;
					E_val[count_E].FC=merge(E_val[count_E-2].FC,E_val[count_E-1].FC);
					count_E++;
				}
				if(!strcmp(attribute[Index+1],"||")){
					flag=2;
					backpatch(E_val[count_E-2].FC,E_val[count_E-1].codebegin);
					E_val[count_E].codebegin=E_val[count_E-2].codebegin;
					E_val[count_E].TC=merge(E_val[count_E-2].TC,E_val[count_E-1].TC);
                    E_val[count_E].FC=E_val[count_E-1].FC;
					count_E++;
				} 
				if(!strcmp(attribute[Index],"!")){
					flag=3;
					E_val[count_E].TC=E_val[count_E-1].FC;
					E_val[count_E].codebegin=E_val[count_E-1].codebegin;
					E_val[count_E].FC=E_val[count_E-1].TC;
					count_E++;
				}				
			}
			if((count==1)&&((Index+1)!=s_Index)&&(strcmp(symbol[s_Index-1],"A"))){//赋值语句的语义处理
				if(!strcmp(attribute[Index+1],"=")){
					count_F++;
					gencode(attribute[Index+1],attribute[Index],"-",nextstat-1);
					if(flag==0)
						backpatch(2,nextstat);						
					else if(flag==1)						
						backpatch(s_yuan_s[nextstat-count_F-1].result,nextstat);	
					else if(flag==2)
						backpatch(nextstat-count_F-1,nextstat);
					else if(flag==3)
						backpatch(1,nextstat);

				}
				else if(strcmp(attribute[Index+1],"=")){
					count_F++;
					if((flag==0)&&(count_F==1))
						backpatch(1,nextstat);
					else if((flag==1)&&(count_F==1))
						backpatch(nextstat-2,nextstat);	
					else if((flag==2)&&(count_F==1))
                        backpatch(s_yuan_s[nextstat-2].result,nextstat);
					else if((flag==3)&&(count_F==1))
						backpatch(nextstat-1,nextstat);

					gencode(attribute[Index+1],attribute[Index],attribute[Index+2],nextstat);
					attribute[Index]=str_dec[nextstat-1];
				}
			}
	return Index;
}

void find_Gene(){	
	int i,j;	
	for(i=0;i<symbolSize;i++){
		for(j=0;j<length;j++){	
			if(strcmp(gene[i].gen[j],gene_rear[j]))
				break;
		}
		if((j==length)&&(gene[i].gen[j]==0)){		
			symbol[s_Index++]=gene[i].head;			
			return;
		}
	}
}

void print(){
	int i;
/*	for(i=1;i<nextstat;i++){		
		if(i%2)
			cout<<"("<<i<<") if "<<s_yuan_s[i].arg1<<s_yuan_s[i].op<<s_yuan_s[i].arg2
			<<" goto "<<s_yuan_s[i].result<<endl;
		else cout<<"("<<i<<")"<<" goto "<<s_yuan_s[i].result<<endl;
	}*/
	for(i=1;i<nextstat;i++)
		cout<<"("<<i<<") ("<<s_yuan_s[i].op<<" "<<s_yuan_s[i].arg1<<" "<<s_yuan_s[i].arg2
		<<" "<<s_yuan_s[i].result<<")"<<endl;	
}

void analysis_process(TNode *head){
	
	TNode *p;
	symbol[0]="#";
    attribute[0]="#";
	s_Index++;
	p=head->next;
	int i,j,s_length;
	while(p){
		if((!strcmp(p->data,"#"))&&(!strcmp(symbol[s_Index-1],"C"))){
			cout<<"This sentence is a right sentence."<<endl;
			return;
		}
        if(!strcmp(p->data,"=")) count++;
		if((!strcmp(p->data,"("))||(!strcmp(p->data,")")))
			p=p->next;
		i=get_Index(symbol[s_Index-1]);
		if((p->type==1)||(p->type==2)){
			if(!strcmp(p->data,"then"))  j=get_Index("then");
			else j=get_Index("i");
		}
		else j=get_Index(p->data);				
		if((Matrix[i][j]=='<')||(Matrix[i][j]=='=')){
			if((p->type==1)||(p->type==2)){
				if(!strcmp(p->data,"then"))
					symbol[s_Index]="then";
				else symbol[s_Index]="i";
			}
			else symbol[s_Index]=p->data;
			attribute[s_Index++]=p->data;
			p=p->next;
		}
		else{
			s_length=s_Index-1;
			s_Index=find_S(s_length);
			find_Gene();
		}
	}
}

int main(){
	show_G();
	init_gene();
	init_Matrix();
    TNode *head,*w_head;
	w_head=word_analysis(head);
    analysis_process(w_head);
	print();
	return 0;
}