dfa/dfa.c

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