yacc.cpp

LL（1）分析 写的语法分析程序

#include<iostream>
#include "YACC.h"
using namespace std;

/*****从文件中输入产生式到Production中,同时得到非终极符
强制规定每一个token之间一定要有空格,s为文件名******/ 
int YACC::input(const char* s)
{
  FILE* fp = fopen(s,"r");
  int len=0; //buff的长度 
  char buff[100]; 
  if(fp==NULL)
  {
    perror("Error opening file"); 
  }
  else
  {
    int k=0;
    NonTerminal.push_back(" ");
    //为了写程序的方便，先初始化一个起点，这样好判断有没有重复的元素 
    while(fgets(buff,100,fp))  
    { 
      printf("%s\n",buff); 
      char *result = strtok(buff," \n"); //获得非终结符  
      printf("%s\n",result);  
      if(result!=NonTerminal[k])
      { 
        NonTerminal.push_back(result);
        k++;
      }   
      Production temp; //定义一条产生式 
      temp.LProduction = result; 
       strtok(NULL," \n"); // 去掉 -> 
        while((result=strtok(NULL," \n"))!= NULL)
       { 
         printf("%s\n",result);         
         temp.RProduction.push_back(result);  //存储产生式右部                    
       } 
        
       P.push_back(temp); //加入一条产生式      */                         
    } 
    
  } 
  fclose(fp);
   return 0; 
}

/***得到文法的终结符*****/ 
int YACC::solveTerminal()
{ 
  int lenP=P.size(); 
  for(int i=0;i < lenP;i++)//遍历整个文法 
  {
    int  lenRProduction=(P[i].RProduction).size(); 
    for(int j=0; j<lenRProduction ;j++) //遍历每个产生式的右部 
    { 
       bool flag = true;  
       for(int k=1;k<NonTerminal.size()&&flag;k++)
       if(NonTerminal[k]==(P[i].RProduction)[j])
        flag=false;//该token在非终极符中没找到
       if(flag) 
       Terminal.insert( (P[i].RProduction)[j] );// 刚把它加到终极符的集合中  
    }      
  }  
   return 0; 
}  
/*****输出NonTerminal*******/ 
inline int YACC::displayNonTerminal()
{
  FILE* fp = fopen("NonTerminal.txt","w");  
  cout<<"there are NonTerminals"<<endl; 
  for(int i=1;i<NonTerminal.size();i++) //注意从1开始 
  { 
    cout<<NonTerminal[i]<<endl; 
    fprintf(fp,"%s\n",(NonTerminal[i]).c_str());                 
  }      
  cout<<endl; 
  fclose(fp); 
   return 0; 
} 

inline int YACC::displayTerminal()
{
  set<string>::iterator it;  
  FILE* fp = fopen("Terminal.txt","w");   
  cout<<"there are Terminals"<<endl; 
  for(it=Terminal.begin();it!=Terminal.end();it++)
  {
    cout<<*it<<endl;    
    fprintf(fp,"%s\n",(*it).c_str());              
  }      
  cout<<endl; 
   return 0;    
} 
/*********s1和s2合并，结果保存在s1中,update为s1到底有没有更新
有更新为true *******/ 
int YACC::union_set(set<string>& s1,set<string>& s2,bool & update) 
{
  set<string>::iterator it;   
  for(it=s2.begin();it!=s2.end();it++)
  {
    if(s1.find(*it)==s1.end()) //s1中没有的元素 
    {
      s1.insert(*it); 
      update= true;
    }                                   
  }    
  return 0;  
} 

/************得到 First**********/
int YACC::solveFirst() 
{
    int lenP=P.size(); 
   int* start = new int[lenP];
   int* end = new int[lenP];
   memset(start,0,lenP); //每一个产生式的起点都为0
  for(int i=0;i < lenP;i++)//遍历整个文法 
  {
    end[i]=P[i].RProduction.size()-1; //初始化每一个产生式的终点  
  } 
  bool update=true; 
  while(update)
  {  
    update= false ; 
     for(int i=0;i < lenP;i++)//遍历整个文法 
    {
     if(start[i]<end[i])
     { 
        set<string>& s2 = First[P[i].RProduction[start[i]]];//s2为产生式右部的下标为start[i]这个token的First
        if(s2.find("@")!=s2.end())// s2中包括空字符@
        {
          start[i]++;
          update = true; //有更新 
          s2.erase("@");
        } 
       //把产生式右部的下标为start[i]这个token的First加入到该产生式左部 
       union_set(First[P[i].LProduction],s2,update);                 
     } 
     else 
     {
        //s2为产生式右部的下标为start[i]这个token的First  
       set<string>& s2 = First[P[i].RProduction[start[i]]];    
       union_set(First[P[i].LProduction],s2,update);     
     } 
    }
  } 
  delete []start; 
  delete []end; 
  start = NULL;
  end = NULL;  
  return 0; 
} 

/******输出First******/ 
 int YACC::displayFirst() 
 {
   FILE* fp = fopen("First.txt","w");
   map<string,set<string > >::iterator it;
   set<string>::iterator s_iter;
   for(it=First.begin();it!=First.end();it++) 
   {
     fprintf(fp,"First(%s)={",it->first.c_str());
     for(s_iter=(it->second).begin();s_iter!=(it->second).end();s_iter++)                                          
      fprintf(fp,"%s ,",(*s_iter).c_str());
      fprintf(fp,"}\n");                                         
   }   
   fclose(fp);
    return 0; 
 }

/*****用 来 求 每一 个非终结符出现的位置的******/ 
int YACC::solvePosition(vector< vector<pair<int,int> > > &position )
{
  vector<pair<int,int> > T;
  int lenP = P.size(); 
  for(int k=1; k<NonTerminal.size(); k++) 
  {  
     position.push_back(T);
     for(int i=0;i<lenP;i++)//看他出现的位置 
     {
        for(int j=0;j<(P[i].RProduction).size();j++)
        {
           if((P[i].RProduction)[j] == NonTerminal[k])
           position[k-1].push_back( make_pair<int,int>(i,j) );       
        } 
     }                                           
  }  
  return 0;  
} 

/*******输出 每一 个非终结符出现的位置******/
int YACC::displayPosition( vector< vector<pair<int,int> > >& position)
{
   
   for(int k=0;k<position.size();k++)
   {
     vector<pair<int,int> >& v= position[k];
     cout<<NonTerminal[k+1]<<":  "; 
     for(int i=0;i<v.size();i++)
     {
       cout<<v[i].first<<" "<<v[i].second<<", ";        
     }                                          
     cout<<endl;      
   }     
} 
 /*****求Follow集*****/ 
int YACC::solveFollow()
{
   int lenP=P.size(); 
   int* end = new int[lenP]; 
  for(int i=0;i < lenP;i++)//遍历所有的产生式 
  { 
    end[i]=P[i].RProduction.size()-1; //初始化每一个产生式的终点  
  }  
  //存每一个非终极符出现的位置 pair<int,int>，
  //第几行(第几个产生式)的下标是第几。 
  vector< vector<pair<int,int> > > position;  
  solvePosition(position); //position 下标从0开始 ,Nonterminal下标从1开始,P下标也从0开始 
  YACC::displayPosition(position); 
  
  bool update=true; 
  while(update)
  {  
    update = false ; 
    for(int k=0;k<position.size();k++)//每一个非终极符 NonTerminal[k+1] 
    {
       for(int i=0; i<position[k].size(); i++) //遍历每一个终极符出现的位置 
       {
         int r = (position[k])[i].first;// NonTerminal[k+1] 所在的是第r个产生式
         int c = (position[k])[i].second;//第r个产生式的第c个位置
      //   cout<<"k="<<k<<"  r="<<r<<"  c="<<c<<endl; 
         if( c < end[r]) //不在产生式的尾部 
         { 
           string s = (P[r].RProduction)[c+1]; //该终级符后面的那个token 
           set<string>& temp =First[s]; //该终极符后面那个token的First集 
            if(temp.find("@")==temp.end()) //不包括空字符 
            {
              //NonTerminal[k+1]是这个非终级符 
              union_set(Follow[NonTerminal[k+1]],temp,update);   //合并                                        
            }
            else
            { 
              temp.erase("@"); //先删除空字符 
              union_set(Follow[NonTerminal[k+1]],temp,update); //合并 
              temp.insert("@"); //因为temp是一个First的引用，所以必须加上空字符 
              //同时加上该产生式左边的Follow集  
              union_set(Follow[NonTerminal[k+1]],Follow[P[r].LProduction],update);
            }   
         } 
         else //在产生式尾部 
         {
           union_set(Follow[NonTerminal[k+1]],Follow[P[r].LProduction],update);     
         } 
       
       }                                               
    } 
    
  }  
  
  delete[] end; 
  end = NULL;   
  return 0;  
} 

/*****输出Follow*****/ 
int YACC::displayFollow()
{
   FILE* fp = fopen("Follow.txt","w");
   map<string,set<string > >::iterator it;
   set<string>::iterator s_iter;
   for(it=Follow.begin();it!=Follow.end();it++) 
   {
     fprintf(fp,"Follow(%s)={",it->first.c_str());
     for(s_iter=(it->second).begin();s_iter!=(it->second).end();s_iter++)                                          
      fprintf(fp,"%s ,",(*s_iter).c_str()); 
      fprintf(fp,"}\n");                                        
   }   
   fclose(fp);
   return 0;      
}

/*****专门用来为分析表加入一个结点的，
 i表示第几条产生式，s表示First集 ******/ 
int YACC::insert_node(set<string>& s,int i)
{
   set<string>::iterator it; 
   node* temp;  
    for(it=s.begin(); it!=s.end(); it++)//遍历这个token的First
    {
       //挂接一条边 
       temp = ParseTable[P[i].LProduction];
       node* p =new node;
       p->s = *it; //这个结点的终结符 
       p->n = i; //对应的产生式编号 
       p->next = temp; 
       ParseTable[P[i].LProduction]= p;                            
    }    
   return 0; 
} 
/******求分析表*********
有邻接法来存分析表*/  
int YACC::solveParseTable()
{
  int lenP= P.size(); 
  set<string>::iterator it; 
  node* temp; 
  for(int i=0;i<lenP;i++)//遍历每一个产生式 
  {
     string& s=(P[i].RProduction)[0];//产生式右部的第一个token
     set<string>& first_set = First[s]; //产生式右部第一个token的First
    if(first_set.find("@")==first_set.end())//First集中没有空字符,则直接用first 
    insert_node(first_set,i);//对First求分析表  
    else 
    {
      first_set.erase("@");
      insert_node(first_set,i);//对First求分析表  
      first_set.insert("@"); 
      insert_node(Follow[P[i].LProduction],i);//对产生式左部的Follow求分析表  
    }    
          
  }    
  return 0;  
} 

/******输出分析表********/ 
int YACC::displayParseTable()
{
  map<string,node* >::iterator it;
  node* p; 
  FILE* fp=fopen("ParseTable.txt","w");  
  for(it=ParseTable.begin(); it!=ParseTable.end();it++)
  {
     p=it->second;
     fprintf(fp,"%s\n",(it->first).c_str()); 
     while(p)
     { 
       fprintf(fp,"%s %d,",(p->s).c_str(),p->n); 
       p=p->next;       
     }       
    fprintf(fp,"\n");                      
  }         
  return 0;      
} 
/*****用来查在邻接表中遇到终极符s 是要对应哪条产生式，
*********没找到时返回-1,找到返回 产生式编号********/ 
int YACC::find(node* start,const string& s)
{
  while(start)
  {
    if(start->s==s)
    return  start->n; 
    start=start->next;          
  }    
  return -1;  
}
//为了输出整个分析的过程，写了这个打印的函数  
int YACC::printf_stack(stack<string>& s,int i,vector<string>& v,FILE* fp)
{
   fprintf(fp,"分析栈 "); 
   while(!s.empty())
   {
     fprintf(fp,"%s ",s.top().c_str());
     s.pop();                 
   }  
   fprintf(fp,"\n字符串 ");
   for(int k=i;k<v.size();k++)
   fprintf(fp,"%s ",v[k].c_str());
   fprintf(fp,"\n\n");
   return 0; 
} 
/******预测分析,成功返回0，错误返回-1******/ 
int YACC::match()
{
  
  stack <string> ParseS;//分析栈
  vector<string> s; 
  FILE* fp = fopen("input.txt","r");
  char buff[1000]; 
  if(fp==NULL)
  {
    perror("open file fail");
    exit(1); 
  } 
    //正确读入要分析的字符串 
    fgets(buff,1000,fp);
    char* result=strtok(buff," \n");
    printf("%s\n",result);
    s.push_back(result);
    while(result=strtok(NULL," \n"))
    {
      s.push_back(result);  printf("%s\n",result);                        
    } 
    fclose(fp); 
    s.push_back("$");//在字符串最后加上一个界符$ 
    ParseS.push("$");//界符和开始符号入分析栈 
    ParseS.push(P[0].LProduction); 
    int k=0;//要分析的串的开始下标 
    fp= fopen("分析过程.txt","w"); 
    stack<string> temp;//用来打印元素的 
    while(!ParseS.empty())//只要分析栈不空 
    {
     temp=ParseS; 
     printf_stack(temp,k,s,fp); 
     string x = ParseS.top();//栈顶元素 
     if(x=="@") //如果栈顶元素是空字符的话。直接出栈 
     { 
       ParseS.pop();
       continue;
     }
      if(x=="$"||Terminal.find(x)!=Terminal.end())//是终极符 或者 是界符 
      { 
        if(s[k]==x)
        {
          ParseS.pop();
          ++k; 
        }    
        else  
        return -1;                                          
      }
      else //不是终极符 
      { 
         int result = find(ParseTable[x],s[k]); 
         if(result == -1) //分析表中没找到  
         return -1;
         else
         {
           ParseS.pop(); 
           for(int i=P[result].RProduction.size()-1; i>=0; i--) //注意产生式的右部的最右边先进栈 
           {
             ParseS.push(P[result].RProduction[i]);        
           } 
         }   
      }                     
    }     
   return 0; 
} 
/****定义一个对像一定要执行的****/ 
int YACC::run()
{
     
   displayNonTerminal(); 
    displayTerminal(); 
} 
/****默认构造函数 ***/ 
YACC::YACC()
{
  YACC::input("Production.txt"); 
  YACC::solveTerminal(); 
  set<string>::iterator it;
  for(int i=1;i<NonTerminal.size();i++) //每一个非终结符的First，Follow初始化为空 
  {
    First.insert(pair<string,set<string> >(NonTerminal[i],set<string>())); 
    Follow.insert(pair<string,set<string> >(NonTerminal[i],set<string>()));  
    ParseTable.insert(pair<string,node*>(NonTerminal[i],0)); //初始化分析表                                           
  }        
  //开始符号的Follow加上界符 $   
  Follow[P[0].LProduction].insert("$"); 
  for(it=Terminal.begin();it!=Terminal.end();it++) //每一个终结符的First初始化为本身 
  { 
    set<string> s;
    s.insert(*it); 
     First.insert(pair<string,set<string> >(*it,s));                                                
  } 
   
  YACC::run(); 
  YACC::solveFirst() ;
  YACC::displayFirst() ;
  
  
  YACC::solveFollow(); 
  YACC::displayFollow(); 
  solveParseTable();
  displayParseTable();
   if(match()== -1)
   cout<<"匹配不成功"<<endl;
   else cout<< "匹配成功"<<endl;
 }

/*****析构函数*****/ 
YACC::~YACC()
{
  map<string,node* >::iterator it; 
  node* p=0;
  node* q=0; 
  for(it=ParseTable.begin(); it!=ParseTable.end();it++)
  {
     p=it->second;
     while(p)
     {
       q=p; 
       p=p->next;
       delete q;        
     }                           
  }            
             
}