dfa/dfa.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: dfa.c,v $
   7  * Revision 1.1  1995-01-24 16:02:52  adam
   8  * New private header file in dfa module (dfap.h).
   9  * Module no longer uses yacc to parse regular expressions.
  10  *
  11  */
  12 #include <stdio.h>
  13 #include <assert.h>
  14
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <ctype.h>
  18
  19 #include <util.h>
  20 #include "dfap.h"
  21 #include "imalloc.h"
  22
  23 #define CAT     16000
  24 #define OR      16001
  25 #define STAR    16002
  26 #define PLUS    16003
  27 #define EPSILON 16004
  28
  29 struct Tnode {
  30     union  {
  31         struct Tnode *p[2];   /* CAT,OR,STAR,PLUS (left,right) */
  32         short ch[2];          /* if ch[0] >= 0 then this Tnode represents */
  33                               /*   a character in range [ch[0]..ch[1]]    */
  34                               /* otherwise ch[0] represents */
  35                               /*   accepting no (-acceptno) */
  36     } u;
  37     unsigned pos : 15;        /* CAT/OR/STAR/EPSILON or non-neg. position */
  38     unsigned nullable : 1;
  39     Set firstpos;             /* first positions */
  40     Set lastpos;              /* last positions */
  41 };
  42
  43 struct Tblock {               /* Tnode bucket (block) */
  44     struct Tblock *next;      /* pointer to next bucket */
  45     struct Tnode *tarray;     /* array of nodes in bucket */
  46 };
  47
  48 #define TADD 256
  49
  50 int debug_dfa_trav  = 0;
  51 int debug_dfa_tran  = 0;
  52 int debug_dfa_followpos = 0;
  53 int dfa_verbose = 0;
  54 int yydebug = 0;
  55
  56 static struct DFA_parse *parse_info = NULL;
  57
  58 static int inside_string;
  59 static const unsigned char *expr_ptr;
  60 static unsigned short *ctrl_chars;
  61 static struct Tnode **posar;
  62
  63 static SetType poset;
  64 static Set *followpos;
  65
  66 static struct Tnode *mk_Tnode      (void);
  67 static struct Tnode *mk_Tnode_cset (BSet charset);
  68 static void        term_Tnode      (void);
  69
  70 static void
  71     del_followpos  (void),
  72     init_pos       (void),
  73     del_pos        (void),
  74     mk_dfa_tran    (struct DFA_states *dfas),
  75     add_follow     (Set lastpos, Set firstpos),
  76     dfa_trav       (struct Tnode *n),
  77     init_followpos (void),
  78     mk_dfa_tran    (struct DFA_states *dfas),
  79     pr_tran        (struct DFA_states *dfas),
  80     pr_verbose     (struct DFA_states *dfas),
  81     pr_followpos   (void),
  82     out_char       (int c),
  83     lex            (void);
  84
  85 static int
  86     nextchar       (int *esc),
  87     read_charset   (void);
  88
  89 static const char
  90     *str_char      (unsigned c);
  91
  92 #define L_LP 1
  93 #define L_RP 2
  94 #define L_CHAR 3
  95 #define L_CHARS 4
  96 #define L_ANY 5
  97 #define L_ALT 6
  98 #define L_ANYZ 7
  99 #define L_WILD 8
 100 #define L_QUEST 9
 101 #define L_CLOS1 10
 102 #define L_CLOS0 11
 103 #define L_END 12
 104 #define L_START 13
 105
 106 static int lookahead;
 107 static unsigned look_ch;
 108 static BSet look_chars;
 109
 110 static struct Tnode *expr_1 (void),
 111                     *expr_2 (void),
 112                     *expr_3 (void),
 113                     *expr_4 (void);
 114
 115 static struct Tnode *expr_1 (void)
 116 {
 117     struct Tnode *t1, *t2, *tn;
 118
 119     t1 = expr_2 ();
 120     while (lookahead == L_ALT)
 121     {
 122         lex ();
 123         t2 = expr_2 ();
 124
 125         tn = mk_Tnode ();
 126         tn->pos = OR;
 127         tn->u.p[0] = t1;
 128         tn->u.p[1] = t2;
 129         t1 = tn;
 130     }
 131     return t1;
 132 }
 133
 134 static struct Tnode *expr_2 (void)
 135 {
 136     struct Tnode *t1, *t2, *tn;
 137     t1 = expr_3 ();
 138     while (lookahead == L_WILD ||
 139            lookahead == L_ANYZ ||
 140            lookahead == L_ANY ||
 141            lookahead == L_LP ||
 142            lookahead == L_CHAR ||
 143            lookahead == L_CHARS)
 144     {
 145         t2 = expr_3 ();
 146
 147         tn = mk_Tnode ();
 148         tn->pos = CAT;
 149         tn->u.p[0] = t1;
 150         tn->u.p[1] = t2;
 151         t1 = tn;
 152     }
 153     return t1;
 154 }
 155
 156 static struct Tnode *expr_3 (void)
 157 {
 158     struct Tnode *t1, *tn;
 159
 160     t1 = expr_4 ();
 161     if (lookahead == L_CLOS0)
 162     {
 163         lex ();
 164         tn = mk_Tnode ();
 165         tn->pos = STAR;
 166         tn->u.p[0] = t1;
 167         t1 = tn;
 168     }
 169     else if (lookahead == L_CLOS1)
 170     {
 171         lex ();
 172         tn = mk_Tnode ();
 173         tn->pos = PLUS;
 174         tn->u.p[0] = t1;
 175         t1 = tn;
 176     }
 177     else if (lookahead == L_QUEST)
 178     {
 179         lex ();
 180         tn = mk_Tnode();
 181         tn->pos = OR;
 182         tn->u.p[0] = t1;
 183         tn->u.p[1] = mk_Tnode();
 184         tn->u.p[1]->pos = EPSILON;
 185         t1 = tn;
 186     }
 187     return t1;
 188 }
 189
 190 static struct Tnode *expr_4 (void)
 191 {
 192     struct Tnode *t1;
 193     switch (lookahead)
 194     {
 195     case L_LP:
 196         lex ();
 197         t1 = expr_1 ();
 198         if (lookahead == L_RP)
 199             lex ();
 200         break;
 201     case L_CHAR:
 202         t1 = mk_Tnode();
 203         t1->pos = ++(parse_info->position);
 204         t1->u.ch[1] = t1->u.ch[0] = look_ch;
 205         lex ();
 206         break;
 207     case L_CHARS:
 208         t1 = mk_Tnode_cset (look_chars);
 209         lex ();
 210         break;
 211     case L_ANY:
 212         t1 = mk_Tnode_cset (parse_info->anyset);
 213         lex ();
 214         break;
 215     case L_ANYZ:
 216         t1 = mk_Tnode();
 217         t1->pos = OR;
 218         t1->u.p[0] = mk_Tnode_cset (parse_info->anyset);
 219         t1->u.p[1] = mk_Tnode();
 220         t1->u.p[1]->pos = EPSILON;
 221         lex ();
 222         break;
 223     case L_WILD:
 224         t1 = mk_Tnode();
 225         t1->pos = STAR;
 226         t1->u.p[0] = mk_Tnode_cset (parse_info->anyset);
 227         lex ();
 228     default:
 229         t1 = NULL;
 230         assert (0);
 231         lex ();
 232     }
 233     return t1;
 234 }
 235
 236 static int parse (dfap, s, cc)
 237 struct DFA_parse *dfap;
 238 char **s;
 239 const unsigned short *cc;
 240 {
 241     int i;
 242     struct Tnode *t1, *t2;
 243
 244     for (i=0; cc[i]; i +=2)
 245         ;
 246     ctrl_chars = imalloc ((i+2) * sizeof(*ctrl_chars));
 247     for (i=0; (ctrl_chars[i] = cc[i]); i ++)
 248         switch (cc[++i])
 249         {
 250         case '(':
 251             ctrl_chars[i] = L_LP;
 252             break;
 253         case ')':
 254             ctrl_chars[i] = L_RP;
 255             break;
 256         case '.':
 257             ctrl_chars[i] = L_ANY;
 258             break;
 259         case '|':
 260             ctrl_chars[i] = L_ALT;
 261             break;
 262         case '?':
 263             ctrl_chars[i] = L_QUEST;
 264             break;
 265         case '+':
 266             ctrl_chars[i] = L_CLOS1;
 267             break;
 268         case '*':
 269             ctrl_chars[i] = L_CLOS0;
 270             break;
 271         case '$':
 272             ctrl_chars[i] = L_END;
 273             break;
 274         case '^':
 275             ctrl_chars[i] = L_START;
 276             break;
 277         case '!':
 278             ctrl_chars[i] = L_ANY;
 279             break;
 280         case '#':
 281             ctrl_chars[i] = L_ANYZ;
 282             break;
 283         case '@':
 284             ctrl_chars[i] = L_WILD;
 285             break;
 286         default:
 287             ctrl_chars[i] = 0;
 288         }
 289     parse_info = dfap;
 290     expr_ptr = (unsigned char *) *s;
 291
 292     inside_string = 0;
 293     lex ();
 294     t1 = expr_1 ();
 295     t2 = mk_Tnode();
 296     t2->pos = ++parse_info->position;
 297     t2->u.ch[0] = -(++parse_info->rule);
 298
 299     parse_info->top = mk_Tnode();
 300     parse_info->top->pos = CAT;
 301     parse_info->top->u.p[0] = t1;
 302     parse_info->top->u.p[1] = t2;
 303
 304     *s = (char *) expr_ptr;
 305     ifree (ctrl_chars);
 306     return 0;
 307 }
 308
 309 static int nextchar (int *esc)
 310 {
 311     *esc = 0;
 312     if (*expr_ptr == '\0' || isspace(*expr_ptr))
 313         return 0;
 314     else if (*expr_ptr != '\\')
 315         return *expr_ptr++;
 316     *esc = 1;
 317     switch (*++expr_ptr)
 318     {
 319     case '\r':
 320     case '\n':
 321     case '\t':
 322     case '\0':
 323         return '\\';
 324     case 'n':
 325         ++expr_ptr;
 326         return '\n';
 327     case 't':
 328         ++expr_ptr;
 329         return '\t';
 330     case 'r':
 331         ++expr_ptr;
 332         return '\r';
 333     case 'f':
 334         ++expr_ptr;
 335         return '\f';
 336     default:
 337         return *expr_ptr++;
 338     }
 339 }
 340
 341 static int read_charset (void)
 342 {
 343     int i, ch0, ch1, esc0, esc1, cc = 0;
 344     look_chars = mk_BSet (&parse_info->charset);
 345     res_BSet (parse_info->charset, look_chars);
 346
 347     ch0 = nextchar (&esc0);
 348     if (!esc0 && ch0 == '^')
 349     {
 350         cc = 1;
 351         ch0 = nextchar (&esc0);
 352     }
 353     while (ch0 != 0)
 354     {
 355         if (!esc0 && ch0 == ']')
 356             break;
 357         add_BSet (parse_info->charset, look_chars, ch0);
 358         ch1 = nextchar (&esc1);
 359         if (!esc1 && ch1 == '-')
 360         {
 361             if ((ch1 = nextchar (&esc1)) == 0)
 362                 break;
 363             if (!esc1 && ch1 == ']')
 364             {
 365                 add_BSet (parse_info->charset, look_chars, '-');
 366                 break;
 367             }
 368             for (i=ch0; ++i<=ch1;)
 369                 add_BSet (parse_info->charset, look_chars, i);
 370             ch0 = nextchar (&esc0);
 371         }
 372         else
 373         {
 374             esc0 = esc1;
 375             ch0 = ch1;
 376         }
 377     }
 378     if (cc)
 379         com_BSet (parse_info->charset, look_chars);
 380     return L_CHARS;
 381 }
 382
 383 unsigned short dfa_thompson_chars[] =
 384 {
 385     '*', '*',
 386     '+', '+',
 387     '|', '|',
 388     '^', '^',
 389     '$', '$',
 390     '?', '?',
 391     '.', '.',
 392     '(', '(',
 393     ')', ')',
 394     0
 395 };
 396
 397 unsigned short dfa_ccl_chars[] =
 398 {
 399     '#', '#',
 400     '!', '!',
 401     '?', '@',
 402     0
 403 };
 404
 405 static int lex_sub(void)
 406 {
 407     int esc;
 408     const unsigned short *cc;
 409     while ((look_ch = nextchar (&esc)) != 0)
 410         if (look_ch == '\"')
 411         {
 412             if (esc)
 413                 return L_CHAR;
 414             inside_string = !inside_string;
 415         }
 416         else if (esc || inside_string)
 417             return L_CHAR;
 418         else if (look_ch == '[')
 419             return read_charset();
 420         else if (look_ch == ' ')
 421             return 0;
 422         else
 423         {
 424             for (cc = ctrl_chars; *cc; cc += 2)
 425                 if (*cc == look_ch)
 426                     return cc[1];
 427             return L_CHAR;
 428         }
 429     return 0;
 430 }
 431
 432 static void lex (void)
 433 {
 434     lookahead = lex_sub ();
 435 }
 436
 437 static const char *str_char (unsigned c)
 438 {
 439     static char s[6];
 440     s[0] = '\\';
 441     if (c < 32)
 442         switch (c)
 443         {
 444         case '\r':
 445             strcpy (s+1, "r");
 446             break;
 447         case '\n':
 448             strcpy (s+1, "n");
 449             break;
 450         case '\t':
 451             strcpy (s+1, "t");
 452             break;
 453         default:
 454             sprintf (s+1, "x%02x", c);
 455             break;
 456         }
 457     else
 458         switch (c)
 459         {
 460         case '\"':
 461             strcpy (s+1, "\"");
 462             break;
 463         case '\'':
 464             strcpy (s+1, "\'");
 465             break;
 466         case '\\':
 467             strcpy (s+1, "\\");
 468             break;
 469         default:
 470             s[0] = c;
 471             s[1] = '\0';
 472         }
 473     return s;
 474 }
 475
 476 static void out_char (int c)
 477 {
 478     printf ("%s", str_char (c));
 479 }
 480
 481 static void term_Tnode (void)
 482 {
 483     struct Tblock *t, *t1;
 484     for (t = parse_info->start; (t1 = t);)
 485     {
 486         t=t->next;
 487         ifree (t1->tarray);
 488         ifree (t1);
 489     }
 490 }
 491
 492 static struct Tnode *mk_Tnode (void)
 493 {
 494     struct Tblock *tnew;
 495
 496     if (parse_info->use_Tnode == parse_info->max_Tnode)
 497     {
 498         tnew = (struct Tblock *) imalloc (sizeof(struct Tblock));
 499         tnew->tarray = (struct Tnode *) imalloc (TADD*sizeof(struct Tnode));
 500         if (!tnew->tarray)
 501             return NULL;
 502         if (parse_info->use_Tnode == 0)
 503             parse_info->start = tnew;
 504         else
 505             parse_info->end->next = tnew;
 506         parse_info->end = tnew;
 507         tnew->next = NULL;
 508         parse_info->max_Tnode += TADD;
 509     }
 510     return parse_info->end->tarray+(parse_info->use_Tnode++ % TADD);
 511 }
 512
 513 struct Tnode *mk_Tnode_cset (BSet charset)
 514 {
 515     struct Tnode *tn1, *tn0 = mk_Tnode();
 516     int ch1, ch0 = trav_BSet (parse_info->charset, charset, 0);
 517     if (ch0 == -1)
 518         tn0->pos = EPSILON;
 519     else
 520     {
 521         tn0->u.ch[0] = ch0;
 522         tn0->pos = ++parse_info->position;
 523         ch1 = travi_BSet (parse_info->charset, charset, ch0+1) ;
 524         if (ch1 == -1)
 525             tn0->u.ch[1] = parse_info->charset->size;
 526         else
 527         {
 528             tn0->u.ch[1] = ch1-1;
 529             while ((ch0=trav_BSet (parse_info->charset, charset, ch1)) != -1)
 530             {
 531                 tn1 = mk_Tnode();
 532                 tn1->pos = OR;
 533                 tn1->u.p[0] = tn0;
 534                 tn0 = tn1;
 535                 tn1 = tn0->u.p[1] = mk_Tnode();
 536                 tn1->u.ch[0] = ch0;
 537                 tn1->pos = ++(parse_info->position);
 538                 if ((ch1 = travi_BSet (parse_info->charset, charset,
 539                                        ch0+1)) == -1)
 540                 {
 541                     tn1->u.ch[1] = parse_info->charset->size;
 542                     break;
 543                 }
 544                 tn1->u.ch[1] = ch1-1;
 545             }
 546         }
 547     }
 548     return tn0;
 549 }
 550
 551 static void del_followpos (void)
 552 {
 553     ifree (followpos);
 554 }
 555
 556 static void init_pos (void)
 557 {
 558     posar = (struct Tnode **) imalloc (sizeof(struct Tnode*)
 559                                        * (1+parse_info->position));
 560 }
 561
 562 static void del_pos (void)
 563 {
 564     ifree (posar);
 565 }
 566
 567 static void add_follow (Set lastpos, Set firstpos)
 568 {
 569     while (lastpos)
 570     {
 571         followpos[lastpos->value] =
 572                union_Set (poset, followpos[lastpos->value], firstpos);
 573         lastpos = lastpos->next;
 574     }
 575 }
 576
 577 static void dfa_trav (struct Tnode *n)
 578 {
 579     switch (n->pos)
 580     {
 581     case CAT:
 582         dfa_trav (n->u.p[0]);
 583         dfa_trav (n->u.p[1]);
 584         n->nullable = n->u.p[0]->nullable & n->u.p[1]->nullable;
 585         n->firstpos = mk_Set (poset);
 586         n->firstpos = union_Set (poset, n->firstpos, n->u.p[0]->firstpos);
 587         if (n->u.p[0]->nullable)
 588             n->firstpos = union_Set (poset, n->firstpos, n->u.p[1]->firstpos);
 589         n->lastpos = mk_Set (poset);
 590         n->lastpos = union_Set (poset, n->lastpos, n->u.p[1]->lastpos);
 591         if (n->u.p[1]->nullable)
 592             n->lastpos = union_Set (poset, n->lastpos, n->u.p[0]->lastpos);
 593
 594         add_follow (n->u.p[0]->lastpos, n->u.p[1]->firstpos);
 595
 596         n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
 597         n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
 598         n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
 599         n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
 600         if (debug_dfa_trav)
 601             printf ("CAT");
 602         break;
 603     case OR:
 604         dfa_trav (n->u.p[0]);
 605         dfa_trav (n->u.p[1]);
 606         n->nullable = n->u.p[0]->nullable | n->u.p[1]->nullable;
 607
 608         n->firstpos = merge_Set (poset, n->u.p[0]->firstpos,
 609                                  n->u.p[1]->firstpos);
 610         n->lastpos = merge_Set (poset, n->u.p[0]->lastpos,
 611                                 n->u.p[1]->lastpos);
 612         n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
 613         n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
 614         n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
 615         n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
 616         if (debug_dfa_trav)
 617             printf ("OR");
 618         break;
 619     case PLUS:
 620         dfa_trav (n->u.p[0]);
 621         n->nullable = n->u.p[0]->nullable;
 622         n->firstpos = n->u.p[0]->firstpos;
 623         n->lastpos = n->u.p[0]->lastpos;
 624         add_follow (n->lastpos, n->firstpos);
 625         if (debug_dfa_trav)
 626             printf ("PLUS");
 627         break;
 628     case STAR:
 629         dfa_trav (n->u.p[0]);
 630         n->nullable = 1;
 631         n->firstpos = n->u.p[0]->firstpos;
 632         n->lastpos = n->u.p[0]->lastpos;
 633         add_follow (n->lastpos, n->firstpos);
 634         if (debug_dfa_trav)
 635             printf ("STAR");
 636         break;
 637     case EPSILON:
 638         n->nullable = 1;
 639         n->lastpos = mk_Set (poset);
 640         n->firstpos = mk_Set (poset);
 641         if (debug_dfa_trav)
 642             printf ("EPSILON");
 643         break;
 644     default:
 645         posar[n->pos] = n;
 646         n->nullable = 0;
 647         n->firstpos = mk_Set (poset);
 648         n->firstpos = add_Set (poset, n->firstpos, n->pos);
 649         n->lastpos = mk_Set (poset);
 650         n->lastpos = add_Set (poset, n->lastpos, n->pos);
 651         if (debug_dfa_trav)
 652             if (n->u.ch[0] < 0)
 653                 printf ("#%d", -n->u.ch[0]);
 654             else if (n->u.ch[1] > n->u.ch[0])
 655             {
 656                 putchar ('[');
 657                 out_char (n->u.ch[0]);
 658                 if (n->u.ch[1] > n->u.ch[0]+1)
 659                     putchar ('-');
 660                 out_char (n->u.ch[1]);
 661                 putchar (']');
 662             }
 663             else
 664                 out_char (n->u.ch[0]);
 665     }
 666     if (debug_dfa_trav)
 667     {
 668         printf ("\n nullable : %c\n", n->nullable ? '1' : '0');
 669         printf (" firstpos :");
 670         pr_Set (poset, n->firstpos);
 671         printf (" lastpos  :");
 672         pr_Set (poset, n->lastpos);
 673     }
 674 }
 675
 676 static void init_followpos (void)
 677 {
 678     Set *fa;
 679     int i;
 680     followpos = fa = (Set *) imalloc (sizeof(Set) * (1+parse_info->position));
 681     for (i = parse_info->position+1; --i >= 0; fa++)
 682         *fa = mk_Set (poset);
 683 }
 684
 685 static void mk_dfa_tran (struct DFA_states *dfas)
 686 {
 687     int i, c;
 688     int max_char;
 689     short *pos, *pos_i;
 690     Set tran_set;
 691     int char_0, char_1;
 692     struct DFA_state *dfa_from, *dfa_to;
 693
 694     assert (parse_info);
 695     max_char = parse_info->charset->size;
 696     pos = (short *) imalloc (sizeof(*pos) * (parse_info->position+1));
 697
 698     tran_set = cp_Set (poset, parse_info->root->firstpos);
 699     i = add_DFA_state (dfas, &tran_set, &dfa_from);
 700     assert (i);
 701     dfa_from->rule_no = 0;
 702     while ((dfa_from = get_DFA_state (dfas)))
 703     {
 704         pos_i = pos;
 705         i = 0;
 706         for (tran_set = dfa_from->set; tran_set; tran_set = tran_set->next)
 707             if ((c = posar[tran_set->value]->u.ch[0]) >= 0 && c <= max_char)
 708                 *pos_i++ = tran_set->value;
 709             else if (c < 0 && (i == 0 || c > i))
 710                 i = c;
 711         *pos_i = -1;
 712         dfa_from->rule_no = -i;
 713
 714         for (char_1 = 0; char_1 <= max_char; char_1++)
 715         {
 716             char_0 = max_char+1;
 717             for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
 718                 if (posar[i]->u.ch[1] >= char_1)
 719                     if ((c=posar[i]->u.ch[0]) < char_0)
 720                         if (c < char_1)
 721                             char_0 = char_1;
 722                         else
 723                             char_0 = c;
 724
 725             char_1 = max_char;
 726             if (char_0 > max_char)
 727                 break;
 728             tran_set = mk_Set (poset);
 729             for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
 730                 if ((c=posar[i]->u.ch[1]) >= char_0)
 731                     if (posar[i]->u.ch[0] <= char_0)
 732                     {
 733                         if (c < char_1)
 734                             char_1 = c;
 735                         tran_set = union_Set (poset, tran_set, followpos[i]);
 736                     }
 737                     else if (c <= char_1)
 738                         char_1 = c-1;
 739             if (tran_set)
 740             {
 741                 add_DFA_state (dfas, &tran_set, &dfa_to);
 742                 add_DFA_tran (dfas, dfa_from, char_0, char_1, dfa_to->no);
 743             }
 744         }
 745     }
 746     ifree (pos);
 747     sort_DFA_states (dfas);
 748 }
 749
 750 static void pr_tran (struct DFA_states *dfas)
 751 {
 752     struct DFA_state *s;
 753     struct DFA_tran *tran;
 754     int prev_no, i, c, no;
 755
 756     for (no=0; no < dfas->no; ++no)
 757     {
 758         s = dfas->sortarray[no];
 759         assert (s->no == no);
 760         printf ("DFA state %d", no);
 761         if (s->rule_no)
 762             printf ("#%d", s->rule_no);
 763         putchar (':');
 764         pr_Set (poset, s->set);
 765         prev_no = -1;
 766         for (i=s->tran_no, tran=s->trans; --i >= 0; tran++)
 767         {
 768             if (prev_no != tran->to)
 769             {
 770                 if (prev_no != -1)
 771                     printf ("]\n");
 772                 printf (" goto %d on [", tran->to);
 773                 prev_no = tran->to;
 774             }
 775             for (c = tran->ch[0]; c <= tran->ch[1]; c++)
 776                 printf ("%s", str_char(c));
 777         }
 778         if (prev_no != -1)
 779             printf ("]\n");
 780         putchar ('\n');
 781     }
 782 }
 783
 784 static void pr_verbose (struct DFA_states *dfas)
 785 {
 786     long i, j;
 787     int k;
 788     printf ("%d/%d tree nodes used, %d bytes each\n",
 789         parse_info->use_Tnode, parse_info->max_Tnode, sizeof (struct Tnode));
 790     k = inf_BSetHandle (parse_info->charset, &i, &j);
 791     printf ("%ld/%ld character sets, %d bytes each\n",
 792             i/k, j/k, k*sizeof(BSetWord));
 793     k = inf_SetType (poset, &i, &j);
 794     printf ("%ld/%ld poset items, %d bytes each\n", i, j, k);
 795     printf ("%d DFA states\n", dfas->no);
 796 }
 797
 798 static void pr_followpos (void)
 799 {
 800     int i;
 801     printf ("\nfollowsets:\n");
 802     for (i=1; i <= parse_info->position; i++)
 803     {
 804         printf ("%3d:", i);
 805         pr_Set (poset, followpos[i]);
 806         putchar ('\t');
 807
 808         if (posar[i]->u.ch[0] < 0)
 809             printf ("#%d", -posar[i]->u.ch[0]);
 810         else if (posar[i]->u.ch[1] > posar[i]->u.ch[0])
 811         {
 812             putchar ('[');
 813             out_char (posar[i]->u.ch[0]);
 814             if (posar[i]->u.ch[1] > posar[i]->u.ch[0]+1)
 815                 putchar ('-');
 816             out_char (posar[i]->u.ch[1]);
 817             putchar (']');
 818         }
 819         else
 820             out_char (posar[i]->u.ch[0]);
 821         putchar ('\n');
 822     }
 823     putchar ('\n');
 824 }
 825
 826 static struct DFA_parse *dfa_parse_init (void)
 827 {
 828     parse_info = (struct DFA_parse *) imalloc (sizeof (struct DFA_parse));
 829
 830     parse_info->charset = mk_BSetHandle (255, 20);
 831     parse_info->position = 0;
 832     parse_info->rule = 0;
 833     parse_info->root = NULL;
 834
 835     parse_info->anyset = mk_BSet (&parse_info->charset);
 836     res_BSet (parse_info->charset, parse_info->anyset);
 837     add_BSet (parse_info->charset, parse_info->anyset, '\n');
 838     com_BSet (parse_info->charset, parse_info->anyset);
 839     parse_info->use_Tnode = parse_info->max_Tnode = 0;
 840     return parse_info;
 841 }
 842
 843 static void rm_dfa_parse (struct DFA_parse **dfap)
 844 {
 845     parse_info = *dfap;
 846     assert (parse_info);
 847     term_Tnode();
 848     rm_BSetHandle (&parse_info->charset);
 849     ifree (parse_info);
 850     *dfap = NULL;
 851 }
 852
 853 static struct DFA_states *mk_dfas (struct DFA_parse *dfap, int poset_chunk)
 854 {
 855     struct DFA_states *dfas;
 856
 857     assert (poset_chunk > 10);
 858     assert (dfap);
 859
 860     parse_info = dfap;
 861     poset = mk_SetType (poset_chunk);
 862     init_pos();
 863     init_followpos();
 864     dfa_trav (parse_info->root);
 865
 866     if (debug_dfa_followpos)
 867         pr_followpos();
 868     init_DFA_states (&dfas, poset, 401);
 869     mk_dfa_tran (dfas);
 870     if (debug_dfa_tran)
 871         pr_tran (dfas);
 872     if (dfa_verbose)
 873         pr_verbose (dfas);
 874     del_pos();
 875     del_followpos();
 876     rm_SetType (poset);
 877     return dfas;
 878 }
 879
 880 struct DFA *dfa_init (void)
 881 {
 882     struct DFA *dfa;
 883
 884     dfa = imalloc (sizeof(*dfa));
 885     dfa->parse_info = dfa_parse_init ();
 886     dfa->state_info = NULL;
 887     dfa->states = NULL;
 888     return dfa;
 889 }
 890
 891 int dfa_parse (struct DFA *dfa, char **pattern)
 892 {
 893     int i;
 894
 895     assert (dfa);
 896     i = parse (dfa->parse_info, pattern, dfa_thompson_chars);
 897     if (i)
 898         return i;
 899     if ( !dfa->parse_info->root )
 900         dfa->parse_info->root = dfa->parse_info->top;
 901     else
 902     {
 903         struct Tnode *n;
 904
 905         n = mk_Tnode ();
 906         n->pos = OR;
 907         n->u.p[0] = dfa->parse_info->root;
 908         n->u.p[1] = dfa->parse_info->top;
 909         dfa->parse_info->root = n;
 910     }
 911     return 0;
 912 }
 913
 914 void dfa_mkstate (struct DFA *dfa)
 915 {
 916     assert (dfa);
 917
 918     dfa->state_info = mk_dfas (dfa->parse_info, 200);
 919     dfa->no_states = dfa->state_info->no;
 920     dfa->states = dfa->state_info->sortarray;
 921     rm_dfa_parse (&dfa->parse_info);
 922 }
 923
 924 void dfa_delete (struct DFA **dfap)
 925 {
 926     assert (dfap);
 927     assert (*dfap);
 928     if ((*dfap)->parse_info)
 929         rm_dfa_parse (&(*dfap)->parse_info);
 930     rm_DFA_states (&(*dfap)->state_info);
 931     ifree (*dfap);
 932     *dfap = NULL;
 933 }