Logo Search packages:      
Sourcecode: yasm version File versions  Download package

actions.c

#include <time.h>
#include <string.h>
#include <stdio.h>

#include "tools/re2c/globals.h"
#include "tools/re2c/parse.h"
#include "tools/re2c/dfa.h"

static Symbol *first = NULL;

void
Symbol_init(Symbol *r, const SubStr *str)
{
    r->next = first;
    Str_init(&r->name, str);
    r->re = NULL;
    first = r;
}

Symbol *
Symbol_find(const SubStr *str)
{
    Symbol *sym;
    for(sym = first; sym; sym = sym->next)
      if(SubStr_eq(&sym->name, str)) return sym;
    return Symbol_new(str);
}

/*
void showIns(FILE *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";
}
*/

static unsigned int
AltOp_fixedLength(RegExp *r)
{
    unsigned int l1 = RegExp_fixedLength(r->d.AltCatOp.exp1);
    /* XXX? Should be exp2? */
    unsigned int l2 = RegExp_fixedLength(r->d.AltCatOp.exp1);
    if(l1 != l2 || l1 == ~0u)
      return ~0;
    return l1;
}

static unsigned int
CatOp_fixedLength(RegExp *r)
{
    unsigned int l1, l2;
    if((l1 = RegExp_fixedLength(r->d.AltCatOp.exp1)) != ~0u )
        if((l2 = RegExp_fixedLength(r->d.AltCatOp.exp2)) != ~0u)
          return l1+l2;
    return ~0;
}

unsigned int
RegExp_fixedLength(RegExp *r)
{
    switch (r->type) {
      case NULLOP:
          return 0;
      case MATCHOP:
          return 1;
      case ALTOP:
          return AltOp_fixedLength(r);
      case CATOP:
          return CatOp_fixedLength(r);
      default:
          return ~0;
    }
    return ~0;
}

void
RegExp_calcSize(RegExp *re, Char *rep)
{
    Range *r;
    unsigned int c;

    switch (re->type) {
      case NULLOP:
          re->size = 0;
          break;
      case MATCHOP:
          re->size = 1;
          for(r = re->d.match; r; r = r->next)
            for(c = r->lb; c < r->ub; ++c)
                if(rep[c] == c)
                  ++re->size;
          break;
      case RULEOP:
          RegExp_calcSize(re->d.RuleOp.exp, rep);
          RegExp_calcSize(re->d.RuleOp.ctx, rep);
          re->size = re->d.RuleOp.exp->size + re->d.RuleOp.ctx->size + 1;
          break;
      case ALTOP:
          RegExp_calcSize(re->d.AltCatOp.exp1, rep);
          RegExp_calcSize(re->d.AltCatOp.exp2, rep);
          re->size = re->d.AltCatOp.exp1->size
                   + re->d.AltCatOp.exp2->size + 2;
          break;
      case CATOP:
          RegExp_calcSize(re->d.AltCatOp.exp1, rep);
          RegExp_calcSize(re->d.AltCatOp.exp2, rep);
          re->size = re->d.AltCatOp.exp1->size + re->d.AltCatOp.exp2->size;
          break;
      case CLOSEOP:
          RegExp_calcSize(re->d.exp, rep);
          re->size = re->d.exp->size + 1;
          break;
    }
}

static void
MatchOp_compile(RegExp *re, Char *rep, Ins *i)
{
    Ins *j;
    unsigned int bump;
    Range *r;
    unsigned int c;

    i->i.tag = CHAR;
    i->i.link = &i[re->size];
    j = &i[1];
    bump = re->size;
    for(r = re->d.match; r; r = r->next){
      for(c = r->lb; c < r->ub; ++c){
          if(rep[c] == c){
            j->c.value = c;
            j->c.bump = --bump;
            j++;
          }
      }
    }
}

static void
AltOp_compile(RegExp *re, Char *rep, Ins *i){
    Ins *j;

    i->i.tag = FORK;
    j = &i[re->d.AltCatOp.exp1->size + 1];
    i->i.link = &j[1];
    RegExp_compile(re->d.AltCatOp.exp1, rep, &i[1]);
    j->i.tag = GOTO;
    j->i.link = &j[re->d.AltCatOp.exp2->size + 1];
    RegExp_compile(re->d.AltCatOp.exp2, rep, &j[1]);
}

void
RegExp_compile(RegExp *re, Char *rep, Ins *i)
{
    switch (re->type) {
      case NULLOP:
          break;
      case MATCHOP:
          MatchOp_compile(re, rep, i);
          break;
      case RULEOP:
          re->d.RuleOp.ins = i;
          RegExp_compile(re->d.RuleOp.exp, rep, &i[0]);
          i += re->d.RuleOp.exp->size;
          RegExp_compile(re->d.RuleOp.ctx, rep, &i[0]);
          i += re->d.RuleOp.ctx->size;
          i->i.tag = TERM;
          i->i.link = re;
          break;
      case ALTOP:
          AltOp_compile(re, rep, i);
          break;
      case CATOP:
          RegExp_compile(re->d.AltCatOp.exp1, rep, &i[0]);
          RegExp_compile(re->d.AltCatOp.exp2, rep,
                     &i[re->d.AltCatOp.exp1->size]);
          break;
      case CLOSEOP:
          RegExp_compile(re->d.exp, rep, &i[0]);
          i += re->d.exp->size;
          i->i.tag = FORK;
          i->i.link = i - re->d.exp->size;
          break;
    }
}

static void
MatchOp_split(RegExp *re, CharSet *s)
{
    Range *r;
    unsigned int c;

    for(r = re->d.match; r; r = r->next){
      for(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;
}

void
RegExp_split(RegExp *re, CharSet *s)
{
    switch (re->type) {
      case NULLOP:
          break;
      case MATCHOP:
          MatchOp_split(re, s);
          break;
      case RULEOP:
          RegExp_split(re->d.RuleOp.exp, s);
          RegExp_split(re->d.RuleOp.ctx, s);
          break;
      case ALTOP:
          /* FALLTHROUGH */
      case CATOP:
          RegExp_split(re->d.AltCatOp.exp1, s);
          RegExp_split(re->d.AltCatOp.exp2, s);
          break;
      case CLOSEOP:
          RegExp_split(re->d.exp, s);
          break;
    }
}

void
RegExp_display(RegExp *re, FILE *o)
{
    switch (re->type) {
      case NULLOP:
          fputc('_', o);
          break;
      case MATCHOP:
          Range_out(o, re->d.match);
          break;
      case RULEOP:
          RegExp_display(re->d.RuleOp.exp, o);
          fputc('/', o);
          RegExp_display(re->d.RuleOp.ctx, o);
          fputc(';', o);
          break;
      case ALTOP:
          RegExp_display(re->d.AltCatOp.exp1, o);
          fputc('|', o);
          RegExp_display(re->d.AltCatOp.exp2, o);
          break;
      case CATOP:
          RegExp_display(re->d.AltCatOp.exp1, o);
          RegExp_display(re->d.AltCatOp.exp2, o);
          break;
      case CLOSEOP:
          RegExp_display(re->d.exp, o);
          fputc('+', o);
          break;
    }
}

void
Range_out(FILE *o, const Range *r)
{
    if(!r)
      return;

    if((r->ub - r->lb) == 1){
      prtCh(o, r->lb);
    } else {
      prtCh(o, r->lb);
      fputc('-', o);
      prtCh(o, r->ub-1);
    }
    Range_out(o, r->next);
}

static Range *doUnion(Range *r1, Range *r2){
    Range *r, **rP = &r;
    for(;;){
      Range *s;
      if(r1->lb <= r2->lb){
          s = Range_new_copy(r1);
      } else {
          s = Range_new_copy(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)){
                unsigned int 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)){
                unsigned int 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;
}

static Range *doDiff(Range *r1, Range *r2){
    Range *r, *s, **rP = &r;
    for(; r1; r1 = r1->next){
      unsigned int 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 = Range_new(lb, r2->lb);
            rP = &s->next;
          }
          if((lb = r2->ub) >= r1->ub)
            goto noMore;
      }
      *rP = s = Range_new(lb, r1->ub);
      rP = &s->next;
    noMore:;
    }
    *rP = NULL;
    return r;
}

static RegExp *merge(RegExp *m1, RegExp *m2){
    if(!m1)
      return m2;
    if(!m2)
      return m1;
    return RegExp_new_MatchOp(doUnion(m1->d.match, m2->d.match));
}

RegExp *mkDiff(RegExp *e1, RegExp *e2){
    RegExp *m1, *m2;
    Range *r;
    if(!(m1 = RegExp_isA(e1, MATCHOP)))
      return NULL;
    if(!(m2 = RegExp_isA(e2, MATCHOP)))
      return NULL;
    r = doDiff(m1->d.match, m2->d.match);
    return r? RegExp_new_MatchOp(r) : RegExp_new_NullOp();
}

static RegExp *doAlt(RegExp *e1, RegExp *e2){
    if(!e1)
      return e2;
    if(!e2)
      return e1;
    return RegExp_new_AltOp(e1, e2);
}

RegExp *mkAlt(RegExp *e1, RegExp *e2){
    RegExp *a;
    RegExp *m1, *m2;
    if((a = RegExp_isA(e1, ALTOP))){
      if((m1 = RegExp_isA(a->d.AltCatOp.exp1, MATCHOP)))
          e1 = a->d.AltCatOp.exp2;
    } else if((m1 = RegExp_isA(e1, MATCHOP))){
          e1 = NULL;
    }
    if((a = RegExp_isA(e2, ALTOP))){
      if((m2 = RegExp_isA(a->d.AltCatOp.exp1, MATCHOP)))
          e2 = a->d.AltCatOp.exp2;
    } else if((m2 = RegExp_isA(e2, MATCHOP))){
          e2 = NULL;
    }
    return doAlt(merge(m1, m2), doAlt(e1, e2));
}

static unsigned char unescape(SubStr *s){
    unsigned char c;
    unsigned char v;
    s->len--;
    if((c = *s->str++) != '\\' || s->len == 0)
      return xlat[c];
    s->len--;
    switch(c = *s->str++){
    case 'n':
      return xlat['\n'];
    case 't':
      return xlat['\t'];
    case 'v':
      return xlat['\v'];
    case 'b':
      return xlat['\b'];
    case 'r':
      return xlat['\r'];
    case 'f':
      return xlat['\f'];
    case 'a':
      return xlat['\a'];
    case '0': case '1': case '2': case '3':
    case '4': case '5': case '6': case '7': {
      v = c - '0';
      for(; s->len != 0 && '0' <= (c = *s->str) && c <= '7'; s->len--, s->str++)
          v = v*8 + (c - '0');
      return v;
    } default:
      return xlat[c];
    }
}

static Range *getRange(SubStr *s){
    unsigned char lb = unescape(s), ub;
    if(s->len < 2 || *s->str != '-'){
      ub = lb;
    } else {
      s->len--; s->str++;
      ub = unescape(s);
      if(ub < lb){
          unsigned char tmp;
          tmp = lb; lb = ub; ub = tmp;
      }
    }
    return Range_new(lb, ub+1);
}

static RegExp *matchChar(unsigned int c){
    return RegExp_new_MatchOp(Range_new(c, c+1));
}

RegExp *strToRE(SubStr s){
    RegExp *re;
    s.len -= 2; s.str += 1;
    if(s.len == 0)
      return RegExp_new_NullOp();
    re = matchChar(unescape(&s));
    while(s.len > 0)
      re = RegExp_new_CatOp(re, matchChar(unescape(&s)));
    return re;
}

RegExp *ranToRE(SubStr s){
    Range *r;
    s.len -= 2; s.str += 1;
    if(s.len == 0)
      return RegExp_new_NullOp();
    r = getRange(&s);
    while(s.len > 0)
      r = doUnion(r, getRange(&s));
    return RegExp_new_MatchOp(r);
}

RegExp *
RegExp_new_RuleOp(RegExp *e, RegExp *c, Token *t, unsigned int a)
{
    RegExp *r = malloc(sizeof(RegExp));
    r->type = RULEOP;
    r->d.RuleOp.exp = e;
    r->d.RuleOp.ctx = c;
    r->d.RuleOp.ins = NULL;
    r->d.RuleOp.accept = a;
    r->d.RuleOp.code = t;
    return r;
}

static void optimize(Ins *i){
    while(!isMarked(i)){
      mark(i);
      if(i->i.tag == CHAR){
          i = (Ins*) i->i.link;
      } else if(i->i.tag == GOTO || i->i.tag == FORK){
          Ins *target = (Ins*) i->i.link;
          optimize(target);
          if(target->i.tag == GOTO)
            i->i.link = target->i.link == target? i : target;
          if(i->i.tag == FORK){
            Ins *follow = (Ins*) &i[1];
            optimize(follow);
            if(follow->i.tag == GOTO && follow->i.link == follow){
                i->i.tag = GOTO;
            } else if(i->i.link == i){
                i->i.tag = GOTO;
                i->i.link = follow;
            }
          }
          return;
      } else {
          ++i;
      }
    }
}

void genCode(FILE *o, RegExp *re){
    CharSet cs;
    unsigned int j;
    Char rep[nChars];
    Ins *ins, *eoi;
    DFA *dfa;

    memset(&cs, 0, sizeof(cs));
    for(j = 0; j < nChars; ++j){
      cs.rep[j] = &cs.ptn[0];
      cs.ptn[j].nxt = &cs.ptn[j+1];
    }
    cs.freeHead = &cs.ptn[1];
    *(cs.freeTail = &cs.ptn[nChars-1].nxt) = NULL;
    cs.ptn[0].card = nChars;
    cs.ptn[0].nxt = NULL;
    RegExp_split(re, &cs);
/*
    for(unsigned int k = 0; k < nChars;){
      for(j = k; ++k < nChars && cs.rep[k] == cs.rep[j];);
      printSpan(cerr, j, k);
      cerr << "\t" << cs.rep[j] - &cs.ptn[0] << endl;
    }
*/
    for(j = 0; j < nChars; ++j){
      if(!cs.rep[j]->nxt)
          cs.rep[j]->nxt = &cs.ptn[j];
      rep[j] = (Char) (cs.rep[j]->nxt - &cs.ptn[0]);
    }

    RegExp_calcSize(re, rep);
    ins = malloc(sizeof(Ins)*(re->size+1));
    memset(ins, 0, (re->size+1)*sizeof(Ins));
    RegExp_compile(re, rep, ins);
    eoi = &ins[re->size];
    eoi->i.tag = GOTO;
    eoi->i.link = eoi;

    optimize(ins);
    for(j = 0; j < re->size;){
      unmark(&ins[j]);
      if(ins[j].i.tag == CHAR){
          j = (Ins*) ins[j].i.link - ins;
      } else {
          j++;
      }
    }

    dfa = DFA_new(ins, re->size, 0, 256, rep);
    DFA_emit(dfa, o);
    DFA_delete(dfa);
    free(ins);
}

Generated by  Doxygen 1.6.0   Back to index