ll1.cpp

实现编译原理中LL1文法分析功能 编译原理课程中

#include"stdio.h"
#include"iostream"
#include"string"
#include"fstream"
#include"ctype.h"
#define N 50

#include"word.h"
using namespace std;
#include"stack.h"

 
class Line{//存一行文法
public:
	char Vn;//非终结符
	string form[10];//产生式
	int f;//产生式个数
	Line()
	{f=0;}
};

class Gwf{//存一个文法的终结符和非终结符
	public:
	string Vn;//非终结符
	string Vt;//终结符
	int Nn;//非终结符
	int	Nt;//终结符个数
	Gwf(char *LLname){
		FILE *fp=fopen(LLname,"r");
		char ch=fgetc(fp);
		char buf[200];
		int i=1;
		while(ch!=EOF)
		{	buf[i++]=ch;
			ch=fgetc(fp);
		}
		buf[0]='\n';
		buf[i]='\0';
		fclose(fp);
		for(i=0;i<strlen(buf);i++){
			ch=buf[i];
			if(isspace(ch)){
				Vn.append(&buf[++i],1);				
			}
			else if(ch=='-'&&buf[i+1]=='>')
				i++;
			else if(isupper(ch)||ch=='|'||ch=='@')
				;//空操作
			else 
				Vt.append(&ch,1);
		}
		Vt.append("#");//结束符
		Nn=Vn.length();
		Nt=Vt.length();
	}
	int pos_n(char n){
		return Vn.find_first_of(n);
	}
	int pos_t(char t){
		return Vt.find_first_of(t);
	}
	bool isvt(char t){//t是终结符？
		if(Vt.find_first_of(t)==string::npos)
			return false;
		else return true;
	}
};

class FirstN{//用来存放一个非终结符的first集
public:
	int p;//第p个产生式
	char Vt;//终结符
	FirstN(){
		p=0;
		Vt='\0';
	}	
};

void readLL(char *LLname,Line *LL){//将文法存入Line LL[]中
	ifstream fin(LLname);
	string buf[N];
	int len=0;
	do{
		fin>>buf[len++];
	}while(!fin.eof());
	for(int i=0;i<len;i++){
		LL[i].Vn=buf[i].at(0);//读入非终结符
		buf[i].erase(0,3);//删除前三个，N->
		buf[i].append("|");
		while(!buf[i].empty()){
			int e=buf[i].find_first_of('|');
			LL[i].form[LL[i].f++].assign(buf[i],0,e);
			buf[i].erase(0,e+1);
		}//while
	}//for //dowhile
	fin.close();
}

///////////////以下求FIRST集///////////////////////

void copyfst(int n,int c,FirstN fst[N][N],int pt){//将fst的第c行复制到第n行后
	int n1=0;//n行的列标
	while(fst[n][n1].Vt!='\0')
		n1++;
	int c1=0;//n的列标
	while(fst[c][c1].Vt!='\0'){
		if(fst[c][c1].Vt=='@'){
			c1++;
			continue;
		}
		fst[n][n1].Vt=fst[c][c1++].Vt;
		fst[n][n1++].p=pt;
	}
}

void first(char n,Line *LL,Gwf GLL,FirstN fst[N][N],int *flag){//求n的FIRST
	int pn=0,pt=0;
	int i=0;
	pn=GLL.pos_n(n);//非终结符n在LL[]中的位置
	if(flag[pn]) return;//如果求过这个，则结束
	for(pt=0;pt<LL[pn].f;pt++){
		char ch;
		int pch;
		int k=0;
		int fg=0;
		do{//////
			ch=LL[pn].form[pt].at(k++);
			if(GLL.isvt(ch)||ch=='@'){//如果产生式的FIRST是@或者终结符，则存入
				fst[pn][i].p=pt;
				fst[pn][i].Vt=ch;
				i++;
			}//if
			else{ //如果是非终结符，则将非终结符的FIRST存入
				first(ch,LL,GLL,fst,flag);
				
				pch=GLL.pos_n(ch);//非终结符ch在LL[]中的位置
				copyfst(pn,pch,fst,pt);			
			}//else
			for(int pk=0;fst[pch][pk].Vt!='\0';pk++)
				if(fst[pch][pk].Vt=='@'){
					fg=1;break;
				}
		}//do
		while(fg);
	}//for
	flag[pn]=1;
}//first

void first_all(Line *LL,Gwf GLL,FirstN fst[N][N]){//求所有非终结符的FIRST集	
	int flag[N]={0};//标记第N个非终结符是否求过FIRST
	int i;
	char n;
	for(i=0;i<GLL.Nn;i++){
		n=GLL.Vn.at(i);
		first(n,LL,GLL,fst,flag);
	}//for
}

//////////////////以下求FOLLOW////////////////////////
int Flagchg;//用来标记FOLLOW是否改变

void uniqueflw(int pn,char flw[N][N]){//将flw[pn][]唯一化
	char ch[N]={'\0'};
	int i=0,j=0;
	while(flw[pn][i]!='\0'){
		char e=flw[pn][i];
		if(e!='@'&&strchr(ch,e)==NULL)
			ch[j++]=e;
		i++;
	}//while	
	strncpy(flw[pn],ch,N);	
}

void addfirst(char n,char b,Gwf GLL,FirstN fst[N][N],char flw[N][N]){//将FIRST(b)加入FOLLOW(n)
	int pn=GLL.pos_n(n);
	char buf[N];
	strcpy(buf,flw[pn]);//改变前的flw[pn]->buf
	int i=strlen(flw[pn]);//查找FOLLOW(N)的最后位置
	if(GLL.isvt(b))//如果b是终结符则直接加入FOLLOW(n)
		flw[pn][i]=b;
	else{//如果不是,将FIRST(b)加入FOLLOW(n)
		int j=0;
		int pb=GLL.pos_n(b);
		while(fst[pn][j].Vt!='\0')
			flw[pn][i++]=fst[pb][j++].Vt;
	}//else
	uniqueflw(pn,flw);
	if(strcmp(flw[pn],buf))
		Flagchg=1;
}


void addfirst_all(Line *LL,Gwf GLL,FirstN fst[N][N],char flw[N][N]){//判断所有A->anb,将FIRST(b)加入FOLLOW(n)
	int i,j,k;//循环变量
	for(i=0;i<GLL.Nn;i++)//fori
		for(j=0;j<LL[i].f;j++){//forj
			int l=LL[i].form[j].length();
			for(k=0;k<l-1;k++){//fork
				char n=LL[i].form[j].at(k);
				char b=LL[i].form[j].at(k+1);
				addfirst(n,b,GLL,fst,flw);
			}//endk
		}//endj//endi
}

bool addfollow(int i,char n,Gwf GLL,FirstN fst[N][N],char flw[N][N]){//flw[i][]加入FOLLOW(n)
	int pn=GLL.pos_n(n);
	if(pn==i)
		return false;
	char buf[N];
	strcpy(buf,flw[pn]);//改变前的flw[pn]->buf
	if(GLL.isvt(n))
		;
	else{		
		strcat(flw[pn],flw[i]);
		uniqueflw(pn,flw);
		if(strcmp(flw[pn],buf))
		Flagchg=1;
	}
	int k=0;
	while(fst[pn][k].Vt!='\0'){
		if(fst[pn][k].Vt=='@')
			return true;//如果@属于n的FIRST,返回真
		k++;
	}	
	return false;
}

void addfollow_all(Line *LL,Gwf GLL,FirstN fst[N][N],char flw[N][N]){//判断所有A->an,将FOLLOW(A)加入FOLLOW(n)
	int i,j;
	for(i=0;i<GLL.Nn;i++)//fori
		for(j=0;j<LL[i].f;j++){//forj
			int len=LL[i].form[j].length()-1;
			char n=LL[i].form[j].at(len);
			while(addfollow(i,n,GLL,fst,flw))//直到最后的不能为空
				n=LL[i].form[j].at(--len);
		}//endj//endi
}

void follow_all(Line *LL,Gwf GLL,FirstN fst[N][N],char flw[N][N]){//求所有非终结符的FOLLOW
	flw[0][0]='#';//将;(即#)置于开始符号的FOLLOW中
	addfirst_all(LL,GLL,fst,flw);//对于所有A->anb,将FIRST(b)加入FOLLOW(n)
	Flagchg=1;
	while(Flagchg){//如果follow有改变就一直执行
		Flagchg=0;
		addfollow_all(LL,GLL,fst,flw);
	}
}

///////////////以下求预测分析表/////////////////////

void forecast(FirstN fst[N][N],char flw[N][N],Line *LL,Gwf GLL,string Mtb[N][N]){//将预测分析表存入Mtb中
	int i,j,c;
	for(i=0;i<GLL.Nn;i++){
		j=0;
		char t=fst[i][j].Vt;
		int pt;
		while(t!='\0'){			
			pt=fst[i][j].p;
			if(t!='@'){
				c=GLL.pos_t(t);//i行c列
				Mtb[i][c]=LL[i].form[pt];
			}else{
				int pf=0;
				while(flw[i][pf]!='\0'){
					char ft=flw[i][pf];
					c=GLL.pos_t(ft);
					Mtb[i][c]=LL[i].form[pt];
					pf++;
				}//while
			}//if else
			j++;
			t=fst[i][j].Vt;
		}//while
	}//for		
}

////////////以下进行词法分析///////////////////////

void error(Stack S,char *expi,int j){//出错分析
	cout<<"错误"<<flush;
	char s=S.get(S.top); 	
	char e=expi[j];
	if(s==')')///栈顶为'('
		switch (e){
			case '#':cout<<"。语法错误:';'前缺少'"<<s<<"'"<<flush;  break;
		}
	if(s=='E')
		switch(e){
			case '+':
			case '*': cout<<"。非法使用符号:"<<e<<flush; break;
		}
	if(s=='F')
		switch(e){
			case '+':
			case '*':
			case ')': cout<<"。非法使用符号:"<<e<<flush; break;
		}
	cout<<endl;	
}

void analyse(char exp[N][N],string Mtb[N][N],Gwf GLL,char *expname){//进行预测分析
	ifstream fin(expname);
	Stack S;
	char start=GLL.Vn.at(0);
	char x;//用于比较
	for(int i=0;strlen(exp[i]);i++){//对exp的每一行
		S.push('#');
		S.push(start);
		string buf;//用来缓存一行代码
		int fa=1;
		int j=0;//exp[i][j]
		while(fa){
			S.pop(x);
			if(x=='@') 
				continue;
			if(GLL.isvt(x)&&x!='#'){//如果是终结符//if1
				if(x==exp[i][j])//if3
					j++;
				else {
					fin>>buf;
					cout<<buf<<endl;
					error(S,exp[i],j);
					fa=0;
				}//end if3
			}//end if1
			else if(x=='#'){//如果是#//if3
				if(x==exp[i][j]){//if2					
					fin>>buf;
					cout<<buf<<endl;
					cout<<"正确"<<endl;
					fa=0;//分析结束
				}else{
					fin>>buf;
					cout<<buf<<endl;
					error(S,exp[i],j);
					fa=0;
				}//else if//end if2
			}//end if3
			else{//如果是非终结符
				int pn=GLL.pos_n(x);//在Mtb中的行号
				int pt=GLL.pos_t(exp[i][j]);//在Mtb中的列号
				if(!Mtb[pn][pt].empty())//如果分析表Mtb中相应的位置不为空
					S.pushstr(Mtb[pn][pt]);//则入栈
				else{//否则,报错
					fin>>buf;
					cout<<buf<<endl;
					error(S,exp[i],j);
					fa=0;
				}
			}
			
		}//while
	}//for i
	fin.close();		
}


/////////////以下为主函数////////////////////////
void main(){
	char *LLname="LL.txt";//文法文件名
	char *expname="expression.txt";//代码文件名
	Gwf GLL(LLname);//将文法的Vn,Vt及个数存入GLL
	Line LL[N];//存文法
	readLL(LLname,LL);//将文法结构读入LL
	FirstN fst[N][N];//存FIRST集
	first_all(LL,GLL,fst);//求FIRST
	char flw[N][N]={'\0'};//存FOLLWS集
	follow_all(LL,GLL,fst,flw);//求FOLLOW
	string Mtb[N][N];//存预测分析表
	forecast(fst,flw,LL,GLL,Mtb);//求预测分析表
	char exp[N][N]={'\0'};//存经词法翻译过的代码
	word(expname,exp);//求翻译后的代码
	analyse(exp,Mtb,GLL,expname);	
}