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