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