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