graph.cpp

智能的词法分析

#include<iostream>
#include<map>
#include<set>
#include "declarant.h"
#include "Graph.h" 
using namespace std;

/********直接由初态里加一条边到终态，比如说加{,}等****/ 
int Graph::add_wedge(const char& c,const string& returnid)
{
  wedge* p =new wedge;
  p->c = c;
  p->state = ++statenum; 
  p->next = G[1] ;
  G[1] = p; 
  Gend.insert(statenum);
  MAP[statenum]=returnid;
  return 0; 
}

/****从文件中输入图,并进行合并****/ 
int Graph::inputG(char* path,const string& s)
{
  FILE* fp= fopen(path,"r");
  if(fp==NULL)
  {
    cout<<"open error"<<endl;    
    exit(1);            
  }
  else
  {
    int num = 0;  //这次输入的图的状态数 
    fscanf(fp,"%d",&num);
  //  cout<<num<<endl; 
    int start = 0; //初态 
    fscanf(fp,"%d",&start);
  //  cout<<start<<endl;
    Gstart.insert(start+statenum); //加入初态 
    
    // 输入终态 
    int end;
    fscanf(fp,"%s",buff); 
    char* p=buff; 
    while(*p)
    {         
       sscanf(p,"%d,",&end);
   //    cout<<end<<endl; 
       p+=2;  
       MAP.insert(pair< int,string >(end+statenum,s)); //每个终态对应的类型 
       Gend.insert(end+statenum);          
    } 
   // 输入图 
      int first=0; 
      while(fscanf(fp,"%d",&first)!=EOF)
      { 
         fscanf(fp,"%s",buff); 
      //   printf("%s\n",buff);
         p=buff; 
         first+=statenum; 
         while(*p)
         {
           wedge* s1 = new wedge; 
           sscanf(p,"%c,%d,",&s1->c,&s1->state);
 //          cout<<s1->c<<"  "<<s1->state<<endl;
           s1->state+=statenum; 
           p+=4; 
           wedge* temp=G[first];           
           G[first]=s1; 
           s1->next=temp;        
         } 
                                                                
      }   
    statenum+=num; // 总状态数增加 
  }    
  return 0;  
}

/*****释放图资源*****/ 
int Graph::freeG()
{
  map<int,wedge* > :: iterator it; 
  for(it=G.begin(); it!=G.end();it++)
  {
     for(wedge* p=it->second; p; p = it->second)                    
     {
        it->second = p->next;
        delete p;           
     }                 
  }         
  return 0;    
} 

/****输出图****/ 
int Graph::dispalyG()
{ 
    
   FILE* fp=fopen("Graph.txt","w"); 
   //先输出总共有几个状态
   fprintf(fp,"%d\n",statenum); 
   // 先输出初态，初态一行 
   set<int>::iterator it; 
   for(it=Gstart.begin();it!=Gstart.end();it++) 
   fprintf(fp,"%d,",*it);
   fprintf(fp,"\n");
    
   // 输出终态，终态一行 
   for(set<int>::iterator it=Gend.begin(); it!=Gend.end();it++)
   {
     fprintf(fp,"%d,",*it);                                                
   } 
   
   fprintf(fp,"\n"); 
   // 输出邻接表
  map<int, wedge* >:: iterator m_iter;
  for(m_iter=G.begin();m_iter!= G.end(); m_iter++)
  { //没有出度的表头不输出 
    if(m_iter->second) 
    fprintf(fp,"%d\n",m_iter->first);                                
    for(wedge* p=m_iter->second; p!=NULL; p=p->next)
    { 
      fprintf(fp,"%c,%d,",p->c,p->state);                  
    }          
    fprintf(fp,"\n");                  
  } 
    fclose(fp);
    return 0;       
} 

/*****输入源代码******/ 
int Graph::input_code(char* filename) 
{
   FILE* fp;
   if((fp=fopen(filename,"r"))==NULL)
   {
     perror("打开文件错误\n");
     exit(1);                             
   }
   else
   {
      while(fgets(buff, 1000, fp ))
      {
         //puts(buff); 
         linenum++;
       //  cout<<linenum<<endl; 
         match();                              
      }
      display_token();     
   } 
    
 return 0;    
}

/*****定义该类对象时必须执行的*****/ 
int Graph::run()
{  
    
   Graph::inputG("relop.txt","relop");
   Graph::inputG("num.txt","num"); 
   Graph::inputG("id.txt","id");
   add_wedge('=',"="); 
   add_wedge('{',"{"); 
   add_wedge(';',";"); 
   add_wedge(',',",");
   add_wedge('(',"(");
   add_wedge('}',"}");
   add_wedge(')',")");
   add_wedge('+',"+");
   add_wedge('-',"-");
   add_wedge('*',"*");    
   token.insert(pair<string,vector<string> >("relop",vector<string>()));  //关系运算符 
   token.insert(pair<string,vector<string> >("num",vector<string>())); // 正整数 
   token.insert(pair<string,vector<string> >("id",vector<string>()));  //标识符 
   token.insert(pair<string,vector<string> >("reserve",vector<string>())); //关键字 
   token.insert(pair<string,vector<string> >("invalid",vector<string>())); //非法字符 
   token.insert(pair<string,vector<string> >("{",vector<string>()));
   token.insert(pair<string,vector<string> >("}",vector<string>()));
   token.insert(pair<string,vector<string> >("(",vector<string>()));
   token.insert(pair<string,vector<string> >(")",vector<string>()));
   token.insert(pair<string,vector<string> >("+",vector<string>()));
   token.insert(pair<string,vector<string> >("-",vector<string>()));
   token.insert(pair<string,vector<string> >("*",vector<string>())); 
   token.insert(pair<string,vector<string> >("=",vector<string>()));
   // 以下是输入关键字 
   isReserve.insert("int");
   isReserve.insert("printf");
   isReserve.insert("return");
   isReserve.insert("if"); 
   isReserve.insert("else"); 
   isReserve.insert("long"); 
   isReserve.insert("switch"); 
   isReserve.insert("case"); 
   isReserve.insert("break"); 
   isReserve.insert("for"); 
   isReserve.insert("char"); 
   isReserve.insert("return"); 
   isReserve.insert("continue"); 
   isReserve.insert("default");
   isReserve.insert("do");
   isReserve.insert("while");
   isReserve.insert("short");
   isReserve.insert("main");
   isReserve.insert("include");
   input_code("coder.txt");
    
   return 0; 
} 
/****输出关键字的集合*****/ 
int Graph::display_set()
{
  set<string> :: iterator it = isReserve.begin();
  for(;it!=isReserve.end();it++)
  cout<<*it<<endl;    
} 

/***获得token通过字符串的起点和终点下标和终态位置******/ 
int Graph::getToken(int last_ac_state,int start,int end,int flag)
{ 
   FILE* fp=fopen("token.txt","a");  
   char temp[50];
   if(end-start==0||end-start==1) 
   {
     memcpy(temp,buff+start,end-start+1);
     temp[end-start+1] = '\0';
   } 
   else
   { 
     memcpy(temp,buff+start,end-start);
     temp[end-start] = '\0';
   } 
   string s = temp; //匹配出来的那个串 
   cout<<s<<endl;  
  
 if(flag) //合法字符  
 {   
    if( isReserve.find(s) != isReserve.end() ) // 表示找到的是关键字   
   {
     vector<string>& t = token["reserve"];
     for(int i=0;i<t.size();i++)
     if(t[i]== s) //以经存在了 
     {
       fclose(fp);  
       return 0; 
     } 
     //否则加入 
     t.push_back(s);   
     fclose(fp); 
     return 0;                           
   } 
    //不是关键字就在 MAP是找， 
   map<int, string>::iterator it = MAP.find(last_ac_state); 
   if(it == MAP.end() )
   {
     perror("did find"); 
     fclose(fp); 
     return 1;  
   }
   else
   {   //it->second是last_ac_state属于什么类别 
     vector<string>& t=token[it->second];
     for(int i=0;i<t.size();i++)
     if(t[i]==s) //以经存在了 
     { 
       fclose(fp);  
       return 0; 
     } 
     t.push_back(s);
   
   }
 }
 else  //非法字符 
 {
    cout<<s<<"  is  invalid in line"<<linenum<<endl; 
    fprintf(fp,"%s is invalid in line %d \n",s.c_str(),linenum);  
    vector<string>& t=token["invalid"];
     for(int i=0;i<t.size();i++)
     if(t[i]==s) //以经存在了 
     { 
       fclose(fp);  
       return 0; 
     } 
   
    t.push_back(s);       
 }  
  fclose(fp); 
  return 0; 
} 

/***看start经过c能否到达一个状态,
能 返回到达的那个状态，不能返回 0****/ 
int Graph::isok(const char& c,int start)
{ 
  for(wedge* p = G[start]; p ; p=p->next)
  if(p->c == c) return p->state;
  return 0;     
} 

/*****对输入串进行匹配,关键字先按标示符处理*****/ 
int Graph::match()
{  
    int advance=0; //向前读的指针  
    int last_ac_state=0;  //匹配中的最后一个终态
    int last_ac_char_position=0;   //匹配中的最后一个字符 
    int flag=0;   //表示未能匹配成功 
  for(int i=0; buff[i]; i=++advance)
  {  
    if(buff[i]==' '||buff[i]=='\n')continue; //滤出空格和回车 
    
     last_ac_state=0;  //匹配中的最后一个终态
     last_ac_char_position=0;   //匹配中的最后一个字符 
     flag=0;   //表示未能匹配成功 
     for(set<int>::iterator myset=Gstart.begin(); myset!=Gstart.end()&&!flag; myset++)
    {//开始结点遍历,
      int stateA = *myset; //前一个状态  
      int stateB=0;   //后一个状态， 
       for(int j=i;buff[j];j++) //串在移动 
       {  
          stateB= isok(buff[j],stateA); 
          advance=j; 
          if(Gend.find(stateA) != Gend.end()) //stateA是终态的话
          {
              last_ac_state=stateA;
              last_ac_char_position=j;
              flag=1; //表示以找到匹配的了                       
          } 
          
            if(stateB==0) //表示走不下去了            
              break;                
            else
            stateA=stateB; //往前走了一步                                
       }                         
                  
    } 
   if(last_ac_state)  
   { 
     getToken(last_ac_state,i,last_ac_char_position,flag);  
     advance = last_ac_char_position ;    
   } 
   if(flag) //匹配成功的时候要返回退一格 
   advance--;  
   else 
   getToken(last_ac_state,i,advance,flag);                                                 
  } 
 return 0; 
}

/*****输出token****/ 
int Graph::display_token()
{
  FILE* fp=fopen("token.txt","a"); 
  map<string , vector<string> >:: iterator it=token.begin();
  for(;it!=token.end();it++)
  {//  cout<<it->first<<endl; 
    int len=it->second.size(); 
    vector<string>& v=it->second; 
    for(int i=0;i<len;i++)
    {
     // cout<<v[i]<<" ------------------ "<<it->first<<endl;
      fprintf(fp,"%s -------------------- %s\n",v[i].c_str(),it->first.c_str());       
    }                                                  
  } 
  fclose(fp); 
  return 0;    
} 

/****析构函数****/ 
Graph::~Graph()
{
  Graph::freeG();              
               
}