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

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//----調試部分使用的代碼
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;
}
//----構造部分
MLR1::MLR1(){
	list_Index0=0;
}
MLR1::~MLR1(){
	if(list_Index0)delete[]list_Index0;
}
void MLR1::ReSet(FILE* pf){
//使用文件指針pf來重新驅動程序
	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(){
//截取一個分號段到tocken中
//功能字符取其負數
	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 '=':
			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){
//該程序為Lex2獨有的子程序
//識別非終結符并加入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;
}
bool MLR1::Lex2(){
//將token中的非終結符用(-1) -- (-127)表示
//進行語法判斷<終結符>=符號表;
	register char *s,*d;
	char * end;
	int i;
	s=d=token;
	end=&token[token_len];
	if(i=Lex2_1(s))*d++=-i;
	else return false;
	if(*s++!=-'=')return false;
	while(s<end){
		if(*s==-';')break;
		else if((int)*s==-'<'){
			if(i=Lex2_1(s,true))*d++=-i;
			else return false;
		}else
			*d++=*s++;
	}
	*d=0;
	return s<end;
}
bool MLR1::Lex3(){
//循環調用Lex1讀入一句，調用Lex2進行語法分析
//判斷bit_map是否為全零，如果不是則表示有未定義的非終結符
	while(Lex1()){
		if(token_len==0)continue;
		if(Lex2())
			list_Express.Add((CString)token);
		else return false;
	}
	for(int i=0;i<MAP_SIZE;i++)
		if(bit_map[i]!=0)return false;
	return true;
}
//----First集
void MLR1::FirstSet1(){
//用增量法判斷所有非終結符能否推出LR_NULL
//時間復雜度為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++){
			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){
//已經知道符號i依賴于符號（j*8+k）
//如果符號（j*8+k）依賴于其它符號則先做
//接下來把符號（j*8+k）的First加到符號i上
/*	有一個假設：圖中沒有環路存在
	程序中按非終結符的編號從大到小求其First集
	有循環時總是大的先調用小的，再有小的調用大的(被拒絕)
	因此依賴關系中沒有大的依賴小的的情況，即無環路*/
	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表示計算完全
//求產生式X的First集放在Fi中
//如果要求符號串的First集,就將X[0]設為0
//假設X中不出現LR_NULL,LR_EOF和LR_EOS
//假設F的長度為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表示沒有進行計算
//求非終結符X的First集放在F中
//如果LR_NULL在其中則返回true
	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=list_Express.GetAt(i-1);
			if(temp[0]==X)
				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變為字符串式
//LR_NULL也用特殊符號表示了
	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(){
//為每個非終結符求First集
//在token中保存各非終結符之間的依賴關系
//最后根據依賴關系完成First集
/*  如遇到A=B;B=A;A=b;時
	計算First(B)時用到First(A)，可以保證First(B)包含First(A)
	計算First(A)時又用到First(B)，不能再調用First(B)而造成死循環
	計算完之后First(B)又有了新符號，為把該新符號寫入First(A)中
	構造依賴表token表示A依賴于B
	如果B又依賴于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變為字符串式
//LR_EOF也用特殊符號表示了
	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則稱此字符“通”
//q到(p-1)之間的字符串是通的
//它們都應該接受First(p)
//如果它們在X的最后面，則都要接受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(){
//此函數求各非終結符的Follow集
//先加入后續符號的First集
//再加入首符號的Follow集
//最后處理循環引用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((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
//如果沒有求解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(){
//構造LR0分析表的主控函數
//s_size和c_size分別表示seed和clouser的索引表的大小
//st,和ct表示當前使用索引表的下標
//buf用于緩沖表達式和LR0項目
//index用于索引表，奇數為seed偶數為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;
	sprintf(buf,"%s",list_Express.GetAt(0));
	LR0_table2(buf);
	list_Seed0.Add((CString)buf);
}
void MLR1::LR0_table2(char*s){
//將表達式s變為LR0項目，s[1]=LR_DOT
	int i;
	for(i=strlen(s);--i>=1;)
		s[i+1]=s[i];
	s[1]=LR_DOT;
}