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