ll1_judge.cpp

vc++实现编译原理中的LL(1)文法的编译过程,非常好用.

#include ".\ll1_judge.h"

LL1_judge::LL1_judge(void)
{
	for(int i=0;i<26;i++)
	{
		m_temp_nt.push_back(char(65+i));
	}
	m_temp_nt_pointer=0;
	m_str_compare="A->a|@";
	for(int j=0;j<(int)m_str_compare.size();j++)
	{
		m_compare.push_back(m_str_compare[j]);
	}
	m_terminal.push_back(m_str_compare[5]);

}

LL1_judge::~LL1_judge(void)
{
}

bool LL1_judge::in_type(string str)
{
	if(str.find("->"))
	{
		vector<char> type;
		for(int i=0;i<(int)str.size();i++)
		{
			type.push_back(str.at(i));
		}
		m_creation.push_back(type);
		cout<<"产生式现有个数"<<(int)m_creation.size()<<endl;
	     return true;
	}
	else
		return false;

}

void LL1_judge::cancel_directly(void)             ///************************8没有分解
{
	for(int i=0;i<(int)m_creation.size();i++)
	{
		if(judge_directly(m_creation[i]))//如果有直接左递归，就消除
		{
			cout<<"第"<<i<<"个产生式有直接左递归，现在消除"<<endl;
			string t_a,t_b;
			bool is_nt;//1为是终结符
			is_nt=false;
			bool is_next;
			is_next=false;
			for(int j=3;j<(int)m_creation[i].size();j++)
			{
				
				if(m_creation[i][j]==m_compare[4])//问题:      不识别|；
				{
					
					is_next=true;
					is_nt=false;
				}
				else if(m_creation[i][j]==m_creation[i][0])
					is_nt=true;
				else if(is_nt==true)
				{
					if(is_next==true&&t_a.size()>0) t_a+=m_str_compare[4];
					t_a+=m_creation[i][j];
					is_next=false;
				}
				else
				{
					if(is_next==true&&t_b.size()>0) t_b+=m_str_compare[4];
					t_b+=m_creation[i][j];
					is_next=false;
				}
			}


			for(int w1=0;w1<(int)t_b.size();w1++)
			{
				if(t_b[w1]==m_str_compare[4])
				{
					t_b.insert(w1,1,m_temp_nt[m_temp_nt_pointer]);//####################
					w1+=1;
				}
			}
			t_b+=m_temp_nt[m_temp_nt_pointer];//bp'  完成了产生式的右部
			m_creation[i].erase(m_creation[i].begin()+3,m_creation[i].end());
			for(int t=0;t<(int)t_b.size();t++)
			{
				m_creation[i].push_back(t_b[t]);
			}//产生式P->BP'完成
			//此步成功完成，
			for(int yy=0;yy<(int)m_creation[i].size();yy++)
			{
				cout<<"#######"<<m_creation[i][yy];
			}
              

			for(int w2=0;w2<(int)t_a.size();w2++)
			{
				if(t_a[w2]==m_str_compare[4])
				{
					t_a.insert(w2,1,m_temp_nt[m_temp_nt_pointer]);
					w2+=1;
				}
			}
            t_a+=m_temp_nt[m_temp_nt_pointer];
			t_a+=m_str_compare[4];
			t_a+=m_str_compare[5];//完成产生式的右部P'->aP'|@
			vector<char> t_vec;
			t_vec.push_back(m_temp_nt[m_temp_nt_pointer]);
			t_vec.push_back(m_str_compare[1]);
			t_vec.push_back(m_str_compare[2]);

			m_non_terminal.push_back(m_temp_nt[m_temp_nt_pointer]);
			m_temp_nt_pointer++;
			for(int r=0;r<(int)t_a.size();r++)
			{
				t_vec.push_back(t_a[r]);
			}
			m_creation.insert(m_creation.begin()+i+1,1,t_vec);
			i++;
			
		}
		
	}
}


int LL1_judge::in_terminal_sign(string str)
{
	for(int i=0;i<(int)str.size();i++)
	{
		m_terminal.push_back(str.at(i));
	}

    return 0;
}
void LL1_judge::in_non_terminal_sign(string str)//非终结符的输入
{
	for(int i=0;i<(int)str.size();i++)
	{
		m_non_terminal.push_back(str.at(i));
		for(int j=0;j<(int)m_temp_nt.size();j++)
		{
			if(m_temp_nt[j]==str.at(i))
			{
				m_temp_nt.erase(m_temp_nt.begin()+j);
			}
		}
	}
	cout<<"非终结符:";
	for(int t=0;t<(int)m_non_terminal.size();t++)
	{
		cout<<m_non_terminal[t];
	}
}

bool LL1_judge::judge_directly(vector<char> vec)
{
	cout<<"到了判断直接左递归了 "<<endl;
	int is_true=0;
	if(vec[0]==vec[3]) is_true=1;
	for(int i=4;i<(int)vec.size();i++)
	{
		if(vec[i]==char("|"))
		{
			if(vec[i+1]==vec[0]){is_true=1;break;}
		}
	}
	if(is_true==1)
	{
		cout<<"发现直接左递归：";
		for(int p=0;p<(int)vec.size();p++)
		{
			cout<<vec[p];
		}
		return true;
	}
	else
	   return false;
}

bool LL1_judge::judge_indirectly()
{
	vector<judge_nt> vec;
	bool is_end=false;
	for(int i=0;i<(int)m_creation.size();i++)
	{
		if(is_end==false)//  --->>>>>
		{
		    vec.clear();
		    for(int r1=0;r1<(int)m_non_terminal.size();r1++)//第一个产生式
		   {
			    if(m_creation[i][3]==m_non_terminal[r1])
				    help_j_ind(vec,m_creation[i][0],m_creation[i][3],is_end);
		    }
		    if(is_end==false)// 尽量减少递归的次数
		    {
	            for(int r2=0;r2<(int)m_creation[i].size();r2++)//以后的产生式
		        {
			        if(m_creation[i][r2]==char("|"))
			        {
				         for(int r3=0;r3<(int)m_non_terminal.size();r3++)
				         {
					        if(m_creation[i][r2+1]==m_non_terminal[r3])
								help_j_ind(vec,m_creation[i][0],m_creation[i][r2+1 ],is_end);
				         }
			         }
		        }
		    }
	     }//if(is_end)
    }
	return is_end;
}

void LL1_judge::help_j_ind(vector<judge_nt> &vec, char zuo,char you,bool &is_end)
                                                                      //函数是一第一个生成式的，第一个产生式开始的，                                                                     //需在调用函数里 根据产生式个数调用此函数
{
	  judge_nt temp;
	  temp.zuo=zuo;
	  temp.you=you;
	  vec.push_back(temp);
	  int find_pointer;
	  for(int t=0;t<(int)m_creation.size();t++)
	  {
		     if(m_creation[t][0]==you)find_pointer=t;
	   }
	    for(int t4=0;t4<(int)vec.size();t4++)//判断第一个产生式是不是是间接左递归成立
	   {
		    if(m_creation[find_pointer][3]==vec[t4].zuo)
		    {
			        is_end=true;
			        break;
		     }
	   }
	   if(is_end==false)//第一次判断结果
	   {

	       for(int t1=0;t1<(int)m_non_terminal.size();t1++)//第一个产生式的递归
	      {
		      if(m_creation[find_pointer][3]==m_non_terminal[t1])
		      {
			       help_j_ind(vec,you,m_creation[find_pointer][3],is_end);
		      }
	      }

	     for(int t2=3;t2<(int)m_creation[find_pointer].size();t2++)//‘|’以后的产生式的递归
	    {
			if(is_end==false)
			{//////////////////////////
			
		          if(m_creation[find_pointer][t2]==m_compare[4])
		          {
			          for(int t5=0;t5<(int)vec.size();t5++)
			         {
				           if(m_creation[find_pointer][t2+1]==vec[t5].zuo)
				           {
					               is_end=true;
					              break;
				             }
			          }//判断这个产生式是不是使间接作递归成立

                       //如果不成立，第一个符号是不是非终结符，是则进入下一次左递归
                       if(is_end==false)
		              {
			                 for(int t3=0;t3<(int)m_non_terminal.size();t3++)
			                 {
				                 if(m_creation[find_pointer][t2+1]==m_non_terminal[t3])
				                 {
					                   help_j_ind(vec,you,m_creation[find_pointer][t2+1],is_end);//&&&&&&&&&&&&&&&&&&&&7
				                  }
			                   }
		                }
				  }
	          }//////////////////////////////////////////////////////////////////////////////////////////////////////////
	       }
	   }
	//好像是每次都要删除了
	vec.erase(vec.end()-1);
}
void LL1_judge::cancel_indirectly(void)
{
	if(judge_indirectly())
	{
	  for(int i=0;i<(int)m_creation.size();i++)
	   {
		bool is_first=true;
		for(int t=3;t<(int)m_creation[i].size();t++)
		{
			
			if(is_first==true)//如果是表达式的第一个符号
			{
				is_first=false;
					for(int t2=0;t2<i;t2++)
					{
						if(m_creation[i][t]==m_creation[t2][0])//到达了替换的条件
						{
							//所有操作在这个条件以内
							string str1,str2;
							for(int t3=3;t3<(int)m_creation[t2].size();t3++)
							{
								str1+=m_creation[t2][t3];
							}
							for(int t4=t+1;t4<(int)m_creation[i].size();t4++)
							{
								if(m_creation[i][t4]==m_compare[4])break;
								else
								{
									str2+=m_creation[i][t4];
								}
							}
							for(int t5=0;t5<(int)str1.size();t5++)
							{
								if(str1[t5]==m_str_compare[4])
								{
									cout<<"到达了串的插入了"<<endl;
									str1.insert(str1.begin()+t5,str2.begin(),str2.end());//问题：关于插入，不成功了
									t5+=(int)str2.length();
								}
							}
							m_creation[i].erase(m_creation[i].begin()+t);
							m_creation[i].insert(m_creation[i].begin()+t,str1.begin(),str1.end());
							//这里先将所有的间接递归替换完后，
							//才判断这句有没有直接递归，不知道有没有射门么问题
							i--;//在每替换一个非终结符的时候，回退一位，看有没有替换完全
							is_first=true;
						}
					}
				}
			   else if(m_creation[i][t]==m_compare[4]) is_first=true;
			   else 
				   is_first=false;
		}
		if(judge_directly(m_creation[i]))
		{
			cancel_directly();
		}
	  }
	}
}
void LL1_judge::display_all(void)
{
	cout<<"产生式显示:"<<endl;
	for(int i=0;i<(int)m_creation.size();i++)
	{
		cout<<"              ";
		for(int j=0;j<(int)m_creation[i].size();j++)
		{
			cout<<m_creation[i][j];
		}
		cout<<endl;
	}
	cout<<"首符集显示："<<endl;
	for(int a1=0;a1<(int)m_first.size();a1++)
	{
		cout<<"               ";
		for(int a2=0;a2<(int)m_first[a1].size();a2++)
		{
			cout<<m_first[a1][a2];
		}
		cout<<endl;
	}
}




void LL1_judge::find_first()
{
	
	for(int i=0;i<(int)m_creation.size();i++)
	{
		bool is_first=true;
		vector<char> temp;
		temp.push_back(m_creation[i][0]);
		for(int j=3;j<(int)m_creation[i].size();j++)
		{
			if(is_first==true)
			{
				is_first=false;
				for(int t1=0;t1<(int)m_terminal.size();t1++)
				{
					if(m_creation[i][j]==m_terminal[t1])
					{
						push_back(temp,m_creation[i][j]);
					}
				}
			}
			else if(m_creation[i][j]==m_compare[4])
			{
				is_first=true;
			}
			else
			{
				is_first=false;
			}
		}
		m_first.push_back(temp);
	}//到这里完成第一遍的终结符扫描 

	for(int a1=0;a1<(int)m_creation.size();a1++)
	{
        bool first=true;
	    bool is_continue;
	    is_continue=false;
	    bool nt_t=true;//1-nt,a-t
		for(int a2=3;a2<(int)m_creation[a1].size();a2++)
		{
			if(first==true||is_continue==true)
			{
				
				//非终结符情况
				for(int a3=0;a3<(int)m_non_terminal.size();a3++)
				{
					if(m_creation[a1][a2]==m_non_terminal[a3])
					{
						nt_t=true;
						push_back(m_first[a1],m_creation[a1][a2]);
						for(int a4=0;a4<(int)m_first.size();a4++)
						{
							if(m_first[a4][0]==m_creation[a1][a2])
							{
								for(int a5=1;a5<(int)m_first[a4].size();a5++)
								{
									if(m_first[a4][a5]==m_compare[5])
									{
										is_continue=true;
									}//有空串就使is_continue=ture
								}
							}
						}//非终结符
					}
				}
				//终结符情况
				if(nt_t==false)
				{
					if(m_creation[a1][a2]==m_compare[4])
					{
						push_back(m_first[a1],m_str_compare[5]);
						first=true;//在最后一个非终结符都有空串的时候，我们加了空串到非终结符集合
					}
					else 
					{
						push_back(m_first[a1],m_creation[a1][a2]);
					}
					is_continue=false;
					nt_t=false;
				}

			}
			else if(m_creation[a1][a2]==m_compare[4])
			{
				first=true;
			}
			else
			{
				first=false;
			}
		}
	}//到这里完成了第二遍的非终结符的扫描，下一步是完成替换规则

	for(int b1=0;b1<(int)m_first.size();b1++)
	{
		vector<char> temp_nt;
		temp_nt.push_back(m_first[b1][0]);
		bool is_deal=false;
		for(int b2=1;b2<(int)m_first[b1].size();b2++)
		{
			for(int b3=0;b3<(int)m_non_terminal.size();b3++)
			{
				if(m_first[b1][b2]==m_non_terminal[b3])
				{
					for(int b6=0;b6<(int)temp_nt.size();b6++)
					{
					    if(m_first[b1][b2]==temp_nt[b6])
					    {
						    m_first[b1].erase(m_first[b1].begin()+b2);
						    b2--;
							is_deal=true;
					     }
					}
					if(is_deal==false)
					{
						is_deal=false;
					    for(int b4=0;b4<(int)m_first.size();b4++)
					    {
						    if(m_first[b4][0]==m_first[b1][b2])
						    {
							    for(int b5=1;b5<(int)m_first[b4].size();b5++)
							    {
								    push_back(m_first[b1],m_first[b4][b5]);
						     	}
							}
						}
						m_first[b1].erase(m_first[b1].begin()+b2);
						b2--;
					}
				}
				is_deal=false;
			}
		}
	}
}

void LL1_judge::push_back(vector<char> &vec, char ch)
{
	bool is_include;
	is_include=false;
	for(int i=0;i<(int)vec.size();i++)
	{
		if(vec[i]==ch)is_include=true;
	}
	if(is_include==false)
	{
		vec.push_back(ch);
	}
}