code.cpp

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

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


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

// there must be at least one span in list;  all spans must cover
// same range

void Go::compact(){
    // arrange so that adjacent spans have different targets
    uint i = 0;
    for(uint j = 1; j < nSpans; ++j){
        if(span[j].to != span[i].to){
            ++i; span[i].to = span[j].to;
        }
        span[i].ub = span[j].ub;
    }
    nSpans = i + 1;
}

void Go::unmap(Go *base, State *x){
    Span *s = span, *b = base->span, *e = &b[base->nSpans];
    uint lb = 0;
    s->ub = 0;
    s->to = NULL;
    for(; b != e; ++b){
        if(b->to == x){
            if((s->ub - lb) > 1)
                s->ub = b->ub;
        } else {
            if(b->to != s->to){
                if(s->ub){
                    lb = s->ub; ++s;
                }
                s->to = b->to;
            }
            s->ub = b->ub;
        }
    }
    s->ub = e[-1].ub; ++s;
    nSpans = s - span;
}

void doGen(Go *g, State *s, uchar *bm, uchar m){
Span *b = g->span, *e = &b[g->nSpans];
uint lb = 0;
for(; b < e; ++b){
    if(b->to == s)
        for(; lb < b->ub; ++lb) bm[lb] |= m;
    lb = b->ub;
}
}

void prt(ostream& o, Go *g, State *s){
Span *b = g->span, *e = &b[g->nSpans];
uint lb = 0;
for(; b < e; ++b){
    if(b->to == s)
        printSpan(o, lb, b->ub);
    lb = b->ub;
}
}

bool matches(Go *g1, State *s1, Go *g2, State *s2){
Span *b1 = g1->span, *e1 = &b1[g1->nSpans];
uint lb1 = 0;
Span *b2 = g2->span, *e2 = &b2[g2->nSpans];
uint lb2 = 0;
for(;;){
    for(; b1 < e1 && b1->to != s1; ++b1) lb1 = b1->ub;
    for(; b2 < e2 && b2->to != s2; ++b2) lb2 = b2->ub;
    if(b1 == e1) return b2 == e2;
    if(b2 == e2) return false;
    if(lb1 != lb2 || b1->ub != b2->ub) return false;
    ++b1; ++b2;
}
}

class BitMap {
public:
static BitMap   *first;
BitMap          *next;
Go                      *go;
State           *on;
uint            i;
uchar           m;
public:
static BitMap *find(Go*, State*);
static BitMap *find(State*);
static void gen(ostream&, uint, uint);
static void stats();
BitMap(Go*, State*);
};

BitMap *BitMap::first = NULL;

BitMap::BitMap(Go *g, State *x) : go(g), on(x), next(first) {
first = this;
}

BitMap *BitMap::find(Go *g, State *x){
for(BitMap *b = first; b; b = b->next){
    if(matches(b->go, b->on, g, x))
            return b;
    }
    return new BitMap(g, x);
}

BitMap *BitMap::find(State *x){
    for(BitMap *b = first; b; b = b->next){
        if(b->on == x)
            return b;
    }
    return NULL;
}

void BitMap::gen(ostream &o, uint lb, uint ub){
    BitMap *b = first;
    if(b){
        o << "\tstatic unsigned char yybm[] = {";
        uint n = ub - lb;
        uchar *bm = new uchar[n];
        memset(bm, 0, n);
        for(uint i = 0; b; i += n){
            for(uchar m = 0x80; b && m; b = b->next, m >>= 1){
                b->i = i; b->m = m;
                doGen(b->go, b->on, &bm[-lb], m);
            }
            for(uint j = 0; j < n; ++j){
                if(j%8 == 0) o << "\n\t";
                o << setw(3) << (uint) bm[j] << ", ";
            }
        }
        o << "\n\t};\n";
    }
}

void BitMap::stats(){
    uint n = 0;
    for(BitMap *b = first; b; b = b->next){
prt(cerr, b->go, b->on); cerr << endl;
         ++n;
    }
    cerr << n << " bitmaps\n";
    first = NULL;
}

void genGoTo(ostream &o, State *to){
    o  << "\tgoto yy" << to->label << ";\n";
}

void genIf(ostream &o, char *cmp, uint v){
    o << "\tif(yych " << cmp << " '";
    prtCh(o, (uchar)v);
    o << "')";
}

void indent(ostream &o, uint i){
    while(i-- > 0)
        o << "\t";
}

static void need(ostream &o, uint n){
    if(n == 1)
        o << "\tif(YYLIMIT == YYCURSOR) YYFILL(1);\n";
    else
        o << "\tif((YYLIMIT - YYCURSOR) < " << n << ") YYFILL(" << n << ");\n";
    o << "\tyych = *YYCURSOR;\n";
}

void Match::emit(ostream &o){
    if(state->link){
        o << "\t++YYCURSOR;\n";
        need(o, state->depth);
    } else {
        o << "\tyych = *++YYCURSOR;\n";
    }
}

void Enter::emit(ostream &o){
    if(state->link){
        o << "\t++YYCURSOR;\n";
        o << "yy" << label << ":\n";
        need(o, state->depth);
    } else {
        o << "\tyych = *++YYCURSOR;\n";
        o << "yy" << label << ":\n";
    }
}

void Save::emit(ostream &o){
    o << "\tyyaccept = " << selector << ";\n";
    if(state->link){
        o << "\tYYMARKER = ++YYCURSOR;\n";
        need(o, state->depth);
    } else {
        o << "\tyych = *(YYMARKER = ++YYCURSOR);\n";
    }
}

Move::Move(State *s) : Action(s) {
    ;
}

void Move::emit(ostream &o){
    (void)o;
}

Accept::Accept(State *x, uint n, uint *s, State **r)
    : Action(x), nRules(n), saves(s), rules(r){
    ;
}

void Accept::emit(ostream &o){
    bool first = true;
    for(uint i = 0; i < nRules; ++i)
        if(saves[i] != ~0){
            if(first){
                first = false;
                o << "\tYYCURSOR = YYMARKER;\n";
                o << "\tswitch(yyaccept){\n";
            }
            o << "\tcase " << saves[i] << ":";
            genGoTo(o, rules[i]);
        }
    if(!first)
        o << "\t}\n";
}

Rule::Rule(State *s, RuleOp *r) : Action(s), rule(r) {
    ;
}

void Rule::emit(ostream &o){
    uint back = rule->ctx->fixedLength();
    if(back != ~0 && back > 0)
        o << "\tYYCURSOR -= " << back << ";";
    o << "\n#line " << rule->code->line
      << "\n\t" << rule->code->text << "\n";
}

void doLinear(ostream &o, uint i, Span *s, uint n, State *next){
    for(;;){
        State *bg = s[0].to;
        while(n >= 3 && s[2].to == bg && (s[1].ub - s[0].ub) == 1){
            if(s[1].to == next && n == 3){
                indent(o, i); genIf(o, "!=", s[0].ub); genGoTo(o, bg);
                return;
            } else {
                indent(o, i); genIf(o, "==", s[0].ub); genGoTo(o, s[1].to);
            }
            n -= 2; s += 2;
        }
        if(n == 1){
            if(bg != next){
                indent(o, i); genGoTo(o, s[0].to);
            }
            return;
        } else if(n == 2 && bg == next){
            indent(o, i); genIf(o, ">=", s[0].ub); genGoTo(o, s[1].to);
            return;
        } else {
            indent(o, i); genIf(o, "<=", s[0].ub - 1); genGoTo(o, bg);
            n -= 1; s += 1;
        }
    }
}

void Go::genLinear(ostream &o, State *next){
    doLinear(o, 0, span, nSpans, next);
}

void genCases(ostream &o, uint lb, Span *s){
    if(lb < s->ub){
        for(;;){
            o << "\tcase '"; prtCh(o, (uchar)lb); o << "':";
            if(++lb == s->ub)
                break;
            o << "\n";
        }
    }
}

void Go::genSwitch(ostream &o, State *next){
    if(nSpans <= 2){
        genLinear(o, next);
    } else {
        State *def = span[nSpans-1].to;
        Span **sP = new Span*[nSpans-1], **r, **s, **t;

        t = &sP[0];
        for(uint i = 0; i < nSpans; ++i)
            if(span[i].to != def)
                *(t++) = &span[i];

        o << "\tswitch(yych){\n";
        while(t != &sP[0]){
            r = s = &sP[0];
            if(*s == &span[0])
                genCases(o, 0, *s);
            else
                genCases(o, (*s)[-1].ub, *s);
            State *to = (*s)->to;
            while(++s < t){
                if((*s)->to == to)
                    genCases(o, (*s)[-1].ub, *s);
                else
                    *(r++) = *s;
            }
            genGoTo(o, to);
            t = r;
        }
        o << "\tdefault:";
        genGoTo(o, def);