mylex.cpp

一个不算完整的编译器实现

#include<iostream>
#include<string>
#include<fstream>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define is_sLetter(ch)    ( 'a'<=(ch)&&(ch)<='z' )
#define is_bLetter(ch)    ( 'A'<=(ch)&&(ch)<='Z' )
#define isLetter(ch)      ( is_sLetter(ch)||is_bLetter(ch) )
#define isDigit(ch)       ( '0'<=(ch)&&(ch)<='9' )
#define isOperator(ch)    ( (ch)=='+'||(ch)=='-'||(ch)=='*'||(ch)=='/'||(ch)=='%' )

ofstream cou("system\\word...txt");
vector<string>errors;
vector<int>errorline;

char f[6][6]=
{
	/* |  &   (   )   *   # */
    {'<','<','<','>','<','>'},
    {'>','<','<','>','<','>'},
    {'<','<','<','=','<','$'},
    {'>','>','$','<','>','$'},
    {'>','>','<','>','<','>'},
    {'<','<','<','$','<','+'}
};

int opMap(char s)
{
    switch(s)
    {
    case'|':return 0;
    case'&':return 1;
    case'(':return 2;
    case')':return 3;
    case'*':return 4;
    case'#':return 5;         
    }
    return -1;    
}

struct Node
{
    char id;
    vector<int>next;
	vector<string>toNext;
	string ID;
	bool accept;
};
struct DFANode
{
    char id;
    int at;
    vector<int>states;
    vector<DFANode*>next;
    vector<string>toNext;
    string ID;
    bool accept;       
};

vector<DFANode*>DFAVector;
vector<Node*>nodeVector;
vector<Node*>MDFA;
vector<string>dataVector;
vector<string>keyWord;
stack<int>dataStack;
stack<char>opStack;
Node* begin;
Node* end;
DFANode* Dbegin;
Node* Begin;

void out(vector<int>s)
{
     int l=(int)s.size();
     cou<<"{";
     for(int i=0;i<l-1;i++)
             cou<<s[i]<<",";cou<<s[l-1]<<"}";    
}
void getNode(string s)
{
    int sum=(int)nodeVector.size();
    
	Node* before = new Node;
	nodeVector.push_back(before);
	dataStack.push(sum);
	before->next.push_back(sum+1);
	before->toNext.push_back(s);
	before->accept=false;
	
	Node* after = new Node;
	nodeVector.push_back(after);
	dataStack.push(sum+1);
	after->accept=false;
}
void runOr()
{
     int sum=(int)nodeVector.size();
     int y2=dataStack.top();dataStack.pop();
     int x2=dataStack.top();dataStack.pop();
     int y1=dataStack.top();dataStack.pop();
     int x1=dataStack.top();dataStack.pop();
     
     Node* before = new Node;
     nodeVector.push_back(before);
     dataStack.push(sum);
     before->accept=false;
     before->next.push_back(x1);
     before->next.push_back(x2);
     before->toNext.push_back("");
     before->toNext.push_back("");
     		
     Node* after = new Node;
     nodeVector.push_back(after);
     dataStack.push(sum+1);
     after->accept=false;
     nodeVector[y1]->next.push_back(sum+1);
     nodeVector[y2]->next.push_back(sum+1);
     nodeVector[y1]->toNext.push_back("");
     nodeVector[y2]->toNext.push_back("");
}
void runAnd()
{
     int y2=dataStack.top();dataStack.pop();
     int x2=dataStack.top();dataStack.pop();
     int y1=dataStack.top();dataStack.pop();
     int x1=dataStack.top();dataStack.pop();
     
     nodeVector[y1]->next.push_back(x2);
     nodeVector[y1]->toNext.push_back("");
     
     dataStack.push(x1);
     dataStack.push(y2);
}
void runClo()
{
     int sum=(int)nodeVector.size();
     int y1=dataStack.top();dataStack.pop();
     int x1=dataStack.top();dataStack.pop();
     
     Node* before = new Node;
     nodeVector.push_back(before);
     dataStack.push(sum);
     before->accept=false;
     before->next.push_back(x1);
     before->toNext.push_back("");
     before->next.push_back(sum+1);
     before->toNext.push_back("");
     
     Node* after = new Node;
     nodeVector.push_back(after);
     dataStack.push(sum+1);
     after->accept=false;
     nodeVector[y1]->next.push_back(sum+1);
     nodeVector[y1]->toNext.push_back("");
     
     nodeVector[y1]->next.push_back(x1);
     nodeVector[y1]->toNext.push_back("");       
}
void runOp(char s)
{
	 if(s==')')
	 {
         char b=opStack.top();
         opStack.pop();
         if(b=='(')  return;
         runOp(b);     
     }
     else if(s=='|')
    	       runOr();
     else if(s=='&')
               runAnd();
     else if(s=='*')
               runClo();
}

void getOp(char s)
{
	char b = opStack.top();
	int x2=opMap(s),x1=opMap(b);
	if(f[x1][x2]=='<')   
    {
        opStack.push(s);
    }
	else if(f[x1][x2]=='>')	
	{
        runOp(b);
        opStack.pop();
        getOp(s);
	}
	else
	{
		opStack.pop();
		if(opStack.empty())
				            return ;
	}
}
void showNFA()
{
    cou<<" NFA:"<<endl;
    int l=(int)nodeVector.size();
    for(int i=0;i<l;i++)
    {
         int s=(int)nodeVector[i]->next.size();
         for(int j=0;j<s;j++)
         {
             cou<<"     "<<i<<"-"<<nodeVector[i]->toNext[j]<<"->"<<nodeVector[i]->next[j]<<endl;        
         }        
    }
    cou<<endl<<" - - - - - - - - - - NFA - END - - - - - - - - - "<<endl<<endl;
    return ;      
}
bool include(vector<string> a,string s)
{
     int l=(int)a.size();
     for(int i=0;i<l;i++)
             if(a[i]==s) return true;
     return false;     
}
void toNFA(string s)
{
     int l=(int)s.length();
     string a="";
     for(int i=0;i<l;i++)
     {
         if(s[i]=='"')
         {
              i++;
              while(s[i]!='"')
              {
                 a+=s[i];
                 i++;           
              }
              if(a!=""&&(!include(dataVector,a)))
                                        dataVector.push_back(a);
              getNode(a);
              a="";       
         }
         else if(opMap(s[i])>=0)
         {
             if(a!="")
             {
                 if(a=="@")		a="";
				 if(a!=""&&(!include(dataVector,a)))
                                           dataVector.push_back(a);
                 getNode(a);
             }
             a="";  
             getOp(s[i]);                                                                  
         }
         else
             a+=s[i];  
     }
     return;     
}
bool include(vector<int> a,int s)
{
     int l=(int)a.size();
     for(int i=0;i<l;i++)
             if(a[i]==s) return true;
     return false;     
}
vector<int> E_closure(int q)
{
     vector<int> res;
     res.push_back(q);
     stack<int> op;
     op.push(q);
     while(!op.empty())
     {
         int t=op.top();op.pop();
         int l=(int)nodeVector[t]->next.size();
         for(int i=0;i<l;i++)
         {
             if(nodeVector[t]->toNext[i]=="")
             {
                  int s=nodeVector[t]->next[i];
                  if(!include(res,s))
                  {
                       res.push_back(s);
                       op.push(s);
                  }                                
             }        
         }                  
     }
     return res;
}
vector<int> move(vector<int>T ,string s)
{
    vector<int> res;
    int l=(int)T.size();
    for(int i=0;i<l;i++)
    {
            int li=(int)nodeVector[T[i]]->next.size();
            for(int j=0;j<li;j++)
            {
                    if(nodeVector[T[i]]->toNext[j]==s)
                    {
                         vector<int> ss=E_closure(nodeVector[T[i]]->next[j]);
                         int lss=(int)ss.size();
                         for(int i=0;i<lss;i++)
                                 if(!include(res,ss[i]))      
                                                 res.push_back(ss[i]);                                  
                    }        
            }
    }
    return res;
}
void showDFA()
{
     int l=(int)DFAVector.size();
     cou<<" DFA:"<<endl;
     for(int i=0;i<l;i++)
     {
         int li=(int)DFAVector[i]->next.size();
         for(int j=0;j<li;j++)
         {
             cou<<"     "<<DFAVector[i]->id<<"-"<<DFAVector[i]->toNext[j]<<"->"<<DFAVector[i]->next[j]->id;
             if(DFAVector[i]->next[j]->accept)
             {
                 cou<<" -> 可被接受为 "<<DFAVector[i]->next[j]->ID;            
             }
             cou<<endl;
         }      
     }
     cou<<endl<<" - - - - - - - - - - DFA - END - - - - - - - - - "<<endl<<endl;    
}
bool equal(vector<int> s1,vector<int> s2)
{
     int l1=(int)s1.size(),l2=(int)s2.size();
     if(l1!=l2)    return false;
     for(int i=0;i<l1;i++)
     {
          int j=0;
          for(j=0;j<l2;j++)
          {
               if(s2[j]==s1[i])
                            break;        
          }
          if(j==l2)    return false;        
     }
     return true;     
}
void getAccept(DFANode* a)
{
     int l=(int)a->states.size();
     for(int i=0;i<l;i++)
     {
         if(nodeVector[a->states[i]]->accept)   
         {
             a->accept=true;
             a->ID=nodeVector[a->states[i]]->ID;
             return;                                       
         }
     }
     a->accept=false;
}
int move(DFANode* d,string s)
{
     int l=(int)d->next.size();
     for(int i=0;i<l;i++)
     {
          if(d->toNext[i]==s)
          {
             int p=d->next[i]->id-'A';
             return DFAVector[p]->at;                   
          }   
     }
     return d->at;