dfa/dfa.c

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