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