dfa.cpp

开放源码的编译器open watcom 1.6.0版的源代码

//Revision 1.1  1994/04/08  15:27:59  peter
//Initial revision
//

#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "globals.h"
#include "substr.h"
#include "dfa.h"

inline char octCh(uint c){
    return '0' + c%8;
}

void prtCh(ostream &o, uchar c){
    uchar oc = talx[c];
    switch(oc){
    case '\'': o << "\\'"; break;
    case '\n': o << "\\n"; break;
    case '\t': o << "\\t"; break;
    case '\v': o << "\\v"; break;
    case '\b': o << "\\b"; break;
    case '\r': o << "\\r"; break;
    case '\f': o << "\\f"; break;
    case '\a': o << "\\a"; break;
    case '\\': o << "\\\\"; break;
    default:
	if(isprint(oc))
	    o << (char) oc;
	else
	    o << '\\' << octCh(c/64) << octCh(c/8) << octCh(c);
    }
}

void printSpan(ostream &o, uint lb, uint ub){
    if(lb > ub)
	o << "*";
    o << "[";
    if((ub - lb) == 1){
	prtCh(o, lb);
    } else {
	prtCh(o, lb);
	o << "-";
	prtCh(o, ub-1);
    }
    o << "]";
}

uint Span::show(ostream &o, uint lb){
    if(to){
	printSpan(o, lb, ub);
	o << " " << to->label << "; ";
    }
    return ub;
}

ostream& operator<<(ostream &o, const State &s){
    o << "state " << s.label;
    if(s.rule)
	o << " accepts " << s.rule->accept;
    o << "\n";
    uint lb = 0;
    for(uint i = 0; i < s.go.nSpans; ++i)
	lb = s.go.span[i].show(o, lb);
    return o;
}

ostream& operator<<(ostream &o, const DFA &dfa){
    for(State *s = dfa.head; s; s = s->next)
	o << s << "\n\n";
    return o;
}

State::State() : rule(NULL), action(NULL), link(NULL), kCount(0), kernel(NULL) {
    go.nSpans = 0;
    go.span = NULL;
}

State::~State(){
    delete [] kernel;
    delete [] go.span;
}

static Ins **closure(Ins **cP, Ins *i){
    while(!isMarked(i)){
	mark(i);
	*(cP++) = i;
	if(i->i.tag == FORK){
	    cP = closure(cP, i + 1);
	    i = (Ins*) i->i.link;
	} else if(i->i.tag == GOTO){
	    i = (Ins*) i->i.link;
	} else
	    break;
    }
    return cP;
}

struct GoTo {
    Char	ch;
    void	*to;
};

DFA::DFA(Ins *ins, uint ni, uint lb, uint ub, Char *rep)
    : lbChar(lb), ubChar(ub) {
    Ins **work = new Ins*[ni+1];
    uint nc = ub - lb;
    GoTo *goTo = new GoTo[nc];
    Span *span = new Span[nc];
    memset((char*) goTo, 0, nc*sizeof(GoTo));
    tail = &head;
    head = NULL;
    nStates = 0;
    toDo = NULL;
    findState(work, closure(work, &ins[0]) - work);
    while(toDo){
	State *s = toDo;
	toDo = s->link;

	Ins **cP, **iP, *i;
	uint nGoTos = 0;

	s->rule = NULL;
	for(iP = s->kernel; i = *iP; ++iP){
	    if(i->i.tag == CHAR){
		for(Ins *j = i + 1; j < (Ins*) i->i.link; ++j){
		    if(!(j->c.link = goTo[j->c.value - lb].to))
			goTo[nGoTos++].ch = j->c.value;
		    goTo[j->c.value - lb].to = j;
		}
	    } else if(i->i.tag == TERM){
		if(!s->rule || ((RuleOp*) i->i.link)->accept < s->rule->accept)
		    s->rule = (RuleOp*) i->i.link;
	    }
	}

        uint j;
	for(j = 0; j < nGoTos; ++j){
	    GoTo *go = &goTo[goTo[j].ch - lb];
	    i = (Ins*) go->to;
	    for(cP = work; i; i = (Ins*) i->c.link)
		cP = closure(cP, i + i->c.bump);
	    go->to = findState(work, cP - work);
	}

	s->go.nSpans = 0;
	for(j = 0; j < nc;){
	    State *to = (State*) goTo[rep[j]].to;
	    while(++j < nc && goTo[rep[j]].to == to);
	    span[s->go.nSpans].ub = lb + j;
	    span[s->go.nSpans].to = to;
	    s->go.nSpans++;
	}

	for(j = nGoTos; j-- > 0;)
	    goTo[goTo[j].ch - lb].to = NULL;

	s->go.span = new Span[s->go.nSpans];
	memcpy((char*) s->go.span, (char*) span, s->go.nSpans*sizeof(Span));

	(void) new Match(s);

    }
    delete [] work;
    delete [] goTo;
    delete [] span;
}

DFA::~DFA(){
    State *s;
    while(s = head){
	head = s->next;
	delete s;
    }
}

void DFA::addState(State **a, State *s){
    s->label = nStates++;
    s->next = *a;
    *a = s;
    if(a == tail)
	tail = &s->next;
}

State *DFA::findState(Ins **kernel, uint kCount){
    Ins **cP, **iP, *i;

    kernel[kCount] = NULL;

    cP = kernel;
    for(iP = kernel; i = *iP; ++iP){
	 if(i->i.tag == CHAR || i->i.tag == TERM){
	     *cP++ = i;
	} else {
	     unmark(i);
	}
    }
    kCount = cP - kernel;
    kernel[kCount] = NULL;

    State *s;
    for(s = head; s; s = s->next){
	 if(s->kCount == kCount){
	     for(iP = s->kernel; i = *iP; ++iP)
		 if(!isMarked(i))
		     goto nextState;
	     goto unmarkAll;
	 }
	 nextState:;
    }

    s = new State;
    addState(tail, s);
    s->kCount = kCount;
    s->kernel = new Ins*[kCount+1];
    memcpy(s->kernel, kernel, (kCount+1)*sizeof(Ins*));
    s->link = toDo;
    toDo = s;

unmarkAll:
    for(iP = kernel; i = *iP; ++iP)
	 unmark(i);

    return s;
}