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