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