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