home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Add-Ons / MPW / MPW re2c 1.1 / code.cc < prev    next >
Encoding:
Text File  |  1995-06-01  |  13.2 KB  |  671 lines  |  [TEXT/MPS ]
  1. // $Log: code.cc,v $
  2. //Revision 1.1  1994/04/08  15:27:59  peter
  3. //Initial revision
  4. //
  5.  
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <ctype.h>
  9. #include <iomanip.h>
  10. #include "substr.h"
  11. #include "globals.h"
  12. #include "dfa.h"
  13.  
  14. // there must be at least one span in list;  all spans must cover
  15. // same range
  16.  
  17. void Go::compact(){
  18.     // arrange so that adjacent spans have different targets
  19.     uint i = 0;
  20.     for(uint j = 1; j < nSpans; ++j){
  21.     if(span[j].to != span[i].to){
  22.         ++i; span[i].to = span[j].to;
  23.     }
  24.     span[i].ub = span[j].ub;
  25.     }
  26.     nSpans = i + 1;
  27. }
  28.  
  29. void Go::unmap(Go *base, State *x){
  30.     Span *s = span, *b = base->span, *e = &b[base->nSpans];
  31.     uint lb = 0;
  32.     s->ub = 0;
  33.     s->to = NULL;
  34.     for(; b != e; ++b){
  35.     if(b->to == x){
  36.         if((s->ub - lb) > 1)
  37.         s->ub = b->ub;
  38.     } else {
  39.         if(b->to != s->to){
  40.         if(s->ub){
  41.             lb = s->ub; ++s;
  42.         }
  43.         s->to = b->to;
  44.         }
  45.         s->ub = b->ub;
  46.     }
  47.     }
  48.     s->ub = e[-1].ub; ++s;
  49.     nSpans = s - span;
  50. }
  51.  
  52. void doGen(Go *g, State *s, uchar *bm, uchar m){
  53. Span *b = g->span, *e = &b[g->nSpans];
  54. uint lb = 0;
  55. for(; b < e; ++b){
  56.     if(b->to == s)
  57.     for(; lb < b->ub; ++lb) bm[lb] |= m;
  58.     lb = b->ub;
  59. }
  60. }
  61.  
  62. void prt(ostream& o, Go *g, State *s){
  63. Span *b = g->span, *e = &b[g->nSpans];
  64. uint lb = 0;
  65. for(; b < e; ++b){
  66.     if(b->to == s)
  67.     printSpan(o, lb, b->ub);
  68.     lb = b->ub;
  69. }
  70. }
  71.  
  72. bool matches(Go *g1, State *s1, Go *g2, State *s2){
  73. Span *b1 = g1->span, *e1 = &b1[g1->nSpans];
  74. uint lb1 = 0;
  75. Span *b2 = g2->span, *e2 = &b2[g2->nSpans];
  76. uint lb2 = 0;
  77. for(;;){
  78.     for(; b1 < e1 && b1->to != s1; ++b1) lb1 = b1->ub;
  79.     for(; b2 < e2 && b2->to != s2; ++b2) lb2 = b2->ub;
  80.     if(b1 == e1) return b2 == e2;
  81.     if(b2 == e2) return false;
  82.     if(lb1 != lb2 || b1->ub != b2->ub) return false;
  83.     ++b1; ++b2;
  84. }
  85. }
  86.  
  87. class BitMap {
  88. public:
  89. static BitMap    *first;
  90. BitMap        *next;
  91. Go            *go;
  92. State        *on;
  93. uint        i;
  94. uchar        m;
  95. public:
  96. static BitMap *find(Go*, State*);
  97. static BitMap *find(State*);
  98. static void gen(ostream&, uint, uint);
  99. static void stats();
  100. BitMap(Go*, State*);
  101. };
  102.  
  103. BitMap *BitMap::first = NULL;
  104.  
  105. BitMap::BitMap(Go *g, State *x) : go(g), on(x), next(first) {
  106. first = this;
  107. }
  108.  
  109. BitMap *BitMap::find(Go *g, State *x){
  110. for(BitMap *b = first; b; b = b->next){
  111.     if(matches(b->go, b->on, g, x))
  112.         return b;
  113.     }
  114.     return new BitMap(g, x);
  115. }
  116.  
  117. BitMap *BitMap::find(State *x){
  118.     for(BitMap *b = first; b; b = b->next){
  119.     if(b->on == x)
  120.         return b;
  121.     }
  122.     return NULL;
  123. }
  124.  
  125. void BitMap::gen(ostream &o, uint lb, uint ub){
  126.     BitMap *b = first;
  127.     if(b){
  128.     o << "\tstatic unsigned char yybm[] = {";
  129.     uint n = ub - lb;
  130.     uchar *bm = new uchar[n];
  131.     memset(bm, 0, n);
  132.     for(uint i = 0; b; i += n){
  133.         for(uchar m = 0x80; b && m; b = b->next, m >>= 1){
  134.         b->i = i; b->m = m;
  135.         doGen(b->go, b->on, &bm[-lb], m);
  136.         }
  137.         for(uint j = 0; j < n; ++j){
  138.         if(j%8 == 0) o << "\n\t";
  139.         o << setw(3) << (uint) bm[j] << ", ";
  140.         }
  141.     }
  142.     o << "\n\t};\n";
  143.     }
  144. }
  145.  
  146. void BitMap::stats(){
  147.     uint n = 0;
  148.     for(BitMap *b = first; b; b = b->next){
  149. prt(cerr, b->go, b->on); cerr << endl;
  150.      ++n;
  151.     }
  152.     cerr << n << " bitmaps\n";
  153.     first = NULL;
  154. }
  155.  
  156. void genGoTo(ostream &o, State *to){
  157.     o  << "\tgoto yy" << to->label << ";\n";
  158. }
  159.  
  160. void genIf(ostream &o, char *cmp, uint v){
  161.     o << "\tif(yych " << cmp << " '";
  162.     prtCh(o, v);
  163.     o << "')";
  164. }
  165.  
  166. void indent(ostream &o, uint i){
  167.     while(i-- > 0)
  168.     o << "\t";
  169. }
  170.  
  171. static void need(ostream &o, uint n){
  172.     if(n == 1)
  173.     o << "\tif(YYLIMIT == YYCURSOR) YYFILL(1);\n";
  174.     else
  175.     o << "\tif((YYLIMIT - YYCURSOR) < " << n << ") YYFILL(" << n << ");\n";
  176.     o << "\tyych = *YYCURSOR;\n";
  177. }
  178.  
  179. void Match::emit(ostream &o){
  180.     if(state->link){
  181.     o << "\t++YYCURSOR;\n";
  182.     need(o, state->depth);
  183.     } else {
  184.     o << "\tyych = *++YYCURSOR;\n";
  185.     }
  186. }
  187.  
  188. void Enter::emit(ostream &o){
  189.     if(state->link){
  190.     o << "\t++YYCURSOR;\n";
  191.     o << "yy" << label << ":\n";
  192.     need(o, state->depth);
  193.     } else {
  194.     o << "\tyych = *++YYCURSOR;\n";
  195.     o << "yy" << label << ":\n";
  196.     }
  197. }
  198.  
  199. void Save::emit(ostream &o){
  200.     o << "\tyyaccept = " << selector << ";\n";
  201.     if(state->link){
  202.     o << "\tYYMARKER = ++YYCURSOR;\n";
  203.     need(o, state->depth);
  204.     } else {
  205.     o << "\tyych = *(YYMARKER = ++YYCURSOR);\n";
  206.     }
  207. }
  208.  
  209. Move::Move(State *s) : Action(s) {
  210.     ;
  211. }
  212.  
  213. void Move::emit(ostream &o){
  214.     ;
  215. }
  216.  
  217. Accept::Accept(State *x, uint n, uint *s, State **r)
  218.     : Action(x), nRules(n), saves(s), rules(r){
  219.     ;
  220. }
  221.  
  222. void Accept::emit(ostream &o){
  223.     bool first = true;
  224.     for(uint i = 0; i < nRules; ++i)
  225.     if(saves[i] != ~0){
  226.         if(first){
  227.         first = false;
  228.         o << "\tYYCURSOR = YYMARKER;\n";
  229.         o << "\tswitch(yyaccept){\n";
  230.         }
  231.         o << "\tcase " << saves[i] << ":";
  232.         genGoTo(o, rules[i]);
  233.     }
  234.     if(!first)
  235.     o << "\t}\n";
  236. }
  237.  
  238. Rule::Rule(State *s, RuleOp *r) : Action(s), rule(r) {
  239.     ;
  240. }
  241.  
  242. void Rule::emit(ostream &o){
  243.     uint back = rule->ctx->fixedLength();
  244.     if(back != ~0 && back > 0)
  245.     o << "\tYYCURSOR -= " << back << ";";
  246.     o << "\n#line " << rule->code->line
  247.       << "\n\t" << rule->code->text << "\n";
  248. }
  249.  
  250. void doLinear(ostream &o, uint i, Span *s, uint n, State *next){
  251.     for(;;){
  252.     State *bg = s[0].to;
  253.     while(n >= 3 && s[2].to == bg && (s[1].ub - s[0].ub) == 1){
  254.         if(s[1].to == next && n == 3){
  255.         indent(o, i); genIf(o, "!=", s[0].ub); genGoTo(o, bg);
  256.         return;
  257.         } else {
  258.         indent(o, i); genIf(o, "==", s[0].ub); genGoTo(o, s[1].to);
  259.         }
  260.         n -= 2; s += 2;
  261.     }
  262.     if(n == 1){
  263.         if(bg != next){
  264.         indent(o, i); genGoTo(o, s[0].to);
  265.         }
  266.         return;
  267.     } else if(n == 2 && bg == next){
  268.         indent(o, i); genIf(o, ">=", s[0].ub); genGoTo(o, s[1].to);
  269.         return;
  270.     } else {
  271.         indent(o, i); genIf(o, "<=", s[0].ub - 1); genGoTo(o, bg);
  272.         n -= 1; s += 1;
  273.     }
  274.     }
  275. }
  276.  
  277. void Go::genLinear(ostream &o, State *next){
  278.     doLinear(o, 0, span, nSpans, next);
  279. }
  280.  
  281. void genCases(ostream &o, uint lb, Span *s){
  282.     if(lb < s->ub){
  283.     for(;;){
  284.         o << "\tcase '"; prtCh(o, lb); o << "':";
  285.         if(++lb == s->ub)
  286.         break;
  287.         o << "\n";
  288.     }
  289.     }
  290. }
  291.  
  292. void Go::genSwitch(ostream &o, State *next){
  293.     if(nSpans <= 2){
  294.     genLinear(o, next);
  295.     } else {
  296.     State *def = span[nSpans-1].to;
  297.     Span **sP = new Span*[nSpans-1], **r, **s, **t;
  298.  
  299.     t = &sP[0];
  300.     for(uint i = 0; i < nSpans; ++i)
  301.         if(span[i].to != def)
  302.         *(t++) = &span[i];
  303.  
  304.     o << "\tswitch(yych){\n";
  305.     while(t != &sP[0]){
  306.         r = s = &sP[0];
  307.         if(*s == &span[0])
  308.         genCases(o, 0, *s);
  309.         else
  310.         genCases(o, (*s)[-1].ub, *s);
  311.         State *to = (*s)->to;
  312.         while(++s < t){
  313.         if((*s)->to == to)
  314.             genCases(o, (*s)[-1].ub, *s);
  315.         else
  316.             *(r++) = *s;
  317.         }
  318.         genGoTo(o, to);
  319.         t = r;
  320.     }
  321.     o << "\tdefault:";
  322.     genGoTo(o, def);
  323.     o << "\t}\n";
  324.  
  325.     delete sP;
  326.     }
  327. }
  328.  
  329. void doBinary(ostream &o, uint i, Span *s, uint n, State *next){
  330.     if(n <= 4){
  331.     doLinear(o, i, s, n, next);
  332.     } else {
  333.     uint h = n/2;
  334.     indent(o, i); genIf(o, "<=", s[h-1].ub - 1); o << "{\n";
  335.     doBinary(o, i+1, &s[0], h, next);
  336.     indent(o, i); o << "\t} else {\n";
  337.     doBinary(o, i+1, &s[h], n - h, next);
  338.     indent(o, i); o << "\t}\n";
  339.     }
  340. }
  341.  
  342. void Go::genBinary(ostream &o, State *next){
  343.     doBinary(o, 0, span, nSpans, next);
  344. }
  345.  
  346. void Go::genBase(ostream &o, State *next){
  347.     if(nSpans == 0)
  348.     return;
  349.     if(!sFlag){
  350.     genSwitch(o, next);
  351.     return;
  352.     }
  353.     if(nSpans > 8){
  354.     Span *bot = &span[0], *top = &span[nSpans-1];
  355.     uint util;
  356.     if(bot[0].to == top[0].to){
  357.         util = (top[-1].ub - bot[0].ub)/(nSpans - 2);
  358.     } else {
  359.         if(bot[0].ub > (top[0].ub - top[-1].ub)){
  360.         util = (top[0].ub - bot[0].ub)/(nSpans - 1);
  361.         } else {
  362.         util = top[-1].ub/(nSpans - 1);
  363.         }
  364.     }
  365.     if(util <= 2){
  366.         genSwitch(o, next);
  367.         return;
  368.     }
  369.     }
  370.     if(nSpans > 5){
  371.     genBinary(o, next);
  372.     } else {
  373.     genLinear(o, next);
  374.     }
  375. }
  376.  
  377. void Go::genGoto(ostream &o, State *next){
  378.     if(bFlag){
  379.     for(uint i = 0; i < nSpans; ++i){
  380.         State *to = span[i].to;
  381.         if(to && to->isBase){
  382.         BitMap *b = BitMap::find(to);
  383.         if(b && matches(b->go, b->on, this, to)){
  384.             Go go;
  385.             go.span = new Span[nSpans];
  386.             go.unmap(this, to);
  387.             o << "\tif(yybm[" << b->i << "+yych] & " << (uint) b->m << ")";
  388.             genGoTo(o, to);
  389.             go.genBase(o, next);
  390.             delete go.span;
  391.             return;
  392.         }
  393.         }
  394.     }
  395.     }
  396.     genBase(o, next);
  397. }
  398.  
  399. void State::emit(ostream &o){
  400.     o << "yy" << label << ":";
  401.     action->emit(o);
  402. }
  403.  
  404. uint merge(Span *x0, State *fg, State *bg){
  405.     Span *x = x0, *f = fg->go.span, *b = bg->go.span;
  406.     uint nf = fg->go.nSpans, nb = bg->go.nSpans;
  407.     State *prev = NULL, *to;
  408.     // NB: we assume both spans are for same range
  409.     for(;;){
  410.     if(f->ub == b->ub){
  411.         to = f->to == b->to? bg : f->to;
  412.         if(to == prev){
  413.         --x;
  414.         } else {
  415.         x->to = prev = to;
  416.         }
  417.         x->ub = f->ub;
  418.         ++x; ++f; --nf; ++b; --nb;
  419.         if(nf == 0 && nb == 0)
  420.         return x - x0;
  421.     }
  422.     while(f->ub < b->ub){
  423.         to = f->to == b->to? bg : f->to;
  424.         if(to == prev){
  425.         --x;
  426.         } else {
  427.         x->to = prev = to;
  428.         }
  429.         x->ub = f->ub;
  430.         ++x; ++f; --nf;
  431.     }
  432.     while(b->ub < f->ub){
  433.         to = b->to == f->to? bg : f->to;
  434.         if(to == prev){
  435.         --x;
  436.         } else {
  437.         x->to = prev = to;
  438.         }
  439.         x->ub = b->ub;
  440.         ++x; ++b; --nb;
  441.     }
  442.     }
  443. }
  444.  
  445. const uint cInfinity = ~0;
  446.  
  447. class SCC {
  448. public:
  449.     State    **top, **stk;
  450. public:
  451.     SCC(uint);
  452.     ~SCC();
  453.     void traverse(State*);
  454. };
  455.  
  456. SCC::SCC(uint size){
  457.     top = stk = new State*[size];
  458. }
  459.  
  460. SCC::~SCC(){
  461.     delete stk;
  462. }
  463.  
  464. void SCC::traverse(State *x){
  465.     *top = x;
  466.     uint k = ++top - stk;
  467.     x->depth = k;
  468.     for(uint i = 0; i < x->go.nSpans; ++i){
  469.     State *y = x->go.span[i].to;
  470.     if(y){
  471.         if(y->depth == 0)
  472.         traverse(y);
  473.         if(y->depth < x->depth)
  474.         x->depth = y->depth;
  475.     }
  476.     }
  477.     if(x->depth == k)
  478.     do {
  479.         (*--top)->depth = cInfinity;
  480.         (*top)->link = x;
  481.     } while(*top != x);
  482. }
  483.  
  484. uint maxDist(State *s){
  485.     uint mm = 0;
  486.     for(uint i = 0; i < s->go.nSpans; ++i){
  487.     State *t = s->go.span[i].to;
  488.     if(t){
  489.         uint m = 1;
  490.         if(!t->link)
  491.         m += maxDist(t);
  492.         if(m > mm)
  493.         mm = m;
  494.     }
  495.     }
  496.     return mm;
  497. }
  498.  
  499. void calcDepth(State *head){
  500.     State *t;
  501.     for(State *s = head; s; s = s->next){
  502.     if(s->link == s){
  503.         for(uint i = 0; i < s->go.nSpans; ++i){
  504.         t = s->go.span[i].to;
  505.         if(t && t->link == s)
  506.             goto inSCC;
  507.         }
  508.         s->link = NULL;
  509.     } else {
  510.     inSCC:
  511.         s->depth = maxDist(s);
  512.     }
  513.     }
  514. }
  515.  
  516. void DFA::findSCCs(){
  517.     SCC scc(nStates);
  518.     State *s;
  519.  
  520.     for(s = head; s; s = s->next){
  521.     s->depth = 0;
  522.     s->link = NULL;
  523.     }
  524.  
  525.     for(s = head; s; s = s->next)
  526.     if(!s->depth)
  527.         scc.traverse(s);
  528.  
  529.     calcDepth(head);
  530. }
  531.  
  532. void DFA::split(State *s){
  533.     State *move = new State;
  534.     (void) new Move(move);
  535.     addState(&s->next, move);
  536.     move->link = s->link;
  537.     move->rule = s->rule;
  538.     move->go = s->go;
  539.     s->rule = NULL;
  540.     s->go.nSpans = 1;
  541.     s->go.span = new Span;
  542.     s->go.span[0].ub = ubChar;
  543.     s->go.span[0].to = move;
  544. }
  545.  
  546. void DFA::emit(ostream &o){
  547.     static uint label = 0;
  548.     State *s;
  549.     uint i;
  550.  
  551.     findSCCs();
  552.     head->link = head;
  553.     head->depth = maxDist(head);
  554.  
  555.     uint nRules = 0;
  556.     for(s = head; s; s = s->next)
  557.     if(s->rule && s->rule->accept >= nRules)
  558.         nRules = s->rule->accept + 1;
  559.  
  560.     uint nSaves = 0;
  561.     uint *saves = new uint[nRules];
  562.     memset(saves, ~0, (nRules)*sizeof(*saves));
  563.  
  564.     // mark backtracking points
  565.     for(s = head; s; s = s->next){
  566.     RuleOp *ignore = NULL;
  567.     if(s->rule){
  568.         for(i = 0; i < s->go.nSpans; ++i)
  569.         if(s->go.span[i].to && !s->go.span[i].to->rule){
  570.             delete s->action;
  571.             if(saves[s->rule->accept] == ~0)
  572.             saves[s->rule->accept] = nSaves++;
  573.             (void) new Save(s, saves[s->rule->accept]);
  574.             continue;
  575.         }
  576.         ignore = s->rule;
  577.     }
  578.     }
  579.  
  580.     // insert actions
  581.     State **rules = new State*[nRules];
  582.     memset(rules, 0, (nRules)*sizeof(*rules));
  583.     State *accept = NULL;
  584.     for(s = head; s; s = s->next){
  585.     State *ow;
  586.     if(!s->rule){
  587.         ow = accept;
  588.     } else {
  589.         if(!rules[s->rule->accept]){
  590.         State *n = new State;
  591.         (void) new Rule(n, s->rule);
  592.         rules[s->rule->accept] = n;
  593.         addState(&s->next, n);
  594.         }
  595.         ow = rules[s->rule->accept];
  596.     }
  597.     for(i = 0; i < s->go.nSpans; ++i)
  598.         if(!s->go.span[i].to){
  599.         if(!ow){
  600.             ow = accept = new State;
  601.             (void) new Accept(accept, nRules, saves, rules);
  602.             addState(&s->next, accept);
  603.         }
  604.         s->go.span[i].to = ow;
  605.         }
  606.     }
  607.  
  608.     // split ``base'' states into two parts
  609.     for(s = head; s; s = s->next){
  610.     s->isBase = false;
  611.     if(s->link){
  612.         for(i = 0; i < s->go.nSpans; ++i){
  613.         if(s->go.span[i].to == s){
  614.             s->isBase = true;
  615.             split(s);
  616.             if(bFlag)
  617.             BitMap::find(&s->next->go, s);
  618.             s = s->next;
  619.             break;
  620.         }
  621.         }
  622.     }
  623.     }
  624.  
  625.     // find ``base'' state, if possible
  626.     Span *span = new Span[ubChar - lbChar];
  627.     for(s = head; s; s = s->next){
  628.     if(!s->link){
  629.         for(i = 0; i < s->go.nSpans; ++i){
  630.         State *to = s->go.span[i].to;
  631.         if(to && to->isBase){
  632.             to = to->go.span[0].to;
  633.             uint nSpans = merge(span, s, to);
  634.             if(nSpans < s->go.nSpans){
  635.             delete s->go.span;
  636.             s->go.nSpans = nSpans;
  637.             s->go.span = new Span[nSpans];
  638.             memcpy(s->go.span, span, nSpans*sizeof(Span));
  639.             }
  640.             break;
  641.         }
  642.         }
  643.     }
  644.     }
  645.     delete span;
  646.  
  647.     delete head->action;
  648.  
  649.     o << "{\n\tYYCTYPE yych;\n\tunsigned int yyaccept;\n";
  650.  
  651.     if(bFlag)
  652.     BitMap::gen(o, lbChar, ubChar);
  653.  
  654.     o << "\tgoto yy" << label << ";\n";
  655.     (void) new Enter(head, label++);
  656.  
  657.     for(s = head; s; s = s->next)
  658.     s->label = label++;
  659.  
  660.     for(s = head; s; s = s->next){
  661.     s->emit(o);
  662.     s->go.genGoto(o, s->next);
  663.     }
  664.     o << "}\n";
  665.  
  666.     BitMap::first = NULL;
  667.  
  668.     delete saves;
  669.     delete rules;
  670. }
  671.