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