parser.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 670 行 · 第 1/2 页

/* $Log:        PARSER.C $
Revision 1.1  93/04/08  09:41:28  Anthony_Scian
.

// Revision 1.1  1992/08/20  17:14:07  peter
// Initial revision
//
 */

#include <time.h>
#include <string.h>
#include <iostream.h>
#include <iomanip.h>

#include "globals.h"
#include "parser.h"
#include "dfa.h"

Symbol *Symbol::first = NULL;

Symbol::Symbol(const SubString &str) : next(first), name(str), re(NULL) {
    first = this;
}

Symbol *Symbol::find(const SubString &str){
    for(Symbol *sym = first; sym; sym = sym->next)
        if(sym->name == str) return sym;
    return new Symbol(str);
}

void showIns(ostream &o, const Ins &i, const Ins &base){
    o.width(3);
    o << &i - &base << ": ";
    switch(i.i.tag){
    case CHAR: {
        o << "match ";
        for(const Ins *j = &(&i)[1]; j < (Ins*) i.i.link; ++j)
            prtCh(o, j->c.value);
        break;
    } case GOTO:
        o << "goto " << ((Ins*) i.i.link - &base);
        break;
    case FORK:
        o << "fork " << ((Ins*) i.i.link - &base);
        break;
    case CTXT:
        o << "term " << ((RuleOp*) i.i.link)->accept;
        break;
    case TERM:
        o << "term " << ((RuleOp*) i.i.link)->accept;
        break;
    }
    o << "\n";
}

uint RegExp::fixedLength(){
    return ~0;
}

char *NullOp::type = "NullOp";

void NullOp::calcSize(Char*){
    size = 0;
}

uint NullOp::fixedLength(){
    return 0;
}

void NullOp::compile(Char*, Ins*){
    ;
}

void NullOp::split(CharSet&){
    ;
}

ostream& operator<<(ostream &o, const Range &r){
    if((r.ub - r.lb) == 1){
        prtCh(o, r.lb);
    } else {
        prtCh(o, r.lb); o << "-"; prtCh(o, r.ub-1);
    }
    return o << r.next;
}

Range *doUnion(Range *r1, Range *r2){
    Range *r, **rP = &r;
    for(;;){
        Range *s;
        if(r1->lb <= r2->lb){
            s = new Range(*r1);
        } else {
            s = new Range(*r2);
        }
        *rP = s;
        rP = &s->next;
        for(;;){
            if(r1->lb <= r2->lb){
                if(r1->lb > s->ub)
                    break;
                if(r1->ub > s->ub)
                    s->ub = r1->ub;
                if(!(r1 = r1->next)){
                    uint ub = 0;
                    for(; r2 && r2->lb <= s->ub; r2 = r2->next)
                        ub = r2->ub;
                    if(ub > s->ub)
                        s->ub = ub;
                    *rP = r2;
                    return r;
                }
            } else {
                if(r2->lb > s->ub)
                    break;
                if(r2->ub > s->ub)
                    s->ub = r2->ub;
                if(!(r2 = r2->next)){
                    uint ub = 0;
                    for(; r1 && r1->lb <= s->ub; r1 = r1->next)
                        ub = r1->ub;
                    if(ub > s->ub)
                        s->ub = ub;
                    *rP = r1;
                    return r;
                }
            }
        }
    }
    *rP = NULL;
    return r;
}

Range *doDiff(Range *r1, Range *r2){
    Range *r, *s, **rP = &r;
    for(; r1; r1 = r1->next){
        uint lb = r1->lb;
        for(; r2 && r2->ub <= r1->lb; r2 = r2->next);
        for(; r2 && r2->lb <  r1->ub; r2 = r2->next){
            if(lb < r2->lb){
                *rP = s = new Range(lb, r2->lb);
                rP = &s->next;
            }
            if((lb = r2->ub) >= r1->ub)
                goto noMore;
        }
        *rP = s = new Range(lb, r1->ub);
        rP = &s->next;
    noMore:;
    }
    *rP = NULL;
    return r;
}

MatchOp *merge(MatchOp *m1, MatchOp *m2){
    if(!m1)
        return m2;
    if(!m2)
        return m1;
    return new MatchOp(doUnion(m1->match, m2->match));
}

char *MatchOp::type = "MatchOp";

void MatchOp::display(ostream &o) const{
    o << match;
}

void MatchOp::calcSize(Char *rep){
    size = 1;
    for(Range *r = match; r; r = r->next)
        for(uint c = r->lb; c < r->ub; ++c)
            if(rep[c] == c)
                ++size;
}

uint MatchOp::fixedLength(){
    return 1;
}

void MatchOp::compile(Char *rep, Ins *i){
    i->i.tag = CHAR;
    i->i.link = &i[size];
    Ins *j = &i[1];
    uint bump = size;
    for(Range *r = match; r; r = r->next){
        for(uint c = r->lb; c < r->ub; ++c){
            if(rep[c] == c){
                j->c.value = c;
                j->c.bump = --bump;
                j++;
            }
        }
    }
}

void MatchOp::split(CharSet &s){
    for(Range *r = match; r; r = r->next){
        for(uint c = r->lb; c < r->ub; ++c){
            CharPtn *x = s.rep[c], *a = x->nxt;
            if(!a){
                if(x->card == 1)
                    continue;
                x->nxt = a = s.freeHead;
                if(!(s.freeHead = s.freeHead->nxt))
                    s.freeTail = &s.freeHead;
                a->nxt = NULL;
                x->fix = s.fix;
                s.fix = x;
            }
            if(--(x->card) == 0){
                *s.freeTail = x;
                *(s.freeTail = &x->nxt) = NULL;
            }
            s.rep[c] = a;
            ++(a->card);
        }
    }
    for(; s.fix; s.fix = s.fix->fix)
        if(s.fix->card)
            s.fix->nxt = NULL;
}

RegExp *mkDiff(RegExp *e1, RegExp *e2){
    MatchOp *m1, *m2;
    if(!(m1 = (MatchOp*) e1->isA(MatchOp::type)))
        return NULL;
    if(!(m2 = (MatchOp*) e2->isA(MatchOp::type)))
        return NULL;
    Range *r = doDiff(m1->match, m2->match);
    return r? (RegExp*) new MatchOp(r) : (RegExp*) new NullOp;
}

RegExp *doAlt(RegExp *e1, RegExp *e2){
    if(!e1)
        return e2;
    if(!e2)
        return e1;
    return new AltOp(e1, e2);
}

RegExp *mkAlt(RegExp *e1, RegExp *e2){
    AltOp *a;
    MatchOp *m1, *m2;
    if(a = (AltOp*) e1->isA(AltOp::type)){
        if(m1 = (MatchOp*) a->exp1->isA(MatchOp::type))
            e1 = a->exp2;
    } else if(m1 = (MatchOp*) e1->isA(MatchOp::type)){
            e1 = NULL;
    }
    if(a = (AltOp*) e2->isA(AltOp::type)){
        if(m2 = (MatchOp*) a->exp1->isA(MatchOp::type))
            e2 = a->exp2;
    } else if(m2 = (MatchOp*) e2->isA(MatchOp::type)){
            e2 = NULL;
    }
    return doAlt(merge(m1, m2), doAlt(e1, e2));
}

char *AltOp::type = "AltOp";

void AltOp::calcSize(Char *rep){
    exp1->calcSize(rep);
    exp2->calcSize(rep);
    size = exp1->size + exp2->size + 2;
}

uint AltOp::fixedLength(){
    uint l1 = exp1->fixedLength();
    uint l2 = exp1->fixedLength();
    if(l1 != l2 || l1 == ~0)
        return ~0;
    return l1;
}

void AltOp::compile(Char *rep, Ins *i){
    i->i.tag = FORK;
    Ins *j = &i[exp1->size + 1];
    i->i.link = &j[1];
    exp1->compile(rep, &i[1]);
    j->i.tag = GOTO;
    j->i.link = &j[exp2->size + 1];
    exp2->compile(rep, &j[1]);
}

void AltOp::split(CharSet &s){
    exp1->split(s);
    exp2->split(s);
}

char *CatOp::type = "CatOp";

void CatOp::calcSize(Char *rep){
    exp1->calcSize(rep);
    exp2->calcSize(rep);
    size = exp1->size + exp2->size;
}

uint CatOp::fixedLength(){
    uint l1, l2;
    if((l1 = exp1->fixedLength()) != ~0 &&
       (l2 = exp2->fixedLength()) != ~0)
        return l1+l2;
    return ~0;
}

void CatOp::compile(Char *rep, Ins *i){
    exp1->compile(rep, &i[0]);
    exp2->compile(rep, &i[exp1->size]);
}

void CatOp::split(CharSet &s){
    exp1->split(s);
    exp2->split(s);
}

char *CloseOp::type = "CloseOp";

void CloseOp::calcSize(Char *rep){
    exp->calcSize(rep);
    size = exp->size + 1;
}

void CloseOp::compile(Char *rep, Ins *i){
    exp->compile(rep, &i[0]);
    i += exp->size;
    i->i.tag = FORK;
    i->i.link = &i[-exp->size];
}

void CloseOp::split(CharSet &s){
    exp->split(s);
}

RegExp *expr(Scanner &);