源程序.cpp

LL输出4元式,运用C语言编程,语言简洁明白!

#include "stdafx.h"
#include <stdio.h> 
#include <ctype.h>
#include <stdlib.h>
#include <string>
#include <iostream>
using namespace std;
#define _IF_        "if\0"                   
#define _THEN_      "then\0"                 
#define _ELSE_      "else\0"                 
#define _LESS_      "<\0"                    
#define _EQUAL_     "=\0"                   
#define _SHARP_     "#\0"                  
#define _V_         "v\0"               
#define _S_         "S\0"
#define _A_         "A\0"
#define _B_         "B\0"                                             
#define Wlength     500
#define Tlength     500
#define Wno         500
#define Slength     500
#define Ssize       500
#define SENlength   500 
typedef struct
{
	int  nno;
	char value[Wlength];
}myWord;
typedef struct node
{
	char str[Slength];
	node* next;
}mynode,*mypNode;
typedef struct 
{
	int itself;
	int parents;
	char str[Slength];
	int adTrue;
	int jump;	
}mySentence;
mypNode proPtrs[4]; 
mypNode MAa[3][7]; 

char stack[Ssize][Slength];
int nStackTop=0;
mySentence senList[Slength];
int nSenListLen=0;
int nAddress=98;
int parentStack[Ssize];
int nParentStackTop=0;
void InitLL1();
void Push(char*);
void Pop(char*);
void PushXPro(mypNode);
void OutPro(mypNode);
void InterpreterFSens();
void Fetchnext(myWord*,char*,int&);
int IsVt(char*);
mypNode ChkMAa(char*,char*);
int InterpreterVt(char*);
int InterpreterVn(char*);
void CreateSenList(char*);
void OutFSens();
int Exit();
void LL_1method(myWord* WordList)
{
	InitLL1();
	Push(_SHARP_);
	Push(_S_);
	int nIndex=0;
	char a[Slength];	
	char X[Slength];
	mypNode pTemp;
	Fetchnext(WordList,a,nIndex);
	int Tag=1;
	cout<<"此语句中使用到的产生式有："<<endl;
	while(Tag)
	{
		Pop(X);        	
		if(IsVt(X))
		{
			if(strcmp(X,a)==0)
				Fetchnext(WordList,a,nIndex);
			else
			{			
                cout<<"语法分析出错！"<<endl;
				exit(0);
			}
		}
		else if(strcmp(X,_SHARP_)==0)
		{
			if(strcmp(X,a)==0)
				Tag=0;
			else
			{		
                cout<<"语法分析出错！"<<endl;
				exit(0);
			}
		}
		else if((pTemp=ChkMAa(X,a)))
		{
			PushXPro(pTemp);			
			OutPro(pTemp);				
		}
		else
		{	
            cout<<"语法分析出错！"<<endl;
			exit(0);
		}
	}
    cout<<"语法分析成功！"<<endl<<endl;	
	InterpreterFSens();
	cout<<"产生相应的四元式为："<<endl;
	OutFSens();
}
void InterpreterFSens()
{
	int i;

	for(i=0;i<nSenListLen;i++)
	{
		if(strcmp(senList[i].str,_IF_)==0)
		{
			int j;
			for(j=0;j<nSenListLen;j++)
			{
				if(senList[j].parents==senList[i].parents && strcmp(senList[j].str,_ELSE_)==0)
				{
					senList[i].jump=senList[j].itself;
					break;
				}
			}
		}
		else if(!((i+1)<nSenListLen && strcmp(senList[i+1].str,_IF_)==0))
		{
			int nJump;
			nJump=Exit();

			senList[i].jump=nJump;
		}
	}	
}
int Exit()
{
	return senList[nSenListLen-1].itself+2;
}

void OutFSens()
{
	int i;	
	for(i=0;i<nSenListLen;i++)
	{
		if(strcmp(senList[i].str,_IF_)==0)
		{
			printf("%d",senList[i].itself);
			printf("(");
			printf("j<,v,v,%d",senList[i].adTrue);		
			printf(")\n");
			printf("%d",senList[i].itself+1);
			printf("(");
			printf("j,-,-,%d",senList[i].jump);		
			printf(")\n");
		}
		else if(!((i+1)<nSenListLen && strcmp(senList[i+1].str,_IF_)==0))
		{
			 printf("%d",senList[i].itself);			 
			 printf("(");			 
			 printf("=,v,-,v");					 
			 printf(")\n");            
			 printf("%d",senList[i].itself+1);			 
			 printf("(");			 
			 printf("j,-,-,%d",senList[i].jump);			 
			 printf(")\n");			 
		}			
	}
     	 printf("%d(-,-,-,#)\n",Exit());	
}
void OutPro(mypNode pTemp)
{   
	printf("%s->",pTemp->str);
	pTemp=pTemp->next;

	char tmepStack[Ssize][Slength];
	int nIndex=0;

	while(pTemp)
	{
		strcpy(tmepStack[nIndex++],pTemp->str);
		pTemp=pTemp->next;
	}

	for(int i=nIndex-1;i>=0;i--)
		 printf("%s ",tmepStack[i]);
    cout<<endl;
}
void PushXPro(mypNode p)
{
	mypNode pTemp=p;
	pTemp=pTemp->next;

	while(pTemp)
	{
		Push(pTemp->str);
		pTemp=pTemp->next;
	}
}
mypNode ChkMAa(char* X,char* a)
{
	int i=InterpreterVn(X);
	int j=InterpreterVt(a);

	if(strcmp(MAa[i][j]->str,"ERR\0")!=0)
	{
		return MAa[i][j];
	}
	else
		return NULL;
}
int InterpreterVt(char* s)
{
	if(strcmp(s,_IF_)==0)
		return 0;
	else if(strcmp(s,_THEN_)==0)
		return 1;
	else if(strcmp(s,_ELSE_)==0)
		return 2;
	else if(strcmp(s,_LESS_)==0)
		return 3;
	else if(strcmp(s,_EQUAL_)==0)
		return 4;
	else if(strcmp(s,_V_)==0)
		return 5;
	else if(strcmp(s,_SHARP_)==0)
		return 6;
	else 
		return -1;
}
int InterpreterVn(char* s)
{
	if(strcmp(s,_S_)==0)
		return 0;
	else if(strcmp(s,_A_)==0)
		return 1;
	else if(strcmp(s,_B_)==0)
		return 2;
	else 
		return -1;
}
int IsVt(char* s)
{
	if(strcmp(s,_IF_)==0)
		return 1;
	else if(strcmp(s,_THEN_)==0)
		return 1;
	else if(strcmp(s,_ELSE_)==0)
		return 1;
	else if(strcmp(s,_LESS_)==0)
		return 1;
	else if(strcmp(s,_EQUAL_)==0)
		return 1;
	else if(strcmp(s,_V_)==0)
		return 1;
	else 
		return 0;
}
void Fetchnext(myWord* WordList,char* a,int& nIndex)
{
	strcpy(a,WordList[nIndex].value);

	if(WordList[nIndex].nno=='v')
	{
		strcpy(a,_V_);
	}

	nIndex++;	
	CreateSenList(a);
}
void CreateSenList(char* s)
{
	int vtType=InterpreterVt(s);

	switch(vtType)
	{
		case 0:
			if(nAddress==98)
			{
				nAddress=nAddress+2;
				senList[nSenListLen].itself=nAddress;				
			}
			else
			{
				senList[nSenListLen].itself=nAddress;				
			}

			if(senList[nSenListLen].itself!=100)
			{
				parentStack[nParentStackTop++]=senList[nSenListLen-1].itself;
			}
			
			senList[nSenListLen].parents=parentStack[nParentStackTop-1];

			strcpy(senList[nSenListLen].str,_IF_);					

			senList[nSenListLen].adTrue=senList[nSenListLen].itself+2;

			nSenListLen++;		

			break;
		
		case 1:
			nAddress=nAddress+2;
			senList[nSenListLen].itself=nAddress;			

			senList[nSenListLen].parents=parentStack[nParentStackTop-1];

			strcpy(senList[nSenListLen].str,_THEN_);			

			nSenListLen++;

			break;
		
		case 2:
			nAddress=nAddress+2;
			senList[nSenListLen].itself=nAddress;			

			senList[nSenListLen].parents=parentStack[nParentStackTop-1];

			nParentStackTop--;

			strcpy(senList[nSenListLen].str,_ELSE_);		

			nSenListLen++;

			break;
	}	
}
void Push(char* s)
{
	strcpy(stack[nStackTop++],s);
}
void Pop(char* s)
{
	nStackTop--;

	strcpy(s,stack[nStackTop]);
}
void InitLL1()
{
	mypNode pTemp;
	proPtrs[0]=new node;
	strcpy(proPtrs[0]->str,_S_);
	proPtrs[0]->next=new node;
	pTemp=proPtrs[0]->next;	
	strcpy(pTemp->str,_B_);
	pTemp->next=new node;
	pTemp=pTemp->next;
	strcpy(pTemp->str,_ELSE_);
	pTemp->next=new node;
	pTemp=pTemp->next;
	strcpy(pTemp->str,_B_);
	pTemp->next=new node;
	pTemp=pTemp->next;
	strcpy(pTemp->str,_THEN_);
	pTemp->next=new node;
	pTemp=pTemp->next;
	strcpy(pTemp->str,_A_);
	pTemp->next=new node;
	pTemp=pTemp->next;	
	strcpy(pTemp->str,_IF_);
	pTemp->next=NULL;
	proPtrs[1]=new node;
	strcpy(proPtrs[1]->str,_A_);
	proPtrs[1]->next=new node;
	pTemp=proPtrs[1]->next;	
	strcpy(pTemp->str,_V_);
	pTemp->next=new node;
	pTemp=pTemp->next;
	strcpy(pTemp->str,_LESS_);
	pTemp->next=new node;
	pTemp=pTemp->next;
	strcpy(pTemp->str,_V_);
	pTemp->next=NULL;
	proPtrs[2]=new node;
	strcpy(proPtrs[2]->str,_B_);
	proPtrs[2]->next=new node;
	pTemp=proPtrs[2]->next;	
	strcpy(pTemp->str,_S_);
	pTemp->next=NULL;
	proPtrs[3]=new node;
	strcpy(proPtrs[3]->str,_B_);
	proPtrs[3]->next=new node;
	pTemp=proPtrs[3]->next;	
	strcpy(pTemp->str,_V_);
	pTemp->next=new node;
	pTemp=pTemp->next;
	strcpy(pTemp->str,_EQUAL_);
	pTemp->next=new node;
	pTemp=pTemp->next;	
	strcpy(pTemp->str,_V_);
	pTemp->next=NULL;
	mypNode pError=new node;
	strcpy(pError->str,"ERR\0");
	pError->next=NULL;
	mypNode pNULL=new node;
	strcpy(pNULL->str,"NULL\0");
	pNULL->next=NULL;
	MAa[0][0]=proPtrs[0];
	MAa[0][1]=pError;
	MAa[0][2]=pNULL;
	MAa[0][3]=pError;
	MAa[0][4]=pError;
	MAa[0][5]=pError;
	MAa[0][6]=pNULL;	
	MAa[1][0]=pError;
	MAa[1][1]=pNULL;
	MAa[1][2]=pError;
	MAa[1][3]=pError;
	MAa[1][4]=pError;
	MAa[1][5]=proPtrs[1];
	MAa[1][6]=pError;	
	MAa[2][0]=proPtrs[2];
	MAa[2][1]=pError;
	MAa[2][2]=pNULL;
	MAa[2][3]=pError;
	MAa[2][4]=pError;
	MAa[2][5]=proPtrs[3];
	MAa[2][6]=pNULL;
	parentStack[nParentStackTop++]=0;
}
void Analyzing(myWord*,int&);
void FetchSource();
char GetCh();
int GetBC(char&);
void Concat(char*,char,int&);
int IsLetter(char);
int IsDigit(char);
int Reserve(char*,int);
void Retract(char&);
void ListInsert(int,char*,int);
myWord WordList[Wno];
int nWordListIndex=0;
char strBuffer[Wno];
int nBufferIndex=0;
void Analyzing(myWord* wordList,int& nLength)
{
	char ch;
	char strToken[Tlength];
	int nTokenIndex;	
	cout<<"请输入满足条件的一条语句，并以#结束 ："<<endl;
	FetchSource();
	cout<<endl;	
	while((ch=GetCh())!='\0')
	{
		if(!GetBC(ch))
			break;	
		nTokenIndex=0;
		strToken[nTokenIndex]='\0';
		if(IsLetter(ch))
		{
			while(IsLetter(ch) || IsDigit(ch))
			{
				Concat(strToken,ch,nTokenIndex);
				ch=GetCh();	
			}

			Retract(ch);

			int code;
			code=Reserve(strToken,nTokenIndex);			
			if(code==0)
			{			
				ListInsert('v',strToken,nTokenIndex);
			}
			else
			{
				int i;
				for(i=0;i<nTokenIndex;i++)
				{
					strToken[i]=tolower(strToken[i]);
				}
				
				ListInsert(code,strToken,nTokenIndex);
			}
		}
		else if(ch=='<')
		{
			ListInsert(4,_LESS_,2);
		}
		else if(ch=='=')
		{
			ListInsert(5,_EQUAL_,2);
		}
		else if(ch=='#')
		{
			ListInsert(6,_SHARP_,2);
		}
		else
		{		
            cout<<"词法分析出错！"<<endl;
			exit(0);
		}		
	}			
	int i;
	for(i=0;i<nWordListIndex;i++)
	{
		wordList[i]=WordList[i];
	}
	nLength=nWordListIndex;
	cout<<"词法分析成功！"<<endl<<endl;		
	cout<<"单词符号序列表为："<<endl;
	for(i=0;i<nWordListIndex;i++)
	{
		printf("<");

		if(WordList[i].nno=='v')
		{   
			printf("%c,",WordList[i].nno);
		}
		else
		{
			printf("%d,",WordList[i].nno);
		}

		printf("%s",WordList[i].value);
          
		printf(">\n");
		
	}  
}
void FetchSource()
{
	char chr;
	while((chr=getchar())!='#')
	{
		if(nBufferIndex==Wno-1)
			break;
		else
			strBuffer[nBufferIndex++]=chr;
	}
	strBuffer[nBufferIndex++]='#';
	strBuffer[nBufferIndex]='\0';
	nBufferIndex=0;
}
char GetCh()
{
	if(nBufferIndex>=Wno-1)
		return '\0';
	else
		return strBuffer[nBufferIndex++];	
}
int GetBC(char& ch)
{
	while(ch==32 || ch==10)
	{
		ch=GetCh();
	
		if(ch==0)
			return 0;
	}

	return 1; 
}
void Concat(char* strToken,char ch,int& nIndex)
{
	if(nIndex<Tlength-1)
	{
		strToken[nIndex]=ch;
		nIndex++;	
	}
}
int IsLetter(char ch)
{
	if(ch>='a' && ch<='z' || ch>='A' && ch<='Z')
		return 1;
	else
		return 0;
}
int IsDigit(char ch)
{
	if(ch>='0' && ch<='9')
		return 1;
	else
		return 0;
}
int Reserve(char* strToken,int nIndex)
{
	strToken[nIndex++]='\0';

	char strTem[Tlength];
	int i;
	for(i=0;i<nIndex;i++)
	{
		strTem[i]=tolower(strToken[i]);
	}

	if(strcmp(strTem,_IF_)==0)	
		return 1;
	else if(strcmp(strTem,_THEN_)==0)
		return 2;
	else if(strcmp(strTem,_ELSE_)==0)
		return 3;
	else 
		return 0;	
}
void Retract(char& ch)
{
	nBufferIndex--;

	ch='\0';
}
void ListInsert(int nno,char* str,int nLen)
{
	WordList[nWordListIndex].nno=nno;
	
	int i;
	for(i=0;i<nLen;i++)
	{
		WordList[nWordListIndex].value[i]=str[i];
	}

	nWordListIndex++;
}
void TitlePrint()
{	
	cout<<"********************************************************************"<<endl;
	cout<<" ◎◎◎◎◎◎◎◎◎    指导老师：李玉强    ◎◎◎◎◎◎◎◎◎◎◎"<<endl;
	cout<<"姓名：夏厚林          班级：计算机0306班         学号：0120310340618"<<endl;
	cout<<"                     编译原理课程设计"<<endl;	
	cout<<"                     ---条件语句的翻译分析程序（LL(1)法、输出四元式）"<<endl;		
    cout<<"********************************************************************"<<endl;	
	cout<<"满足条件的文法描述如下："<<endl;	
	cout<<"S->if A then B else B"<<endl;	
    cout<<"A->v < v"<<endl;	
    cout<<"B->v = v"<<endl;	
	cout<<endl;
}
int main()
{
	myWord WordList[Wno];
	int nWordListIndex;
	TitlePrint();	
	Analyzing(WordList,nWordListIndex);	
	LL_1method(WordList);
	cout<<endl;
	return 0;
}