#include "stdafx.h"
#include "LR.h"
#include "MLR1.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//----調(diào)試部分使用的代碼
CString MLR1::GetFirst(int i){
	CString rc,f;
	if(i<0||i>=GetIdentNum())return "";
	rc=FirstSet5(m_first[i].Fi,m_first[i].flag&2);
	f.Format("First(%s) = %s",list_Ident.GetAt(i),rc);
	return f;
}
CString MLR1::GetFollow(int i){
	CString rc,f;
	if(i<0||i>=GetIdentNum())return "";
	rc=FollowSet1(m_first[i].Fo,m_first[i].flag&0x08);
	f.Format("Follow(%s) = %s",list_Ident.GetAt(i),rc);
	return f;
}
//----構(gòu)造部分
MLR1::MLR1(){
	list_Index0=0;
}
MLR1::~MLR1(){
	if(list_Index0)delete[]list_Index0;
}
void MLR1::ReSet(FILE* pf){
//使用文件指針pf來(lái)重新驅(qū)動(dòng)程序
	int i;
	p_file=pf;
	list_Express.RemoveAll();
	list_Ident.RemoveAll();
	list_Seed0.RemoveAll();
	list_Clouser0.RemoveAll();
	if(list_Index0)delete[]list_Index0;
	list_Index0=0;
	for(i=0;i<MAP_SIZE;i++)
		bit_map[i]=0;
	for(char* p=(char*)m_first+sizeof(s_first)*MAX_IDENT-1;
		p>=(char*)m_first;p--)
		*p=0;

	Lex3();
	FirstSet1();
	FirstSet6();
	FollowSet3();
}
//----輸入分析部分
bool MLR1::Lex1(){
//截取一個(gè)分號(hào)段到tocken中
//功能字符取其負(fù)數(shù)
	char ch=0;
	bool end=false;
	token_len=0;
	if(feof(p_file))return false;
	while(!end&&!feof(p_file)){
		if(token_len>=LINE_LENGTH)break;		
		if(fread(&ch,1,1,p_file)<=0)break;
		if(ch<=0)goto error;
		switch(ch){
		case ';':
			end=true;
		case '<':
		case '>':
		case '=':
		case '|':
			ch=-ch;
			break;
		case '\\':
			fread(&ch,1,1,p_file);
			if(ch<=0)goto error;
			break;
		}
		token[token_len++]=ch;
	}
	token[token_len]=0;
	return true;
error:
	fprintf(stderr,"must be 1--127");
	return false;
}
int MLR1::Lex2_1(char*&s,bool isUse){
//該程序?yàn)長(zhǎng)ex2獨(dú)有的子程序
//識(shí)別非終結(jié)符并加入list_Ident
	char ident[ID_LENGTH+1];
	int  t=0;
	if((int)*s++!=-'<')return 0;
	if(isalpha(*s))ident[t++]=*s++;
	else return 0;
	while(isalpha(*s)||isdigit(*s))ident[t++]=*s++;
	while(*s=='\'')ident[t++]=*s++;
	if((int)*s++!=-'>')return 0;
	if(t==0)return 0;
	ident[t]=0;
	for(t=list_Ident.GetSize()-1;t>=0;t--)
		if(list_Ident[t]==(CString)ident)break;
	if(t<0){
		if(list_Ident.GetSize()>=MAX_IDENT)return false;
		list_Ident.Add((CString)ident);
		t=list_Ident.GetSize()-1;
		if(isUse)bit_map[t/8]|=1<<(t%8);
	}
	if(!isUse)bit_map[t/8]&=~(1<<(t%8));
	return t+1;
}
int MLR1::Lex2(){
//將token中的非終結(jié)符用(-1) -- (-127)表示
//進(jìn)行語(yǔ)法判斷<終結(jié)符>=符號(hào)表;
//-1表示出錯(cuò),0表示結(jié)束,1表示還有或分支保存在token中指針s所指處
	char *d;
	char * end;
	int i;
	static char* s=0;
	if(s==0){
		s=d=token;		
		if(i=Lex2_1(s))*d++=-i;
		else return false;
		if(*s++!=-'=')return false;
	}else{
		d=token+1;
	}
	end=&token[token_len];
	while(s<=end){
		if(*s==-';'){
			s=0;
			*d=0;
			return 0;
		}else if((int)*s==-'<'){
			if(i=Lex2_1(s,true))*d++=-i;
			else
				return -1;
		}else if((int)*s==-'|'){
			s++;
			*d=0;
			return 1;
		}else
			*d++=*s++;
	}
	return -1;
}
bool MLR1::Lex3(){
//循環(huán)調(diào)用Lex1讀入一句，調(diào)用Lex2進(jìn)行語(yǔ)法分析
//判斷bit_map是否為全零，如果不是則表示有未定義的非終結(jié)符
	int rc;
	while(Lex1()){
		if(token_len==0)continue;
		do{
			rc=Lex2();
			if(rc==-1)return false;
			list_Express.Add(new pchar(strlen(token)+ADJUST,token));
			//list_Express.Add((CString)token);
		}while(rc!=0);
	}
	for(int i=0;i<MAP_SIZE;i++)
		if(bit_map[i]!=0)return false;
	return true;
}
//----First集
void MLR1::FirstSet1(){
//用增量法判斷所有非終結(jié)符能否推出LR_NULL
//時(shí)間復(fù)雜度為m*n
	bool chg;
	int  n,m,i,j;
	char temp[LINE_LENGTH];
	char *p;
	n=list_Ident.GetSize();
	m=list_Express.GetSize();
	do{
		chg=false;
		for(j=0;j<m;j++){
			strcpy(temp,((pchar*)list_Express.GetAt(j))->getData());
			//sprintf(temp,list_Express.GetAt(j));
			p=temp+1;
			while(*p!=0){
				if(*p>=1)break;
				if((m_first[-*p-1].flag&0x03)!=3)break;
				p++;
			}
			if(*p==0){
				m_first[-temp[0]-1].flag|=0x03;
				n--;
				chg=true;
			}
		}
	}while(chg&&(n>0));
	for(i=0;i<n;i++)
		m_first[i].flag|=0x01;
}
void MLR1::FirstSet2(int i,int j,int k){
//已經(jīng)知道符號(hào)i依賴(lài)于符號(hào)（j*8+k）
//如果符號(hào)（j*8+k）依賴(lài)于其它符號(hào)則先做
//接下來(lái)把符號(hào)（j*8+k）的First加到符號(hào)i上
/*	有一個(gè)假設(shè)：圖中沒(méi)有環(huán)路存在
	程序中按非終結(jié)符的編號(hào)從大到小求其First集
	有循環(huán)時(shí)總是大的先調(diào)用小的，再有小的調(diào)用大的(被拒絕)
	因此依賴(lài)關(guān)系中沒(méi)有大的依賴(lài)小的的情況，即無(wú)環(huán)路*/
	int ii,jj,kk;
	ii=j*8+k;
	for(jj=0;jj<16;jj++){
		for(kk=0;kk<8;kk++){
			if(token[ii*16+jj]&(1<<kk))
				FirstSet2(ii,jj,kk);}
	}
	for(ii=0;ii<MAP_SIZE;ii++)
		m_first[i-1].Fi[ii]|=m_first[j*8+k-1].Fi[ii];
	if(m_first[j*8+k-1].flag&0x02)
		m_first[i-1].flag|=0x02;
	token[i*16+j]^=1<<k;
}
bool MLR1::FirstSet3(const char *X,char*Fi){
//返回true表示計(jì)算完全
//求產(chǎn)生式X的First集放在Fi中
//如果要求符號(hào)串的First集,就將X[0]設(shè)為0
//假設(shè)X中不出現(xiàn)LR_NULL,LR_EOF和LR_EOS
//假設(shè)F的長(zhǎng)度為MAP_SIZE,有128b
	const char *p=X+1;
	bool rc=true;
	while(*p!=0){
		if(*p>=1){
			Fi[(*p)/8]|=1<<(*p)%8;
			return rc;
		}else{
			if(*p!=*X){
				if(!FirstSet4(*p,Fi)){
					//token[*X,*p]=1,*X需要*p
					token[(-*X)*16+(-*p)/8]|=1<<(-*p)%8;
					rc=false;
				}
			}
			if((m_first[-*p-1].flag&0x02)==0)
				return rc;
		}
		p++;
	}
	return rc;
}
bool MLR1::FirstSet4(char const X,char*Fi){
//返回false表示沒(méi)有進(jìn)行計(jì)算
//求非終結(jié)符X的First集放在F中
//如果LR_NULL在其中則返回true
	char* temp;
	//CString temp;
	if(m_first[-X-1].flag&0x40)return false;
	if((m_first[-X-1].flag&4)==0){
		m_first[-X-1].flag|=0x40;
		for(int i=list_Express.GetSize();i>0;i--){
			temp=((pchar*)list_Express.GetAt(i-1))->getData();
			//temp=list_Express.GetAt(i-1);
			if(temp[0]==X)
				FirstSet3(temp,m_first[-X-1].Fi);
				//FirstSet3((LPCSTR)temp,m_first[-X-1].Fi);
		}
		m_first[-X-1].flag|=4;
		m_first[-X-1].flag^=0x40;
	}
	if(Fi!=m_first[-X-1].Fi){
		for(int i=0;i<MAP_SIZE;i++)
			Fi[i]|=m_first[-X-1].Fi[i];
	}
	return true;
}
CString MLR1::FirstSet5(const char*Fi,bool has_null){
//將集合表示的First變?yōu)樽址?//LR_NULL也用特殊符號(hào)表示了
	char t[128];
	char *p=t;
	int  i,j;
	for(i=0;i<MAP_SIZE;i++){
		if(Fi[i])for(j=0;j<8;j++)
			if(Fi[i]&(1<<j))
				*p++=i*8+j;
	}
	if(has_null)*p++=LR_NULL;
	*p=0;
	return (CString)t;
}
void MLR1::FirstSet6(){
//為每個(gè)非終結(jié)符求First集
//在token中保存各非終結(jié)符之間的依賴(lài)關(guān)系
//最后根據(jù)依賴(lài)關(guān)系完成First集
/*  如遇到A=B;B=A;A=b;時(shí)
	計(jì)算First(B)時(shí)用到First(A)，可以保證First(B)包含F(xiàn)irst(A)
	計(jì)算First(A)時(shí)又用到First(B)，不能再調(diào)用First(B)而造成死循環(huán)
	計(jì)算完之后First(B)又有了新符號(hào)，為把該新符號(hào)寫(xiě)入First(A)中
	構(gòu)造依賴(lài)表token表示A依賴(lài)于B
	如果B又依賴(lài)于C，則必須先求出完整的First(B)*/
	int i,j,k;
	for(i=0;i<2048;i++)
		token[i]=0;
	for(i=list_Ident.GetSize();i>0;i--){
		if((m_first[i-1].flag&4)==0)
			FirstSet4(-i,m_first[i-1].Fi);
	}
	for(i=0;i<128;i++){
		for(j=0;j<16;j++){
			if(token[i*16+j]){
				for(k=0;k<8;k++)
					if(token[i*16+j]&(1<<k))
						FirstSet2(i,j,k);
			}
		}
	}
}
CString MLR1::FollowSet1(const char*Fo,bool has_eof){
//將集合表示的Follow變?yōu)樽址?//LR_EOF也用特殊符號(hào)表示了
	char t[128];
	char *p=t;
	int  i,j;
	for(i=0;i<MAP_SIZE;i++){
		if(Fo[i])for(j=0;j<8;j++)
			if(Fo[i]&(1<<j))
				*p++=i*8+j;
	}
	if(has_eof)*p++=LR_NULL;
	*p=0;
	return (CString)t;
}
bool MLR1::FollowSet2(const char *X){
//如果X中某字符可以推出LR_NULL則稱(chēng)此字符“通”
//q到(p-1)之間的字符串是通的
//它們都應(yīng)該接受First(p)
//如果它們?cè)赬的最后面，則都要接受Follow(X[0])
//返回值保留
	const char *p,*q,*t;
	int  i;
	p=q=X+1;
	while(*p!=0){
		if(*p>0){
			for(t=q;t<p;t++)
				m_first[-*t-1].Fo[*p/8]|=1<<(*p%8);
			q=p+1;
		}else{
			for(t=q;t<p;t++)
				for(i=0;i<MAP_SIZE;i++)
					m_first[-*t-1].Fo[i]|=m_first[-*p-1].Fi[i];
			if((m_first[-*p-1].flag&0x02)==0)
				q=p;				
		}
		p++;
	}
	for(t=q;t<p;t++){
		//token[*t,*X]=1,*t需要*X
		token[(-*t)*16+(-*X)/8]|=1<<(-*X)%8;
	}
	return true;
}
void MLR1::FollowSet3(){
//此函數(shù)求各非終結(jié)符的Follow集
//先加入后續(xù)符號(hào)的First集
//再加入首符號(hào)的Follow集
//最后處理循環(huán)引用Follow集的情況
	int i,j,k;
	for(i=0;i<2048;i++)
		token[i]=0;
	m_first[0].flag|=0x08;
	for(i=list_Express.GetSize();i>0;i--)
		FollowSet2(((pchar*)list_Express.GetAt(i-1))->getData());
		//FollowSet2((LPCSTR)list_Express.GetAt(i-1));
	for(int c=0;c<2;c++){
	for(i=0;i<128;i++){
		for(j=0;j<16;j++){
			if(token[i*16+j]){
				for(k=0;k<8;k++)
					if(token[i*16+j]&(1<<k))
						FollowSet4(i,j,k);
			}
		}
	}}
}
bool MLR1::FollowSet4(int i,int j,int k){
//如果正在求X的Follow集則返回false
//如果沒(méi)有求解i,則先求解i
	int ii,jj,kk;
	if(m_first[i-1].flag&0x20)return false;
		m_first[i-1].flag|=0x20;
		ii=j*8+k;
		for(jj=0;jj<16;jj++){
			for(kk=0;kk<8;kk++){
				if(token[ii*16+jj]&(1<<kk))
					FollowSet4(ii,jj,kk);}
		}
		m_first[i-1].flag^=0x20;
	for(ii=0;ii<MAP_SIZE;ii++)
		m_first[i-1].Fo[ii]|=m_first[j*8+k-1].Fo[ii];
	if(m_first[j*8+k-1].flag&0x08)
		m_first[i-1].flag|=0x08;
	token[i*16+j]^=1<<k;
	return false;
}
void MLR1::LR0_table1(){
//構(gòu)造LR0分析表的主控函數(shù)
//s_size和c_size分別表示seed和clouser的索引表的大小
//st,和ct表示當(dāng)前使用索引表的下標(biāo)
//buf用于緩沖表達(dá)式和LR0項(xiàng)目
//index用于索引表，奇數(shù)為seed偶數(shù)為clouser
	char * buf=token;
	char * index=&token[LINE_LENGTH];
	int s_size,c_size;
	int	st,ct;
	s_size=c_size=0;
	st=ct=0;
	index[s_size++]=0;
	strcpy(buf,((pchar*)list_Express.GetAt(0))->getData());
	//sprintf(buf,"%s",list_Express.GetAt(0));
	LR0_table2(buf);
	list_Seed0.Add((CString)buf);
}
void MLR1::LR0_table2(char*s){
//將表達(dá)式s變?yōu)長(zhǎng)R0項(xiàng)目，s[1]=LR_DOT
	int i;
	for(i=strlen(s);--i>=1;)
		s[i+1]=s[i];
	s[1]=LR_DOT;
}