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