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