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