winlex.h

用VC写的一个词法分析器

#include"winlexclass.h"
#include<string>
#include<iostream>
#include<stack>

using  namespace std;

class winlex
{
private:
	string keychar;
    int nfai;
	int dfai;
	regnode *rhead;
	sdlink *chead;
    nfanode *nhead,*np;
	dfanode *dhead;
	dnlink *dnlhead;
	void regstrtolink(string regulastr);
	void nfacreate();
    void errorfun(int e);
	regnode * searchfirstc(regnode *trp);
	regnode * searchlc2(regnode *rp);
	void closelink(nfanode * n1);
	regnode * searchlc(regnode * rp);
	void rlinktoclink();
	void dfacreate();
	void dnlins(dilink *dip);

public:
	winlex();
	winlex(string regulastr);
	bool recognise(string inpstr);

};

winlex::winlex()
{
	winlex("");
}

winlex::winlex(string regulastr)
{
	keychar="()*|\\";
	nfai=0;
	dfai=0;
	rhead=NULL;
	chead=NULL;
	nhead=NULL;
	np=NULL;
	dnlhead=NULL;
	regstrtolink(regulastr);
	rlinktoclink();
    nfacreate();
	dfacreate();
}


void winlex::nfacreate()
{
	stack<regnode *> s1;
	regnode *rp,*trp;
    rp=rhead->rnext;
	nhead=new nfanode(nfai);
    np=nhead;
	np->isstart=true;
    while(rp!=NULL)
	{
        if(rp->ischar==false)
		{
			switch (rp->rval)
			{
                case'(':s1.push(rp);
            		break;
				case'|':trp=rp->rpre;
                    while((trp->ischar==false)&&(trp!=rhead))
					{
						if(trp->rval=='|'||trp->rval=='(')
							errorfun(2);
                        trp=trp->rpre;
					}
					if(trp==rhead)
						errorfun(1);
					else
						s1.push(trp);
                    trp=rp->rnext;
                    trp=searchfirstc(trp);
					trp->insed=true;
					break;
				case')':
					if(s1.empty())
						errorfun(1);
					else
					{
						trp=s1.top();
                        if(trp->rval=='('&&trp->ischar==false)
                            s1.pop();
                        else
						{
							while(trp->ischar==true&&!s1.empty())
							{
								delete(trp->pilnode->nnext);
								trp->pilnode->nnext=np;
								s1.pop();
								trp=s1.top();
                            }
							if(trp->rval=='('&&trp->ischar==false)
                                s1.pop();
							else
								errorfun(1);
						}
					}
					break;
				case'*':
					trp=searchlc2(rp);
                    closelink(trp->pnfan);
					break;
			}
		}
		else
		{
			if(rp->insed==false)
			{
				np=np->iins(rp,np,nfai);
			}
			else
			{
				np=searchlc(rp)->pnfan;
				np=np->iins(rp,np,nfai);               
			}
		}
        rp=rp->rnext;
	}
	if(!s1.empty())
        errorfun(1);
	np->isend=true;
}

void winlex::regstrtolink(string regstr)
{
    rhead=new regnode;
	regnode *rp;
	rp=rhead;
	rp->rnext=NULL;
	unsigned int i;
	basic_string <char>::size_type j;
    rp=new regnode();
	rp->ischar=false;
	rp->lnum=0;
	rp->rval='(';
	rp->rpre=rhead;
	rp->rnext=rhead->rnext;
	rhead->rnext=rp;
	for(i=0;i<regstr.length();i++)
	{
		if(regstr.at(i)!='\\')
		{
            rp->rnext=new regnode;
            (*rp).rnext->rpre=rp;
            rp=rp->rnext;
            rp->rnext=NULL;
            (*rp).lnum=i+1;
            (*rp).rval=regstr.at(i);
			j=-1;
			j=keychar.find(regstr.at(i));
			if(i==0)
			{
				if(j==-1)
					rp->ischar=true;
				else
					rp->ischar=false;
			}
			else
			{
				if(j==-1)
					rp->ischar=true;
				else
				{
					if(regstr.at(i-1)=='\\')
						rp->ischar=true;
					else
						rp->ischar=false;
				}
			}
		}
	}
	rp->rnext=new regnode();
	rp->rnext->rpre=rp;
	rp=rp->rnext;
	rp->lnum=i;
	rp->rval=')';
	rp->ischar=false;
}

regnode * winlex::searchfirstc(regnode *trp)
{
    while(trp->ischar==false)
    {
        if(trp->rval!='(')
            errorfun(3);
        else
		{
            trp=trp->rnext;
			if(trp==NULL)
				errorfun(1);
		}
	}
	return(trp);
}

regnode * winlex::searchlc2(regnode *rp)
{
	stack<char> s2;
	regnode *trp;
	trp=rp->rpre;
	if(trp->ischar==true)
		return(trp);
	else
	{
		if(trp->rval==')')
			s2.push(')');
		else
			errorfun(4);
		while(!s2.empty()&&trp!=rhead)
		{
			trp=trp->rpre;
			if(trp->ischar==false&&trp->rval==')')
				s2.push(')');
			if(trp->ischar==false&&trp->rval=='(')
				s2.pop();
		}
		if(trp==rhead)
			errorfun(1);
		else
            return(searchfirstc(trp));        
	}
	return(NULL);
}

void winlex::closelink(nfanode * n1)
{
	bool find=false;
	nunode *tnup,*tnup1;
	tnup=np->nuhead->nunext;
	tnup1=np->nuhead;
	while(tnup!=NULL)
	{
		if(tnup->nunfa==n1)
			find=true;
		tnup1=tnup;
		tnup=tnup->nunext;
	}
	if(!find)
	{
		tnup1->nunext=new nunode;
		tnup=tnup1->nunext;
        tnup->nunfa=n1;
        tnup=new nunode;
        tnup->nunfa=np;
        tnup->nunext=n1->nuhead->nunext;
        n1->nuhead->nunext=tnup;
	}
}

regnode * winlex::searchlc(regnode * rp)
{
	stack<char> s2;
	regnode *trp;
	trp=rp->rpre;
	while(trp->rval!='|')
	{
        if(trp->rval!='(')
			errorfun(3);
		trp=trp->rpre;
	}
	trp=trp->rpre;
	if(trp==rhead)
		errorfun(1);
	else
	{
		if(trp->ischar==false)
			if(trp->rval=='('||trp->rval=='|')
				errorfun(2);
		while(trp->rval!='('||!s2.empty()||trp->ischar==true)
		{
			if(trp->ischar==false)
			{
				if(trp->rval==')')
					s2.push(')');
				if(trp->rval=='(')
				{
					if(s2.empty())
						errorfun(1);
					else
						s2.pop();
				}
			}
			trp=trp->rpre;
		}
		if(trp!=rhead)
			return(searchfirstc(trp));
		else
			errorfun(1);
	}
	return(NULL);
}

void winlex::rlinktoclink()
{
	chead=new sdlink();
	regnode *rp;
	sdlink *cp,*cp1;
	bool find=false;
	cp=chead;
	rp=rhead->rnext;
	while(rp!=NULL)
	{
		if(rp->ischar==true)
		{
			find=false;
            cp=chead;
            while(cp->next!=NULL)
            {
                if(((sdlink *)cp->next)->cval==rp->rval)
				{
					find=true;
                    break;
				}
				cp=(sdlink *)cp->next;
            }
			if(!find)
			{
                cp1=new sdlink();
                cp1->cval=rp->rval;
                cp1->next=cp->next;
                cp->next=cp1;
			}
		}
		rp=rp->rnext;
	}
}

void winlex::dfacreate()
{
	sdlink *sdlp;
	dnlink * dnp;
	dfanode *dp;
	dlink *sp;
	dnlhead=new dnlink(dfai);
	dnp=dnlhead;
	dhead=new dfanode();
	sp=new dlink();
	dhead->selflinkhead->next=sp;
	sp->pdton=nhead;
	dp=dhead;
	dnp->pd=dhead;
	dhead->selfclosure();
	dhead->nval=0;
	dhead->dfasetend(nfai-1);
	while(dnp!=NULL)
	{
		dp=dnp->pd;
		sdlp=(sdlink *)chead->next;
        while(sdlp!=NULL)
		{
			dp->dfailins(sdlp->cval);
			dp->dfaclollink();
            dnlins(((dilink *)dp->ilhead->next));
			sdlp=(sdlink *)sdlp->next;
		}
		dnp=(dnlink *)dnp->next;        
	}
}

void winlex::dnlins(dilink *dip)
{
	dnlink *dnp,*dnp1;
	dnp=dnlhead;
	dlink *dp1,*dp2;
	dp2=(dlink *)dip->pd->selflinkhead->next;
	bool bs=true;
	if(dp2==NULL)
		return;
	while(dnp!=NULL)
	{
		bs=true;
        dp1=(dlink *)dnp->pd->selflinkhead->next;
		dp2=(dlink *)dip->pd->selflinkhead->next;
		while(dp1!=NULL&&dp2!=NULL)
		{
			if(dp1->pdton->nnum==dp2->pdton->nnum)
			{
				dp1=(dlink *)dp1->next;
				dp2=(dlink *)dp2->next;
			}
			else
			{
				bs=false;
				break;
			}
		}
		if(bs==true&&dp1==NULL&&dp2==NULL)
		{
            delete(dip->pd);
			dip->pd=dnp->pd;
			return;
		}
		dnp1=dnp;
		dnp=(dnlink *)dnp->next;
	}
	dnp1->next=new dnlink(dfai);
	dnp1=(dnlink *)dnp1->next;
	dnp1->pd=dip->pd;
	dnp1->pd->nval=dnp1->nval;
    dnp1->pd->dfasetend(nfai-1);
}

bool winlex::recognise(string inpstr)
{
    dfanode *dp;
	dp=dhead;
	dilink *dip;
	unsigned int i;
	bool find;
	for(i=0;i<inpstr.length();i++)
	{
		find=false;
		dip=(dilink *)dp->ilhead->next;
        while(dip!=NULL)
		{
			if(dip->cval==inpstr.at(i))
			{
				dp=dip->pd;
				find=true;
				break;
			}
			dip=(dilink *)dip->next;
		}
		if(!find)
			return(false);
	}
	if(dp->isend)
		return(true);
	return(false);
}

void winlex::errorfun(int e)
{
	switch(e)
	{
        case 0:
			break;
	    case 1:cout<<"正规式格式错误：左右括号不匹配"<<endl;
    		break;
		case 2:cout<<"正规式格式错误：'|'前面不能为'|'或'('"<<endl;
			break;
		case 3:cout<<"正规式格式错误：'|'后面不能为'|'或'('或'*'"<<endl;
		    break;
		case 4:cout<<"正规式格式错误：'*'前面不能为'|'或'('或'*'"<<endl;
		    break;
		default:cout<<"正规式格式错误"<<endl;
			break;
	}
	exit(0);
}